Разработка программы для решения задачи на взвешивание в фибоначчиваемой системе счисления средствами Delphi

 

 

 

 

 

 

 

 

КУРСОВАЯ РАБОТА

 

Разработка программы  для решения задачи на взвешивание в фибоначчиваемой системе счисления средствами Delphi

 

 

 

 

 

 

                                                                           Научный руководитель:

                                                                           …………………………………

                                                                           …………………………………

Архангельск – 2011

Содержание

1. Введение……………………………………………………………………..4

2. Теоретическая часть………………………………………………………...5

2.1. Система счисления………………………………………………....5

2.2. Виды систем счисления……………………………………………5

2.2.1. Позиционные системы  счисления………………………..5

2.2.2. Непозиционные системы  счисления……………………..7

2.2.3. Смешанные системы  счисления………………………….7

2.3. Числа Фибоначчи…………………………………………………..7

2.4. Использование чисел  Фибоначчи в различных областях……….8

2.5. Фибоначчиева система  счисления……………………………….15

2.6. Задача на взвешивание……………………………………………16

2.6.1. Решение  задачи на взвешивание………………………...16

3. Практическая часть………………………………………………………..19

3.1. Описание программы…………………………………………….19

3.2. Интерфейс программы…………………………………………...19

3.3. Блок-схема………………………………………………………....22

4. Заключение………………………………………………………………....23

5. Список литературы………………………………………………………..24

6. Приложение………………………………………………………………..26

6.1. Листинг программы………………………………………………26

 

1. Введение

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

Целью курсовой работы, выполненной  на тему "Разработка программы для  решения задачи на взвешивание в  фибоначчиваемой системе исчисления средствами Delphi", является разработка программы, позволяющей получать как результат представление любого натурального числа в фибоначчиевой системе счисления.

Были поставлены следующие  задачи:

1. изучение чисел Фибоначчи;
2. рассмотрение различных систем счисления;
3. изучение фибоначчиевой системы счисления;
4. изучение возможностей применения чисел Фибоначчи в различных областях;
5. реализация на компьютерном языке программирования программы для перевода чисел в фибоначчиеву систему счисления.

Разработка такой программы является актуальной, так как позволяет производить операцию перевода любого числа в фибоначчиеву систему счисления и получать результат в виде последовательности нулей и единиц.

Данная программа может быть использована как одно из средств  в областях, связанных с математическими вычислениями и расчетами.

 

2.Теоретическая часть.

2.1. Система счисления.

Системой  счисления или нумерацией называется определенный способ записи чисел.

Системы счисления  подразделяются на позиционные, непозиционные  и смешанные. Числа заключают в себе количественную информацию. Запись чисел по определенным правилам определенной системы счисления есть способ кодирования чисел. От способа кодирования зависит размер кода, т.е. количество цифр в записи числа, а также правила выполнения вычислений.

Одной из главных  проблем, которые нужно было решить изобретателям ЭВМ – проблема представления чисел в памяти компьютера и алгоритма их обработки (вычислений) процессором. Для понимания  того, как были решены эти проблемы, нужно знать принципы организации систем счисления.

2.2. Виды систем счисления.

2.2.1. Позиционная система счисления.

В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен. Так, в целом десятичном числе 325, тройка означает три сотни, двойка - два десятка, пятерка - пять единиц:   . Такая запись называется развернутой формой записи числа: число записывается в виде суммы, в которой каждое слагаемое – это цифра, умноженная на свой вес. Вот еще пример развернутой записи смешанного десятичного числа:

В десятичной системе  счисления степени веса равны  степеням десятки (положительным и  отрицательным). Каждая позиция в записи числа называется разрядом числа. Разряды нумеруются в целой части числа положительными целыми числами, начиная от нуля, в дробной части – отрицательными числами, начиная от минус единицы:

Разряды:	3	2	1	0	-1	-2	-3
Число:	6	2	4	8,	5	4	7

Из этой таблицы видно, что веса соответствующих цифр равны десяти в степени, равной номеру разряда, в котором стоит эта цифра. Бесконечный в обе стороны ряд целых степеней десятки называется базисом десятичной системы счисления.       К основным понятиям позиционных систем относятся цифры (символы, используемые для записи чисел), алфавит (совокупность всех цифр), размерность (количество цифр, составляющих алфавит).  Система счисления называется традиционной, если ее базис образует геометрическую прогрессию. Знаменатель этой прогрессии называется основанием системы счисления. У традиционных систем счисления знаменатель базиса совпадает с размерностью ее алфавита.  Основание десятичной системы счисления равно десяти, т.к. размерность её алфавита и знаменатель равны десяти.     По такому же принципу организованы все другие традиционные системы счисления. Наименьшим основанием для позиционной системы является двойка – двоичная система. Система с основанием 1 не может быть позиционной, поскольку для неё невозможно построить базис – единица в любой степени равна единице, отсюда можно сделать вывод, что основанием традиционной системы может быть любое натуральное число, начиная от двух.

 

 

2.2.2. Непозиционная система счисления.

Непозиционная система счисления - это система счисления, в которой значение цифры не изменяется в зависимости от ее расположения. Примером непозиционной системы счисления служит римская система, в которой вместо цифр используются латинские буквы, например: Число 242 можно записать  ССXLII (т.е. 100+100+(50-10) +1+1).

2.2.3. Смешанная система счисления.

Смешанная система счисления зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая  последовательность чисел,  и каждое число X представляется как линейная комбинация. В качестве примера смешанной системы счисления рассматривается также фибоначчиева система счисления.

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

В качестве примера  смешанной системы счисления  рассмотрим так называемую фибоначчиеву систему счисления. Базисом этой системы является следующий числовой ряд: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 и т.д. Он называется рядом Фибоначчи или числами Фибоначчи (название по имени средневекового математика Леонардо Пизанского, известного как Фибоначчи). Ряд строится следующим образом: первые два числа задаются как начальные значения: .      Каждое следующее число равно сумме двух предыдущих чисел: и т.д. (рекурсивный метод) - 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,…. Эти числа связаны между собой рядом любопытных соотношений, например, отношение между любым числом и следующим более высоким числом приближается 0.618 после первых четырех вычислений, а отношение между любым числом и следующим более низким числом - приблизительно 1.618 (инверсия 0.618)

Последовательность была исследована Фибоначчи в его труде «Liber Abaci» (1202). Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, предполагая что:     В «нулевом» месяце имеется пара кроликов (1 новая пара).   В первом месяце первая пара производит на свет другую пару (1 новая пара).             Во втором месяце обе пары кроликов порождают другие пары и первая пара погибает (2 новые пары).        В третьем месяце вторая пара и две новые пары порождают в общем три новых пары, а старая вторая пара погибает (3 новые пары).   Закономерным является тот факт, что каждая пара кроликов порождает ещё две пары на протяжении жизни, а затем погибает.    Пусть популяция за месяц n будет равна . В это время только те кролики, которые жили в месяце n-2, являются способными к размножению и производят потомков, тогда пар прибавится к текущей популяции F(n-1). Таким образом, общее количество пар будет равно .

2.4. Использование  чисел Фибоначчи в различных  областях.

- Дерево Фибоначчи — АВЛ-дерево (сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1) с наименьшим числом вершин при заданной высоте (глубине).        Если для какой-либо из вершин высота поддерева, для которого эта вершина является корнем, равна h, то правое и левое поддерево этой вершины имеют высоты равные соответственно h − 1 и h − 2 или h − 2 и h − 1. Каждое поддерево дерева Фибоначчи также является деревом Фибоначчи.  Пустое дерево — дерево Фибоначчи высоты 0.    Дерево с одной вершиной — дерево Фибоначчи высоты 1.

Рис. 1. Дерево Фибоначчи

- Золотое сечение (золотая пропорция, деление в крайнем и среднем отношении) — деление непрерывной величины на две части в таком отношении, при котором меньшая часть так относится к большей, как большая ко всей величине. Отношение большей части к меньшей в этой пропорции выражается квадратичной иррациональностью:  Также золотое сечение можно получить с помощью такого деления чисел Фибоначчи:

Рис. 2. Золотое  сечение в треугольнике.

- Метод Фибоначчи с запаздываниями - один из методов генерации псевдослучайных чисел (алгоритме, генерирующем последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному)). Особенности распределения случайных чисел, генерируемых линейным конгруэнтным алгоритмом, делают невозможным их использование в статистических алгоритмах, требующих высокого разрешения.      В связи с этим линейный конгруэнтный алгоритм постепенно потерял свою популярность, и его место заняло семейство фибоначчиевых алгоритмов, которые могут быть рекомендованы для использования в алгоритмах, критичных к качеству случайных чисел.    Наибольшую популярность фибоначчиевы датчики получили в связи с тем, что скорость выполнения арифметических операций с вещественными числами сравнялась со скоростью целочисленной арифметики, а фибоначчиевы датчики естественно реализуются в вещественной арифметике.           Также существует несколько распространенных инструментов технического анализа, основанных на числах Фибоначчи. Общий принцип интерпретации этих инструментов состоит в том, что при приближении цены к построенным с их помощью линиям следует ожидать изменений в развитии тенденции:             -Дуги Фибоначчи - состоят из кривых линий, которые обозначают потенциальные ключевые уровни поддержки и сопротивления, и время изменения тренда, используются для прогнозирования потенциальных уровней поддержки и сопротивления цены.

Рис. 3. Дуги Фибоначчи.       -Веер Фибоначчи - между двумя экстремальными точками проводится линия тренда (прямая линия, которая соединяет две важные минимальные или максимальные точки цены на графике) - например, от впадины до противостоящего пика. Затем через вторую экстремальную точку автоматически проводится «невидимая» вертикальная линия. Далее из первой экстремальной точки проводятся три линии тренда, пересекающие невидимую вертикальную линию на уровнях Фибоначчи 38,2%, 50% и 61,8%. Считается, что эти линии представляют собой уровни сопротивления и поддержки.

Рис. 4. Веер Фибоначчи.      -Временные зоны Фибоначчи - это ряд вертикальных линий на линии тренда с интервалами Фибоначчи 1, 2, 3, 5, 8, 13, 21, 34 и т.д. Считается, что вблизи этих линий следует ожидать значительных ценовых изменений. Для построения инструмента необходимо задать две точки, которые будут определять длину единичного интервала. Все остальные линии строятся на основе этого единичного отрезка в соответствии с числами Фибоначчи.

Рис. 5. Временные зоны Фибоначчи.      - Уровни коррекции Фибоначчи - в ходе коррекции трендового движения рынок часто либо отскакивает, либо полностью разворачивается на уровнях Фибоначчи - 23,6, 38,2, 50, 61,8, 76,4 процентов (последний уровень используется редко). Для определения наиболее вероятных уровней остановки коррекции, между максимальной точкой тренда и его начальным уровнем строят линию и на этой линии отмечают уровни 23,6, 38,2, 50, 61,8, 76,4% - это и есть уровни наиболее вероятных коррекций тренда.

Рис. 6. Уровни коррекции Фибоначчи       -Расширение Фибоначчи – во многом похож на уровни коррекции Фибоначчи, строящийся на двух линиях тренда

Рис. 7. Расширение Фибоначчи        -Канал Фибоначчи - является одним из видов Уровней Коррекции Фибоначчи, где линии тренда расположены по диагонали, а не по горизонтали. Каналы используются для определения уровней поддержки и сопротивления. Канал строится по максимальным и минимальным точкам тренда, при этом ширина канала принимается за единицу. После построения канала на график наносятся параллельные линии на расстоянии 23,6%, 38,2%, 50%, 61,8%, 76,4%, 100%, 161,8%, 261,8%, 423,6% (числа ряда Фибоначчи) от канала. Эти линии предположительно будут уровнями поддержки и сопротивления, когда цена на выходе из канала начнет корректироваться.

Рис. 8. Канал Фибоначчи.

2.5. Фибоначчиева система счисления.      Базис фибоначчиевой системы счисления не является геометрической прогрессией, поэтому её нельзя отнести к традиционной системе счисления. Алфавит фибоначчиевой системы счисления состоит из двух цифр: 0 и 1, как у двоичной системы счисления. Число 8 можно представить тремя способами: 8=10000, 8=1100, 8=1011. Такое свойство называется избыточностью. Избыточность представления чисел в Фибоначчиевой системе счисления по сравнению с классической двоичной колеблется от 28% до 45%. Следовательно, данная система требует для представления чисел на 28–45% больше двоичных разрядов, чем двоичная. Кроме того, из-за межразрядных переносов и большего количества самих разрядов в представлении числа алгоритмы сложения, вычитания, умножения и деления не могут быть быстрее соответствующих алгоритмов двоичной системы. Однако достоинство Фибоначчиевой системы счисления в том, что ее избыточность позволяет обнаруживать ошибки при выполнении арифметических преобразований данных. Отсюда и интерес к фибоначчиевой системе счисления со стороны конструкторов вычислительной техники. Несмотря на очевидную непрактичность Фибоначчиевой системы счисления для конструирования цифровых вычислительных устройств, видна неисследованность разнообразия систем счисления и необходимость поиска систем с новыми качествами.         Согласно теореме Цекендорфа - любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно. Таким образом, происходит избавление от избыточности.