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.
<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): </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 " />
";
?>
<input type="submit" name="rendez" value="Rendez/Újra" />
</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>