357503523
18. Rozdział. Zanim wystartujemy
dopóki a>0 wykonuj;
podstaw za c reszto z dzielenia a przez b;
podstaw za b liczbę a;
podstaw za a liczbę c;
podstaw za res liczbę b;
rezultat: res.
Oczywiście Euklides nie proponował swojego algorytmu dokładnie w ten sposób (w miejsce funkcji i reszty z dzielenia stosowane były sukcesywne odejmowania), ale jego pomysł można zapisać w powyższy sposób bez szkody dla wyniku, który w każdym przypadku będzie taki sam. Nie jest to oczywiście jedyny algorytm, z którym mieliśmy w swoim życiu do czynienia. Każdy z nas z pewnością umie zaparzyć kawę:
• włączyć gaz;
• zagotować niezbędną ilość wody;
• wsypać zmieloną kawę do szklanki;
• zalać kawę wrzącą wodą;
• osłodzić do smaku:
• poczekać, aż odpowiednio naciągnie...
Powyższy przepis działa, ale zawiera kilka słabych punktów: co to znaczy „odpowiednia ilość wody"? Co dokładnie oznacza stwierdzenie „osłodzić do smaku"? Przepis przygotowania kawy ma cechy algorytmu (rozumianego w sensie zacytowanych wyżej definicji słownikowych), ale brak mu precyzji niezbędnej do wpisania go do jakiejś maszyny, tak aby w każdej sytuacji umiała ona sobie poradzić z poleceniem „przygotuj mi małą kawę". (Np. jak w praktyce określić warunek, że kawa "odpowiednio naciągnęła"?).
Jakie w związku z tym cechy powinny być przypisane algorytmowi rozumianemu w kontekście informatycznym? Dyskusję na ten temat można by prowadzić dość długo, ale przyjmując pewne uproszczenia można zadowolić się następującymi wymogami:
Każdy algorytm:
• posiada dane wejściowe (w ilości większej lub równej zero) pochodzące z dobrze zdefiniowanego zbioru (np. algorytm Euklidesa operuje na dwóch liczbach całkowitych);
• produkuje pewien wynik (niekoniecznie numeryczny);
• jest precyzyjnie zdefiniowany (każdy krok algorytmu musi być jednoznacznie określony);
Wyszukiwarka
Podobne podstrony:
ALG8 18 Rozdziali. Zanim wystartujemy dopóki a>0 wykonuj; podstaw za c resztę z dzielenia a prze
2012 10 06 43 18 Warunek konieczny i wystarczający * Zajście zdarzenia P pociągnie za sobą zajście
ALG0 20 Rozdział 1. Zanim wystartujemy (Na marginesie warto dodać, że przedsiębiorstwo Hollcritha
ALG2 22 Rozdział 1. Zanim wystartujemy programowania nic znikły bynajmniej z horyzontu: Dijkstra, H
ALG4 24 Rozdział 1. Zanim wystartujemy Aby zaradzić zaanonsowanym wyżej problemom, przyjęło się zwy
ALG6 26 RozdziaH. Zanim wystartujemy 1.5 metody niezmienników (zwanej niekiedy metodą Floyda). Mają
20 Rozdział 1. Zanim wystartujemy (Na marginesie warto dodać, że przedsiębiorstwo Holeritha
22_ Rozdział 1, Zanim wystartujemy programowania nic znikły bynajmniej z horyzontu; Dijkstra, Hoare,
Spis treści Moje dopiski K. Przedmowa... 9 Rozdziałl Zanim wystartujemy
Skan8 (2) 58 V ROZDZIALI wiecznej pary, natury i kultury, i podstawienia na to miejsce za pośrednic
więcej podobnych podstron