Задачи,советы и ответы - часть 2

Программа 5_01.bas

DECLARE FUNCTION FIB%(N%)

INPUT "Задайте порядковый номер числа Фибоначчи - ",N%

PRINT "Число Фибоначчи с номером ";N%;" равно ";FIB%(N%)

END

FUNCTION FIB%(N%)

IF N% < 2 THEN

FIB%=N% ELSE

FIB%=FIB%(N%-2)+FIB%(N%-1)

END IF

END FUNCTION

Программа 5_01.с

#include <stdio.h>

#include <conio.h>

Совет 1 (общий)

Алгоритм нахождения наибольшего общего делителя (нод) двух натуральных чисел приписывают Евклиду. Он базируется на трех сравнительно тривиальных утверждениях:

HОД(kl,k2) = HOД(k2,kl) // поэтому можно считать, что kl < k2

HОД(0,k) = k // неудивительно, т.к. О делится на все

HОД(kl,k2) = HОД(k3,kl) // k3 - остаток от деления k2 на kl. В истинности последнего несложно убедиться, если записать: k1*m + k3 = k2 // m - частное от деления k2 на k1

Если kl и k2 делятся на свой нод, то и k3 делится на это же число без остатка. Поэтому алгоритм Евклида состоит из следующих шагов:

Если первое число kl больше второго, то поменять их местами.

Если kl=0, то вычисления прекращаются.

Находим остаток от деления k2 на kl и заменяем им большее число.

Повторяем шаги, начиная с первого.

Совет 2 (общий)

За счет небольшой потери эффективности от перестановки большего и меньшего чисел можно отказаться. При этом подпрограмма лишний раз обратится к себе:

НОД(120,84)=НОД(84,120)=НОД(36,84)=НОД(12,36)=НОД(0,12)==12 Поэтому тело функции можно построить из единственного условного оператора.

Программа 5_02.bas

DECLARE FUNCTION NOD&(NlS,N2&)

PRINT "Введите 2 натуральных числа, разделяя их запятой"

INPUT "",M&,N&

PRINT "Их наибольший общий делитель равен ";NOD&(M&,N&)

END

FUNCTION NOD&(N1&,N2&) IF Nl&=0 THEN

NODS=N2& ELSE

NOD&=NOD&(N2& MOD N1&,N1&)

END IF

END FUNCTION

Программа 5_02.с

#include <stdio.h>

#include <conio.h>

long nod(long nl,long n2);

Содержание Назад Вперед