Ero sivun ”Rekursio” versioiden välillä
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
HTu (keskustelu | muokkaukset) p →Hanoin torni: ehkä se on kuitenkin skripti |
HTu (keskustelu | muokkaukset) |
||
Rivi 54:
}
</source>
==Labyrintti==
Kaksiulotteisen labyrintin polun selvittäminen on yksinkertaista ratkaista rekursiolla. Ajatellaan vaikkapa seuraavaa sokkeloa:
<pre>
Alku -> XXXXX..XXX
.X..X..X..
.X..X.XXX.
.X..X.X.X.
XX..XXX.XX
X..XX.X..X
X.....XX.X
XXXXX.X...
X..XX.XX..
XXXX...XXX <- Loppu
</pre>
Seuraava Perl-skripti ratkaisee polun koordinaatit:
<source lang="perl">
#!/usr/bin/perl
#
@laby = (
[1,1,1,1,1,0,0,1,1,1],
[0,1,0,0,1,0,0,1,0,0],
[0,1,0,0,1,0,1,1,1,0],
[0,1,0,0,1,0,1,0,1,0],
[1,1,0,0,1,1,1,0,1,1],
[1,0,0,1,1,0,1,0,0,1],
[1,0,0,0,0,0,1,1,0,1],
[1,1,1,1,1,0,1,0,0,0],
[1,0,0,1,1,0,1,1,0,0],
[1,1,1,1,0,0,0,1,1,1]);
@polku = ();
sub minotaurus($$)
{
if($_[0]<0 or $_[0]>9 or $_[1]<0 or $_[1]>9)
{
return 0;
}
elsif($laby[$_[0]][$_[1]] != 1)
{
return 0;
}
else
{
$laby[$_[0]][$_[1]] = 2;
if($_[0] == 9 and $_[1] == 9)
{
unshift @polku, "-> ($_[1],$_[0])";
return 1;
}
if( minotaurus($_[0]+1, $_[1])
or minotaurus($_[0]-1, $_[1])
or minotaurus($_[0], $_[1]+1)
or minotaurus($_[0], $_[1]-1))
{
unshift @polku, "-> ($_[1],$_[0])";
return 1;
}
return 0;
}
}
minotaurus 0, 0;
$polku[0] =~ s/^-> // if defined $polku[0];
print "@polku\n";
</source>
Ajattaessa tulostuu: (0,0) -> (1,0) -> (2,0) -> (3,0) -> (4,0) -> (4,1) -> (4,2) -> (4,3) -> (4,4) -> (5,4) -> (6,4) -> (6,5) -> (6,6) -> (6,7) -> (6,8) -> (7,8) -> (7,9) -> (8,9) -> (9,9).
{{tynkä/Matematiikka}}
| |||