Pomoc - Szukaj - Użytkownicy - Kalendarz
Pełna wersja: [php] wyznacznik i rząd macierzy
Forum PHP.pl > Forum > PHP
coco
Mam napisać skrypty php:
1. liczący rząd dowolnej macierzy 3x3
2. obliczający wyznacznik dowolnej macierzy
Co do 1 to nie wiem jaką metodę tu wybrać, aby było to w ogóle możliwe do napisania. W 2 wiem, że tutaj metodą może być rozwinięcie Laplace'a, ale nie mam pomysłu jak to rekurencyjnie napisać.
Przyda mi się każda pomoc i za każdą z góry dziękuję.
vokiel
Co do pierwszego punktu to możesz to obliczyć metodą Gaussa
thek
ad 1) Wikipedia i przeczytaj tam o rzędzie macierzy... Masz nawet przykład jak zastosować do tego eliminacje Gaussa.
ad 2) Znów Wikipedia i tam poczytaj o wyznacznikach macierzy. Dla Twojego przypadku zwróć uwagę na rozwinięcie Laplace'a (trudniejsze w implementacji) lub eliminację Gaussa. To drugie ma mnóstwo implementacji w necie. Najprostsza sekwencyjna to
Kod
for( s=0; s<n; ++s)
{
  tmp = tab[i][s] / tab[s][s];
  for ( i=s+1; i<n; ++i)
  {
     for ( j=s; j<=n; ++j)
       A[i][j] = A[i][j] - tmp * A[s][j];
  }
}
Gdzie A to macierz, zaś tab to wiersz wynikowy popularnie oznaczany w algebrze jako b dla równania Ax = b smile.gif Po implementacji algorytmu sobie zobacz gdzie masz wyniki winksmiley.jpg Nie wiem czy istnieje prostsze niż to przedstawienie algorytmu Gaussa w pseudokodzie, który tak naprawdę jest już niemal gotowcem biggrin.gif
coco
z tym rzędem już mi się udało, ale wyznacznika nie umiem za nic. Udało mi się znaleźć w internecie skrypt JS na wyznacznik, próba przekształcenia na php dała to:
  1. <?
  2. function wyznacznik($tablica){
  3. $tablica=Array(Array(1,2), Array(3,4));
  4. $wynik=0;
  5. print_r($tablica);
  6. if (count($tablica)==1) {return $tablica[0][0];}
  7. for ($a=0;$a<$count($tablica[0]);$a++){
  8. $znak=1;
  9. if($a%2!=0) $znak=-1;
  10. $mnoznik = $tablica[0][$a];
  11. $m=Array();
  12. $m2=Array();
  13. for($b=1;$b<count($tablica); $b++){
  14. $d=0;
  15. for($c=0;$c<count($tablica[$b])-1; $c++){
  16. if($c==$a) {$d = 1;}
  17. $m2[$c] = $tablica[$b][$c+$d];
  18. }
  19. $m[$b-1]= $m2;
  20. $m2=Array();
  21. }
  22. $wynik+=$znak*$mnoznik*$wyznacznik($m);
  23. }
  24. return $wynik;
  25. }
  26. ?>
  27.  

ale zgodnie z przewidywaniami nie działa. Gdyby ktoś był uprzejmy pomóc ...
thek
Mój błąd... Podałem rozwiązanie na liczenie Gaussa jako układu równań. Czyli masz wtedy jeszcze wektor wynikowy b. Ty zaś masz sam wyznacznik policzyć. Do tego też jest masę linków w google. Wpisz sobie: wyznacznik kod Gauss i pooglądaj tematy winksmiley.jpg Już w pierwszych masz gotowce. Tyle że wspominają o małej niedogodności tam i czasem konieczności używania pivotingu, ale to normalne przy macierzach. Przypadki jednak by trzeba go było użyć są raczej rzadkie.
coco
Cytat(thek @ 22.10.2009, 13:23:56 ) *
Mój błąd... Podałem rozwiązanie na liczenie Gaussa jako układu równań. Czyli masz wtedy jeszcze wektor wynikowy b. Ty zaś masz sam wyznacznik policzyć. Do tego też jest masę linków w google. Wpisz sobie: wyznacznik kod Gauss i pooglądaj tematy winksmiley.jpg Już w pierwszych masz gotowce. Tyle że wspominają o małej niedogodności tam i czasem konieczności używania pivotingu, ale to normalne przy macierzach. Przypadki jednak by trzeba go było użyć są raczej rzadkie.

Wpisuję i wpisuję, ale z php nie da się nic znaleźć, nawet po angielsku szukanie nic nie daje. Jedynie to są jakiś przydługawe programy z delphi czy C++ czego na pewno nie przerzucę na PHP, skoro nawet mi się nie udało "przetłumaczyć' z JS. Więc chyba nie tak łatwo i nie takie gotowce, bo od 3 godzin nie ruszam ani kroku w przód z tym.
thek
C++ jest tak proste do przerzucenia na PHP, że ja nie wiem gdzie widzisz problem blinksmiley.gif Większość tu piszących powie Ci to samo. Wiele języków skryptowych ma składnię wzorowaną na C++ i PHP tu nie jest wyjątkiem. Umiejąc C++ łatwo nauczysz się PHP i vice versa. Mają podobne nazewnictwo, struktury danych, struktury kontrolne. Jedynie czasem masz nieco inne podejście do danych bo jawnie podajesz ich typ i to wszystko. PHP jest znacznie prostszy niż C++.
Dla tych znających choć podstawy C++ przepisanie kodu Gaussa z C++ na PHP z tych gotowców to będzie góra minutka smile.gif Zmienią może kilka rzeczy, tu coś dopiszą, tam usuną i to wszystko. Powiedz mi, czy z kodu w moim ostatnim poście zrobiłbyś kod w PHP? Jeśli tak to mam niespodziankę dla Ciebie. To jest kod w C++, gdzie n, s, tmp, A, tab, i, j zostały by zadeklarowane poza tym przeklejonym fragmentem. To co Ty wkleiłeś to na oko moim zdaniem algorytm rozwinięcia Laplace'a, bo widzę rekurencję w nim i liczenie wyznacznika w wyznaczniku z mnożeniem i dodawaniem. Algorytm liczący, ale makabrycznie długo dla dużych tablic. O ile by Ci pamięci starczyło by nie sypnął się winksmiley.jpg
A swoją drogą.. Przed chwilą spytałem wujka google i mi pokazał:
  1. /*Element maxymalny w wierszu*/
  2. max=M[0][0];
  3. for(j=0;j<n;j++)
  4. {if (M[0][j]>max) max=M[0][j];}
  5. /*Zamiana kolumn pierwszej z ta gdzie jest element maxymalny*/
  6. for (i=0; i<n; i++)
  7. {max=M[i][j];
  8. zm= M[i][0];
  9. M[i][0]=M[i][j];
  10. M[i][j]=zm;
  11. }
  12. /*Zerowanie do macierzy trojkatnej*/
  13. for( i=1; i<n; i++){
  14. for (j=0; j<n; j++){
  15. M[i][j]=M[i][j]-((M[i][0]/M[0][0])*M[0][j]);
  16. }
To sobie tylko do PHP przerób. Jeśli masz już macierz trójkątna to wyznacznik jest równy iloczynowi liczb na przekątnej, czyli masz wzór dodatkowy powiększony jeszcze o:
  1. $wyznacznik = 1;
  2. for($i=0, $i<$n; $i++)
  3. $wyznacznik *=M[i][i];
coco
moja przeróbka:
  1. <?
  2. $wym=2;
  3. $tablica=Array(Array(2,4),Array(1,1));
  4. $max=$tablica[0][0];
  5. for($j=0;$j<$wym;$j++){
  6. if ($tablica[0][$j]>$max) $max=$tablica[0][$j];
  7. }
  8. for ($i=0; $i<$wym; $i++)
  9. {
  10. $max=$tablica[$i][$j];
  11. $zm=$tablica[$i][0];
  12. $tablica[$i][0]=$tablica[$i][$j];
  13. $tablica[$i][$j]=$zm;
  14. }
  15. for($i=1; $i<$wym; $i++){
  16. for ($j=0; $j<$wym; $j++){
  17. $tablica[$i][$j]=$tablica[$i][$j]-(($tablica[$i][0]/$tablica[0][0])*$tablica[0][$j]);
  18. }
  19. $wyznacznik=1;
  20. for($i=0; $i<$wym; $i++){
  21. $wyznacznik *=$tablica[$i][$i];
  22. }
  23. }
  24. echo "$wyznacznik";
  25. ?>

z czego jest:
Warning: Division by zero in ......, oraz wyświetla niepoprawną wartość wyznacznika 0. To jakieś fatum sciana.gif . Nie widzę błędu ...
thek
Jeśli nie widzisz błędu to debuguj krok po kroku cały skrypt. Zobacz gdzie Ci wyskoczy to dzielenie przez zero. Może jakaś zmienna się nie inicjuje prawidłowo. W pętlach więc może sobie wyświetlaj co się dzieje. W ten sposób wykryjesz na jakim etapie błąd wyskakuje.
pheter
Trochę to tak napisane jak w szkole kazali (dawno temu) ale powinno działać (nie wiem na ile efektywnie).
  1. <?php
  2. // elementy tablicy podać w formacie:
  3. // a=a11,a12,...,a1n;a21,...,a2n;...;an1,an2,...ann
  4.  
  5. $a=kon($_GET['a']);
  6. if (spr($a)<>0) echo "Błędne parametry!".spr($a);
  7. else
  8. { echo "Macierz:<br><table>";
  9. $n=count($a);
  10. for ($i=0;$i<$n;$i++)
  11. { echo "<tr><td>|</td>";
  12. for ($j=0;$j<$n;$j++)
  13. { $t=$a[$i][$j];
  14. echo "<td align=\"right\">$t</td>";
  15. }
  16. echo "<td>|</td></tr>";
  17. }
  18. echo "</table>Wyznacznik = ".wyz($a);
  19. }
  20.  
  21. function kon($t)
  22. { $p=explode(";",$t);
  23. $r=array();
  24. $n=count($p);
  25. for ($i=0;$i<$n;$i++)
  26. $r[]=explode(",",$p[$i]);
  27. return $r;
  28. }
  29.  
  30. function spr($a)
  31. { $n=count($a);
  32. if ($n==0) return 1;
  33. for ($i=0;$i<$n;$i++)
  34. if (count($a[$i])==$n) for ($j=0;$j<$n;$j++) $a[$i][$j]=(int)($a[$i][$j]);
  35. else return 2;
  36. return 0;
  37. }
  38.  
  39. function wyz($a)
  40. { if (($n=count($a))==1) return $a[0][0];
  41. else
  42. { $w=0;
  43. $b=-1;
  44. for ($i=0;$i<$n;$i++) $w+=($b=-$b)*$a[0][$i]*wyz(dop($a,$i));
  45. return $w;
  46. }
  47. }
  48.  
  49. function dop($m,$k)
  50. { $a=array();
  51. $n=count($m);
  52. for ($i=1;$i<$n;$i++)
  53. { $a[$i-1]=array();
  54. for ($j=0;$j<$n;$j++) if ($j<>$k) $a[$i-1][]=$m[$i][$j];
  55. }
  56. return $a;
  57. }
  58.  
  59. ?>

Zaczynam się bawić w php i dlatego proszę bardziej doświadczonych o komentarz.
coco
Cytat(pheter @ 23.10.2009, 04:30:53 ) *
Trochę to tak napisane jak w szkole kazali (dawno temu) ale powinno działać (nie wiem na ile efektywnie).
  1. <?php
  2. // elementy tablicy podać w formacie:
  3. // a=a11,a12,...,a1n;a21,...,a2n;...;an1,an2,...ann
  4.  
  5. $a=kon($_GET['a']);
  6. if (spr($a)<>0) echo "Błędne parametry!".spr($a);
  7. else
  8. { echo "Macierz:<br><table>";
  9. $n=count($a);
  10. for ($i=0;$i<$n;$i++)
  11. { echo "<tr><td>|</td>";
  12. for ($j=0;$j<$n;$j++)
  13. { $t=$a[$i][$j];
  14. echo "<td align=\"right\">$t</td>";
  15. }
  16. echo "<td>|</td></tr>";
  17. }
  18. echo "</table>Wyznacznik = ".wyz($a);
  19. }
  20.  
  21. function kon($t)
  22. { $p=explode(";",$t);
  23. $r=array();
  24. $n=count($p);
  25. for ($i=0;$i<$n;$i++)
  26. $r[]=explode(",",$p[$i]);
  27. return $r;
  28. }
  29.  
  30. function spr($a)
  31. { $n=count($a);
  32. if ($n==0) return 1;
  33. for ($i=0;$i<$n;$i++)
  34. if (count($a[$i])==$n) for ($j=0;$j<$n;$j++) $a[$i][$j]=(int)($a[$i][$j]);
  35. else return 2;
  36. return 0;
  37. }
  38.  
  39. function wyz($a)
  40. { if (($n=count($a))==1) return $a[0][0];
  41. else
  42. { $w=0;
  43. $b=-1;
  44. for ($i=0;$i<$n;$i++) $w+=($b=-$b)*$a[0][$i]*wyz(dop($a,$i));
  45. return $w;
  46. }
  47. }
  48.  
  49. function dop($m,$k)
  50. { $a=array();
  51. $n=count($m);
  52. for ($i=1;$i<$n;$i++)
  53. { $a[$i-1]=array();
  54. for ($j=0;$j<$n;$j++) if ($j<>$k) $a[$i-1][]=$m[$i][$j];
  55. }
  56. return $a;
  57. }
  58.  
  59. ?>

Zaczynam się bawić w php i dlatego proszę bardziej doświadczonych o komentarz.

Działa. Zdecydowanie ładna sprawa. Dziękuję.
To jest wersja lo-fi głównej zawartości. Aby zobaczyć pełną wersję z większą zawartością, obrazkami i formatowaniem proszę kliknij tutaj.
Invision Power Board © 2001-2025 Invision Power Services, Inc.