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

       

когда итальянский математик Леонардо Пизанский


Задание 5.01. Числа Фибоначчи

История чисел Фибоначчи восходит к началу XIII в., когда итальянский математик Леонардо Пизанский нашел изящное решение задачи о размножении кроликов. Пусть в начале эксперимента имеется единственная пара -самец и самка, которые приносят каждый месяц приплод, состоящий также из самца и самки. Дети включаются в цикл продолжения рода через два месяца. Требуется определить количество пар, спустя k месяцев после начала эксперимента. Ситуация не так уж и сложна:

  • в начале эксперимента — 1 родительская пара;

  • через 1 месяц — 2 пары (родители и дети первого поколения);

  • через 2 месяца — 3 пары (родители и дети двух поколений);

  • через 3 месяца — 5 пар (родители, дети трех поколений, внуки от первого поколения);

  • через 4 месяца — 8 пар (родители, дети четырех поколений, 2 пары внуков от первого поколения, 1 пара внуков от второго поколения);

  • ..............................................................................

    Леонардо догадался, что числа указанной последовательности связаны рекуррентным соотношением:

    fk = fk-2 + fk-1

    В разных учебниках последовательность чисел Фибоначчи дополняют либо еще одной единицей, либо нулем и единицей:

    1,1,2,3,5,8,13,21,34,55,...

    0,1,1,2,3,5,8,13,21,34,.....



    Последний вариант принят в приводимых ниже программах, отсчет порядковых номеров чисел Фибоначчи ведется от 0. Диапазон действия этих программ не так уж велик: fit>(22)=17711, fib(23) =28657 и уже 24-е число выходит за пределы предусмотренного диапазона. Если вас заинтересуют числа с большими номерами, то можно изменить тип функции fib или воспользоваться формулой Бинэ:

    f ib (k) = ( ( (1+sqrt (5) ) /2)*k- ( (1-sqrt (5) ) /2} ^k) /sqrt (5)

    Наиболее известное применение чисел Фибоначчи — оптимальный выбор точек при поиске экстремума унимодальной функции на заданном отрезке. Рекурсивная реализация нахождения чисел Фибоначчи абсолютно неэффективна, т. к. в теле процедуры при каждой итерации происходит два обращения к этой же процедуре и объем вычислений с ростом k возрастает почти в геометрической профессии.


    Программа 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);


    main() {

    long m,n;

    printf("\n Введите 2 натуральных числа, разделяя их пробелом\n");

    scanf("%ld %ld",&n,&m);

    printf("Их наибольший общий делитель равен %ld",nod(m,n));

    getch(); }

    long nod(long n1,long n2) {

    if(nl==0) return n2;

    return nod(n2%nl,nl); }

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

    program Euclid;
    var

    n,m:longint;

    function nod(nl,n2:longint):longint;
    begin

    if nl=0 then nod:=n2

    else nod:=nod(n2 mod n1,n1);
    end;
    begin

    writeln('Введите два натуральных числа');

    readln(n,m);

    writeln{'Иx наибольший общий делитель равен ',nod(n,m));

    readln; end.

    Задание 5.03. Ханойские башни

    Игра "Ханойские башни" была придумана французским математиком Э. Люка в конце XIX в. На подставке установлены три шпильки, которые

    мы условно назовем А, в и с. На шпильку А надето k дисков разного диаметра таким образом, что они образуют "правильную" пирамиду (каждый диск, расположенный выше, имеет диаметр меньший, чем у всех, лежащих ниже). Цель игры заключается в переносе пирамиды на шпильку с. При этом за один ход разрешается переложить один диск, надевая его на одну из шпилек таким образом, чтобы верхний диск всегда был меньшего диаметра.

    Можно показать, что число ходов, необходимое для решения этой задачи, равно 2k-i. Для k=1 и k=2 это легко проверяется. Дальнейшие рассуждения выполняются по индукции: если это справедливо для любого k-1, то докажем справедливость утверждения о числе шагов и для любого k. Предположим, что мы умеем переносить пирамиду из k-1 дисков за 2k-1-1 ходов. Тогда для переноса башни из k дисков можно поступить следующим образом:

  • переносим верхние k-l диски со шпильки А на шпильку в;

  • переносим оставшийся самый большой диск со шпильки А на шпильку с (это еще один ход);

  • используя освободившуюся шпильку А в качестве рабочей, переносим пирамиду из k-1 диска со шпильки в на шпильку с.

    Таким образом, число ходов, которое мы затратили для переноса пирамиды из k дисков, равно:

    2k-1 - 1 + 1 + 2k-1 -1 = 2k-l


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

    Для построения рекурсивной программы необходимо последовательно уменьшать размерность задачи, сводя ее на каждой итерации к последовательности трех описанных выше перемещений. Для этой цели нам понадобятся две процедуры:

    MoveAll(k,from,to,tmp) MoveOne(from,to)

    Первая из них выполняет шаги по переносу пирамиды из k дисков со шпильки from на шпильку to, используя в качестве рабочей шпильку tmp. Вторая переносит один диск со шпильки from на шпильку to.

    Совет 2 (QBasic)

    Переменная т% введена для нумерации ходов. Для того чтобы ее значение сохранялось после очередного перемещения одного диска в заголовке подпрограммы MoveOne использован указатель STATIC.

    Совет 3 (Паскаль)

    В программе нельзя использовать идентификатор to, т. к. он занят под служебное слово в операторе цикла for.

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

    DECLARE SUB MoveAll(k%,from$,to$,tmp$)

    DECLARE SUB MoveOne(from$,to$)

    CLS

    INPUT "Введите количество дисков ",k%

    MoveAll k%,"A","C","B"

    END

    SUB MoveAll (k%, from$, to$,tmp$)

    IF k%=0 THEN EXIT SUB

    MoveAll k%-l,from$,tmp$,to$

    MoveOne from$,to$

    MoveAll k%-l,trap$,to$,from$ END SUB

    SUB MoveOne(from$,to$) STATIC

    m%=m%+l

    PRINT USING "#### : &--> & ";m%;from$;to$ END SUB

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

    #include <stdio.h>

    #include <conio.h>

    void MoveAll(int k,char from,char to,char trap);

    void MoveOne(char from,char to);

    int m=0;

    main () {

    int k;

    clrscr () ;

    printf("\n Введите количество дисков - ");

    scanf("Id",&k);

    MoveAll(k,'A','C','B');

    getch(); }

    void MoveAll(int k,char from,char to,char tmp)

    {

    if(k==0) return; MoveAll(k-1,from,tmp,to);
    MoveOne(from,to); MoveAll(k-1,tmp,to,from); }

    void MoveOne(char from,char to) {

    m++;

    printf("\n%4d : %c --> %c",m,from,to); }

    Программа 5_03.pas

    program Hanoi; uses Crt; var

    k:integer; const

    m: integer=0;

    procedure MoveOne(from,tol:char);
    begin

    inc (m) ;

    writeln(m:4,from:2, ' —> ',tol);
    end;

    procedure MoveAll(k:integer;from,tol,tmp:char);
    begin

    if k = 0 then exit;

    MoveAll(k-1,from,tmp,tol);

    MoveOne(from,tol);

    MoveAll(k-1,tmp,tol,from);

    end;

    begin

    clrscr;

    write('Введите количество дисков - ') ;
    readln(k);

    MoveAll(k, 'А', 'С', 'В');
    readln;
    end.

    Содержание раздела