Ваш браузер устарел. Рекомендуем обновить его до последней версии.




 


Магические числа. Ряд Фибоначчи

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

Рассмотрим классическую задачу по отысканию магических чисел. Магическое число это такое трехзначное число, для которого сумма кубов цифр его составляющих равна самому числу. Например, магическим является число 153. Действительно:

13 + 53 + 33 = 1 + 125 + 27 = 153

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

 

int s, d, e, a, b;     //резервирование памяти

for (s=1; s<10; s++)     //перебор числа сотен

for (d=0; d<10; d++)     //перебор числа десятков

for (e=0; e<10; e++)     //перебор числа единиц

{

a = s*100 + d*10 + e*1;     //формирование числа

b = s*s*s + d*d*d + e*e*e;     //сумма кубов цифр числа

//проверка чисел на магичность и вывод магических на экран

if (a == b) Label1->Caption = Label1->Caption + IntToStr (a) + "  ";

}

 

Первая строка объявляет переменные s, d, e для числа сотен, десятков и единиц соответственно, переменные a, b для формирования проверяемого числа и для суммы кубов цифр из которых состоит это число. Далее идет внешний цикл, который перебирает сотни от одной до девяти. В этот внешний цикл вложен цикл, перебирающий десятки от нуля до девяти. И, наконец, в цикл десятков вложен цикл единиц, перебирающий единицы от нуля до девяти. Тогда внешний цикл для сотен выполнится девять раз. Вложенный цикл для десятков выполнится десять раз. Еще более глубоко вложенный цикл для единиц выполнится тоже десять раз. В результате работы этого алгоритма три команды самого глубокого цикла единиц выполнятся девятьсот раз! Хотя программа содержит всего семь строк. Вот почему программирование немыслимо без циклических конструкций.

Строку, вычисляющую сумму кубов цифр составляющих трехзначное число

b = s*s*s + d*d*d + e*e*e; 

можно записать и так:

b = pow(s,3) + pow(d,3) + pow(e,3);

Вспомните, для того чтобы оператор pow возведения числа в некоторую степень заработал, необходимо в заголовочной части файла Unit1.cpp включить инструкцию #include <math.h>.

Запустите программу. Компьютер практически мгновенно отыщет все магические числа. Как видите, магических чисел существует всего четыре: 153, 370, 371, 407.

А теперь рассмотрим ряд чисел Фибоначчи. Сначала немного из истории появления этой последовательности. В 1202 году итальянский математик Леонардо Пизанский по прозвищу Фибоначчи написал «Книгу об абаке», а 1228 году он основательно ее переработал. Абак – это доска с канавками, в которых располагались камешки. С каждой следующей канавкой росло старшинство разряда числа. Абак был прообразом русских счет с костяшками. Эта книга об искусстве счета стала самым значительным математическим произведением на несколько столетий вперед. В этом объемистом труде содержатся почти все арифметические и алгебраические достижения того времени, алгоритмы операций над числами. Именно из этой книги европейцы познакомились с индийской системой цифр, которой мы пользуемся в настоящее время. В «Книге об абаке» есть много оригинальных задач, одна из них – задача о кроликах:

«Сколько пар кроликов рождается за год от одной пары, если через месяц пара производит на свет другую, а рождают кролики со второго месяца после своего рождения?»

Результатом решения этой задачи получается следующая интересная последовательность:

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

В этой числовой последовательности каждый ее элемент равен сумме двух предыдущих:

an = an-1 + an-2

Причем первые два элемента последовательности определены как:

a1 = a2 = 1

Построим программу, выводящую на экран ряд Фибоначчи. Для вычисления следующего элемента ряда программа должна помнить два предыдущих элемента. Таким образом, необходимо три переменных, значения которых нужно будет одновременно хранить в памяти.

 

int a, b, c, n;         //резервирование памяти

a = 1;

b = 1;

c = 1;

Label1->Caption = Label1->Caption + "  " + c;

for (n=0; n<11; n++)    //цикл ДЛЯ

{

Label1->Caption = Label1->Caption + "  " + c;

c = a + b;     //вычисление следующего элемента ряда

a = b;     //смещение первого предыдущего вправо по ряду

b = c;     //смещение второго предыдущего вправо по ряду

}

 

Запустите программу на выполнение – на экране появится ряд чисел Фибоначчи. Эта программа построена на основе обмена переменными своими значениями. Поэтому ни в один момент времени вся последовательность целиком не будет находиться в памяти. Будет лучше, если выделить для данной последовательности одномерный массив. Тогда программа может выглядеть так:

 

 

int a[12];     //резервирование памяти для одномерного массива

a[0] = 1;

a[1] = 1;

Label1->Caption = Label1->Caption + a[0] + "  " + a[1];

for (int n=2; n<12; n++)

{

a[n] = a[n-1] + a[n-2];     //вычисление следующего элемента ряда Фибоначчи

Label1->Caption = Label1->Caption + "  " + a[n];

}

 

Теперь после выполнения программы ряд Фибоначчи будет храниться в памяти! Попробуйте увеличить число элементов этой замечательной последовательности.

Flag Counter
200stran.ru: показано число посетителей за сегодня, онлайн, из каждой страны и за всё время
Яндекс.Метрика
Besucherzahler russain brides
счетчик посещений

Выбери лучшее!

allbest