Сайт Информационных Технологий

Каталог >> ИИ >> Нейронные сети и генетические алгоритмы

оглавление

 

3. Системы счисления, основанные на числах Фибоначчи и Золотой Пропорции.

 

 

В этом разделе речь пойдет о различных представлениях чисел, основанных на числах Фибоначчи и Золотой Пропорции.

Доказано, что любое целое число можно представить в виде:

N = a1*F1 + …………………… + an*Fn , (1)

где ai Î {0, 1} , i Î {1, ……, n}

Основным свойством этого представления, называемого представлением Цекендорфа, является избыточность:

5 = 1+1+3 , 5 = 2+3;

16 = 8+5+2+1 , 16 = 13+3 и т.д.

(здесь слагаемые - 1, 2, 3, 5, 8, 13 - являются числами Фибоначчи)

 

 

 

 

Система счисления, основанная на степенях З.С., называется системой счисления Бергмана:

A = å ai*t i , (2)

где A – произвольное действительное число,

t = (1+Ö 5)/2 (З.С.) ,

ai Î {0, 1} , i Î {-¥ , ¥ } .

 

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

В то же время, в отличие от систем счисления с рациональным основанием, мы можем представить некоторые иррациональные числа в виде конечной суммы.

 

Упростим вид представления (2) : будем записывать его в виде:

a i a i-1 ……. a 0 , a -1 ……. a -j

Например, 1 = 1,0 , 2 = 10,01 , 3 = 100,01 ,

4 = 101,01 ( т.е.4 = t 2 + t 0 + t -2 ) и т.д.

 

 

Z – свойство натуральных чисел (от “zero” – “ноль”) :

Если некоторое натуральное число N представить в виде (2) , а затем заменить t ­ i на F*i (числа из расширенного ряда Фибоначчи) ,

то полученная сумма å ai F*i ( i Î {-¥ , ¥ } , ai взяты из представления (2) ) будет равна нулю для любого натурального числа N .

Например:

4 = t 2 + t 0 + t -2 è F*2 + F*0 + F*-2 = 1 + 0 + (-1) = 0 .

 

Система счисления Бергмана, как и представление Цекендорфа, является избыточной, например:

3 = 11,01 = 100,01 .

 

Различные представления числа в системе Бергмана могут быть получены с помощью операций “свертки” ( 011 à 100 ) и “развертки” ( 100 à 011 ) . Если над кодовым представлением числа выполнить все возможные операции свертки, мы получим “минимальную форму”, в которой не встречается рядом 2-х единиц; если выполнить все операции развертки, мы придем к “максимальной форме”, в которой не встречается рядом 2-х нулей.

___________________________________________________________________

 

Однако наиболее интересным является представление, предложенное А.П.Стаховым. Оно напоминает представление Бергмана, но с 2-мя отличиями:

 

Представление Стахова ( “троичное представление” ):

A = å ai*t 2i , (3)

где A – произвольное действительное число,

t = (1+Ö 5)/2 (З.С.) ,

ai Î {1, 0, 1} , i Î {-¥ , -¥ } , 1 = -1 .

 

Стаховым предложена следующая форма записи представления:

a i a i-1 ……. a 0 , a -1 ……. a -j ,

где ai Î {1, 0, 1} , 1 = t 0 - троичная единица, 1 - троичная минус единица.

Например: 2 = 11,1 = t 2 - t 0 + t -2 .

 

Порядок выполнения операций над числами в троичном представлении в основном определяется следующим соотношением:

t 2n + t 2n = t 2(n+1) - t 2n + t 2(n-1) (4)

Доказательство формулы (4) : Ранее было показано, что:

t n+1 = t n + t n-1 , т.е. t n = t n+1 - t n-1 ;

возведем это равенство в квадрат:

t 2n = t 2(n+1) - 2t 2n + t 2(n-1) è (4)

 

Из равенства (4) вытекает следующее правило сложения троичных единиц:

1 + 1 = 111

и правило сложения троичных минус единиц

1 + 1 = 111

При этом имеются в виду 1-цы и 1-цы, находящиеся в любом разряде, т.е. ai = 1 ( или ai = 1 ) для некоторых i .

 

Остальные правила троичных арифметических действий - следующие:

0 + 0 = 0 , 1 + 0 = 1 , 1 + 0 = 1 , 1 + 1 = 0 .

 

Примеры записи натуральных чисел в троичной системе:

1 = 1,0 (=t 0)

2 = 11,1 (=t 2 - t 0 + t -2)

3 = 11,1 + 1,0 = 10,1 (=t 2 + t -2)

 

Каждый раз, желая получить большее на 1 натуральное число, мы прибавляем единицу к нулевому разряду предыдущего числа и попадаем в одну из трех ситуаций:

  1. a0 = 0 , тогда a0 + 1 = 1 , т.е.:

    an ….. a10 , a -1 ….. a -n + 1 = an ….. a11 , a -1 ….. a -n

  2. a0 = 1 , тогда a0 + 1 = -1 + 1 = 0 , т.е.:

    an ….. a11 , a -1 ….. a -n + 1 = an ….. a10 , a -1 ….. a -n

  3. a0 = 1 , тогда, используя правило сложения единиц, получаем:

a0 + 1 = 1 + 1 = 11,1 , т.е. изменяется не только нулевой разряд, но и два соседних, причем изменяются они симметрично.

Заметим, что как первое из чисел натурального ряда, единица, обладает "зеркальной симметрией" относительно нулевого разряда ( 0001,000 ) , так и правило прибавления единицы обладает тем же свойством. Следовательно, при записи любого нат. числа в данном троичном представлении левая часть (без нулевого разряда) зеркально совпадает с правой.

Итак, после прибавления единицы к a0 = 1 мы должны добавить единицу к следующим разрядам.

Если там стоит 0 или 1 , процесс останавливается, например:

111, 11 + 1 = 101,01 ( т.е. 5 + 1 = 6 ) ,

101,01 + 1 = 111,11 ( т.е. 8 + 1 = 9 ) .

Если же и в следующем разряде находится единица, то "ползем" дальше по разрядам до тех пор, пока не "натолкнемся" на 0 или 1.

Схематично можно изобразить этот процесс так:

+0

1

1

1

1

1

,

1

1

1

1

0

         

1

,

       

0

0

1

1

1

(1+1)

1

,

(1+1)

1

1

1

0

0

1

1

(1+1)

1

1

,

1

(1+1)

1

1

0

0

1

(1+1)

1

0

1

,

0

1

(1+1)

1

0

0

(1+1)

1

0

0

1

,

0

0

1

(1+1)

0

1

1

0

0

0

1

,

0

0

0

1

1

 

Еще раз обратим внимание, что правая часть представления натур. числа нам фактически не нужна - в силу зеркальной симметрии.

Из данной естественной избыточности А.П.Стаховым делается вывод о целесообразности создания компьютера (процессора), основанного на троично-зеркальной симметрии, обеспечивающей универсальный способ контроля всех арифметических операций.

 

Внимательно посмотрев на алгоритм прибавления единицы, можно убедиться, что у положительного целого числа в старшем разряде всегда стоит 1-ца. Если провести все те же рассуждения с отрицательными целыми числами, прибавляя каждый раз (-1)-цу, можно увидеть, что любое отрицательное число имеет в старшем разряде (-1)-цу.

И последнее (глупое) замечание. Пусть некоторое положительное целое X представлено в виде (3) :

X = å ai*t 2i

Умножим X на (-1) : все ai инвертируются.

Пример: 9 = 111,11 , -9 = 111,11

 

Приложение: Таблица разложения натуральных чисел по t 2 от 1 до 47:

 

N

t 2

1

1,0

2

11,1

3

10,1

4

11,1

5

111,11

6

101,01

7

100,01

8

101,01

9

111,11

10

110,11

11

111,11

12

1101,011

13

1111,111

14

1110,111

15

1111,111

16

1011,101

17

1001,001

18

1000,001

19

1001,001

20

1011,101

21

1010,101

22

1011,101

23

1111,111

24

1101,011

25

1100,011

26

1101,011

27

1111,111

28

1110,111

29

1111,111

30

11001,0011

31

11011,1011

32

11010,1011

33

11011,1011

34

11111,1111

35

11101,0111

36

11100,0111

37

11101,0111

38

11111,1111

39

11110,1111

40

11111,1111

41

10101,0101

42

10111,1101

43

10110,1101

44

10111,1101

45

10011,1001

46

10001,0001

47

10000,0001

 

далее


Site of Information Technologies
Designed by  inftech@webservis.ru.