когда итальянский математик Леонардо Пизанский
Задание 5.01. Числа Фибоначчи
История чисел Фибоначчи восходит к началу XIII в., когда итальянский математик Леонардо Пизанский нашел изящное решение задачи о размножении кроликов. Пусть в начале эксперимента имеется единственная пара -самец и самка, которые приносят каждый месяц приплод, состоящий также из самца и самки. Дети включаются в цикл продолжения рода через два месяца. Требуется определить количество пар, спустя k месяцев после начала эксперимента. Ситуация не так уж и сложна:
Леонардо догадался, что числа указанной последовательности связаны рекуррентным соотношением:
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 делится на это же число без остатка. Поэтому алгоритм Евклида состоит из следующих шагов:
Совет 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 дисков, равно:
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)
Совет 3 (Паскаль)
Программа 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.
