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

-2

Быстрый метод для быстрого вычисления Фибоначчи, используя свойство Matrixстратегии, чтобы понять код, который я не могу получить

Divide_Conquer_Fib(n) { 
    i = h = 1; 
    j = k = 0; 
    while (n > 0) { 
    if (n%2 == 1) { // if n is odd 
    t = j*h; 
    j = i*h + j*k + t; 
    i = i*k + t; 
    } 
t = h*h; 
h = 2*k*h + t; 
k = k*k + t; 
n = (int) n/2; 
} 
    return j;

}

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

источник

2013-11-22 ERJAN

Я бы посмотрел, как он работает для 1,2,3,2n, 2n + 1, поскольку этот алгоритм работает на четном и нечетном. И я бы использовал бумагу и ручку вместо printf – Jekyll

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

Этот вопрос кажется не по теме, потому что он просит мнения программиста и заявив, что «важно видеть, как разумы разных разработчиков пойдут на понимание этого кода», что значительно отличается от темы для этого сайта. –

Я начал бы запускать его против нескольких значений n, чтобы проверить, что на самом деле это дает правильные ответы. Затем я прочитал математическую теорию, чтобы понять, как она, вероятно, будет работать, и, наконец, использовать эти знания, чтобы взять ее на бит ...

Раздел в Википедии в Matrix form объясняет основу этого алгоритма.

источник

2013-11-22 22:04:38 EricM

Ну, правильный способ взглянуть на этот код - это знать, что он делает: числа Фибоначчи часто появляются как интересное упражнение, плюс есть довольно немного контекста, говорящего о том, что он делает: он использует свойство матрицы вместе с разделяй и побеждай. Оказывается, можно вычислить вектор (FIB _п, Fib _п-1) как произведение некоторой матрицы и (FIB _п-1, Fib _п-2). Давайте предположим, что две строки в коде ниже находятся всего две строки одной и той же матрицы:

(Fib[n] ) (1 1) (Fib[n-1]) 
(  ) = ( ) * (  ) 
(Fib[n-1]) (1 0) (Fib[n-2])

Теперь матрица умножения квадратных матриц ассоциативно, то есть, если выше матрица M можно вычислить Фибо _n как M ⁿ раз (1, 0).

Следующим шагом является вычисление ^{М н} используя разделяй и властвуй. Основная хитрость в том, что M ^п можно разложить по битам н: Вместо вычисление мощности по п умножения вы разлагаетесь вычислениями в вычислительные квадраты и умножение дополнительного члена, если значение странный.

Это основной базовый подход. Вычисление полномочий выполняется в другом направлении, однако, что работает - I думаю - потому что матрица симметрична. Я не думаю, что вы можете легко получить алгоритм из кода, если вы не знаете о базовом подходе.

источник

2013-11-22 22:33:52

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

ответ

Смежные вопросы