Nadesłany przez Dominik Goździuk, 28 lutego 2012 19:46
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.Pobierz pełne rozwiązanie.
szukanie_polowkowe_1_pl.pl:
#! /usr/bin/perl #Szukanie elementu w tablicy metoda bisekcji (metoda polowkowa) #Dominik Gozdziuk #www.algorytm.org #Procedura sortujaca tablice podana jako parametr sub sort { for ($i = 0; $i <= $#_; $i++) { $min = $i; for ($j = $i+1; $j <= $#_; $j++) { if ($_[$j] < $_[$min]) { $min = $j; } } $tmp = $_[$i]; $_[$i] = $_[$min]; $_[$min] = $tmp; } } @tab = (45,24,56,43,78,67,25,7,58,95,69,49,32); #Wywolanie procedury sort &sort(@tab); print "Tablica posortowana: "; #Wyswietlenie tablicy foreach $zmienna (@tab) { print "$zmienna "; } #Pobranie szukanego elementu print "\nWprowadz szukany element: "; $szukana = <STDIN>; chomp($szukana); $p = 0; #indeks pierwszego elementu tablicy $k = $#tab; #indeks ostatniego elementu tablicy $ok = 0; #zmienna pomocnicza while ($p <= $k) { $s = ($p+$k)/2; $s = int($s); # Wyciagamy czesc calkowita if ($tab[$s] == $szukana) { $ok = 1; $p = $k+1; #Zmieniamy p aby zakonczyc petle } elsif ($tab[$s] > $szukana) { #Szukana jest mniejsza, zawezamy obszar poszukiwan $k = $s-1; #Zmieniamy k } else { # Szukana jest wieksza $p = $s+1; #Zmieniamy p } } #Wyswietlamy wynik if ($ok == 1) { print "\nSzukany element znajduje sie w tablicy\n"; } else { print "\nSzukany element nie znajduje sie w tablicy\n"; }