Практика программирования (Бейсик, Си, Паскаль)



         

Задачи,советы и ответы - часть 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);




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