Теория чисел Фибоначчи (стр. 10 из 14)
Итак, в результате анализа, основанного на использовании пропорции Фибоначчи, физики пришли к следующим интригующим выводам:
1. Найдено простое и красивое соотношение, связывающее важнейшие безразмерные константы: постоянную тонкой структуры α, число π и золотое отношение Φ.
2. Формула позволила получить новое точное значение постоянной тонкой структуры. Полученные результаты подтверждают геометрический статус постоянной тонкой структуры.
3. Геометрический статус постоянной тонкой структуры указывает на то, что все безразмерные параметры, которые характеризуют микромир и Вселенную, являются принципиально вычисляемыми.
4. Геометрический статус постоянной тонкой структуры указывает на то, что существуют математические соотношения для точного и независимого вычисления значения постоянной тонкой структуры (α), как это имеет место отдельно для числа пи (π) и отдельно для золотой пропорции (Φ).
5. Постоянная тонкой структуры и число пи являются онтологическими суперконстантами, от которых происходят все безразмерные физические константы.
6. То, что α и π оказались связанными с золотым отношением Φ, вытекающим из чисел Фибоначчи, указывает на причастность постоянной тонкой структуры (α), и числа пи (π) к закону гармонии в природе.
7. Отсутствие геометрической теории с применением двух констант – числа пи и постоянной тонкой структуры говорит о том, что геометрия, которой воспользовалась природа остается еще вне поля зрения ученых.
4. Алгоритмы вычисления чисел Фибоначчи и их сложность
В последней главе дипломной работы исследуем вопрос о возможности быстрого вычисления чисел Фибоначчи на компьютере. Эта задача представляет интерес, в связи с тем, что пропорции Фибоначчи обнаруживают свое проявление в самых разнообразных областях. Как известно, правильность – далеко не единственное качество, которым должна обладать хорошая программа. Одним из важнейших качеств является эффективность, характеризующая прежде всего время выполнения программы T(n) для различных входных данных (параметра n).
Нахождение точной зависимости T(n) для конкретной программы – задача достаточно сложная. По этой причине обычно ограничиваются асимптотическими оценками этой функции, то есть описанием ее примерного поведения при больших значениях параметра n. Иногда для асимптотических оценок используют традиционное отношение O (читается "О большое") между двумя функциями f(n) = O(g(n)), определение которого можно найти в любом учебнике по математическому анализу, хотя чаще применяют отношение эквивалентности Θ (читается "тэта большое").
В качестве первого примера вернемся к только что рассмотренным программам нахождения факториала числа. Легко видеть, что количество операций, которые должны быть выполнены для нахождения факториала n! Числа № в первом приближении прямо пропорционально этому числу, ибо количество повторений цикла (итераций) в данной программе равно n. В подобной ситуации принято говорить, что программа (или алгоритм) имеет линейную сложность (сложность O(n) или Θ(n)). Или более обще:
ОПРЕДЕЛЕНИЕ. Алгоритм имеет линейную сложность, если количество выполняемых при этом машинных операций (сложность O(n) или Θ(n)) пропорционально первой степени объема данных задачи (например, количеству перемножаемых чисел, количеству городов в транспортной задаче и т. п.)
Можно ли вычислить факториал быстрее? Оказывается, да. Можно написать такую программу, которая будет давать правильный результат для тех же значений n, для которых это делают все приведенные выше программы, не используя при этом ни итерации, ни рекурсии. Ее сложность будет Θ(1), что фактически означает организацию вычислений по некоторой формуле без применения циклов и рекурсивных вызовов!
Не менее интересен и пример вычисления n-го числа Фибоначчи. В процессе ее исследования фактически уже было выяснено, что ее сложность является экспоненциальной и равна Θ(2n). Подобные программы практически не применимы на практике. В этом очень легко убедиться, попробовав вычислить с ее помощью 40-е число Фибоначчи. По этой причине вполне актуальна следующая задача.
Задача 1: Написать программу, печатающую n-ое число Фибоначчи, которая имела бы линейную сложность.
Вот решение этой задачи, в котором переменные j и k содержат значения двух последовательных чисел Фибоначчи.
Текст программы.
public class FibIv1 {
public static void main(String [] args) throws Exception {
int № = Xterm. inputInt("Введите n-> ");
Xterm. print("f(" + № + ")");
if (n < 0) {
Xterm. print(" не определено\n");
} else if (n < 2) {
Xterm. println(" = " + n);
} else {
long i = 0;
long j = 1;
long k;
int m = n;
while (--m > 0) {
k = j;
j += i;
i = k;
}
Xterm. println(" = " + j);
}
}
}
Следующий вопрос вполне естественен – а можно ли находить числа Фибоначчи еще быстрее?
После изучения определенных разделов математики совсем просто вывести следующую формулу для n-ого числа Фибоначчи Fn, которую легко проверить для небольших значений n:
Может показаться, что основываясь на ней, легко написать программу со сложностью Θ(1), не использующую итерации или рекурсии.
Текст программы.
public class FibIv2 {
public static void main(String [] args) throws Exception {
int № = Xterm. inputInt("Введите n-> ");
double f = (1.0 + Math. sqrt(5.)) / 2.0;
int j = (int)(Math. pow(f,n) / Math. sqrt(5.) + 0.5);
Xterm. println("f(" + № + ") = " + j);
}
}
На самом деле эта программа использует вызов функции возведения в степень Math. pow(f,n), которая не может быть реализована быстрее, чем за логарифмическое время (log2 №). Про алгоритмы, в которых количество операций примерно пропорционально log № (в информатике принято не указывать основание двоичного логарифма) говорят, что они имеет логарифмическую сложность (Θ(log №)).
Для вычисления n-го числа Фибоначчи существует такой алгоритм, программную реализацию которого мы приведем без дополнительных комментариев, – иначе нужно объяснять слишком много (связь чисел Фибоначчи со степенями матрицы порядка два, использование классов для работы с матрицами, алгоритм быстрого возведения матрицы в степень).
Задача 2: Написать программу, печатающую n-ое число Фибоначчи, которая имела бы логарифмическую сложность.
Текст программы.
public class FibIv3 {
public static void main(String [] args) throws Exception {
int № = Xterm. inputInt("Введите n-> ");
Xterm. print("f(" + № + ")");
if (n < 0) {
Xterm. println(" не определено");
} else if (n < 2) {
Xterm. println(" = " + n);
} else {
Matrix b = new Matrix(1, 0, 0, 1);
Matrix c = new Matrix(1, 1, 1, 0);
while (n>0) {
if ((n&1) == 0) {
№ >>>= 1; c. square();
} else {
n-= 1; b. mul(c);
}
}
Xterm. println(" = " + b. fib());
}
}
}
class Matrix {
private long a, b, c, d;
public Matrix(long a, long b, long c, long d) {
this. a = a; this. b = b; this. c = c; this. d = d;
}
public void mul(Matrix m) {
long a1 = a*m. a+b*m. c; long b1 = a*m. b+b*m. d;
long c1 = c*m. a+d*m. c; long d1 = c*m. b+d*m. d;
a = a1; b = b1; c = c1; d = d1;
}
public void square() {
mul(this);
}
public long fib() {
return b;
}
}
Если попробовать посчитать десятимиллионное число Фибоначчи с помощью этой и предыдущей программ, то разница во времени счета будет вполне очевидной. К сожалению, результат будет неверным (в обоих случаях) в силу ограниченности диапазона чисел типа long.
В заключение приведем сравнительную таблицу времен выполнения алгоритмов с различной сложностью и объясним, почему с увеличением быстродействия компьютеров важность использования быстрых алгоритмов значительно возрастает.
Рассмотрим четыре алгоритма решения одной и той же задачи, имеющие сложности log n, n, n2, 2n и соответственно. Предположим, что второй из этих алгоритмов требует для своего выполнения на некотором компьютере при значении параметра n=103 ровно одну минуту времени. Тогда времена выполнения всех этих четырех алгоритмов на том же компьютере при различных значениях параметра будут примерно такими, как в таблице 2.
Таблица 2
Сравнительная таблица времен выполнения алгоритмов
| Сложность алгоритма | n=10 | n=103 | n=106 |
| log n | 0.2 сек. | 0,6 сек. | 1,2 сек. |
| n | 0.6 сек. | 1 мин. | 16,6 час. |
| n2 | 6 сек. | 16,6 час. | 1902 года |
| 2n | 1 мин. | 10295 лет | 10300 000 лет |
Когда начинающие программисты тестируют свои программы, то значения параметров, от которых они зависят, обычно невелики. Поэтому даже если при написании программы был применен неэффективный алгоритм, это может остаться незамеченным. Однако, если подобную программу попытаться применить в реальных условиях, то ее практическая непригодность проявится незамедлительно.
С увеличением быстродействия компьютеров возрастают и значения параметров, для которых работа того или иного алгоритма завершается за приемлемое время. Таким образом, увеличивается среднее значение величины, и, следовательно, возрастает величина отношения времен выполнения быстрого и медленного алгоритмов. Чем быстрее компьютер, тем больше относительный проигрыш при использовании плохого алгоритма.
5. Методика изучения чисел Фибоначчи в старших классах
5.1. Общие методические указания
Начинать изучение чисел Фибоначчи следует с демонстрации их естественного появления во многих задачах и ситуациях. Помимо классической задачи о кроликах необходимо сформулировать и другие задачи, в которых появляются числа Фибоначчи.
Наглядный пример естественного возникновения чисел Фибоначчи дают, например, так называемые "родословные деревья пчел" Рассмотрим родословную пчелы-самца. Каждый самец (называемый также трутнем) появляется на свет непарным путем от самки (называемой также маткой), однако каждая самка имеет двух родителей – самца и самку. Несколько начальных уровней такого дерева представлены ниже на рисунке 13.