1
Temat XI.
Przykłady algorytmów klasycznych
1.
Algorytm Euklidesa (powtórzenie)
Program 1. Napisz program, który oblicza największy wspólny dzielnik (NWD)
program r11_z_1;
uses Crt;
var a, b : integer;
function NWD(x,y:integer):integer;
begin
while x<>y do
if x > y then x:=x-y
else y:=y-x;
NWD:=x;
end;
begin
ClrScr;
Write('Podaj a: '); Readln(a);
Write('Podaj b: '); Readln(b);
Writeln('Najwiekszy wspolny dzielnik liczb ',a,'
i ',b,' : ',NWD(a,b));
repeat until keypressed;
end.
Program 2. Napisz program, który skraca podany ułamek. (Patrz rozdział 7 zad.3.)
2.
Liczby Fibonacciego
Leonardo, syn Bonacciego, czyli Fibonacci (1170-1240), był wybitnym matematykiem, pochodzącym z Pizy. W jednym
ze swych dzieł, "Liber Abaci", uczony zajął się problemem... szybkości rozmnaŜania się królików. Przy załoŜeniu, Ŝe
początkowo mamy tylko jedną parę, króliki mogą się rozmnaŜać według następujących zasad:
- nowa para staje się płodna po miesiącu Ŝycia;
- kaŜda płodna para w ciągu miesiąca przysparza jednej pary nowych królików,
- króliki nigdy nie umierają.
Pytanie brzmi - ile będzie par królików po upływie k miesięcy?
≥
+
∈
=
−
−
3
}
2
,
1
{
1
2
1
n
dla
F
F
n
dla
F
n
n
n
Program 3. Napisz program, który oblicza kolejne liczby ciagu Fibonacciego.
program R11_z_3;
{$N+}
uses Crt;
var i, liczba :integer;
function Fib(n:integer):extended;
var wynik,f1, f2 : extended;
i : integer;
begin
if n<3 then Fib:=1
else begin
f1:=1;
f2:=1;
for i:=3 to n do
begin
wynik:=f1+f2;
f2:=f1;
f1:=wynik;
end;
Fib:=wynik;
end;
end;
begin
Clrscr;
Write('Podaj ktora liczbe ciagu Fibonacciego
chcesz obliczyc: ');
readln(liczba);
for i:=1 to liczba do WriteLn('F(',i,')=',Fib(i):5:0);
repeat until keypressed;
end.
2
3.
Schemat Hornera
Schemat Hornera jest algorytmem słuŜącym do szybkiego obliczania wartości wielomianu, a takŜe przelicza-
nia na postać dziesiętną liczb zapisanych w innym systemie liczbowym oraz szybkiego podnoszenia do potęgi.
RozwaŜmy wielomian drugiego stopnia:
W(x)= ax
2
+bx +c = (ax + b)x +c
Analogicznie wielomian trzeciego stopnia:
W(x)=ax
3
+ bx
2
+cx + d = ((ax +b)x +c)x + d
… i wielomian n-tego stopnia:
W
n
(x) = (((a
0
x + a
1
)x + a
2
)x + … + a
n-1
)x + a
n
program r11_z_4;
uses Crt;
var MojeWsp
: array [0..20] of real;
x,MAX_WSP : integer;
procedure WprowadzWsp(var w:array of real);
var i:integer;
begin
for i:=MAX_WSP downto 0 do
begin
Write('Podaj wspolczynnik nr ',i,': ');
ReadLn(w[i]);
end;
end;
procedure WypiszWielomian(var w:array of real);
var i:integer;
begin
for i:=MAX_WSP downto 1 do Write(w[i]:6:2,'*x^',i,' + ');
WriteLn(w[0]:6:2);
end;
function Horner(var w:array of real; x:real):real;
var i :integer;
wynik :real;
begin
wynik:=w[MAX_WSP];
for i:=MAX_WSP-1 downto 0 do
wynik:=w[i]+x*wynik;
Horner:=wynik;
end;
begin
ClrScr;
Write('Podaj ktorego stopnia wielomian chcesz liczyc: ');
readln(MAX_WSP);
Writeln('*** Wprowadzanie wspolczynnikow wielomianu ***');
WprowadzWsp(MojeWsp);
WypiszWielomian(MojeWsp);
Write('Podaj wartosc x: ');
ReadLn(x);
WriteLn('Wartosc wielomianu=',Horner(MojeWsp,x):8:2);
repeat until keypressed;
end.
3
Temat XII.
Algorytmy sortowania
1.
Sortowanie bąbelkowe
program r12_z_1;
uses crt;
var a: array [1..20] of integer;
n: integer;
procedure Czytaj(n:byte);
var i: byte;
begin
for i:=1 to n do begin
write('a[',i,'] = ');
Readln(a[i]);
end;
end;
procedure pisz(n:byte);
var i:byte;
begin
writeln;
for i:=1 to n do writeln('a[',i,'] = ',a[i]);
end;
procedure zamien(var a,b:integer);
var t: integer;
begin
t:=a;
a:=b;
b:=t;
end;
procedure sortuj_b(n:byte);
var i:byte;
zamiana: boolean;
begin
repeat
zamiana:=false;
for i:=1 to n-1 do
if a[i]<a[i+1] then
begin
zamien(a[i],a[i+1]);
zamiana:=true;
end;
until zamiana=false;
end;
begin
clrscr;
write('Podaj liczbe elementow, n: ');
readln(n);
czytaj(n);
sortuj_b(n);
writeln;
pisz(n);
repeat until keypressed;
end.
2.
Sortowanie przez wybieranie
program r12_z_2;
uses crt;
var a: array [1..20] of integer;
n: integer;
procedure Czytaj(n:byte);
procedure pisz(n:byte);
procedure przez_wybieranie(n:byte);
var i,j,temp,min : integer;
begin
for i:=1 to n-1 do
begin
min:=i;
for j:=i+1 to n do
if a[j]<a[min] then min:=j;
temp:=a[i];
a[i]:=a[min];
a[min]:=temp;
end;
end;
begin
clrscr;
write('Podaj liczbe elementow, n: ');
readln(n);
czytaj(n);
przez_wybieranie(n);
writeln;
pisz(n);
repeat until keypressed;
end.
4
Temat XIII.
Rekurencyjny sposób realizacji algorytmów
1.
Algorytm obliczania silni
Definicja rekurencyjna obliczania silni dla liczby naturalnej n:
>
⋅
−
=
=
0
)!
1
(
0
1
!
n
dla
n
n
n
dla
n
program r13_z_1;
uses Crt;
var i:integer;
function SilniaRek(n:integer): LongInt;
begin
if n=0 then SilniaRek:=1
else SilniaRek:=n*SilniaRek(n-1);
end;
begin
ClrScr;
for i:=0 to 12 do WriteLn(i,'! = ',SilniaRek(i));
(* Powyzej 12 nastepuje przekroczenie zakresu longint *)
repeat until keypressed;
end.
2.
Algorytm Euklidesa
program r13_z_2;
uses Crt;
var a,b:word;
function EuklidesRek(a,b:word):word;
begin
if a=b then EuklidesRek:=a
else if a>b then EuklidesRek:=EuklidesRek(a-b,a)
else EuklidesRek:=EuklidesRek(a,b-a);
end;
begin
Write('Podaj a: '); ReadLn(a);
Write('Podaj b: '); Readln(b);
WriteLn('NWD = ',EuklidesRek(a,b));
repeat until keypressed;
end.
3.
Liczby Fibonacciego
program r13_z_3;
uses Crt;
var i:word;
function Fib(n:word):longint;
begin
if n<3 then Fib:=1
else Fib:=Fib(n-2)+Fib(n-1);
end;
begin
for i:=1 to 40 do WriteLn('F(',i,')=',Fib(i));
repeat until keypressed;
end.
Obliczenia dla n = 4
1.
4! = 3!
⋅
4
2.
3! = 2!
⋅
3
3.
2! = 1!
⋅
2
4.
1! = 0!
⋅
1
5
4.
Schemat Hornera
Definicja rekurencyjna funkcji obliczającej wartość wielomianu n-tego stopnia ma postać:
≥
+
=
=
−
0
)
(
0
)
(
1
0
n
dla
a
x
x
W
n
dla
a
x
W
n
n
n
program r13_z_4; {rozwiązanie Migra}
{$N+}
Const MAX_WSP=5;
Type TWsp=array [0..MAX_WSP] of extended;
var MojeWsp :TWsp;
x
:real;
procedure WprowadzWsp(var w:TWsp);
var i:integer;
begin
for i:=MAX_WSP downto 0 do
begin
Write('Podaj wspolczynnik nr ',i,': ');
ReadLn(w[i]);
end;
end;
procedure WypiszWielomian(var w:TWsp);
var i:integer;
begin
for i:=MAX_WSP downto 1 do
if w[i]<>0 then Write(w[i]:6:2,'*x^',i,' + ');
WriteLn(w[0]:6:2);
end;
procedure LosujWsp(var w:TWsp);
var i:integer;
begin
for i:=MAX_WSP downto 0 do w[i]:=Random*40-20;
end; (* LosujWsp *)
function Horner(var w:TWsp; n:integer; x:real):real;
var wynik:real;
begin
if n=MAX_WSP then Horner:=w[MAX_WSP]
else Horner:=w[n]+x*Horner(w,n+1,x);
end;
function ObliczWielomian(var w:TWsp; x:real):real;
begin
ObliczWielomian:=Horner(w,0,x);
end;
begin
WriteLn('*** Wprowadzanie wspolczynnikow wielomianu ***');
WprowadzWsp(MojeWsp);
WypiszWielomian(MojeWsp);
WriteLn('Podaj wartosc x: ');
ReadLn(x);
WriteLn('Wartosc wielomianu=',ObliczWielomian(MojeWsp,x):8:2);
end.
6
Temat XIV.
Przetwarzanie plików
Ogólny schemat operacji plikowej w Pascalu obejmuje cztery etapy:
I.
Skojarzenie zmiennej plikowej z odpowiednim plikiem (znajdującym się na dysku lub nowo tworzo-
nym).
II.
Otwarcie pliku, przygotowujące go do zapisywania lub odczytywania informacji.
III.
Jedna lub więcej operacji zapisu lub odczytu danych.
IV.
Zamknięcie pliku i przerwanie skojarzenia pomiędzy zmienną plikową i plikiem.
Zmienną plikową deklaruje się w sposób następujący:
nazwa : text
{ dla pliku tekstowego }
nazwa : file of typ
{ dla pliku elementowego }
Plik tekstowy zawiera on taki sam tekst, jak ten wpisywany z klawiatury i wyświetlany na monitorze. Dane
zapisane w postaci czytelnej dla człowieka i podzielone na wiersze zakończone znakami końca wiersza.
Plik elementowy składa się z jednakowych elementów tego samego typu (nieco podobnie do tablicy) zapisa-
nych w takiej samej postaci, w jakiej przechowywane są w pamięci.
var
plik_1 : text;
{ plik tekstowy }
plik_2 : file of real;
{ plik liczb rzeczywistych }
Aby skojarzyć zmienną plikową z fizycznym plikiem znajdującym się na dysku uŜyjemy procedury assign:
assign(zmienna_plikowa, nazwa-pliku)
assign(plik_1, 'c:\tp\dane.txt')
Podstawowymi procedurami uŜywanymi w Pascalu do otwierania plików są reset i rewrite:
reset(zmienna-plikowa)
rewrite(zmienna-plikowa)
Procedura reset umoŜliwia otwarcie juŜ istniejącego pliku, ustawiając tzw. wskaźnik plikowy na jego począt-
ku. W przypadku, gdy otwierany plik nie istnieje, wywołanie procedury reset kończy się błędem wykonania.
Procedura rewrite umoŜliwia otwarcie pliku niezaleŜnie od tego, czy istniał on poprzednio: jeśli nie - tworzy
ona nowy plik o danej nazwie, zaś jeśli tak - zeruje długość istniejącego pliku i ustawia wskaźnik plikowy na
jego początku (czego efektem jest utracenie wszystkich danych zawartych w pliku).
Dla plików tekstowych istnieje trzecia metoda otwarcia – słuŜąca do dopisywania na jego końcu nowych
danych – append.
append(zmienna-plikowa)
Do wymiany danych pomiędzy programem a plikiem słuŜą znane nam juŜ procedury read (odczyt) i write
(zapis).Aby zapisać do pliku niezbędne jest podanie dodatkowego argumentu określającego plik, z/do którego
informacja ma być odczytana lub zapisana.
read(zmienna-plikowa, lista-elementów)
write(zmienna-plikowa, lista-elementów)
Po wykonaniu Ŝądanych operacji zapisu i odczytu danych plik naleŜy zamknąć. Realizuje je procedura close:
close(zmienna-plikowa)
Do sprawdzania i zmiany bieŜącego połoŜenia w pliku słuŜy kilka uŜytecznych procedur:
Eoln(zmienna_plikowa) : boolean; – True jeśli jesteśmy na końcu wiersza (
tylko pliki tekstowe
)
Eof(zmienna_plikowa) : boolean; – True jeśli jesteśmy na końcu pliku
Dla plików elementowych:
Seek(zmienna_plikowa, pozycja); – ustawia wskaźnik plikowy na Ŝądanej pozycji.
FilePos(zmienna_plikowa) : LongInt; – zwraca bieŜącą pozycje w pliku.
FileSize(zmienna_plikowa) : LongInt; – zwraca liczbę elementów w pliku.
7
Zapamiętaj:
1)
Do trwałego przechowywania informacji w systemie komputerowym słuŜą pliki.
2)
Turbo Pascal umoŜliwia obsługę plików elementowych, tekstowych oraz amorficznych.
3)
Pliki elementowe składają się z elementów tego samego typu (prostego lub strukturalnego). Liczba ele-
mentów jest zawsze całkowita.
4)
Pliki tekstowe zawierają dane reprezentowane w postaci wierszy tekstu. MoŜna ich uŜywać do przecho-
wywania danych róŜnych typów.
5)
Pliki elementowe umoŜliwiają dostęp swobodny, natomiast pliki tekstowe pozwalają wyłącznie na dostęp
sekwencyjny.
6)
Plik reprezentowany jest w programie przez zmienną plikową, którą naleŜy skojarzyć z fizycznym plikiem
za pomocą procedury assign.
7)
Operacje na zawartości pliku muszą być poprzedzone jego otwarciem (reset lub rewrite) i zakończone
zamknięciem (close).
8)
Swobodny dostęp do elementów pliku umoŜliwia procedura Seek, ustawiająca wskaźnik plikowy na zada-
nej pozycji.
9)
Mechanizmy obsługi plików tekstowych umoŜliwiają przesyłanie danych nie tylko na dysk, lecz równieŜ z
i do standardowych urządzeń wejścia-wyjścia systemu operacyjnego.
Program 1. Napisz program, który wprowadza do pliku tekst, aŜ do napotkania pustego wiersza.
program r11_z_1;
uses Crt;
const NazwaPliku = 'WPROW.TXT';
var F
: Text;
Wiersz : String;
begin
ClrScr;
Assign(F, NazwaPliku);
Rewrite(F);
repeat
{ czytaj kolejne wiersze i wpisuj je do pliku }
readln(Wiersz);
if Wiersz <> '' then writeln(F, Wiersz);
until Wiersz ='';
Close(F);
{ ZAMKNIJ PLIK, jeśli nie chcesz stracić danych! }
writeln ('Zapisywanie do pliku zakończono.');
repeat until keypressed;
end.
Program 2. Napisz program, który wypisze na ekranie tekst zapisany poprzednio w pliku wprow.txt.
program r14_z_2;
uses Crt;
const NazwaPliku = 'WPROW.TXT';
var F
: Text;
Wiersz
: String;
begin
ClrScr;
Assign(F, NazwaPliku);
Reset(F);
while not Eof(F) do
{ czytaj i wypisuj kolejne wiersze az do konca pliku }
begin
readln(F, Wiersz);
writeln(Wiersz)
end;
Close (F);
repeat until keypressed;
end.
8
Program 3. Napisz program, który wprowadza do pliku wszystkie znaki aŜ do napotkania klawisza ESC
program r14_z_3;
uses CRT;
const nazwapliku = 'plik_3.txt';
var f: file of char;
c: char;
begin
ClrScr;
Assign(f,nazwapliku);
{ Skojarzenie zmiennej plikowej z plikiem o podanej nazwie }
ReWrite(f);
{ Otwarcie pliku do zapisu }
repeat
c := ReadKey;
if c <> #27 then begin
Write(c);
{ Wypisanie znaku na ekranie }
Write(f,c);
{ Zapisanie znaku klawisza do pliku }
end;
until c = #27;
Close(f);
{ Zamkniecie pliku }
Writeln;
Writeln('Zapisywanie do pliku zakończone');
repeat until keypressed;
end.
Program 3. Napisz program, który sprawdza czy plik o podanej nazwie istnieje.
program r14_z_3;
uses Crt;
var nazwa :string;
function Istnieje(Plik : String) : Boolean; {Funkcja sprawdza, czy plik o danej nazwie istnieje.}
var F : Text;
begin
Assign(F,Plik);
{$I-} Reset (F); {$I+} { wyłącz kontrole we-wy i spróbuj otworzyć plik }
if IOResult = 0 then
begin
Close (F);
Istnieje := True;
end
else Istnieje := False
end;
begin
ClrScr;
write('Podaj nazwe pliku: ');
readln(nazwa);
if Istnieje(nazwa) then writeln('Podany plik istnieje')
else writeln('Podany plik nie istnieje');
repeat until keypressed;
end.
9
Program 3. Napisz program, który zapisuje i wyświetla z pliku losowe liczby oraz wyświetla największą.
program r14_z_3;
uses Crt;
const NazwaPliku = 'losowe.txt';
var F : file of Integer;
procedure wprowadz(NPliku :string);
var i,temp:integer;
begin
Assign(F, NPliku);
ReWrite(F);
Randomize;
for i:=1 to 20 do
begin
temp:=random(100);
write(F,temp);
end;
close(f)
end;
procedure wyswietl(NPliku:string);
var temp : integer;
begin
Assign(F, NPliku);
Reset(F);
while not EOF(f) do
begin
Read(F,temp);
Write(temp,', ');
end;
close(F);
end;
function max(NPliku:string):integer;
var temp,w_max : integer;
begin
Assign(F, NPliku);
Reset(F);
read(F,temp);
w_max:=temp;
while not EOF(f) do
begin
Read(F,temp);
if temp>w_max
then w_max:=temp;
end;
close(F);
max:=w_max;
end;
begin
ClrScr;
wprowadz(nazwaPliku);
wyswietl(nazwaPliku);
writeln;
writeln('Wartosc maksymalna to:' ,
max(nazwaPliku));
writeln;
writeln ('... nacisnij dowolny klawisz.');
repeat until keypressed;
end.
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _ _ _
W przykładach wykorzystałem materiały z:
−
ksiąŜki TURBO Pascal 5.5 Andrzeja Marciniaka
−
podręczników GraŜyny Koby Informatyka cz. I i Informatyka cz. II
−
z serwisu: http://helion.pl/online/turbo-pasca