http://gorbem.hu/PHP.php

Véletlen latin négyzet

 

Feladat: készítsünk véletlen latin négyzetet előállító oldalt php segítségével. A négyzet oldalát egy beviteli mező segítségével meg lehessen adni. (Véletlen latin négyzet: olyan N x N-es négyzetes táblázat, melyben N féle elemből N2 elem helyezkedik el úgy, hogy egyetlen sorban és oszlopban sincs két ugyanolyan elem. Ebben a programban az elemek 1-től N-ig terjedő egész számok.) Egy ilyen 5 x 5-ös véletlen latin négyzet látható a következő screenshot-on:

 

 

 

A számokat egy $tomb nevű kétdimenziós tömbben tároljuk. A kiindulási állapotban minden sorba 1-től N-ig növekedő sorrendben beírjuk a számokat, ahogy azt a következő screenshot-on láthatjuk:

 

 

 

            Ha ezek után csak azonos sorokban lévő két elemet engedünk cserélgetni, akkor csak az oszlopok szerinti ütközést kell ellenőrizni. Az ütközési számot a teljes táblázaton végigfutó egymásba ágyazott kettős for ciklus számolja. A rendezés az ütközésmentesítő algoritmus segítségével történik.

 

A latin négyzet képernyőn való megjelenítésére, az elemek cseréjére és az ütközési szám meghatározására függvényeket írtunk. A rendezés az Rendezés/Újra feliratú gomb megnyomásra indul, melyben először alapértelmezés szerinti helyezzük el a számokat, majd 200-szor véletlen cseréket hajtunk végre (egy soron belüli elemek között). Ezek után ütközésmentesítéssel addig rendezzük a táblázatot, amíg az ütközési szám nulla nem lesz, végül a helyes elhelyezést megjelenítjük. A rendezés egy kicsit időigényes, ezért az oldal nagyságát 10-ben maximalizáltuk.

 

http://gorbem.hu/PH/Latin.php

 

<html>

<head>

<title>Véletlen latin négyzet</title>

</head>

<body>

<form name="" action="Latin.htm" method="POST">

<input type="submit" name="vissza" value="Vissza" />

</form>

<center>

<h1><u>Véletlen latin négyzet</u></h1>

<form name="" action="Latin.php" method="POST">

<font size="4"><b>Kérem a négyzet oldalát (max. 10): &nbsp; </b>

<?php

            print "<input type=\"text\" name=\"meret\" size=\"1\" ";

     

            if ( isset($_POST['meret']) ){

                  $n = $_POST['meret'];

                  if ( $n>10 ){

                        $n = 10;

                  }

                  print "value=\"$n\" ";

            }

            else{

                  print "value=\"5\" ";

            }

            print " /> &nbsp; ";

?>

<input type="submit" name="rendez" value="Rendez/Újra" /> &nbsp;

</font>

</form>

<?php

function csere($tomb,$s,$o1,$o2){

            $p = $tomb[$s][$o1];

            $tomb[$s][$o1] = $tomb[$s][$o2];

            $tomb[$s][$o2] = $p;

            return $tomb;

}

function utkszam($tomb,$s,$o,$n){

            $utsz = 0;

            for ($i=0; $i<$n; $i++){

                  if (($i !== $s) && ($tomb[$i][$o] == $tomb[$s][$o])){

                        $utsz++;

                  }

            }

            return $utsz;

}

function utkozes($tomb,$n){

            $utkoz = 0;

            for ($i=0; $i<$n; $i++){

                  for ($j=0; $j<$n; $j++){

                        $utkoz = $utkoz+utkszam($tomb,$i,$j,$n);

                  }

            }

            return $utkoz;

}

function kepre($tomb,$n){

            print "<table border=\"1\" cellpadding=\"5\" cellspacing=\"0\" >\n";

            for ($i=0; $i<$n; $i++){

                  print "<tr>\n";

                  for ($j=0; $j<$n; $j++){

                        print "\t<td align=\"center\" width=\"40\"><font size=\"6\">";

                        print $tomb[$i][$j];

                        print "</font>";

                        print "</td>\n";

                  }

                  print "</tr>\n";

            }

            print "</table>\n";

            return true;

      }

     

      if ( isset($_POST['rendez']) && isset($_POST['meret']) && $_POST['meret'] !== 0 ){

            $n = $_POST['meret'];

            if ( $n>10 ){

                  $n = 10;

            }

            $tomb = array( array() );

            //tömbfeltöltés

            for ($i=1; $i<=$n; $i++){

                  for ($j=1; $j<=$n; $j++){

                        $tomb[$i-1][$j-1] = $j;

                  }

            }

            //keverés

            for ($i= 0; $i<200*$n; $i++){

                  $s = rand(0,$n-1);

                  $o1 = rand(0,$n-1);

                  $o2 = rand(0,$n-1);

                  $tomb = csere($tomb,$s,$o1,$o2);

            }

            //rendezés ütközésmentesítő algoritmussal

            $ut = utkozes($tomb,$n);

            while ($ut !== 0){

                  $sz = 0;

                  while ($sz == 0){

                        $s = rand(0,$n-1);

                        $o1 = rand(0,$n-1);

                        $sz = utkszam($tomb,$s,$o1,$n);

                  }

                  $o2 = rand(0,$n-1);

                  $el = utkozes($tomb,$n);

                  $tomb = csere($tomb,$s,$o1,$o2);

                  $ut = utkozes($tomb,$n);

                  if ($ut>$el){

                        $tomb = csere($tomb,$s,$o1,$o2);

                        $ut = utkozes($tomb,$n);

                  }

            }

            kepre($tomb,$n);

      }

      if ( !isset($_POST['rendez']) ){

            $n = 5;

            $tomb = array( array() );

            //tömbfeltöltés

            for ($i=1; $i<=$n; $i++){

                  for ($j=1; $j<=$n; $j++){

                        $tomb[$i-1][$j-1] = $j;

                  }

            }

            kepre($tomb,$n);

      }

?>

</center>

</body>

</html>