Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Математика _ Теория Алгоритмов

Автор: TOPEHTO 19.05.2007 21:47

Выбился из сил...может у кого есть из вас.
Нужно доказать что НОД и НОК - это примитивно рекурсивные функции. Если у кого есть решение буду рад. Хотя бы помогите алгоритмом и какими теоремами пользоваться. Заранее спс... wink.gif ...

Автор: LuckyI 21.05.2007 1:00

Цитата
примитивно рекурсивные функции
Это как? Тебе нужен алгоритм нахождения НОД и НОК? Или что?

Автор: TOPEHTO 21.05.2007 13:52

Примитивно рекурсивное описание...

Автор: Кошка 12.06.2007 3:23

Цитата(TOPEHTO @ 21.05.2007 10:52) *

Примитивно рекурсивное описание...

Может быть, этот вариант подойдёт:

function gcd(a,b:integer):integer;
var
t:integer;
begin
if a<b then
begin
t:=a; a:=b; b:=t;
end;
if b<1 then gcd:=a else
begin a:=a-b; gcd:=gcd(a,b);
end;
end;

Автор: Michael_Rybak 12.06.2007 3:32

Думаю, тему можно и нужно закрыть, разобрались пытались разобраться в аське, ОП в решении уже не заинтересован (сдал).

Света, "примитивная рекурсия" - это термин из теории алгоритмов, практически ничего общего с рекурсией в программировании не имеющий. Кстати, как и теория алгоритмов имеет довольно опосредованное отношение к нашему разделу "Алгоритмы". Это совсем разные алгоритмы smile.gif

Хочешь - http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B8%D0%BC%D0%B8%D1%82%D0%B8%D0%B2%D0%BD%D0%BE_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F в википедии.