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