MINISTERUL ÎNVĂŢĂMÂNTULUI
LICEUL TEORETIC "NICOLAE TITULESCU"
ATESTAT PROFESIONAL LA
INFORMATICĂ
CUPRINS
Capitolul I Elemente de baza ale limbajului Pascal...............3
Capitolul II Cerintele problemei............8
Capitolul III Prezentarea programului...........8
Capitolul IV Realizarea programului............14
Bibliografie.................30
Capitalol I
Elemente de baza ale limbajului Pascal
Evolutia limbajelor de programare cunoaste 3 mari perioade distincte de timp si anume: anii 1950-1959, 1960-1969, dupa 1970.
Anii `50 reprezinta etapa de pionierat în domeniul programarii calculatoarelor. În aceasta perioada s-a cristalizat notiunea de program. Initial, programele erau scrise în cod masina (instructiunile, datele de intrare-iesire, formate din succesiuni de 0 si 1, asa cum, de fapt, prelucreaza orice calculator din lume). Datorita acestui fapt, scrierea programelor, introducerea datelor, erau activitati deosebit de migaloase si putin productive. Un pas important în evolutie este dat de aparitia limbajelor de asamblare. Acestea folosesc pentru fiecare instructiune în cod masina o abreviere din limba engleza ce sintetizeaza efectul instructiunii respective. Desi mult usurata, activitatea de programare într-un limbaj de asamblare ramâne dificila. Cu toate acestea, si astazi limbajele de asamblare sunt utilizate datorita unor avantaje cum ar f 22522r178w i: posibilitatea scrierii unor programe specifice calculatorului pe care se ruleaza un anumit program (deci cu mare viteza de executie), posibilitatea scrierii unor secvente de program care nu se pot scrie într-un limbaj evoluat (din lipsa unor instructiuni specifice).
În aceasta perioada apar si limbajele de nivel înalt (FORTRAN, COBOL). De aceasta data, scrierea programelor se face cu ajutorul unor expresii din limba engleza (desi extrem de restrictive). De asemenea, formulele care se solicita pentru calculul unor expresii sunt asemanatoare formulelor matematice. Un mare avantaj al limbajelor de nivel înalt îl constituie portabilitatea programelor scrise cu ajutorul lor (posibilitatea ca un program scris sa poata fi rulat pe diverse tipuri de calculatoare).
În anii `60 se dezvolta cu precadere aparatul matematic necesar crearii si utilizarii limbajelor de programare. Astfel, regulile de scriere ale programelor în limbajele respective sunt formalizate matematic. De asemenea, apare conceptul de recusivitate în programare. Pentru prima data apare notiunea de alocare dinamica a memoriei (alocarea spatiului de memorie pentru diverse variabile se face în timpul executiei programului, atunci când este cazul, si tot în acest timp se poate sterge un spatiu alocat, când nu mai este necesar). Toate acestea apar pentru prima data în limbajul ALGOL. Acest limbaj a avut un rol fundamental în dezvoltarea ulterioara a informaticii.
La începutul anilor `70 a aparut programarea structurata (initiatorii ei fiind E. W. Dijkstra si C. A. Hoare). Pentru prima data apar metode standardizate de elaborare a programelor. Redactarea oricarui program se poate face utilizând câteva structuri simple (secventiala, alternativa, repetitiva). O problema complexa se descompune în subprobleme, care apoi la rândul lor se descompun din nou, pâna când sunt suficient de simple pentru a putea fi transpuse în programe.
Limbajul Pascal a aparut la începutul anilor 1970 si a fost elaborat de matematicianul N. Wirth. Initial, limbajul a fost conceput pentru predarea sistematica a disciplinei de programare a calculatoarelor (structurile clasice din programarea structurata au fost transformate în instructiuni). Cu timpul, limbajul a început sa fie folosit si în activitatea practica de programare a calculatoarelor. Un rol fundamental pentru aceasta l-a avut firma americana Borland, care a implementat o varianta numita TURBO-PASCAL, care pe lânga instructiunile clasice ale limbajului contine si multe altele. Un mare avantaj al acestui limbaj este acela ca utilizatorul are posibilitatea sa-si declare propriile tipuri de date. Ultimele versiuni ale limbajului permit si realizarea programari pe obiecte.
End.
Acesta este un program care se poate rula. Efectul sau este nul. Nu citeste, nu scrie, nu efectueaza nici un calcul. Totusi din analiza acestuia rezulta urmatoarele:
Orice program începe printr-un cuvânt numit "program" care este urmat de numele programului si de semnul " ; "
Orice program contine cel putin o data cuvintele BEGIN si END;
Orice program se termina prin punct.
Orice cuvânt al programului poate fi scris cu litere mari sau mici. În versiunea Turbo, prima linie poate sa lipseasca. Plasarea cuvintelor pe linie si numarul de spatii dintre ele sunt la alegerea programatorului (putem scrie întreg programul pe o singura linie însa este bine ca programul sa fie scris în asa fel încât sa fie înteles).
Un program scris în Pascal, oricât de complex ar fi el, are structura urmatoare:
Program nume;
Definitii de constante;
Definitii de tipuri;
Declaratii de variabile;
Declaratii de proceduri si functii;
Begin
Instructiuni
End.
Nu este obligatoriu ca într-un program sa figureze toate acestea, dar daca figureaza trebuie sa apara în aceasta ordine.
Vocabularul oricarui limbaj este format din:
Setul de caractere; reprezinta ansamblul de caractere cu ajutorul carora se poate realiza un program Pascal (literele mari si mici ale alfabetului, cifrele sistemului de numeratie în baza 10 si caractere speciale).
Identificatori; acestia sunt o succesiune de litere, cifre sau caracterul special "_" din care prima trebuie sa fie litera. Cu ajutorul identificatorilor se asociaza nume constantelor, variabilelor, procedurilor. O categorie speciala de identificatori este data de cuvintele cheie ale limbajului. Acestea sunt: AND, ARRAY, BEGIN, CASE, CONST, DIV, DO, DOWNTO, ELSE, END, FILE, FOR, FUNCTION, GOTO, IF, IN, LABEL, MOD, NILL, NOT, PROCEDURE, PROGRAM, RECORD, REPEAT, SET, OF, OR, ORIGIN, OTHERWISE, PACKED, THEN, TO, TYPE, UNTIL, VAR, WHILE, WITH.
Separatori;
Comentarii; acestea pot fi scrise în doua feluri: între acolade sau între paranteze rotunde urmate de "*".
Capitolul II
Cerintele problemei
Sa se realizeze un program care sa genereze toate permutarile unei multimi de forma si toate aranjamentele de " n " elemente luate câte " p ". Valorile " n " si " p " se vor citi de la tastatura.
Capitolul III
Prezentatrea Programului
Pentru a realiza generari de permutari sau aranjamente cea mai la îndemna metoda este TEHNICA BACKTRACKING. Aceasta tehnica se foloseste în cazul problemelor care îndeplinesc simultan urmatoarele probleme:
Solutia lor poate fi pusa sub forma unui vector S=x1,x2,.xn, cu x1 apartinând lui A1; x2 apartinând lui A2;
Multimile A1, A2,.,An sunt multimi finite, iar elementele lor se considera ca se afla într-o relatie de ordine bine stabilita;
Tehnica Backtracking are la baza un principiu extrem de simplu:
se construeiste solutia pas cu pas;
daca se constata ca, pentru o valoare aleasa, nu avem cum sa ajungem la solutie, se renunta la acea valoare si se reia cautarea din punctul în care am ramas.
Tehnica Backtracking are ca rezultat obtinerea tuturor solutiilor problemei.
Pentru generarea solutiilor permutarilor vom considera ca acestea se afla într-o stiva. Astfel x1 se va gasi pe primul nivel, x2 se va gasi pe al doilea nivel al stivei iar xk se va gasi pe nivelul k al stivei. Stiva o vom nota cu " st ". Programul prin care se va realiza generarea de permutari si aranjamente reprezinta tehnica de Backtracking ITERATIV si se va compune din 4 proceduri : init, succesor, valid si tipar, o functie în cazul în care am ajuns la solutia finala (function solutie) si rutina Backtracking.
Generarea permutarilor se va face tinând cont ca orice permutare va fi alcatuita din elemente distincte ale multimii A.
Procedura " INIT " este procedura de initializare si are doi parametri: " k ", nivelul stivei care trebuie initializat si " st " (stiva). Pentru generarea permutarilor multimii orice nivel al stivei va lua valori de la 1 la n. Initializarea unui nivel (oarecare) se va face cu valoarea 0, deoarece initializarea trebuie facuta cu o valoare aflata înaintea tuturor valorilor posibile din multime.
Procedura " SUCCESOR " are trei parametri. Pe lânga parametri " k" si " st " se foloseste si parametrul " as " (am succesor) care este o variabila booleana. Gasirea urmatorului element al multimii care nu a mai fost testat se face cu ajutorul acestei proceduri. În situatia în care am gasit elementul, acesta este pus în stiva si " as " va lua valoarea TRUE, în caz contrar (nu a ramas un element netestat) "as " va lua valoarea FALSE.
Procedura " VALID " are trei parametri. " k", nivelul stivei, " st " stiva si variabila booleana " ev " (este valid). Aceasta procedura face ca odata ales un element ea va verifica daca acesta îndeplineste conditiile de continuare, în cazul permutarilor daca elementul se mai gaseste sau nu în stiva. Daca acest element este gasit într-un nivel inferior atunci variabila booleana " ev " va lua valoarea FALSE, iar daca acest element nu se mai gaseste pe nici unul din nivelurile stivei ce au fost deja completate variabila va lua valoarea TRUE.
Functia " SOLUŢIE " testeaza daca s-a ajuns sau nu la o solutie finala, adica daca s-au completat toate nivelurile stivei cu valori distincte . Parametrul acestei functii este nivelul stivei " k ".
Procedura " TIPAR " este procedura care tipareste solutia.
Diferenta în cazul generarii aranjamentelor consta în faptul ca aici stiva are doar înaltimea " p ". Fiecare nivel de la 1 la p ia valori între 1 si n. si aici, elementele plasate pe diverse niveluri trebuie sa fie distincte.
Rutina BACKTRACKING apeleaza functiile si procedurile astfel ca se începe de la nivelul 1 al stivei si prin apelarea procedurii INIT se initializeaza nivelul 1 al stivei cu 0. Atâta timp cât nivelul stivei, k, este mai mare decât 0 se intra în instructiunea REPEAT - UNTIL. Aici se va verifica daca avem succesor si în caz afirmativ se va testa validitatea acestui element nou gasit, prin apelarea procedurilor SUCCESOR si VALID. Instructiunea repeat este utilizata pâna când nu mai avem succesor sau în cazul în care am gasit succesor si acesta este valid. Daca avem succesor atunci se verifica daca aceasta este solutie si pentru raspuns afirmativ se tipareste. În caz negativ, daca aceasta nu este o solutie se va trece la nivelul urmator al stivei care se va initializa prin apelarea functiei "init". Daca nu am mai fi avut succesor atunci am fi coborât în stiva cu un nivel.
O alta metoda de calcul este Backtracking-ul recursiv. De aceasta data procedurile si functiile folosite sunt aceleasi, cu doua mici exceptii:
SUCCESOR nu mai este procedura ci functie booleana ceea ce va face sa dispara variabila "as".
RUTINA BACKTRACKING se transforma în procedura, care se apeleaza prin BACK (1).
Principiul de functionare al procedurii " back " este urmatorul:
în situatia în care avem o solutie, o tiparim si revenim pe nivelul anterior;
în caz contrar, se initializeaza nivelul si se cauta un succesor;
când am gasit unul, verificam daca este valid; procedura se autoapeleaza pentru k+1, în caz contrar urmând a se continua cautarea succesorului;
daca nu avem succesor, se trece pe nivelul inferior (k-1) prin iesirea din procedura back.
Pentru a genera permutarile se poate realiza o procedura PERMUT. Pentru aceasta avem în vedere posibilitatea de revenire la situatia initiala: dupa ce am operat o interschimbare a elementelor ai si aj, urmata de o reapelare a procedurii, pentru valoarea k+1, interschimbam din nou ai cu aj.
În mod practic programul functioneaza astfel (n=3)
se apeleaza procedura PERMUT pentru k=1;
se genereaza ;
se reapeleaza procedura pentru k=2;
se genereaza si se interschimba 1 cu 2, obtinând ;
se reapeleaza procedura pentru k=3;
se genereaza si se interschimba 2 cu 3, obtinând ;
se reapeleaza procedura pentru k=4;
se tipareste ;
se revine în procedura pentru k=3 si se interschimba elementele 3 si 2 obtinând ;
se interschimba 3 cu 1 obtinând ;
se reapeleaza procedura pentru k=4;
algoritmul continua în acest mod pâna când se revine la programul principal;
Metoda urmatoare se bazeaza pe definitia recursiva a permutarilor si anume:
Daca n=1 singura permutare este (1);
Daca n>1 din fiecare permutare p=(p1,.pn-1) de grad n-1 se obtin permutarile (p1,.pn-1,n), (p1,.n,pn-1),., (p1,n,p3,.,pn-1,p2), (n,p2,.pn-1,p1) care rezulta prin inversarea fiecarui element al permutarii p cu elementul n al permutarii cu n elemente, la care se adauga permutarea obtinuta prin alaturarea la p1, p2,.pn a elementului n.
O alta metoda consta în generarea permutarilor conform ordinii lexicografice crescatoare. Se pleaca de la permutarea cea mai mica în ordine lexicografica si anume de la permutarea identica (1,2,.,n).
Având construita o permutare p=(p1,p2,.pn) pentru determinarea urmatoarei permutari, punem în evidenta acel indice i astfel încât pi<pi+1; pi+1>pi+2>.>pn.
Urmatoarea permutare se obtine din p prin înlocuirea lui pi cu cel mai mic dintre elementele pi+1,.,pn care este mai mare decât pi, urmata de inversarea ordini ultimilor n-i elemente, încât ele sa apara în ordine crescatoare. Daca nu exista un indice i ca mai sus, înseamna ca am ajuns la permutarea cea mai mare în ordinea lexicografica adica la (n,n-1,.1 ) si algoritmul se termina.
Pentru a obtine aranjamentele trebuie generata o submultime cu p (p<k) elemente . cu ajutorul ei se pot genera submultimi cu p+1 elemente. Pentru aceasta procedam în felul urmator:
se calculeaza maximul dintre i1,i2,i3,.,ip;
componenta p+1 va lua valori începând de la valoarea maxima gasita, la care se adauga 1, pâna la valoarea n;
la fiecare noua valoare a componentei p+1, se inverseaza, pe rând, componenta p+1 cu componentele 1, 2,.,p, se reapeleza procedura dupa care se revine la ordinea initiala (se procedeaza asa pentru a obtine o submultime cu p+1 elemente ordonate în toate modurile posibile).
Capitolul IV
Realizarea programului
Uses Crt;
type cul=record
r,g,b:byte;
end;
pal=array[0..15] of cul;
type aleg=(ch,col);
var ecran:array [1..25,1..80,ch..col] of byte absolute $b800:0;
rval,sgn:integer;
const
maxcol:integer=80;
maxrow:integer=25;
scroll_delay:integer=5;
mask:array[1..30] of integer=(0,3,3,3,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,4,4,3,3,3,0);
type stiva=array[1..1000] of integer;
var st:stiva;
n,k,p:integer;
as,ev:boolean;
procedure init(k:integer;var st:stiva);
begin
st[k]:=0;
end;
procedure tipar;
var i:integer;
begin
for i:=1 to k do write(st[i],' ');
writeln;
end;
procedure scrie;
var i:integer;
begin
writeln;
for i:=1 to n do write(st[i],' ');
end;
procedure succesor(var as:boolean;var st:stiva;k:integer);
begin
if (st[k]<n)
then begin
st[k]:=st[k]+1;
as:=true;
end
else
as:=false;
end;
procedure valid (var ev:boolean;st:stiva;k:integer);
var i:integer;
begin
ev:=true;
for i:=1 to k-1 do
if st[k]=st[i] then ev:=false;
end;
function solutie(k:integer):boolean;
begin
solutie:=(k=p);
end;
procedure arj1;
begin
write ('n=');
readln (n);
write ('p=');
readln (p);
k:=1;
init(k,st);
while (k>0) do
begin
repeat
succesor (as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev);
if as then
if solutie(k)
then tipar
else begin
k:=k+1;
init(k,st);
end
else k:=k-1;
end;
end;
procedure aranj(var c:stiva;k,pas:integer);
var i,j,max,m:integer;
begin
if pas=k+1 then
tipar
else
if pas=1
then
for i:=1 to n do
begin
c[pas]:=i;
aranj(c,k,pas+1);
end
else
begin
max:=c[1];
for i:=2 to pas-1 do
if c[i]>max then max:=c[i];
for i:=max+1 to n do
begin
c[pas]:=i;
for j:=1 to pas do
begin
m:=c[pas];
c[pas]:=c[j];
c[j]:=m;
aranj(c,k,pas+1);
m:=c[pas];
c[pas]:=c[j];
c[j]:=m;
end;
end;
end;
end;
procedure arj2;
begin
write ('n=');
readln(n);
write('k=');
readln(k);
aranj (st,k,1);
end;
procedure succesor_p1 (var as:boolean;var st:stiva;k:integer);
begin
if st[k]<n then
begin
st[k]:=st[k]+1;
as:=true;
end
else
as:=false;
end;
procedure valid_p1(var ev:boolean;st:stiva;k:integer);
var i:integer;
begin
ev:=true;
for i:=1 to k-1 do
if st[k]=st[i] then
ev:=false;
end;
function solutie_p1(k:integer):boolean;
begin
solutie_p1:=(k=n);
end;
procedure per1;
begin
write('n=');
readln(n);
k:=1;
init (k,st);
while (k>0) do
begin
repeat
succesor_p1 (as,st,k);
if as then valid_p1(ev,st,k);
until (not as) or (as and ev);
if as then
if solutie_p1(k) then tipar
else begin
k:=k+1;
init(k,st);
end
else begin k:=k-1;end;
end;
end;
function succesor_p2(var st:stiva;k:integer):boolean;
begin
if st[k]<n
then
begin
st[k]:=st[k]+1;
succesor_p2:=true;
end
else
succesor_p2:=false;
end;
procedure valid_p2(var ev:boolean;st:stiva;k:integer);
var i:integer;
begin
ev:=true;
for i:=1 to k-1 do
if (st[i]=st[k]) then ev:=false;
end;
function solutie_p2 (k:integer):boolean;
begin
solutie_p2:=(k=n+1);
end;
procedure back(k:integer);
begin
if solutie_p2 (k)
then scrie
else begin
init(k,st);
while succesor_p2(st,k) do begin
valid_p2(ev,st,k);
if ev then back(k+1);
end;
end;
end;
procedure per2;
begin
write('n=');
readln(n);
back(1);
end;
procedure permut(k,n:integer;var p:stiva);
var i,j,c:integer;
begin
if k=n+1
then scrie
else
begin
p[k]:=k;
for i:=1 to k do
begin
c:=p[i];
p[i]:=p[k];
p[k]:=c;
permut(k+1,n,p);
c:=p[i];
p[i]:=p[k];
p[k]:=c;
end;
end;
end;
procedure per3;
begin
write('n=');readln(n);
permut(1,n,st);
end;
procedure permuta (k:integer);
var i,aux:integer;
begin
if k=n+1 then scrie
else for i:=k downto 1 do
begin
aux:=st[i];
st[i]:=st[k];
st[k]:=aux;
permuta(k+1);
aux:=st[i] ;
st[i]:=st[k];
st[k]:=aux;
end;
end;
procedure per4;
var i:integer;
begin
write('n=');
readln(n);
for i:=1 to n do st[i]:=i;
permuta(1);
end;
procedure getpal(var p:pal);
var i:byte;
begin
for i:=0 to 15 do begin
Port[$3c7] := i;
p[i].R := Port[$3c9];
p[i].G := Port[$3c9];
p[i].B := Port[$3c9];
end;
end;
procedure show_;assembler;
asm
mov ah,1
mov ch,6
mov cl,7
int 16
end;
Procedure Hide_;assembler;
asm
mov ah,1
mov ch,32
mov cl,7
int 16
end;
procedure setpal(var p:pal);
var i:byte;
begin
for i:=0 to 15 do begin
port[$3c8]:=i;
port[$3c9]:=p[i].r;
port[$3c9]:=p[i].g;
port[$3c9]:=p[i].b;
end;
end;
procedure setcol(x,y,c:integer);
begin
ecran[y,x,col]:=c;
end;
procedure scroll(Text:String;y:integer);
var i,j:integer;
textc1,textc2:integer;
begin
gotoxy(1,y);
for i:=1 to maxcol do
write(random(9));
textc1:=maxcol div 2 - length(text) div 2;
textc2:=textc1 + length(text);
gotoxy( textc1, y);
write(text);
gotoxy(maxcol,maxrow);
for i:=-30 to maxcol do begin
for j:=1 to 30 do
if((j+i<maxcol) and (j+i > 1)) then begin
if ((textc1 <= j+i) and (textc2 > j+i )) then
setcol(j+i,y,2)
else
setcol(j+i,y,mask[j]);
end;
if rval = 63 then sgn:=-1;
if rval = 30 then sgn:=1;
rval:=rval+sgn;
port[$3c8]:=2;
port[$3c9]:=1;
port[$3c9]:=rval;
port[$3c9]:=1;
delay(scroll_delay);
end;
end;
var pal1,pal2:pal;
i:integer;
Begin
hide_;
clrscr;
getpal(pal2);
for i:=0 to 15 do begin
pal1[i].r:=0;
pal1[i].g:=0;
pal1[i].b:=0;
end;
pal1[3].g:=10;
pal1[4].g:=20;
pal1[5].g:=30;
pal1[6].g:=40;
setpal(pal1);
rval:=30;
scroll('Atestat profesional realizat de',6);
scroll('Enache Victoria',7);
scroll('Clasa a XII-a C',8);
scroll('An scolar 2003-2004',9);
scroll('apasati o tasta...',19);
while not keypressed do scroll('',20);
readkey;
clrscr;
while 1=1 do begin
scroll('Alegeti o varianta',6);
scroll('Permutari (varianta 1): 1',8);
scroll('Permutari (varianta 2): 2',9);
scroll('Permutari (varianta 3): 3',10);
scroll('Permutari (varianta 4): 4',11);
scroll('Aranjamente (varianta 1): 5',12);
scroll('Aranjamente (varianta 2): 6',13);
scroll('Iesire: Esc',15);
scroll('apasati o tasta...',19);
while not keypressed do scroll('',20);
clrscr;
gotoxy(1,maxrow);
textcolor(5);
show_;
case readkey of
'1':per1;
'2':per2;
'3':per3;
'4':per4;
'5':arj1;
'6':arj2;
chr(27):break;
end;
Writeln;
Writeln;
hide_;
textcolor(0);
scroll('apasati o tasta...',23);
while not keypressed do scroll('',24);
clrscr;
readkey;
end;
setpal(pal2);
End.
Bibliografie:
Niculescu St., Cerchez E., serban M., Lica D., Onea E., Voicu A. "Bacalaureat si atestat",Editura L&S Infomat, 1999;
Rancea D. "Informatica", Editura Computer Libris Agora, 1999;
Knuth D. E. "Tratat de programare a calculatoarelor. Algoritmi fundamentali", Editura Tehnica, 1974;
Cristea "Initiere în Turbo Pascal", Editura Teora, 1995;
Tudor Sorin "Tehnici de progamare" Editura L&S Infomat, 2000 .
|
