PHP: ищем представление Цекендорфа для чисел

Красивое утверждение, называемое теоремой Цекендорфа, гласит, что любое натуральное число может быть представлено в виде суммы не идущих подряд чисел Фибоначчи и это представление единственно.

Ниже показан небольшой код на PHP, который выводит представления Цекендорфа для чисел $m, $m-1, ..., 1, значение $m задано в первой строке скрипта.

Вывод скрипта вот такой (показан верхний фрагмент экрана):

вывод скрипта представлений Цекендорфа

После отладочной печати массива из самих чисел Фибоначчи, в очередной строке печатается десятичное число, затем его представление в Фибоначчиевой системе счисления и в виде десятичной суммы Цекендорфа, при этом умножаемые на единицу, а не на ноль числа Фибоначчи выделены красным цветом.

В конце строк в скобках выводятся результаты проверки сгенерированной формулы функцией eval, обратите внимание на оператор eval("return $formula;"), если в $formula записано что-то вроде 0*1+0*2+1*3+0*5+1*8, это нужно делать именно так. Выполнить скрипт, как и любой другой код на PHP, можно на локальном хосте, если его установить и настроить.

Ниже приведён полный исходник скрипта на PHP.

<?php
$m = 100; //Верхняя граница обработки

//Делаем ряд Фибоначчи из чисел до $m 
$F = array(1,1);
while ($F[count($F)-1] <= $m) $F[] = $F[count($F)-1] + $F[count($F)-2];

print_r ($F); echo '<br>'; //Печатаем ряд Фибоначчи (для отладки)
 
while ($n = $m--) { //Обрабатываем числа от $m до 1
 while ($F[count($F)-1] > $n) array_pop($F);
 $l = count($F)-1;
 echo "$n = "; //Исходное число
 //В Фибоначчиевой системе счисления:
 $number = '';
 while ($n) { 
  if ($n >= $F[$l]) {
   $n = $n - $F[$l];
   $number .= '1';
  } 
  else $number .= '0';
  --$l;
 }
 $number .= str_repeat('0',$l);
 echo $number.' = ';
 //В десятичном представлении:
 $formula = $text = ''; //Формула для проверки и текст с выделением цветом
 $k = 1;
 for ($i=strlen($number)-1; $i>-1; $i--) {
  $formula .= $number[$i]. '*'. $F[$k];
  $text .= $number[$i]. '*'. ($number[$i]=='1'?'<font color="red">':'').
   $F[$k++]. ($number[$i]=='1'?'</font>':'');
  if ($i>0) { $formula .= '+'; $text .= '+'; }
 }
 echo $text.' ('.eval("return $formula;").")<br>\n";
}
?>

27.10.2017, 14:06 [2150 просмотров]