 | ||
|
| ||
|
| ||
|
| ||
|
| ||
|
| ||
|
| ||
|
| ||
Первой задачей настоящего проекта является осознание того, как можно представить различные числа, а второй задачей - как с этими представлениями работать и какими свойствами они обладают.
Наиболее популярными операциями с числами являются арифметические действия - сложение, умножение и т. д. Интересный вопрос - количество элементарных операций, необходимых для того, чтобы сложить/умножить/etc два/три/etc длинных (100-200 цифр) числа.
Во многих областях необходимо уметь быстро определять по виду числа, делится ли оно на какое-нибудь ещё число. Потому неплохо бы найти какие-нибудь признаки делимости.
В ЭВМ часто применяются смешанные системы - например, двоично-десятичная, и неплохо бы понять, как машина работает с числами, записанными в таких системах.
Желающим будет предложено оценить экономичность системы - запас чисел, которые можно записать с помощью определенного числа знаков (например, в десятичной системе для записи 1000 чисел требуется 29 знаков, вдруг в какой-то еще системе с помощью этого количества знаков можно будет записать больше чисел?)
С помощью полученных знаний можно попытаться решить некоторые прикладные задачи, например, такую: определить наименьший набор гирь (по одной штуке каждого наименования), с помощью которого можно уравновесить любой груз массой не более N граммов, кладя гири а) только на одну чашку весов; б) на обе чашки весов.
выполнила: Давыдова Евгения
руководитель проекта: Чесноков Андрей
Пущино, 2002
На нашем проекте мы рассмотрели последовательность чисел Фибоначчи. Эта последовательность строится по такому правилу: каждое следующее число в этой последовательности - это сумма двух предыдущих чисел. По данному правилу первые два числа мы не можем определить и поэтому положили их равными единицам, а так как первые два числа - единицы, первая сумма - это двойка. То есть числа Фибоначчи - это такие числа: 1, 1, 2, 3, 5, 8, 13, 21...
Любое натуральное число L можно представить в виде суммы различных чисел Фибоначчи. Для этого сначала нужно найти наибольшее число Фибоначчи, которое меньше данного натурального числа или равно ему (обозначим его A). То есть нужно рассмотреть последовательные пары соседних чисел Фибоначчи и найти, между числами какой пары находится наше число L. Из этих двух чисел надо выбрать меньшее число, это и будет A.
Например, L=20. Смотрим, число 20 находится между числами Фибоначчи 13 и 21: 1, 1, 2, 3, 5, 8, 13, 21, 34
Затем надо вычесть его из этого натурального числа, и для разности сделать то же самое, что и для L. Так нужно делать, пока разность между тем, что осталось после вычитания, и числом Фибоначчи, которое мы каждый раз ищем, не будет равна нулю. Затем все числа Фибоначчи, которые мы нашли, запишем в виде суммы.
Например: при L=20, A, как мы уже нашли равна 13. Дальше мы вычитаем из 20 13 и получаем 7 - следующее число, для которого нужно найти A. Находим, получаем 5. Вычитаем из семи пять, получаем 2. Опять ищем A, уже для двух. A=2. Вычитаем из двух два, получаем ноль. Это означает, что мы нашли все слагаемые, а именно: 20=13+5+2.
Зная, как представить натуральное число в виде суммы чисел Фибоначчи, можно представить это натуральное число в системе счисления, где в качестве цифр используются только 0 и 1. Для этого построим бесконечную таблицу, в которой верхняя строчка - это числа Фибоначчи, последовательно идущие друг за другом по убыванию, а первый столбик - это натуральные числа. Мы берем какое-то из них и представляем его в виде суммы чисел Фибоначчи. Затем в таблице записываем единицу под теми числами Фибоначчи, которые есть в сумме, а нули - под теми числами, которых нет в сумме. Начало такой таблицы приведено в конце отчета. Для представления натурального числа в системе с ноликами и единицами надо сначала взять самую левую единицу, а потом записать все следующие нолики и единицы последовательно, как они стоят (слева направо).
Представить таким способом натуральное число можно не единственным способом, например, число 5 - его поэтому мы договорились это делать так, чтобы при записи числа в системе с ноликами и единицами единицы не стояли рядом. Наш алгоритм дает именно такое представление (чтобы единицы не стояли рядом), поэтому это всегда можно сделать. Докажем это. Предположим, что в результате работы алгоритма появилось число, в котором встречается последовательность цифр 0 1 1. Обозначим сумму того, что идет перед нулем, буквой S, число Фибоначчи, соответствующее нулю - x, y и z - числа, соответствующие этим двум единицам, а натуральное число, которое мы представляем в виде суммы - M. Если бы сумма S и x была меньше или равна M, то на месте нуля стояла бы единица, следовательно, сумма S и x больше M. Так как после нуля стоят две единицы, то сумма S, y и z меньше M, а она должна быть больше, потому что по определению, что каждое число Фибоначчи- это сумма двух предыдущих чисел, сумма y и z равна x, а сумма S и x больше M. Получается противоречие: сумма S и x больше M, а сумма S, y и z - меньше М, тогда как x и y + z равны.
Часть таблицы, построенной по сумме чисел Фибоначчи
| 8 | 5 | 3 | 2 | 1 | |
| 1 | 0 | 0 | 0 | 0 | 1 |
| 2 | 0 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 1 | 0 | 0 |
| 4 | 0 | 0 | 1 | 0 | 1 |
| 5 | 0 | 1 | 0 | 0 | 0 |
| 6 | 0 | 1 | 0 | 0 | 1 |
| 7 | 0 | 1 | 0 | 1 | 0 |
| 8 | 1 | 0 | 0 | 0 | 0 |
| 9 | 1 | 0 | 0 | 0 | 1 |