Как найти миллионное число в серии: 2 3 4 6 9 13 19 28 42 63 ...? - PullRequest
Новая
       49

Как найти миллионное число в серии: 2 3 4 6 9 13 19 28 42 63 ...?

27 голосов
/ 15 мая 2010

Требуется около минуты, чтобы набрать 3000 в моем компе, но мне нужно знать миллионное число в серии. Определение является рекурсивным, поэтому я не вижу никаких ярлыков, кроме как вычислить все до миллионного числа. Как быстро рассчитать миллионное число в серии?

Серия Def

n_{i+1} = \floor{ 3/2 * n_{i} } и n_{0}=2.

Интересно, что только один сайт перечисляет серию по версии Google: этот .

Слишком медленный код Bash 

#!/bin/bash

function series 
{
        n=$( echo "3/2*$n" | bc -l | tr '\n' ' ' | sed -e 's@\\@@g' -e 's@ @@g' );
                                        # bc gives \ at very large numbers, sed-tr for it
        n=$( echo $n/1 | bc )           #DUMMY FLOOR func
}

n=2
nth=1

while [ true ]; #$nth -lt 500 ];
do
        series $n                        # n gets new value in the function through global value
        echo $nth $n
        nth=$( echo $nth + 1 | bc )     #n++
done

Ответы [ 12 ]

0 голосов
/ 16 мая 2010

Я преобразовал идеи Тимо в elisp. Сбой с 100, давая отрицательное число. FAIL, пожалуйста, смотрите нет BigNums ! 

(progn
  (let ((a 2)
        (dummy 0))
    (while (< dummy 100)
      (setq a (+ a (lsh a -1)))
      (setq dummy (1+ dummy)))
    (message "%d" a)))
-211190189 #WRONG evalution
0 голосов
/ 15 мая 2010

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

т.е. (Псевдокод) 

bignum x = 2
for (int i = 1; i < 1000000; i++) {
    x = floor(3.0/2*x)
}

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

Страница:
...