1907967367

<6>

Informatyka +

1 WPROWADZENIE

Komputery nadal - jak kiedyś - służą również do wykonywania różnych obliczeń. Kurs jest poświęcony m.in. algorytmom: wyznaczania dziesiętnej i binarnej reprezentacji liczb, obliczania wartości wielomianu, największego wspólnego dzielnika dwóch liczb (algorytm Euklidesa) oraz wartości potęgi. Motywacją dla wprowadzenia tych algorytmów jest chęć objaśnienia metody szyfrowania informacji z kluczem publicznym RSA, powszechnie stosowanej w kryptografii komputerowej.

Część praktyczna zajęć jest poświęcona wprowadzeniu podstawowych instrukcji języka programowania (ite-racyjnych i warunkowych oraz procedury i funkcji niestandardowej), wystarczających do zaprogramowania i uruchomienia komputerowych realizacji omówionych algorytmów, język programowania służy głównie do zapisywania i testowania rozwiązań rozważanych problemów, a nie jest celem zajęć samym w sobie. Przytoczono ciekawe przykłady zastosowań omawianych zagadnień.

W drugiej części kursu są przedstawione wybrane techniki rozwiązywania problemów za pomocą komputera, m.in. podejście zachłanne (do wydawania reszty), przeszukiwanie z nawrotami (do ustawiania hetmanów na szachownicy) i rekurencja w realizacji wybranych algorytmów. Zajęcia praktyczne będą poświęcone komputerowej realizacji wybranych technik algorytmicznych na odpowiednio dobranych przykładach problemów.

Rozważania ogólne na temat algorytmiki, algorytmicznego myślenia i rozwiązywania problemów z pomocą komputerów są zamieszczone w Dodatku (rozdz. 10). Materiał tam zawarty może być dobrym podsumowaniem zajęć.

jako literaturę rozszerzającą prowadzone tutaj rozważania polecamy podręczniki [2], a zwłaszcza książki [5] i [6],

2 WARM-UP- ROZGRZEWKA

W tym rozdziale, naszym celem jest uruchomienie pierwszego programu. A zatem. Ci uczniowie, którzy mają już pewne doświadczenie w programowaniu, mogą go pominąć, zachęcamy ich jednak do szybkiego zapoznania się z zawartym tutaj materiałem.

Zacznijmy od bardzo prostego problemu. Każdy problem, który będziemy rozwiązywać na tych zajęciach, będzie opisany swoją nazwą oraz wyszczególnieniem danych i wyników. Taki opis problemu nazywa się specyfikacją - patrz rozdz. 10. A więc nasz problem ma postać:

Problem. Pole trójkąta

Dane:    a, b,c- trzy dodatnie liczby.

Wynik:    S - pole trójkąta, którego boki mają długości a.bic.

jeśli ten problem ma rozwiązać za nas komputer, to musimy go poinformować o danych, czyli o trzech liczbach, oraz, co ma być wynikiem, czyli jak pole trójkąta zależy od długości jego boków - posłużymy się tutaj wzorem Herona. Te czynności zapiszemy jako nasz pierwszy algorytm w postaci listy kroków¹, a powyższą specyfikację problemu przyjmiemy za specyfikację tego, co ma wykonać algorytm a później program.

Algorytm. Pole trójkąta

Dane:    a,b,c- trzy dodatnie liczby.

Wynik: S - pole trójkąta, którego boki mają długości a.bic.

Krok 1. Wprowadź trzy liczby: a, b, c.

Krok 2. Oblicz połowę długości obwodu trójkąta: p = (o + b + c)/2.

Krok 3. Oblicz pole trójkąta według wzoru:

ie również w postaci schematów blokowych. Przykładowy schemat