Отправляет email-рассылки с помощью сервиса Sendsay

Всё о работе в Интернет

Подписаться Бесплатная «Серебряная» новостная рассылка Подписчиков 7.350 RSS
←   Октябрь 2009   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://bestinvestblog.com
Открыта: 10-02-2009

Автор
bestinvestblog

Статистика

7.350 подписчиков
0 за неделю
←   Все выпуски   →

Занятие 49. Циклы в популярных задачах арифметики. Возведение в степень. Числа Фибоначчи.


Сегодня, уважаемые подписчики, мы с вами продолжаем изучать циклические алгоритмы решения популярных арифметических задач.

Есть в программированьи тихом
            Азарт, интрига, жесть и страсть…

ЦИКЛЫ В ПОПУЛЯРНЫХ ЗАДАЧАХ АРИФМЕТИКИ

1. Возведение в степень.

Решим следующую задачу.

Задача C.1.6. “Возведение в степень”. Построить подпрограмму “точного” возведения произвольного числа A в целую положительную степень N.

Известно (см. http://a-morgun.narod.ru/a08-01/a0008-0001-0001-0005.html), что при X > 0 функция XY вычисляется при любых Y с помощью выражения Exp(Ln(X)*Y). Там же рассмотрены и некоторые случаи аналогичного возведения в степень отрицательных чисел. Однако, следует признать, что использование для возведения в степень экспоненциальной и логарифмической функций Паскаля неминуемо ведёт к появлению погрешностей вычислений. И причиной этого является не только ограниченная разрядность чисел, но и несовершенство методов вычисления функций. В частности, для экспоненциальных и логарифмических функций используются их разложения в бесконечные ряды слагаемых. Естественно, при вычислениях приходится ограничиваться какой-то частью членов ряда, в результате чего и появляется, так называемая, погрешность метода.

Нижеследующие примеры демонстрируют отличающиеся между собой результаты, полученные для одного и того же вычисления разными методами:

-       Exp(Ln(3.3)*5)=391.353930000216;

-       a:Real; a=3.3; n = 5; Exp(Ln(a)*n)=391.353929999750; 

-       точное значение 3.35 = 391.35393.

Некоторые шансы на получение более точного результата возведения в степень даёт использование последовательного умножения, которое и реализовано в подпрограмме C.1.6 (функция Power).

   Function Power ( A: Real; N: Integer ): Real;
      Var i: Integer; P: Real;
   Begin
      P:=1;
      For i:=1 To N Do P := P*A;
      Power:=P
   End;

Алгоритм подпрограммы C.1.6, выполняющей возведение в целую положительную степень AN путём последовательного умножения A само на себя N раз, можно рассматривать как частный случай вычисления произведения первых N членов арифметической прогрессии со стартовым членом A и разностью R = 0. Таким образом, подпрограмма C.1.6 является соответствующей модификацией подпрограммы C.1.5, что легко обнаружить непосредственным их сравнением.

При произвольном A подпрограмма всегда даёт правильный результат при всех N>=0 за исключением того единственного случая, когда A и N равны нулю одновременно. Этот случай соответствует величине 00, которая в математике считается неопределённой.

Разумеется, и последовательное умножение вещественных чисел также выполняется неточно. Однако же, вообще говоря, нас никто не принуждает использовать для умножения стандартную арифметическую операцию “*”. В конце концов, можно использовать алгоритм “точного” умножения “в столбик” и за счёт этого получить “точный” результат возведения в степень. Когда-нибудь мы с вами, уважаемый подписчик, займёмся и этим тоже. Таким образом, будем считать, что актуальность алгоритма возведения в степень посредством последовательного умножения нами доказана.  

2. Числа Фибоначчи.

Решим следующую задачу.

Задача C.1.7. “Числа Фибоначчи”. Построить подпрограмму для определения числа Фибоначчи с порядковым номером N.

Последовательность натуральных чисел 1, 1, 2, 3, 5, 8, ... , в которой каждое число (кроме первых двух) равно сумме двух предыдущих, называется числами Фибоначчи. Числа в последовательности считаются пронумерованными по порядку, начиная с единицы.

Числа Фибоначчи представляют собой последовательность рекуррентного типа, в которой значение каждого члена, начиная с третьего, связано функциональной зависимостью со значениями двух предыдущих членов этой же последовательности. Комбинированная формула общего члена рекуррентной последовательности Фибоначчи может быть описана следующим образом: Ai = 1 при i = 1, 2; Ai = Ai–1 + Ai–2 = 1 при i = 3, 4, ….

   Function Number_Fibo ( N: Integer ): LongInt;
      Var a,b,c: LongInt; i: Integer;
   Begin
      a:=1; b:=1; c:=1;
      For i:=3 To N Do
         Begin c:=a+b; a:=b; b:=c End;
      Number_Fibo:=c
   End;

Для нахождения числа Фибоначчи с заданным порядковым номером в подпрограмме C.1.7 (функция Number_Fibo) используется скользящая вдоль последовательности тройка переменных a, b и c.

Скольжение реализуется следующим образом:

-       пусть a=1 и b=1 – первоначальные значения переменных, соответствующие первому и второму числу Фибоначчи; первое суммирование c=a+b даёт третье число Фибоначчи, то есть 2 = 1 + 1;

-       затем значения переменных a и b переопределяются; сначала переменная a получает значение переменной b, то есть a=1; затем переменная b получает значение переменной c, то есть b=2;

-       теперь очередное суммирование c=a+b даёт четвёртое число Фибоначчи, то есть 3 = 1 + 2;

-       при повторном переопределении сначала переменная a получает значение переменной b, то есть a=2, а затем переменная b получает значение переменной c, то есть b=3;

-       теперь очередное суммирование c=a+b даёт пятое число Фибоначчи, то есть 5 = 2 + 3 и т. д.

Как показывает комбинированная формула общего члена, использование рекуррентного соотношения начинается только с третьего числа Фибоначчи. Поэтому в подпрограмме циклический процесс последовательного образования чисел Фибоначчи начинается числом с порядковым номером i=3. Завершается цикл, естественно, числом с порядковым номером i=N. Результатом является значение вспомогательной переменной c. При N<3 цикл не выполняется, поэтому значение результата определяется перед циклом непосредственным присваиванием переменной c значения 1.

Уважаемые подписчики! При необходимости задать вопрос, проконсультироваться, уточнить или обсудить что-либо обращайтесь через Гостевую книгу моего персонального сайта http://a-morgun.narod.ru. При этом настоятельно рекомендую пользоваться браузером Internet Explorer.

С уважением, Александр.
В избранное