Nadesłany przez Marek Rynarzewski, 03 września 2012 18:56
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.Pobierz pełne rozwiązanie.
srm.php:
<?php //Szybka rekurencja modularna //Marek Rynarzewski //www.algorytm.org echo("test_mulmat: ".(test_mulmat()?"true":"false").'<br/>'); //Oblicz pietnascie pierwszych wartosci ciagu Fibonacciego for($i = 0; $i != 15; $i++) { $a = fibonaccilog($i); echo 'Obliczy�em '.$i.'. ty wyraz w '.round($end - $start, 10000).' sekund.<br/>'; echo $a.'<br/>'; } //Testuje mnozenie macierzy function test_mulmat() { $a = array( array(1, 1), array(1, 0) ); $b = array( array(1, 1), array(1, 0) ); $c = mulmat($a, $b); $result = true; if ($c[0][0] != 2) $result = false; if ($c[0][1] != 1) $result = false; if ($c[1][0] != 1) $result = false; if ($c[1][1] != 1) $result = false; //table($a); table($b); table($c); return $result; } //Mnozenie macierzy a * b function mulmat(array $a, array $b) { $c = array(); for ($i=0;$i <= count($a)-1; $i ++) { //echo("i = $i;"); for ($j=0;$j <= count($b[0])-1; $j ++) { //echo("j = $j;"); $suma = 0; for ($k = 0; $k <= count($b)-1; $k ++) { $suma += $a[$i][$k] * $b[$k][$j]; } $c[$i][$j] = $suma; } } return $c; } //Podnosi macierz a do potegi n function powmat($a, $n) { echo('run powmat with<br/>a =('.table($a).', '.$n.')<br/>'); if ($n == 0) return unimat(count($a)); if ($n == 1) return $a; if ($n % 2 != 0) return mulmat($a, powmat($a, $n - 1)); else { $a = powmat($a, floor($n/2)); return mulmat($a, $a); } } //Tworzy macierz jednostkowa o rozmiarze n function unimat($n) { $c = array(); for ($i = 0; $i < $n; $i ++) { for ($j = 0; $j < $n; $j ++) { if ($i == $j) { $c[$i][$j] = 1; } else { $c[$i][$j] = 0; } } } return $c; } //Oblicza n-ty wyraz ciagu Fibonacciego uzywajac szybkiej rekurencji modularnej function fibonaccilog($n) { global $start, $end; $start = microtime(); $a = array( array(1, 1), array(1, 0) ); $a = powmat($a, $n); $end = microtime(); return $a[0][0]; } //Wypisuje wartosc macierzy c w tabeli function table($c) { $result = '<br/><table border="1">'; foreach($c as $row) { $result .= '<tr>'; foreach($row as $cell) { $result .= '<td>'.$cell.'</td>'; } $result .= '</tr>'; } $result .= '</table><br/>'; return $result; }