Практика программирования (Бейсик, Си, Паскаль)
Задачи,советы и ответы - часть 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 делится на это же число без остатка. Поэтому алгоритм Евклида состоит из следующих шагов:
Совет 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);