algorytm.org

Implementacja w Perl

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Szukanie połówkowe (binarne) - Implementacja w Perl
Ocena użytkownikóww: *****  / 1
SłabyŚwietny
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";
}
Dodaj komentarz