Treceți la conținutul principal

LIMBAJUL PASCAL PROBLEME


I. introducere in informatica

1.gandirea algoritmica

a. problema ordonarii crescatoare


maimare(a,b)
maimic(a,b)
egal(a,b)
diferit(a,b)
notnull(a)
ordonare()
schimbare(a,b)
asezare(a,b)
creazasir()
init()

b.problema determinarii minimului

min(a,b)
max(a,b)
sortare()
aranjare()
alege(x)
cautare()

c.algoritm ordonare

daca n>0 atunci
alegeX(n)
adauga(x)
ordonare(n-1)


algoritm cautare secventiala(x,s[1..n])
{
fie element curent = primul element
atata timp cat element curent <> element x si
pozitie element curenta <= ultima pozitie elemente(n)  executa
{
daca element curent == element x atunci mesaj 'gasit'
altfel treci la urmatorul element
 }
}



algoritm cautare binara(x,s[1..n])
{
element curent = element din mijlocul lui s
daca n=1 atunci
daca x = el cautat atunci mesaj 'gasit'
altfel mesaj 'negasit'
altfel
{
imparte s in doua jumatati s[1..mijloc] si s[mijloc+1..n]
daca el curent = x atunci mesaj 'gasit'
altfel
daca el curent < x atunci cautare binara(x,s[mijloc+1..n])
altfel cautare binara(x,s[1..mijloc])
}
}

d.recursiv()


2. programare structurata

daca .. atunci .. altfel  if ..then.. else
atata timp cat .. executa while do and do while


algoritm intrare la medic
{
bate la usa
daca raspunsul e 'poftim' atunci
intra in cabinet
altfel
{
atata timp cat cabinetul este ocupat de alt pacient executa
citeste ziarul
intra in cabinet
}
}

instructiune a=5
decizie alternativa if then else endif
repetitie do while and while do
instructiune compusa / bloc {} 
schema logica 
salt conditionat goto


3. variabila . constanta, expresie, atribuire

algoritm minim(n)
{
fie i =1
fie minim = hi
 atata timp cat i < n executa
{
daca hi < minim atunci
fie minim = hi
altfel fie i = i +1
}
}


algoritm ecuatie(a,b,c)
{
daca a <>0 atunci x = (c-b) /a
altfel mesaj 'diviziune prin zero'
}


4.limbaj de programare. calculator electronic. inforamtica

pseudocod

5. tip de date

int
float
double
char
bool



probleme propuse

a. calculati suma s = a1/a + a2/2 +.....+an/n
b.fie triunghiul a,b,c aflati daca triunghiul este echilateral
c.calculati s=a1-a2+a3-.....an unde ai sunt reale
d.calculati perimetrul unui dreptunghi l x L
e.aflati minimul intre 3 numere
f.aflati media aritmetica a ,b
g.calculati (x-y+ab-y)/(a-(a-x/y^2))
h.calculati aria unui triunghi
i. maxim a,b
j.medie geometrica a,b
k.aria patrat de latura n
l.medie aritmetica a n numere
m.maximul dintro multime de numere n
o. factorial de n! pt n>0
p. cate fete si cati baieti sunt intrun grup de n elevi






lectia 2 pag 30
elemente de baza ale limbajului pascal

1.identificatori. constante

cmmdc()
pi = 1.1415926

2. variabila. tip de data

3.int

abs()
par()
impar()
precedent()
succesor()
cmmmc()
div()
mod()

4.float double

sqrt()
sin()
cos()
round()
trunch()
int()

5.char
ascii()
char()

6. bool
ord()
! not
& and
| or
<> diferit
echilateral()
prim()

7.string

8. operatii comune tuturor tipurile predefinite

operatori
operanzi


9.structura unui program in limbajul pascal

calcularie()
{
pi = 3.1415926
raza = 2
aria = pi * sqrt(raza)
}

10.introducerea si extragerea datelor


read()
write()

11. utilizarea bibliotecii crt pentru lucrul cu ecranul

sclrscr()

gotoxy()
blink()
textcolor()
textbackground()
sound()
delay()
nosound()


probleme propuse


1.aria si perimerul triunghiului
2.viteza, distnta si timpul
3.aria unui trapez, baza mica, baza mare si inaltimea
4.aria unui cerc, diametrul si lungimea sa
5.lungimea unui cerc in functie de aria sa
6.ipotenuza, catete,perimetrul si aria unui triunghi
7.nr total de randuri din cartea x cu nr foi si nr randuri pe foaie
8.kmph transformati in kmps
9.lucrare executata in timpul t de catre 1 muncitor si de catre n muncitori
10.nrm1 si nrm2 membrii echipa, nrz1 nr zile finalizare lucrare de catre nrm1 . aflati nrz2 pentru nrm2
11.avem produsele n in kg la pretul pkg. aflati pretul total al tuturor produselor din magazin
12. avem ng si np gaini si pisici, aflati cate aripi si cate picioare sunt in curte














lectia 3 pag 43 instructiuni de control 

1.instructiunea de decizie if

necesitate

if conditie then
instr1
else
instr2


semantica

program laturi triunghi()
{
if(a>0) && (b>0) && (c>0) then
if(a<b+c) &&(b<c+a) &&(c<a+b) then
'formeaza triunghi'
else
'o latura este prea mare'
else
'laturi negative'
}

program triunghi isoscel()
{
if (a==b)||(b==c)||(c==a) then 'triunghi isoscel'
}

program egalitate()
{
if a==b ' egalitate'
else
'diferenta'
}

program ecdegrI() ax+b = 0
{
a,b,x reale
read a,b,c
if a ==0 then
 if b==0 then 'nedeterminata'
else 'imposibilitate'
else
x = -b/a 'solutie'
}



program ecdegrII(){ ax^2 + bx +c = 0

a,b,c,x1,x2,d reale;
read a,b,c
if a == 0 ' ec de gr I'
else
d = sqrt(b)=4*a*c;
if d >= 0 then
 x1 = (-b-sqrt(d))/(2*a)
 x2 = (-b+sqrt(d))/(2*a)
x1 x2 'solutii'
else 'nu sunt solutii reale'
}

probleme propuse

1.triunghi laturi, perimetrul,
2.triunghi isoscel, echilateral,dreptunghic
3 max si min int
4.ordonare nume cu input
5.divizibil a divide b1,b2,b3
6. a,b reale. medie aritmetica, medie geometrica
7.a,b,c reale. arie si perimetrul
8.x intreg. zilele saptamanii
9.aria cerc in fucntie de diametru sau lungime
10. venituri cheltuieli si profit, profit minim
11.triunghi isoscel si ax+b = 0

2. instructiunea repetitiva while

sintaxa

while conditie do
instr

semantica

program suma()
{
i,s,n int
read n
s =0
i = 1
while i<=n do 
s = s +1
i = i+i

'suma' s

}


keypress()
readkey()
crt()
chr(27) = escape

program tasta(){
char key
while key <> chr(27) do
if keypress then
key - readkey
ord(key)
delay (7000)
else
'nimic apasat'
}


program cmmdcsicmmmc()
{
a ,b, u , v ,cd,cm int
read a,b

if a*b ==0 then
{
if a +b <> 0 then  a+b
else 'nu exista cmmdc'
}
else
{
u =a 
v=b
while a<>b do
if a >b then
a =a -b
else
b = b -a
cd = a
cm = u * v div cd
}
}


probleme propuse 

1.factorial n! n e intreg n! = produs(xi) de la 1 la n
2.miscare bila pe o masa fara frecare
3.deplasare sus, jos, st , dr o litera pe ecran using kb
4.joc ping pong. prg2, o paleta st-dr ,sunet lovire si iesire bila. stop joc
6.radical x e Real metoda lui newton
a0 =1 
an = (an-1 + x / an-1)/2 sir de numere generat recursiv
if an - an-1 < 0.000001 => return
 an este sqrt

7.maxim din lista , dimensiune lista, introducere date in lista
8.dreptunghi filled cu o culoare. coordonate colt st sus si dr jos

9. dreptunghiuri aleatorii cu dimensiune si pozitie si culaore diferita random pana la apasarea unei taste

rezolvare problema 9

Random
Random(n)
Randomize

Interschimbare(a,b)
{
aux =x
x = y
 y = aux
}


program desneazacutiialeatorii
{
x1,x2,y1,y2,x,y,aux int

while !keypressed do
{
delay(100)
x1 = random(80)+1
x2 = random(80)+1
if x1 > x2 then
{
interschimbare(x1,x2);
}
y1 = random(25)+1
y2=random(25)+1
if y1 > y2 then
{
interschimbare(y1,y2);
}
random(16)
x = x1
while x<=x2 do
{
y = y1
while y<=y2 do
{
gotoxy(x,y)
y = y+1
x = x+1
}
}
clrscr()
}

10. prim de intreg
11.oglindire numar ex 10758 -- 85701
12. baza 10 in baza 2
13. baza 10 in baza p si din baza x in baza y


3.instructiunea repetitiva for
sintaxa

succesiv
for v=e1 to e2 do
instr

precedent
for v-e1 downto e2 do
instr

semantica

exemple
1. suma(xi) de la 1 la 2n-1

s=0
for i =1 to n do
s = s +2 * i -1

2. dreptunghi

for x = x1 to x2 do
 for y = y1 to y2 do
 gotoxy(x,y)
'#'


3.afisare alfabet
c = char
 for c = 'z' downto 'a' do
write(c)



program piramida numerelor()
{
i,j,n int
n = ?
read n
for i = 1 to n do
{
write j
}
}


probleme propuse

2.p=produs(1-(1/n^2)) de la 1 la n
4. suma(1 + 1*2 + 1*2*3+...+1*2*3*...*n)
5.suma(1-2+3-4+...+-n)
6.suma(1-1*2+1*2*3*...*n)
7.piramida de numere de mai jos
n n-1 n-2 ... 3 2 1
...
3 2 1
2 1
1
8.sunet screscator si descrescator pana la pasarea unei taste
9. piramida de numere
       1
    1 2 3
1 2  3 4 5
...
1 ... (2n-1)

10.deplasare bila de la st la dr , dr la st si sus jos si jos sus

4.instructiunea repetitiva cu test final repeat

sintaxa
repeat
instr iton
until cond

semantica

program anul(){
n int
repeat
read(n)
until n==1 or n==2
if n ==1 then '1st half'
else '2nd half'
}

program euclidcmmdc(){
a,b,de,im,re,cmmdc int
ra char

repeat
read a,b
de =a
im = b
repeat
re = de mod im
de = imp
im = re
until im = 0
cmmdc = de
read ra
until ra == 'n'
}



probleme propuse

1.suma(2n) dela 1 la n ,n>=1 pare
2.sunet aleator pana la key
3.lectia 2 prg 4 cu repeat nu cu while


5.instructiunea de selectie multipla case

sintaxa
case expr of
cazi : instri
...
cazn : instrn
else instrn+1


program litere(){
case ch of
'a'..'z' : 'litera'
'0'..'9' : 'cifra'
'+','-', : 'operator'
else 'char special'
}

program anotimp(){
nr int
nume string

read nr
if nr == 1 then 'iarna'
else if nr==2 then 'primavara'
else 'nu este corect'
}


program anotimp2(){
nr int
nume string
read nr
case nr of 1: 'iarna'
else 'nu este corect'
}

program testeminescu(){
an int
read an
case an of
1850 : 'foarte bine'
else
'grav'}


probleme propuse

1.min si max din sir simultan determinate
2.media nr din sir pana intalnim zero
3.n sir de nr naturale, p si k int. cate din nr din sir se impart la p si dau restul k
4.produsul a 2 nr int prin adunari repetate
5.impartirea a 2 nr naturale fara div sau mod
6.cifrele unui nr natural
7.palindrom 
8.prime <= cu m
9.suma cifrelor n prim <= m
10. nr de trei cifre care citite invers sunt tot nr prime
11.suma (1/(n*(n+1)))
12.patrat perfect n int
13.ec de gr II pana la iesire user
14.n int este cub perfect
15.n = a^3 + b^3 cu 1 <=a <= 5 si 1<=b<=5
16.triunghiuri diferite cu laturile int pozitive si perimetrul p
17.nr <=n a caror suma a cifrelor este divizibila cu 5
18.baza 10 in baza p<10
19.baza p <10  in baza 10
20. afisati 
1
12
123
...
123..n
123..n
...
123
12
1
21.baza p in baza q unde p si q <= 10
22.se citeste nr pana intalnim 0. solutiile ec de gr I unde a si b sunt perechile de nr citite consecutiv in care b este divizibil prin a
23. se citeste nr int pana intalnim real. suma s a nr citite, catul si restul dintre s si suma cifrelor lui s
24.se citeste nr pana intalnim 12. sa se afiseze tripeletele de numere citite consecutiv in care al treilea nr este restul impartirii nr1 la nr2
25.se citeste nr pana intalnim 0. sa se afiseze tripeletele de numere citite consecutiv in care al treilea nr este media aritmetica si geometrica dintre primul si al doilea
26.... perechile de nr consecutive pt care nr2 este egal cu suma cifrelor nr1
27.... nr2  e restul impartirii nr1 la suma cifrelor sale
28....  nr2 e nr aparitiilor ale cifrei 3 in patratul primului
29....   nr2 patrat nr de aparitiile ale cifre 1 in primul
30 ... triplete...nr3 e suma nr1 si nr2
31 .....triplete... laturile unui triunghi
32.....tripelete...laturile triunghi isoscel
33..reale....tripletelaturile triunghi dreptunghic
34. reale....tripelete solutiile ec de gr II in care b^2-4ac=0
35....                            b^2-4ac >0
36..... perechi .. n1>n2 si suma cifrelor lui n1 < suma cifrelor n2
37.n natural ... suma de nr naturale consecutive
38 prim
39.

program prim1(){
d ,x longint
prim bool

read x
prim = t
d = 2
while (d<=trunc(sqrt(x)) and prim do
if x mod d == 0 then prim = f
else if d = 2 then d = d + 1
else d = d+2
if prim then 'este prim'
else 'nu este prim'

}


program prim2(){
d,x longint
prim bool
read x
prim t
for d = 2 to trunc(sqrt(x)) do
if x mod d == 0 then prim = f
if prim then
'prim'
else
'nu e prim'
}

40. i,j,k laturile triunghi cu perimetrul p

program laturi1(){
i,j,k,p int
read p
for i =1 to p do
for j = 1 to p-i do
k = p-(i+j)
if (i<j+k) and (j<i+k) and (k<i+j) then
write i j k
}

program laturi2(){
i,j,k,p int
read p
for i =1 to p do
for j = 1 to p do
for k =1 to p do
if (i+j+k==p) and (i<j+k) and (j<i+k) and (k<i+j)
then
writer i j k
}


41. ridicarea la putere

program npowKa(){
i , n , k , p longint
read n
read k
p =1 
for i -1 to k do p-p*n
write p
}

program npowKb(){
i,n,k,p longint
read n
read k
p = 1
while k>0 do
if k mod 2 == 0 then 
{n = n*n
k = k div 2
} 
else{
p = p*n
k=k-1
}
}

42. nr pagini carti. n cifre. cate pagini are cartea












lectia 4 pag 70 tip de date definite de programator

1.enumerare si subdomeniu

enumerare
type/enum culori ={'alb', 'rosu'}
culori var1;

subdomeniu
type byte 0..255;

probleme propuse

1.enum an,lunile,zile,anotimpuri,discipline
2.subdomeniu litere si cifre
3.enum zile si subdomeniu zile lucratoare
4. type litere mici si mari si cifre si cifre impare si pare
5.type culori si subdomeniu culori deschise

2.vectori sau tablorui unidimensionale

string
vector
tablou
matrice

operatii simple cu vectori

1.read

for i =1 to n do
read x[i]

2.write

write x[i]

2.1 inversare

type domeniu = 1..20
vector = array[domeniu] of real
vector x
domeniu i,n

read n
for i = 1 to n do
read x[i]

for i = n downto 1 do
write x[i]

3.inversare vector in vector

for i =1 to n do
y[i] = x[n+1-i]

4.inversare unui vector in el insusi

for i=1 to n  div 2 do
aux = x[i]
x[i]=x[x+1-i]
x[n+1-1]=aux

5.minim vectorului

min = x[i]
for i = 2 to n do
if x[i] < min then min = x[i]

6.min si max

min = x[1]
max=x[1]
for i = 2 to n do
if x[i]<min then min = x[i]
if x[i]> max then max=x[i]

7. insumare componentelor vectorului

sum = 0
for i =1 to n  do
sum = suma + x[i]

8. afisare elemente pare din vector cu elemente intregi

for i =1 to n do
if not odd(x[i]) then write x[i]

9.afisare elemente pare de pe pozitii impare

for i = 1 to n do
if not odd(i) and odd(i) then write x[i]

10. nr eleme poztive si negative ind vector

inc()
dec()

nn = 0
np =0

for i =1 to n do
 if x[i] to n do
if x[i] < 0 then inc(nn)
else inc(np)
write nn
write np


11.cautare secventiala a unui element in vector

gasit = f
i = 1
while i<-n and not gasit do
if x[i] = y then gasit = t
else
 inc(i)

12.inserare element in vector

for i = n+1 downto p+1 do
x[i] = x[i-1]
x[p] = m
n = n +1

program nrprimedinvectorulV(){
int [20] x
int rad, i , n, d
read n
for i = 1 to n do
read x[i]
for i = 1 to n do
if x[i]==1 then prim = f
else if x[i] mod 2 = =0 then
 if x[i]==2 then prim = t
else prim = f
else
d = 3
prim = t
rad = trunc(sqrt(x[i]))
while d<=rad and prim do
if x[i] mod d = =0 then prim = f
else d= d+2
if prim then
write x[i]
}

probleme propuse

1.real a[20]. e int, e real:
a.e = suma(xi) i de la 1 la n
b. e = suma nr impare pana la n
c. e = produs xi i de la 1 la n
d. e = produs xi de la 1 la n
e. e = media aritmetica a lui a
f. suma patratelor elem lui a
g. e = suma cuburilor componente negative din a
h. e = suma(xi-xi+1) i de la 1 la n

2.x[20] si y[20] real, n int.
a.z[i] = x[i]+y[i]
b. z[i]=x[i]-y[i]
c. z[i] = min x si y

3.x[20] si y[20] real, n int.  i de la 1 la n
a. produs(xi+yi) 
b. suna (xi*yi)
c. e = min (xi,y(n-i+1))
d. e = suma(xi^2 * yi) 


produsul scalar a doi vectori

v = ai + bj + ck versori 3d spatiu

4.n nr prime memorate in vectorul v
5.n nr prime > 999 care invers sunt tot prime
6.x[i] intregi deca iar y[i] binar 
7.x[i] intregi si y[i] restul impartirii lui x[i] la suma cifrelor lui x[i]. prin scaderi repetate nu prin impartire
8.x[i] intregi det cel mai mare nr prim din vector p. apoi impartiti x[i] la suam cifrelor lui p
radicalul prin metoda lui newton iar impartirea prin scaderi repetate


greedy

init b la vid
repeta pana la determinarea bi
se alege un element din a
se testeaza daca poate fi adauga in b

tehnica euristica - criterii matematice de obtinere a solutiilor

3. ordonarea si interclasarea vectorilor

pentru i de la 1 la n-1 executa
 pentru j de la i + 1 la n executa
 daca x[j] < x[i] atunci schimba pe x[i] cu x[j]


program bubble sort
{
int x[20]
int n , i , aux
bool gata

read n
for i = 1 to n do
read x[i]
repeat
gata = t
for i = 1 to n-1 do
 if x[i+1] < x[i] then
{
gata = f
schimba (x[i],x[i+1])
}
until gata

for i = 1 to n write x[i] , i
}

program admintere liceu
{
const max 50
string nume[max]
real media[max]
i,j,nre i..max
string aux1
real aux2

read nre

for i = 1 to nre do
{
read nume[i]
read media[i]
}

for i = 0 to nre -1 do
{
for j = i+1 to nre do
{
if media[j] > media[i] then
{
aux1 = nume [i]
nume[i]=nume[j]
nume[j]=aux1
aux2 = media [i]
media[i]=media[j]
media[j]=aux2
}
for i =1 to nre do
write nume[i] media[i]
}

program elevi la concurs de admitere
{
pag87..
}


interclasarea a doi vectori

program interclasare(){
const max =10
int a[max],b[max]
int c[3*max]
m,n,i,j,k int

read m
for i = 1 to m do read a[i]

read n
for i=1 to n do read b[i]

i=1
j=1
k=0
while i<=m and j<=n do
if a[i]<b[j] then
k = k+1
c[k]=a[i]
i=i+1
else
k=k+1
c[k]=b[j]
j=j+1

if i<=m then
while i<=m do
k=k+1
c[k]=b[j]
j=j+1

for i =1 to k do
write c[i]

}


4.alte aplicatii ale vectorilor

histograme
{
int punctaj[10]
string nume[10]
nre, i , j int

for i = 1 to nre do
write i read i read punctaj[i]

for i = 1 to nre do
for j = 1 to 2*punctaj[i] do
if odd(i) then gotoxy(pozitieA) else gotoxy(pozitieB)
write nume[i]
}

operatii cu multimi memorate sub forma de vectori

reunire
{
//init
int mx
int a[mx],b[mx],r[mx]
m , n , p , i , j int
bool g
//copy a in r
for i = 1 to m do r[i]=a[i]
p=m
//add b care nu sunt deja in a
for i = 1 to n do
j=1 
g=f

while j<=m and !g do
if b[i] = a[i] then g=t else j=j+1
if !g then
p=p+1
r[p]=b[i]
//afisare r
for i = a to p do write r[i]
}

intersectie{
//init
int mx
int a[mx],b[mx],in[mx]
m , n , p , i , j int
bool g
//add a in in
p=0
for i =1 to m do
j=1 
g=f
while j<=n and !g do
if a[i]=b[j] then 
g=t
else j = j+1
if g then
p=p+1
in[p]=a[i]
//afisare
for i =1 to p do write in[i]

}



polinoame {
// suma (An-i * X^n-i  ) i de la 0 la n
//A0  reale  coeficientipP
//n gradul P
//X variabila P


max = 20

real a [max]
int i,n
real x,xi,px

read n 
for i = n downto 0 do
read a[i]
read x
[x = 0
xi = 1

for i = 0 to n do
px = px+a[i]*xi;
xi=xi*x

write px

}


program polinom(){
int i,n
real x,a,p
read n
read x
p =0
for i = n downto 0 do
read a
 p = P*x+a
write p
}

animatie cu bile 
{
max=20
int v[max]
v x,y,dx,dy,c
int i,n

//initbile
read n
for i = 1 to n do
x[i]=random(77)+2
y[i]=random(22)+2
c[i]=1+random(15)
dx[i]=random(2)
if dx[i]==0 then dx[i]=-1
dy=random(2)
if dy==0 then dy[i]=-1

repeat
for i = 1 to n do
//sterge si scrie bila pe noi pozitii
gotoxy(x[i],y[i])
write ' '
x[i]=x[i]+dx[i]
y[i]=y[i]+dy[i]

if (x[i]==1 or x[i]==80) then
sound(500)
delay(10)
nosound
dx[i]=-dx[i]

if y[i]==1 or y[i]==25 then
sound(100*i)
delay(10)
nosound
dy[i]=-dy[i]
textcolor(c[i])
gotoxy(x[i],y[i])
write #15

//strge ecranul
delay 50
until keypressed
clrscr
}



5. tipul string

functii si proceduri

concat()
copy()
pos()
insert()
delete()
val
str
chr(cod)
ord(car)
upcase()

programe propuse

1. change case
{
for i =1 to lenght(s) do s[i] = upcase(s[i])

sau

for i =1 to lenght(s) do
if s[i]>='A' and s[i]<='Z' then s[i] = chr(ord(s[i]+32)
}

2. limba pasareasca
{
string s
int i

read s

i = 1
while i<length(s) do
if s[i]=='a' or s[i]=='e'...'i','y','o','u',... then
insert('p',s,i)
i=i+2
insert('p',s,i)
i=i+1
else
i=i+1
write s
}



3. despartirea unei propozitii in cuvinte si numararea lor
{
string s
string c[20]
int p,i,nrc
read s
s=s+ ' '
nrc = 0

while s<>' ' do
p=pos(' ',s)
inc(nrc)
c[nrc]=copy(s,1,p-1)
delete(s,1,p)

for i =1 to nrc do writes c[i]
}

program contor cuvinte (){
string s,c
cu [] string
ap[20] int
p,j,nrc int
bool g

read s
s = s+ ' '
nrc =0

while s<>' ' do
p = pos(' ',s)
cu = copy(s,i,p-1) 
j=1
g = f

while j <=nrc and !g do
if cu = cu[j] then g = t else inc(j)
if !g then 
inc(nrc)
cu[nrc]=cu
ap[nrc]=1
else
ap[j] = ap[j]+1
delete(s,1,p)

write 'cuvinte'
for j =1 to nrc do
write j cuv[j] ap[j]
}



4.afisarea unui sir prin litere care cad

program sircarecad(){
string s
int i,j
char t

read s
if s = ' ' then s= 'prez'
for i = 1 to length(s) do
 for j =2 to 20 do

gotoxy (10+2*i,j-1), write ' '
gotoxy (10+2*i,j) write s[i]
gotoxy (1,1) sound(200-10*j) delay 10
no sound
t = readkey
}


5. program scris defilant(){

string s
int i
read s
for i = 1 to 80 do s= ' ' + s+ ' '
repeat
for i = 1 to length(s) - 79 do
gotxy(1,20) write(copy(s,i,80)) delay(50)
until keypressed
}



6. tablou bidimensional - matrice

c
STRING S[10][10][..];
p
var x array: [1..4,1..5] of string;

tip de date scalare

orar 7 x n
tabla de sah 8x8

program 
celmaibundintretoti pag 103
celmaifericitbarbat pag 104

probleme propuse

1. avem n litere mici
a.sa se gaseasca toate litere distincte si cele care apar de mai multe ori
b.sa se ordoneze literele alfabetic

2.avem perechi de forma i,j a n persoane. ce persoana i e influenteaza mai mult de j
3.matrice nxm, n coloan impare, cu nr naturale de la 1 la n^2, un patrat magic in care suma liniilor , coloanelor sau diagonalelor e aceasi . verificati daca matricea este una magica dintr-o singura parcurgere
4.sirul a cu n elemente intregi. det ce element se afla pe positia k in sirul obtinut din sirul a prin ordonare fara a-l ordona pe a si fara a utiliza alte siruri
5.avem n valori ale colesterolului pentru n persoane. o persoana este sanatoasa daca are colesterolul intre doua limite a si b. aflati nr de pers sanatoase si media aritmetica a colesterolului persoanelor bolnave
6.o pers are de cumparat din m magazine n produse cu pret diferit. in ce magazin este pretul cel mai mic pentru fiecare produs.cunoscand cantitatile ce trebuie cumparate din fiecare produs det suma ce urmeaza a fi cheltuita
7.se considera n aruncari cu un zar . se cere :
a.det de cate ori apare fiecare fata si la a cata aruncare
b.sa se det toate perechile de forma fi, ki cu proprietatea fi+ki este un numar par ,unde fi reprezinta numarul fetei iar ki = nr de aparitii ale fetei fi
8.se da un nr natural n. sa se verifice daca nr obtinut prin eliminarea primei si ultimei cifre din n este patrat perfect
9.sa se det cmmdc a n numere


7. tipul inregistrare - campuri rand/coloana

p
type elev = record 
nume:string
end

referirea la un camp
c[5].nume = 'michelle'

instructiunea with

with camp do instr

program demo admintereliceu pag 111

probleme propuse

1.scrieti declaratii de tip pentru a specifica
a.data 
b.timp
c.nr complex
d.un punct in planul euclidian dat prin coordonatele sale

2.amestecarea unor carti de joc intre 9 si 'as'
3. simulator miscare bile pe ecran(){
type tbila = record x,y
bila array p1..max] of tbila

for i = 1 to n do
 with bila[i] do
x = random y = random
dx = random id dx==0 then dx=-1
dy = random if dy then dy=-1
repeat
for i =11 to n do
with bila[i] do
gotoxy
write ' '
x = x+dx
y = y +dy
if x==1 or x==80 then
sound() delay() nosound dx=-dx
if y==1 or y ==25 then
sound() delay () nosound dy=-dy
gotoxy(x,y) write #15
delay ()
until keypresses
clrscr
}


4. desenati o fereastra pe ecran. coltul st-sus si dr-jos, nume si culori(){
//chenar
for x = x1 +1 to x2-1 do gotoxy(x,y1) gotoxy(x,y2)
for y = y1+1 to y2-1 dogotoxy(x1,y) gotoxy(x2,y)
//colturi
x1 , y1 to x1,y2
x2,y1 to x2,y2
//nume
x1+(x2-x1) div 2 -1 +length(nume)) div 2 , y1
}


8. tipul multime
p
type id = set of id

operatii cu multimi
1.reuniune
2.intersectia
3.diferenta
4.incluziune
5.apartine


program citireaisaremultime pag 118

program ciurulluieratostene1(){
n int
int elem,j
sita, prim : set of 2..50
read n
sita  = [2..n]
prim = []
elem = 2
repeat
while not [elem in sita] do elem = succ(elem)
prim = prim + [elem]
j=elem
write(elem)
while j<=n do
sita = sita=[j]
j = j + elem
until sita=[]
}


progameratostene2(){
int n,nn
sita, prim : set of 2..50
next, j ,elem  int

read n
nn = 2*n
sita = [2..nn]
prim = []
next = 2
repeat
while not (next in sita) do next = succ(next)
prim = prim + [next]
elem = 2 * next -1
j = next
while j<=n do
sita = sita-[j]
j = j+elem
until sita = []
}


probleme propuse

1.administrare parc auto. automobil:nr locuri, cai putere,marca,nr inmatriculare,tip de carburran, natura. intrari si iesiri masini, inlocuire masina
2.avem o propozitie cu cuvinte despartite prin spatiu sau punct, punct si virgula, semnul exclamarii si semnul intrebarii.despartiti propozitia in cuvinte
3.avem matricea m . listati punctele minim de pe coala i si maxim de pe coalana j , sa
4.avem tempoeraturile in iecare ora, precum si cant de precipitatii din luna resp.afisati temp maxima , ziua si ora, temp minima , ziua si oa , lista zilelor ordonata desc in fct de cant de precipitatii, media precip zilnice din resp luna a anului eventuale histrograme
5.eliminati din matricea a cu m linii si n coloane linia l si coloana k si sa se realiz. matricea ramasa. fara a folosi o alta matrice
6.sa se bordeze o matrice a m,n cu linia m+1 si coloana n+1 unde a[m+1,j] sa fie suma elementelor de pe coalana j cu j de la 1 la n iar a[i,n+1] sa ie suma elem de pe linia i cu i  de la 1 la m
7.avem vectorul v cu n componente elem intregi sa se formeze un nou vector w[i] care sa contina suma si produsul cifrelor elem vectorului v[i]
8.sa se def un subdomeniu pentru literele mici ale alfabetului atin. fie un vector v cu elem de acest tip. sa se formeze un vector w care sa contina numai elem din v ce sunt consoane si sa se afiseze toate majusculele coresp. literelor din w
9.sa se gen. aleator cuvinte de lungime 4. chr
10.sa se insereze intre oricare doua elem din vector de nr reale media lor aritmetica
11. sa se det de cate ori se intampla ca intrun vector de nr reale sa existe un elem ce respr produsul elem sale vecine
12. sa se scrie in spirala nr de la 1 la n^2 intro matrice patratica cu n linii si n coloane . a . di ncentrul matricei n impar b. din coltul st sus . se vor considera pe rand ambele sensuri de deplasare
13.se da o matrice patratica de ordin n. se considera ca cele doua diagonale impart matricea in patru zone : nord, sub, est, vest. elem de pe diagonala n ufac parte din nici o zona
a.suma elem nord, produs sud, media aritmetica est,elem nenule vest
b.simetrica matricei initale fata de diagonala principala
c...vezi b. secundara
d.vezi b fata de o axa oriz ce trece prin centrul matricei
e.vezi d verticala ce trece prin centrul matricei
14.considerand enum culori sa se stabileasca ce valori reprezinta:
a.ord('z' - ord('maro'))[3]
b.pred( ord ('gri));[ 4]
c. succ ('rosu') [1]
d.succ (chr( ord ('b') + 3 - ord( ' alb')) [2]
15.det erorile de sintaxa pag 121
16.matrice m,n reale sa se listeze liniile , nr de ordine cu cel putin k elem nule
17.matrice simetrica fata de diagonala principala sau daca are toate elem nule
18.multime y cu nx lem intregi si y cu ny elem intregi unde nx>ny. sa se dicida daca y este subsir al lui x  adica exista k pt care:
kx = y1, xk+1 = y2,..., xk+ny-1 = yny
19.avem doua matrice cu elen reale. a cu m,n si n cu n,p. produsul matricelor a si b este matricea c cu m,p in care 
c[i,j] = suma a[i,1]*b[1,j] + b[2,j]+..+a[i,n]*b[n,j] i de la 1 la m si j de la i la p.
programul va citi a si b si afiseaza si calculeaza produsl lor in c
20.avem vectoru x=(xi i de la i la n) modificati vectorul ai sa avem:
a.x(x2,x2....xn,x1)
b.x(xn,x1,..,x-1)
c.x(x2,x1,x4,x3,..,.xn,xn-1) n - par
21.baza 10 in baza 2 memorand rez in a.vector si b.sir de caractere
22.admitere liceu:
a.init db a vectorului de inred de tip elev
b.add elev in db
c. replace elev
d. insert elev pe o pozitie
e. elimin elev de pe o poz
f.elimin elev cu anumit nume
g.cautare elev
h.calculare medii
i.listare alfabetica nume
j.listare in ordiena desc medii
k.lista elevi cu medie peste val x
l.amestecarea elevilor in db
m.elimina ultimul elev din db
23.deplasare fereastra pe ecran cu kb si redimensionarea la apasarea a doua taste home si end
24.dif a doua multimi din vectori si reuniunea direfentelor denumita diferenta simetrica
25.doua polinoae in vectori. suma, dif, si produsul lor
26.p/p memorate in vectori obtinand alti doi vectori in care sa pastram catul si restul impartirii
27.realizati jocul puzzle/perspico cu o matrice de 4x4. cu numere de la 1 la 15 ultima casuta fiind libera.se amesteca numerele la inceput apoi se deplaseaza o casuta sus, jos , st sau dr in functie de casuta libera. adaugati functia de reface a matricei cu ajutorul cursorrului kb. obtineti o generalizare pentru nxn casute
28.tip de date complexe si calcule in nr complexe conform alg clasa x
29.nr de la 1 la n sunt asezate in ordine cresc pe circumferinta unui cerc de la n la 1.incepand cu nr s se elimina din cerc nr din k in k dupa fiecare eliminare cercul strangandu-se. care v-a fi nr care ramane
30.vezi 29... dar nr nu se elimina ci se marcheaza pana unul din ele va fi marcat de doua ori. cate numere au ramas nemarcate
31.fie a[m][n] reale. det linia l si coloana k pe care suma elem este maxima
32.fie matricea a m,n cu nr reale si vectorul v cu n componente reale. det daca acest vector apare ca linie in matricea a si in caz afiramtiv sa se afiseze nr aceste ilinii
33.det toate sol de tipe byte ale ecuatiei 7x-4y=3
34. fie v un vector cu elem char. sa se constr un vector w ai w[i] = nr de aparitii ale v[i] in vectorul v
35.avem vectorul de nr intregi. sa se det cea mai lunga subsecventa de elem consecutive prime ale caror oglindire sunt to nr prime
36. avem vectorul de nr intregi v. afisati subsecventa palindromica de lungime maxima (elem subsecventei sunt elemente consecutive in vector)


















index lectia 5 pag 124 subprograme

1.functii si proceduri 124
proceduri si subprograme 125
functii 125
declaratii si parametrii 127
parametrii formali/argumente si efectivi
rezultatul returnat de functie
corpul functiei
antet 128

probleme propuse 129
1 cmmdc 129
2 factorial 130
3 fact 130
4 cmmdcX 131
5 cmmdceuclid 132
6 argumente 132
schimba 133
apel prin valoare
7 prim 134

modularizarea  135
domenii de vizibilitate a identificatorilor

proceduri 136
modularizare
programare ordientata obiect

2.aplicatii ale subprogramelor 137

1.admitere liceu 137
2. simplificare fractie 140
3. hanoi 141

3.variabile initializate
variabile de tip functie sau procedura 144
 x = function()

4. recursivitate 145
conditia de consistenta a unei definitii recursive 146
stiva in recursivitate 147
fact 147
recursivitate 147
recursivitate directa si indirecta sau incrucisata 148
forward, 
probleme propuse 149
1 to 8

5. aplicatie : evaluator de expresii algebrice 149

algoritm 150
evaluarea unei functii intrun punct 150
protectia la erori 154
programul 156

6. probleme propuse 161
1 to 18

program cmmdc(a,b){
while a<>b do
if a > b then a = a-b
else b=b-a
cmmdc=a
}

program factorial(n){
int i,p
p=1
for i =1 to n do p=p*i
factorial = p
}

program fact(n){
if n ==0 then fact = 1 else fact = fact*(n-1)*n
}

program cmmdcX(){

int a[10];
x,n,i int;

cmmdc3(x : vector, n int){
if n == 2 then cmmdc3 = cmmdcx(x[1],x[2])
else
cmmdc3 = cmmdcx(cmmdc3(x,n-1),x[n])
}

}



program cmmdc22(a,b){
aux int;
while b<>0 do
aux = b
b=1 mod b
a = t
cmmdc22 =a
}

program cmmdc23(a,b){
if b == 0 then cmmdc23 = a else cmmdc23 = cmmdc23(b,a mod a)
}


program gresit(s string){
s = '#'+s+'#'
gresit = length(s)
}

program corect(var s string){
s = '#'+s+'#'
corect = length(s)
}


program schimba(a,b){...}

program nrprime(x in){
function este prim(x int): bool;
function radical(xx:real):real;
const eps = 0.0001;
an,an1 real;
an1 = 1
an = (1+xx)/2
while abs(an-an1)>eps do
an1=an
an=(an+xx/an)/2
radical = an
int d, rad
prim bool

if x mod 2 == 0 then if x ==2 then prim = t else prim = f
else
}d = 3
prim = t
rad = trunc(radical(x))
while (d<=rad) and prim do
if x mod d == 0 then prim = f else d=d+2
}
esteprim = prim
n,i int
read n
for i = 2 to n do
if esteprim(i) then write i
}

2.1 program admitere liceu pag 137
introduceredateelevi()
listareelevi()
ordonaredupamedii()
ordonarealfabetica()
meniu()


2.2 simplificarea unei fractii(a,b,u,v){
//cmmdc(a,b)
int a,b,u,v
read a,b
if b == 0 then write ' inexistenta'
else if a ==0 then write '0'
else
simplifica(a,b,u,v)
if v==1 then write u
else write u ,'/', v
}

2.3 turnurile din hanoi pag 142 de revazut



3.
programe 
maimic(x,y){ x<y}
maimare(x,y){x>y}

4. ackerman recursivitate(m,n){
if m ==0 then a = n+1
else if n==0 then a=a(m-1,n)
esle
a=a(m-1,a(m,n-1))
}

program inconsistent(n){
if n == 0 then inconsistent = 1
else inconsistent = n*inconsistent(n+1)
}

programstivarecursivafactorial(n){
if n == 0 then fact = 1 else fact = fact(n-1)*n
}


program simularerecurisivitate(){
const max = 20
type stiva = record...end
procedure initstiva(s stiva){s.n=0}
function estegoalastiva(s stiva){ret=s.n=0}
procedure puneinstiva(stiva s, elem int){ with s do
if n =max then write 'plin'
else inc(n)
x[n]=elem
}
procedure scoatedinstiva(s stiva, elem int){
with s do
if n == 0 the write ' gol'
else elem=x[n]
dec(n)
}
function factorial(n){
s stiva
f int
initstiva(s)
f=1
repeat 
puninstiva(s,n);
dec(n);
until n==0
f=1
repeat
scoatedinstiva(s,n)
f=f*n
until estegoalastiva(s)
factorial=f
}
int n
read n
write ractorial(n)
}

program recursivitateindirecta(){
function f(x) forward
function g(x){
if x = 0 then g=1 else g=g(x-1)+f(x-1)
function f
if x = 0 then f=1 else f=f(x-1)+g(x-1)
write f(5)
}



probleme propuse 

1.suma(n) = 1+3+5+..+(2n-1)
2.produ1(n) = 1 * 4 * 7  * ...* (3n-2)
produs2(n) = 2*4*6*...*(2n)
3.produsul componentelor unui vector
4.inversati un sir de caractere
5.apartenenta unui el la un vector de int
6.verif daca vectorul v contine cel putin un element nul in primele n elemente
7.afisati vectorul
8. inversati vectorul

5.evaluator de expresii algebrice pag 149 de revenit


probleme propuse pag 161 18 probleme

1.invers(s string){
s string; int i;
t = '';
for i = length(s) downto 1 do t=t+s[i];
invers = t
}
a.estepalindrom()
b.'aerisirea = t
c.abracadabra = f

2.rescrierti subprogramele de lucru cu siruri de caractere
3.def un tip de data pentru numere naturale foarte mari si sa se scrie proceduri care sa adune si sa scada astfel de numere
4.det dif intre doua momente de timp prin ora, min si sec
5.tabelati o functie definita in textul programului ai sa afiseze valori in n puncte din intervalul [a,b]
6.update admitereliceu pt stergere,inserare,modifica  date elev.listare elevi cu medii intre doua valori date
7.este consistenta ?
test(x){
if x == 0 then test = 1
else if x==1 then test=test*(x+1) else test = test*(x+2)+x
}
8.test{
int x
function f(x int){ sau function f(var x int){
x = x+1
f=x*x}
x=2 write f(x)
}
9.sintaxa
10.muta n discuri de pe turnul p pe turnul q in t din hanpoi procedura ? este consistenta ?
hanoi2(n,p,q int){
int r
r = 6-p-q
if n ==1 then write p '-' q
else
write p '-' r
hanoi2(n-1,p,r)
write r '-' q
}
11.calculati s= suma(i) i de la 1 la n si produsul p(i) i impar de la 1 la 2n-1 iterativ uilizand stive
12.program test(){
int x,y
function f(var z,y int) {
x = x-y
x=x+1
f=x+y+z}
y = 2
x=y+5
write x , y , f(x,y), x, y}

13.afisati o propozitie pe ecran fiecare litera fiind pozitionata aleator air mai apoi miscati literele spre pozitia finalka din mijlocul ecranului
14.program test{
function f(var x int){
x = x+1
f = x
}
function g(x,y int){g=x+y}
y int
y = 2
write g(f(y),f(x)))
}
15.program triunghi cu coordonate varfuri
2 triunghiuri au :
a.aceasi arie
b.sunt asemenea
c.primul este in interiorul celui de al doilea

16.fie tabla de sah n*n pe care plasam doua dame prima pe l1 si c1 iar a doua pe l2 si c2. verificati daca damele se ataca intre ele sau nu
17. divide(a,b , c,d int) pentru a obtine o impartire cu rest
18.procedura care util un vector cu primele n componente primele n nr prime care citite invers sunt tot nr prime

2.1 program admitere liceu pag 137
2.3 turnurile din hanoi pag 142 de revazut
5.evaluator de expresii algebrice pag 149 de revenitlectia 6 pag 164 metode de elaborare a algoritmilor to pag 197
index lectia 6

1. generarea de multimi 164
gen permutari 164
loxic 165
gen combinari 166
gen aranjamente 166
gen produs cartezian 168
gen submultime a unei multimi 170

2.metode simple de sortare 171
selectie directa 171
bubble sort 171
numarare sort 172
insertion sort 172
insertie directa 172
shell 173

3.greedy 173
rucsac() 174

4.backtraking 175
backtraking recursiv 177
dame() 178
rucsac discret() 180
labirint()181


5.mouse in modul text 184

labirint magic 185

6. divide et impera 187

sort interclasare 188
quick sort 189

7. programare dinamica 191
subsir crescator de lungime maxima 191
raft() 193


probleme propuse 194 to197

.........

1. permutari
inductie matematica
nr permutarilor = n!

procedure nextperm(n int, p vector){
int i,j,k
schimba(x,y int){aux=x,x=y,y=aux}
if gata then {for i = 1 to n do
p[i] = i
gata = false
}
else
{
i = n-1; 
while(i>-) and p[i]>p[i+1]) do
{ i = i -1}
}
if i = 0 then gata = true
else
{
k = n
while p[i]>p[k] do
k=k-1
schimba(p[i],p[k])
for j = 1 to n-1 div 2 do
schimba (p[i+j],p[n-j+1])
}
}
}


combinari de n luate cate m  ci<n-m+i

procedure comb(m,n int, var c vector){
i,j int
if gata then
{
for i =1 to m do
{
c[i]=i;
gata = false
}
else
{
i=m
while( i>=1 and c[i]=n-m+1 do i=i-1
if i =0 then gata = true
else
{
c[i]=c[i]+1 
}
for j=i+1 to m do 
c[j]=c[j-1]+1
}
}
}


aranjamente

program generari {

const max = 20
int vector [max]
gp, gc bool
m,n,i int
p,c,a vector

procedure scrie (x vector, n int){
i int
for i = 1 to n do write x[i]
}

procedure nextperm(n int, p vector){
int i,j,k
procedure schimba(){...}
if gp then
for i = 1 to n do p [i]=1
gp = false
else
i=n-1
while i>0 and p[i]>p[i+1] do i = i -1
if i = 0 then gp = true
else
k = n
while p[i]> p[k] do k=k-1
schimba(p[i],p[k])
for j = 1 to n-1 div 2 do schimba ( p[i+j],p[n-j+1])
}}}


procedure nextcomb(m,n int, c vector){
i , j int
if gc tehn fori  =1 to m do c[i] = i ; gc = false
else
i = m
while ( i >=1) and (c[i]=n-m+1) do i=i-1
if i = 0 then gc = true
else
c[i]=c[i]+1
for j = i+1 to m do c[j]=c[j-1]+1
}}}

//gen aranjamentelor
{
read n
read m
gp = t
gc = t
repeat
nextcomb(m,n,c)
if not gc then
repeat
nextperm(m,p)
if not gp then
for i = 1 to m do a[i] = c[p[i]]; scrie(a,m)
}
until gp
until gc
}

}



produs cartezian

program cuplaj(){
m,n,i,j int
read m,n
for i = 1 to m do
 for j = 1 to n do
write i , j
}


program produs cartezian{
vector int [10];
vec int[3];
p int
cu vector
g gool

const nume [3][4] string = {{" ",,,,},{,,,,}}

vec n [] = {3,4,2}

procedure scrie( v vector, p int){
i int
for i = 1 to p do
write nume[i,v[i]]
}

procedure next(p int, n vec, v vector){
//produs cartezian
i int
g bool;

if g then 
for i = 1 to p do v[i] = 1
g = f
else
i = p
g = f
while i>0 and !g do
if v[i]<n[i] then 
v[i]=v[i]+1
g t
else
v[i]=1
i=i-1

if !g then g = true
}

g = t
repeat
next(3,n,cuplare)
if !g then scrie (cuplare,3)
until g
}


submultimea unei multimi

n multime
vid
vectorul caracteristic asociat
vectroul v cu n elem in care v[i]=1 sau v[i]=0 daca nu apartine
se obtine produsul cartezian a n multimi {0,1}
codificarea multimii in baza 2 de la 0 la 2^n -1
transformarea elem multimii de la 1 la  2^n -1 in baza 2 rezulta vectorii caracteristici


2. sortare

selectie directa

for i = 1 to n-1 do
 for j = i+1 to n do
 if x[j]<x[i] then schimba x[i],x[j]

bubble sort

repeat
g = t
for i = 1 to n-1 do
 if x[i+1] < x[i] do
 schimba x[i], x[i+1]
 g = f
until g

sort numarare

procedure numsort(n int, a vector){
vector b,k
int i,j
for i = 1 to n do k[i]=0
for i = 1 to n-1 do
for j = i+1 to n do
 if a[i]<a[j] then k[j] = k[j]+1
else k[i] = k[i]+1
for i = 1 to n do b [k[i]+1] = a[i]
for i = 1 to n do a[i] = b[i]
}


insertion sort

insertiedirectasort(n int, a vector){
int aux
i , j , k int
g = bool
for i = 2 to n do
aux =a[i]
k=0
j=i-1
g = f
while j>=1 and !g do
if a[j]>aux then
a[j+1]=a[j]
j=j-1
else
k=j
g=t
a[k+1]=aux
} 


shell sort( n int , avector){
i,h int
g = bool
h = n
while h>1 do
h = h div 2
repeat
g = t
for i = 1 to n-h do
if a[i]>a[i+h] then
schimba a[i],a[i+h]
g=f
until g
}


3. metoda greedy

-init vector b la multimea vida
-alege un element din a
-verifica daca poate fi adaugat in b daca indeplineste conditia
-repeta pana cand au fost determinate toate elementele din b

problema continua rucsac(){
/*
greutate maxima rucsac gg
seria de obiecte n de greutati gi de utilitati ci
pentru obiectul i din care luam doar  o parte din el xi intre [0,1] avem atunci  problema rucsas continua
pentru un obiect intreg din care nu se pot lua parti din el  avem atunci  problem rucsac discret
*/
const max=5
c[max],g[max],x[max] real
n,i,j int
gg,ggr, aux real

read n

for i = 1 to n d
write i read c[i]
write i read g[i]


read gg
for i = 1 to n-1 do
 for j = 1 +1 to n do
 if c[j]/g[j] >c[i]/g[i] then
aux =c[j]
c[j] = c[i]
c[i]=aux
aux = g[j]
g[j] = g[i]
g[i] = aux


for i = 1 to n do
write i, c[i] , i , g[i] , c[i]/g[i]
ggr = gg
i=1

while i <=n do
if ggr >g[i] then
x[i]=1
ggr = ggr-g[i]
i=i+1
else
x[i] = ggr/g[i]
for j = i + 1 to n do
x[j] = 0
i = n + 1

for i = 1 to n do
write i, x[i]
}



4. metoda backtracking{
tip vector[max]
a tip
k int
c bool

k=1
while k > 0 do 
c = f
while mai exista o val a apartine sk netestat and !c do
xk = a
if fi(x1,...,xk) then c = t

if not c then k = k - 1
else if k = n then scrie (x) else k = k + 1
}


program backtracking{
vector [max] tip;
procedura backtracking(n int, x vector){
k int
c bool

k = 1 
x[k ]=0
while k>0 do
c = f
wile x[k]< n and !c do
x[k] = x[k]+1
 if potcontinua(x,k) then
c = t
if !c then
k = k-1
else if k = n then scrie (x)
else
k=k+1
x[k] = 0
}
}


procedure backtracking recursiv(i, n int x vector){
k int
k = 1
while k <= n do
x [i]=k
if potcontinua (x,k) then
if k = n then scrie (x)
else backtracking recursiv(i+1,n,x)
k = k + 1
}

ALTE PROBLEME
VARFURILE UNUI GRAF
VARFURILE UNEI HARTI
PERMUTARI
CIRCUIT HAMILTONIAN

problema bool potcontinua(x vector, k int){
a bool
i int
a = f
i = 1
while i < k and !a do
if x[i] = x[k] or abs(x[i]=x[k])=k-1 then
a = t
esle 
 i = i+1
potcontinua = !a
}


problema damelor iterativ{

const max = 20
vector [max] int
s  int

procedura scrie (n int, x vector){
i int
inx(s)
writer sol
for i = 1 to n do
write i , x[i]
}

function potcontinua (x vector, k int) bool{..}

procedure dame(n int, x vector){
k int
c bool
k = 1
x[k] = 0
while k > 0 do
x = f
while x[k]< n and !c do
x[k] = x[k] +1
if potcontinua(x,k) then c = t

if !c then k = k-1
else
if k = n then scrie(n,x) else
k = k+ 1
x[k] = 0
}

aseazadamele vector
nrdame int

s = 0
nrdame = 5
dame(nrdame,aseazadame)


2.dame recursiva( i , n int, x vector){

k int
c bool
k = 1
while k<= n do
x[i] = k
if potcontinua(x,i) then
if i = n then scrie (n,x) else
dama(n+1,n,x)
k = k+1

}



problema discreta a rucsacului {
 max = 20
cm,cc,gg int
c,g,x,ia array[max] int
n , k i int
co bool

function potcontinua(k int){
i[max] int
gr int
gr = 0
for i = 1 1 to k do 
if x[i]=1 then
gr = gr+g[i]
potcontinua=gr<=gg
}

procedure backtrack discret{

k = 1 
x[k] = -1
cm = 0
while k> 0 do
c = f
while (x[k]<1 and !c do
x[k] = x[k]+1
c = potcintinua(k)
if co then
if k = n then
cc = 0
for i = 1 to n do 
if x[i] = 1 then
cc = cc+c[i]
if cc>=cm then
cm = cc
for i = 1 to n do
ia [i]=x[i]
else
k=k+1
x[k]=-1
else
k =k-1
}

read n
for i = 1 to n do
write i rad c[i] write i read g[i]
read gg 
backtrak();
for i = 1 to n do 
if ia[i]=1 then write i , cm
}



problema labirint{

m = 8
n = 10

sir[4] int
mx[m][n] byte

lb mx={{,,,,,,,,,},{},{},{},{},{},{},{}}
ho sir =(,,,)
ve sir = (,,,)

traseu mx
i,j,ii,ji,if,jf byte

procedure scrie(){
i , j int
fori i = 1 to m do
for j = 1 to n do write traseu[i,j]
}

procedure drum(i,j,pas byte){
//backtrack recursiv
in,jn int
vr byte

for vr = 1 to 4 do
in = i+ or[vr]
jn = j+ve[vr]
if in in [1..m] and jn in [i..n] then
if lab[in,jn]=1 and trase[in,jn]=0 then
traseu [in,jn]=pas
if in=if and jn=jf then scrie()
else drum(in,jn,pas+1)
traseu[in,jn] = 0
}

for i = 1 to m do 
for j = 1 to n do
traseu[i,j] = 0
read ii,ji
read if,jf
traseu[ii,ji]=1
drum(ii,ji,2)
}



5. mouse in modul text

tpmouse{
mouseinit() {asm mox ax,0; int $33}
mouseshow() {asm mov ax,1; int $33}
mousehide (){asm moc ax,2; int$33}

mousetdata(buton, x,y int){
bb,xx,yy int
asm mov ax,3; int$33
mov bb,bx;
mov xx,cx
mov yy,dx
buton = bb
x = xx div 8 + 1
y = yy div 8 + 1}

b,x,y int
clrscr
mouseinit
mouseshow
repeat
mousetdata(b,x,y)
if b = 1 then 
mousehide
gotoxy(x,y)
write #178 
mouseshow
until b=2
}


program labirintul magic(){

m

proc. printat(x,y int, sir strig){
gotoxy(x,y)
write sir

function apartine(x,y,x1,y1,x2,y2 int) bool{
apartine = x1<=x and x<=x2 and y1<=y and y<=y2
}

const m = 8; n = 10;
... cxontinuare pag 186-187

de revenit pag 186 labirintul magic
}



6. divide et impera
-recursiva
-rezolvabila direct se rezolva
-daca nu atunci se descompune in mai multe probleme mai simple care se rezolva prin aceasi metoda subprobleme
-solutiile se obtin combinand solutiile subproblemelor

procedura divideetimpera (p,q int, var a...){
if q = p < e then prelucreaza (p,q,a)
else
divide (p,q,m)
divideetimpera(p,m,b)
bivideetimpera(m+1,q,y)
combina(b,y,a)
}


problema sortare prin interclasare{
max = 10
a[max] int
i[max],n [max] int

proc. interclaseaza( start, mijloc, finis int){
b[max] int;
i,j,k int
k = start
i = start
j = mijloc+1
while i <= mijloc and j<=finish do
if a[i]<a[j] then
b[k]=a[i]
i=i+1
k=k+1
else
b[k]=a[j]
j=j+1
k=k+1

if i<= mijloc then
for j =1 to mijloc do
b[k]=a[j]
k=k+1
else
fpr i = i=j to finish do
b[k]=a[i]
k=k+1
for i = start to finish do
a[i]=b[i]
}

pro. sortinterclass(inc,sf int){
ce int
if inc < sf then
ce = (inc + sf) div 2
sortinterclass(ce+1,sf)
sortinterclass(inc,ce,sf)
}

read n
for i = 1 to n do
write i read a[i]
sortinterclass(1,n)
for i = 1 to n do write a[i]

}




quick sort(){

max = 10
vector [max] int
a vector
i,n int

proc poz(s,f int, k int, a vector){
proc schimba (x,y int){...}
i,d,j int
d = 0
i = s
j = f
while i < j do
if a[i]>a[j] then schimba(a[i],a[j]); d=1-d
inc(i,d)
dec(j,1-d)
k=1
}
proc quick(in,sf int, a vector){
k int
if in < sf then
poz(in,sf,k,a)
quick(in,k-1,a)
quick(k+1,sf,a)
}
read n
for i = 1 to n do write i read a[i]
quick(1,n,a)
for i = 1 to n write a[i]
}



7.metoda programarii dinamice

-secventa de decizii - politicii de sistem
-decizia di det sistemul sa evolueze din starea si-1 in si pentru orice i intre 1 si n
-principiul optimalitatii   di de la 1 la n si s0 to sn atunci:
-dk...dn sir optim de decizii sk-1 ...sn inainte
-d1...dk duce din s1 la sk inapoi
-d1..dk si dk+1 ...dn transforma starea sistemului s1 in sk respectiv sk+1 in sn. mixta
-se verifica optimalitatea
-relatii corespunzator formei si programul




problema subsir crescator de lungime maxima{
max = 10
v[max], l [max] int
n,i,k,m,t int

write n read n
for i = 1 to n 
write i read v[i]
l[n]=1
for k =n-1 to n do
if v[i]>=v[k] and l[i]>m then
m=l[i]
l[k]=1+m
m=l[1]
t=1

for k = 1 to n do
if l[k] > m then 
m=l[k]
t-k
write v[t]

for i = t+1 to n do
if  v[i] >=v[t] {!} and l[i]=m-1 then
write v[i]
m=m-1
}
}


problema rafturilor{

pag 194 de revenit.
}



probleme propuse

1.puneti in ordine fireasca cuvinte in propozitie si faze aleator generate si det daca sunt corecte programatic
2.platouri. avem a[0..n-1] cu proprietatea a[0]<=a[1]<=a[n-1]. platorul este o secventa max de lem care contin aceasi val si apartin a iar lungimea nr elem care compun platorul. det lungimea p a celui mai lung platou
3.det pentru vectorul a nr platourilor posibile. panta este secventa de elem consecutive din a ai a[i]=a[i-1]+1. det panta de lungime max.
4.numere pitagoreice. det n int toate tripletele de nr pitagoreice a,b,c deci c^2=a^2+b^2 ai 1<=a, b<=n
5.steagul national olandez. interschimbati elementele u[n] culori pentru a compune steagul
6.tabla de sah. aveti cate o piesa pe tabla de sah pozitionatile ai sa nu se atace: cal, cal si rege, cal si tura, cal si nebun si un nebun
7.cautare binara in vectorul. divide et impera
8.formati toate cuvintele din m litere m<=n cu litere ordonate alfabetic in care o litera apare de cel mult m ori si toate cuvintele posibile dim m litere ordonate alfabetic iar o litera se poate repeta de cel mult k ori
9. avem 5 melodii. in cate moduri pot fi ele prezentate
10.permutari de grad n prin backtracking
11.parcurgeti cu un cal o tabla de sah cu n.m c/l ai sa s treaca prin fieare cauta doar o sg data
12. sa se aseze 2n-2 nebuni pe o tabal; de sahcu n^2 patrate ai nici o pereche de nebuni sa nu se ameninte
13.puneti pe o tabla de sah cu nn patrate cat mai multe dame ai sa n use atace intre ele
14.cautati recursiv si iterativ cunvinte ordonate intrun vector dat
15.avem o tabla de l/h cu n gari de coordonate nr intregi. deupati din ea o arie maxima fara gauricu taieturi verticale si orizontale. divide et impera
16.produs cartezian nxn pentru a,b,c apartin N. cu prop asoc si timpul necesar de axbxc secunde. in ce timp se poate efectua produsul xi,xi+1 de la i la n xi apartinand lui N, n>=3 ?
17.dorim sa plantam o livada . avem mxn patrate de dim egale pe fiecare plantand un sg pom din 4 soiuri diferite.
a.nu trebuie sa avem un soi de acelasi fel pe doua casute invecinae ortogonal sau diagonal
b.fiecae pom sa fie inconjurat de cel putin un pom din toate celelalte trei soiuri. 
c.avem suficienti pomi de fiecare soi ? 
18.mxn matrice zone de inaltime h. un alpinist poate ajunge de la min la max deplasandu-se diagonal sau ortogonal urcand si coborand pe acelasi niveluri pana in varful unuia in munti. aratati solutiile
19.attila si regele. un cal si u nrege pe trabal de sah. avem campuri arse cunoscute incare calul nu are acces iar orice miscare a calului arde campul prin care trece.exista o succesiune de mutari permise cu restrictiile de mai sus prin care calul sa ajunga la rege si sa revina la poz intiala. poz intiala a calului precum si a regelui nu sunt arse















lectia 7 pag 198 algoritmi referitoare la grafuri

index lectia 7

1.notiuni 198
necesitate 198
graf 199
subgraf 199
conexitate 200
tip de graf 200
digraf 201
conexitate in digraf 201
prezentare graf 202
relatii 203

2.explorare graf205
largime 205
adancim 207
componente conexe 207
exploraregraf() 208

3.drum de cost minim in graf 210

probmele economice ce conduc la probleme de drumuri in di graf 210
dijkstra 211
det cost tuturor drumurilor minime 214

4.arbore partial de cost minim
def 216
rezolvare 217
kruskal 218
prim 218
kruskal 220

probleme propuse 221



...
1 Grafuri

dictionar de articole = cuvinte + nume proprii +  informatii/definitii/explicatii/grafice
lista de legaturi intre articole vecine
graf = retea de noduri legate prin curbe de orientare sau nu denumite arce sau muchii

definitie graf

pereche ordonata G = V,E 
V multime nevida finita de varfuri nodurile grafului
E submultime a lui P2 (V) formata din perechi neordonate de varfuri
v,w apartin E cu v,w apartin V adica muchii.
daca e(v,w) apartin E atunci i ngraful G vf sunt adiacente sau e este muchie incidenta cu varfurile v,w sau v,w sunt extremitatile michiei e sau v,w sunt vf vecine.

vecinatatea unui varf v este multimea vecinilor sai 
nr de elem ale acestei multimi se numeste gradul varfului v in graful G
NG(v) = {v ap. V, vw ap.E}, dG(v) = |NG(v)|

varf terminat  are gradul = 1
varf izolat are gradul = 0

t.
G=V,E are m muchii si varfurile vi i la natunci
suma (dG(vi) )= 2*m

Subgraf

graf partial H=V,E' cu G=G insa E'<=E
sub graf H=V'E' cu V'<=V iar E'=E cu extremitatile in multimea de vf V'
Kn graf complet de ordin n= oricare doua vf sunt adiacente cu m=Cn^2 muchii

Conexitate

lant = sir de vf L={vi}, oricare doua vf sunt adiacente
X0 si Xr se numesc extremitatile lantului
r lungimea lantului

drum = lant in care vf sunt distincte doua cate doua

lant elementar cu extremitatile adiacente = ciclu elementar

graf conex = pt rice pereche de vf x,y cu x!=y exiat lantul de la x la y

componente conexe = parti din graf partitionat in subgrafuri conexe ale sale
subgraf conex al lui G = componenta conexa C a lui G  maximal in raport cu prop.
nu exista un lant in G care sa uneasca un vf din C cu un vf care nu apartine lui C


Tip de grafuri

graf bipartit = Vi patitie din vf lui G ai nu exista muchie intre doruile Vi ci doar muchii xy cu xapVi si y apVi+1
G= V1,V2,E

multigraf - daca intre nodurile G apar muchii

ciclu hamiltonian = ciclu elementar al lui G care trece prin toate vf grafului
G este atunci graf hamiltonian

graf eulerian = are lant eulerian inchis cu muchii distincte
lant care trece prin toate muchiile grafului si se intoarce in vf de unde a plecat

T. daca g are n>=3 vf ai dG(v)>=n/2 , ai vapV atunci g este hamiltonian
T.graf fara vf izolate este eulerian daca si numai daca este conex si gradele vf sunt pare

digraf G orientat , o pereche ordonata D = V,A .
V multime vf, noduri
A multime arce, muchii orientate
A = perechi ordonate u,v cu u,v apV

D drum in digraf 
D tare conex drum de la u la v in D
D unilateral conex cu drum de la u la v sau de la v la u in D
D conex daca G suport al sau este conex
G suport este G din D renuntand la orientarea arcelor

D hamiltonian
D eulerian

Prezentare Grafuri. 

-matrice de adiacenta Anxn  n nr vf, Aij=1 daca i,j apEsi Aij= 0 in caz contrar
A[max][max] ;0..1

-adauga muchia ij inseamna A[i,j] = 1 si a[j,i]=1
{
new p
p^ .info = j
p^.urm = graf[i]
graf[i]=p
new p
p^.info = i
p^.urm = graf[j]
graf[j]=p
}
-lista de adiacenta pt fiecare nod se memoreaza lista vecinilor sai

Date de tip Referinta
{
type lista = ^nod
nod = record
info 1..max
urm lista

graf array[1..max] of lista
p lista

}



relatii pag 203{....} de revenit


2.explorarea grafurilor
-din nodul n al G sa se exploreze G avand matricea sa de adiacenta
-se verifica daca exista o muchie/arc intre noduri
-se viziteaza nodurile de pe acelasi drum de la nodul de start
-det comp conexe G

Explorare in largime
-nod initial -> noduri adiacente lui
-se trece la primul nod cu muchii/arce adiacent neexploatat ->nodurile adiacente lui...

Coada Queue Q LIFO last in first out
vector[] IN SPATE SI OUT FATA
primulElement int
ultimulElement int
adauga  indice sfarsit ...
elimina indice inceput

algoritm explorare in largime(s){
marcheaza s
afiseaza s
pune s in Q
cat timp Q nu este vid do
fie v = primul nod din Q
pentru fiecare nod w adiacent lui v do
daca w nu este marcat atunci
marcheaza w
afiseaza w
pune w in Q
}

Explorare in adancime
-marcheaza nodul vizitat initial
-parcurge in adancime recursiv fiecare nod adiacent cu el
-iterativ se utiliz. o stiva

algoritm Explorare in adancime{

daca s nu este marcat atunci
marcheaza s
afiseaza s
pentru fiecare nod v adiacent lui s executa
explorare in adancime(v)
}



det componentelor conexe - explorare

- vf nemarcat si se exploreaza G
-alege primul vf nemarcat si exploreaza G
-repeta pasii cu vf nemarcate

algoritm det compo conexe G{
nrcompo = 0
repeta
 det primul nod v nemarcat
 daca v exista atunci
  exploreaza(v)
  treci la o linie noua
  nrcompo++
 pana cand v nu mai exista
 afiseaza nr de comp conexe nrcompo
}


explorare varfuri pag 208{ ...de revenit}


3. drum de cost minim in G

probleme economice ce conduc la probleme de drumuri in digraf si graf

1.stabilirea var tehnologice optime de prelucrare a unui produs
activitati n - cost partial Ci  = cost total minim
G =V,E, 
arc de cerc - trecerea de la o activitate la alta
digraf sau graf orientat
fara cicluri
arc ij ii este atribuit un cj pt cn+1=0
2.prelucrare produse necesitate.
ordinea de prelucrare, succesiunea corecta
modelare in matematica
G si Pi. arc ij
digraf si drum hamiltonian in D
cost minim de a la nodul 0 la n+1


algoritmul dijkstra

D/G= V,E si C:E->r pt muchii det drumurile minime de cost minim de la nodul i0 la toate nodurile G si costurile acestor dumuri.

-greedy
-selectam nodurile pe rand in n-1 pasi in ordine crescatoare a costului drumului de  la nod start la ele 
-in multimea nodurilor la init exista doar nodul de start
-folosim un vector anterior[] cu legatur ide tip tata unde anterior[i]=k, 
-k nodul anterior nodului i pe drumul minim de la i0 la nodul i
-utiliz d[] si selectat[] cu n componente ai:
- d[i] costul min al drum de la i0 la i
-selectat[i] = treu pt i este selectat

algoritm dijkstra{
select i0
la fiecare pas p din cei n-1 pasi executa
 cauta nodul l, neselectat cu d[i] minim fie acesta k si se selecteaza
 se actualizeaza vectorul d[] pentru acele noduri i neselectate si pentru care d[i] este mai mare decat d[k]+costul muchiei i,k a.i. d[i] devine d[k]+c[k,i] iar anterior[i]=k.
 drumul de la i- lai are ca nod intermediar pe nodul k exact inainte de i
folosing vectorul anterior[] afisati drumurile de la i0 la i al grafului precum si costurile acestor drumuri

}

program dijkstra pag 212 {...} de revenit

Det costurilor tuturor drumurilor minime

in G dat de matricea costurilor C atasata muchiilor se det lungimea drumurilor de cost minim intre oricare doua vf.
-metoda programarii dinamice :fie i,j doua vf ale G daca drumul minim de la i la j trece prin vf intermediar k atunci drumurile de la i la k si de la k la j sunt minime
-matrice recurenta c^0=C obtinem sirul de n matrici c^k obtinuta din matricea c^k-1.
-prin c^k(i,j) se intelege lungimea minima intre i si j , drumul trecand prin primele k vf.
-elem matricei c^k se det astfel: pt fiecare pereche de vf i,j lungimea drumului optim se calculeaza ca minim intre drumul optim deja gasit (drum prin k-1 vf) si suma intre lungimile drumurilor optime care legau vf i de vf k si k de j prin primele k-1 vf date.

c^k(i,j) = c(i,j) pt k =0 iar pt k!=0 min(c^k-1(i,j), C^k-1(i,k)+c^k-1(k,j))

program drumuriminime() pag 215 de revenit


4. arborele partial de cost minim

def

graf conex si fara cicluri = arbore
arbore partial a unui graf conex G = G partial care este arbore
arbore agatat de un vf radacina ai ramurile  atarna in jos
padure = graf neorientat si fara cicluri
comp conexe ale unei paduri = arbori
arborele are n-1 muchii unde n = nr vf
arbori aranjati cu orientarea arcelor O dintre varfuri numite arborescente

5. metoda generala de rezolvare a problemei arborelui partial de cost minim

se cnsidera o problema economica ce conduce la problema arborelui partial de cost minim

retea de comunicatii interne intre sectiile unei intreprinderi. 
necesar materiale , def proiect
det un sistem de legaturi ce trebuie construit ai sa fie racordate oricare sectie la retea com iar costurile sa fie minime

modelarea matematica

G = V,E
C:E->R
C(e) = cost muchie
det arbore partial a lui g, T*
ai C(T*) = min(c(t); C(T) = suma C(ei) i de la 1 la n-1
arborele T va avea n-1 muchii

rezolvare

pas0 familie de arbvori disjuncti T^0={Ti^0} i de la i la nl ti^0 = i/vid
pas k k de la 0 la n-2
 se dispune T^k = (T^ki i de la 1 la n-k) anterior construiti
 se constr T^k+1 ai:
-se alege Ts^k apT^k
-dintre toate muchiile lui G cu extremitatea in Ts ^ k si in V\V(Ts^k) se alege una de cost minim e* = VsVj unde Vj ap V{Tj^k}, j*!=s
-T^k+1 = ({T^k\Ts^k,Tj*^k}) reunit T
T arborescenta obtinuta din Ts^k si Tj*^k la care se adauga muchia e*
-familia T^n-1 constr in pasul n-1 este formata din arborele T1^n-1 , arborele partial minim

puteam avea doia algoritmi in functie de alegerea arborelui Ts^k:
-prim : arbore cu cele mai multe vf din familia de arbori curenta la fiecare pas add cate o muchie a aceluiasi arbore cu o extremitate in el si alta in restul grafului
-kruskal : se alege un arbore cu proprietatea uniti printro muchie cu extremitatile in arbori diferiti . aceasta alegere se reali simplu prin sortarea muchiilor grafului crescator in raport cu costurile


algoritmul lui prim
{
vecin[]
-daca vecin[i]=0 atunci i este arborele partial construit pana in acel moment
-daca vecin[i]<>0 atunci vf i nu este in arbore air muchiile i,v cu v dn arbore i,v0 are costul cel mai mic

punem in arbore vf 1  vecin tuturor vf dn afara arborelui
vecin[1]=0
vecin[i]=1
fie i = 2...n :A

la fiecare din ceilalti n-1 pasi se executa
-det cea mai mica muchie in sensul costului cu un vf in afara arborelui si alt vf in arbore. vecin[i] pentru a avea cea mai mica muchie din cele ce le formeaza i cu vf din arborele deja format, fie aceasta muchie k,vecin[k]: B
-add muchia k,vecin[k] la arbore si se actualizeaza costul :C
-actualizeaza vecin[] :D
= se pune vecin[k]=0
=pt vf ramase i in afara arborelui se ver daca muchia i,k n ueste mai mica decat muchia veche i,vecin[i] care lega pe i de arbore in caz afirmativ punandu-se vecin[i]=k

program prim {pag 218} de revenit
}

algoritmul lui kruskal{
-greedy
-alege muchia de cost minim
-add repetat de n-1 ori muchia de octs minim nealeasa anterior si care nu formeaza cu precedentele un ciclu

radacina/tata[] - memoram vf pt a urmari apartitie cicluri 
radacina arborelui are tata[i] nr de vf din arbore deci n arbori fircare format din cate un nod radacina sa
tata[i] = -1 la inceput :A

daca muchia de ordinul i u,v devine candidata muchiile se iau in ordinea crescatoare costurilor lor :B
se ver carui arbore componenta apartin u  si v : C
avem arb1 si arb2 : D
daca arb1 == arb2 atunci adaugarea muchiei u,v ar duce la aparitia unu iciclu
daca arb<> arb2 atunci adaugam muchia : E
reunim cei doi arbori : F
arborele mic se leaga de cel mai mare
radacna tata a arborelui mai mare este si radacina arbore mai mic : G

program kruskal(){}
pag 220 de revenit
}

probleme propuse

1.circuit hamiltonian
avem o harta se cere sa det toate posibiltatile de a efectua o execursie prin toate orasele de pe harta tracand prin fiecare oras o sg data si intorcandute din pct de plecare
2.colorare vf graf. se da harta administrativa in care sunt puse in evidenta regiunile. sa se coloreze regiunile ai daca doua judete sunt vecine ele sa aiba culori diferite. avem m culori distincte
3.inchidere tranzitiva a unei relatii binare
pe un lac avem n placi de forma dreptunghiulara de coordonate stsus si drjos.
acestea pot acoperi suprafete comune de apa
pe o placa se aseaza o pisica ia pe alta un soarece
poate ajunge pisica la soarele mergand doar pe placi fara a pasi pe apa ?
sa se enumere pe care placi iar daca nu sa se precizeze daca exista o suprafata acoperita de toate placile pe care poate ajunge pisica



 






















lectia 8 pag 223 structuri dinamice de date

cuprins lectia 8 223

1. referinte 223
static si dinamic 223
definire tip 224
utilizare si avantaje 225

2.stiva si coada 227
stiva 228
coada 228
programstiva 230
programcoada 231

3.liste dublu inlantuite 232

4.arbori binari 238
arborescenta grafurilor 238
implementare arbori binari 238

5.derivare formala 241

6. memorare arbori oarecare in arbori binari 250
teorie 250
algoritmul 251

probleme propuse

...


1. referinte 223
static si dinamic 223
definire tip 224
type tr = ^tvd

memorie .. program ... zona var statice ... zona heap

complex{
type pc = ^c
c = record re
im real
r1,r2 pc
r3 ^c
r4 ^char
}

articol{
a,b int
urmator lista}

type lista = ^articol
l lista


utilizare dinamic si avantaje 225

alocare zona mem vardinamice prin new
mem efectiva , depunerea la adresa pregatita a datelor coresp var dinamice
eliberare zona de mem var dinamica prin dispose

testpointer{
px = pc
new(pz)
pz^.re=1.2
pz^.im=5.6
write pz^.re, pz^.im
dispose(pz)

-foloseste spatiu de mem redus
-eficienta util spatiu mem prin reutilizarea sa dupa dispose

persoana{pag226} de revenit
listadinamica{pag227}


2.stiva si coada 227
stiva 228 lifo

celula {info int; prec stiva}
stiva = ^celula;
s stiva

push input
pop output

program stiva{}
coada 228 fifo

celulaq{ inf int, urm pcelula}
pcelula = ^ celulaq
coada = {prim, ultim pcelula}
c coada

programcoada{pag 231 de revenit}

programstiva 230  de revenit
programcoada 231 de revenit

3.liste dublu inlantuite 232

pointer st,fin celule capat
pointer curent celula curenta
element are doi pointeri urm si prec
camp lungime

init
add
ins
del
print

program operatii listadubla inlantuita pag 234 de revenit

4.arbori binari 238
arborescenta grafurilor 238

fie H = V,E digraf sau graf orientat
V0 apV este vf radacina a lui G 
exista de la v0 la v apV un drum
graful suport lui H este graful fara orientarea arcelor
H arborescenta daca are radacina si graful sau suport este arbore
arborescentele sunt denumite tot arbori cu radacina si cu orientarea implicita a muchiilor coresp parurgerii drumului unic de la radacina la vf
fiecare vf are fii vecini urmatori pe drum de la radacina in jos catre frunze /noduri fara fii.
arbore cu cel mult doi fii este un arbore binar


implementare arbori binari 238

arbore binar - pointer catre nodul sau radacina
fiecare nod este un record cu elem {info int, pointer subarbore st si dr}

proprietate:
fiecare nod din arbore este mai mare sau egal cu nodurile din fiul st si mai mic decat nodurile din fiul dr dpdv al informatiei
arborele de cautare si sortare

se pleaca in directia a daca el cautat este mai mic atunci se merge pe fiul st altfel pe cel dr
daca se incearca trecerea dincolo de un nod terminal atunci nil cautare esuata

returnare subarbore avand radacina elementul gasit in arborele in care se cauta{
parcurgere :
- inordine : recursiv, fiul st - radacina -fiul dr = afisare crescatoare a elem 
-postordine: fiul st - fiul dr - radacina
-preordine: radacina- fiul st - fiul dr
}

program arborebinar{pag 240 de revenit}


5.derivare formala 241

expresie derivata matematica memorata in arbore binar sau arbore expresiei derivate

f(x) = E(x) E -expresie
f'(x) = D(x) D - derivata

regulile fundamentale de derivare
(f*g)'=f'*g+f*g' .....

forma poloneza inversa

formam arbore si apoi scriem expresia coresp cu opt binari in forma infixa iar functiile unare in forma prefixa

utiliz doua stive operatori si functii si una a operanzilor
arbori din care se vor forma arbori mai mari
radacina este vf stivei cu operatii la un moment dat

program derivare{} pag245 de revenit

6. memorare arbori oarecare in arbori binari 250
teorie 250

arbore oarecare { info int, nrfii int, vector de pointeri referinte catre fii nodului in cauza

algoritmul transformarearboreoarecareinarborebinar {} pag 251 de revenit

probleme propuse

1.se citesc n int pana la zero. creaza doua liste cu nr negative si pozitive prime
2.lista cu nr intregi pozitive. ceraza o lista care sa contina doar numere pare apoi concateneaza cele doua liste
3.se dau arbori binari. inlocuiti fiecare nod al primului cu cel de al doilea arbore
4.se da un arbore oarecare. info din nod fiind string. constr o lista dublu inlantuita care sa contina string din nodurile arborilor cu lungime impare apoi ordonatile
5. se cietste numele unor persoane. pentru fiecare din ele nr de descenndenti si numele lor. dandu-se numele a doua persoane sa se stabielasca relatia de rudenie intre ele fiu, tata, nepot bunic, frate, nepot unghi, unchi, stranepot, strabunic
6.avem un arbore binar cu litere mici si mar isi cifre. afisati cuvintele ce se pot forma din radacina stiind ca o cifra indica terminarea unui cuvant si blocheaza accesul la subarborele corespunzator









lectia 9 pag 257 fisiere

cuprins lectia 9 fisiere pag 257

1.fisire dos 257
msdos
directoare
program tree{pag 258 de revenit}


path 258
program construiestePath{pag 260 de revenit}

2.despre fisiere 261

3. fisiere text 262
declarare
operatii
write

read 263 

eoln 63
eof 263
program readfila{
f Text
x real
assign(f,'t.txt')
reset (f)
while no eof(f) do
while no eoln(f) do
read(f,x) write x
readln f
close f
}

program triunghiuri{
real a,b,c
text f,g
byte i
assign f ,in.txt
rewrite f
for i =1 to 10 do
read a,b,c
writeln a,b,c
close f
reset f
assign g,out.txt
rewrite g
while not eof(f) do
readln f,a,b,c
if a =b and b=c then g, echilateral
else if a=b or b=c then g,isoscel
else if aa=bb+cc or bb=cc+aa or cc=aa+bb then g, dreptunghic
else g,oarecare
close f
close g
}

rewrite()
fisiere() 264
CONCATENARE()265
{
f,g text
linie, nume1,nume2 string
read nume1 , nume2
assign f,nume1
append f
assign g, nume2
reset g
while not eof g do
readln g,linie
writeln f, linie
close g
close f
writeln nume1

}

parametrii in linia de comanda 266
numeprogram parami
program concat2{} pag 266 de revenit
 
erase 267
rename 267
sortarea fisierelor 267 
program sortare fisier {... de revenit}


4. fisiere cu tip 269
f file of T
program x de revenit 269{...}
declarare 269
operatii 270
write
read

assigncrt 270
controlul op de io 271
program exista fisier de revenit 271{...}
program admitere liceu  de revenit 271{...}

sortarea unui fisier cu tip 277
program de revenit 277{...}

5.fisiere fara tip 279
operatii 280
read
program copy de revenit 281{...}


probleme propuse 281

1. afisati distributia frecventei lungimii cuvintelor aflate in fila separate prin spatiu
2.comparati lnie cu linie doua file afisati si ordinea liniile diferite
3.string s si t si o fila f. scrieti procedura care copiaza continutul lui f in fila g inlocuind peste tot s cu t
4.admin unui top de muzica. file cu tip
5.concatenati doua file oarecare in fila 3 utiliz param din linia de comanda
6.progra magenda telefonica pt gestionarea de persoane cu adrese si nr de tel
op : add,del, find,modif,ordonare,listare
7.multimea persoanelor intre care exista simpatii. se mem intro fila de record , fiecare inreg fiind repr de un cuplu de prieteni. creati o alta fila in care fiecare persoana sa fie insotita de nr sau de prieteni si ordonati fila
8. rez problemele 1 si 4 de la pag 120 utiliz file text si cu tip
9. program pian. permite compunerea de melodii prin actionarea tastelor. salavti melodiilor in file, resrauarai si intrepretati melodiile
play pentru doua melodii simultan
10.creati un program gen norton commander cu op principale pt file si dir











lectia 10 pag 283 biblioteci

cuprins lectia 10 pag 283 biblioteci

1.generalitati 283
crt
dos
uses printer

standard library 283

2.user defined library 284

unit nume ;
interface
implementation
..

forma generala 284
unit 284  de revenit...
vectori 285 de revenit...
observatii 287

3.aplicatii 287
listare la imprimanta a unui program 287 de revenit...
lucrul cu mouse si cursorul in modul text 289 de revenit...
probleme propuse
1.realiz o librarie pt op cu string : inversare, despartire in cuvinte, palindrom, nr de aparitii ale unui caracter sau subsir in string, transformare nr in baza p in q , op matematice utilizand string pentru memorare, ordonare vector string
2.realiz o lib. ce curpinde proc de generare de combinari, aranjamente, permutari, prosu cartezian a mai multo multimi
3. realiz. vgraf unit pentru grafuri

algoritmi si proc din cap 5,6,7,8








lectia 11 pag 292 grafica si animatie

cuprins lectia 11 pag 292 grafica si animatie

1.notiuni introductive 292
clrscr
gotoxy
textcolor
backgoundcolor
read
write
readkey
keypressed
sound
delau
nosound
getmaxx
getmaxy
getmaxcolor
setwritemode
setcolor
line
rectangle
circle
elipse
fillelipse
bar
setfillstyle

procedure opengraphgeneral{...s93 de revenit}

functii grafice 293
drivere 294
vga cod mod grafic cod rezolutie culori pagini

proc. opengraph{
gd,gm int
gd detect
initgraph(gd,gm,path.bgi)
}

gdidemo.pas pag 295 de revenit...

program desenariDiverse{de revenit pag 296
}

io in modul grafic 297 {de revenit}

outtextxy
setextjustify


unit graphic 301 {de revenit}
setviewport
clearviewport
cleardevice

memorarea si reafisarea unei imagini 302
{de revenit}
getimage
putimage
imagesize
getmem
getimage
freemem


2. figuri recursive 303 {de revenit}

3.graficul unei functii 305 {de revenit}

4.pictura cu mouse 308 
mouse in modul grafic 308 {de revenit}
desenator() 311 {de revenit}
desenator2() 312 {de revenit}

5.explorarea fisierelor de caractere chr 314
trip.chr  {de revenit}

formatul fisierelor de caractere chr 314 {de revenit}
proceduri de afisare speciale 318 {de revenit}

6.animatie 322
xorput
setwtitemode

fisiere fli 322
tehnici simple de animatie 322
pingpong 323 {de revenit}
pingpong2 324 {de revenit}
morphing , transformari de imagini 325 {de revenit}
editor de imagine 333 {de revenit}
suprafete 334 {de revenit}
animatie profesionala 336
xor
setwritemode
setactivepage
setvisualpage

formatul si antetul fisierelor fli 336
lectia 12 pag 342 programare orientata pe obiecte

cuprins lectia 12 pag 342 programare orientata pe obiecte

1.introducere 342
poo,oop 342
clase
derivata
mostenire


2.definire de tipuri obiect 344 de revenit
type t=object...

init
clear
display
move

program obiectgrafic pag 347 de revenit

3.derivare 248 de revenit

4.polimorfism 249 de revenit

5.metode virtuale 350 de revenit

6. joc oop 355 de revenit
sound blaster 355 de revenit
afisare rapida 355 de revenit
sound blaster utilizare 357 de revenit
joc navele 358 de revenit

probleme propuse 364

1.problema bilelor
avem mai multe bile pe o matrice 80x25.
culoare,se misca pe diagonala pana intalnesc maginea
unghi incident de deplasare in contact cu marginea
isi continua deplasarea pana la keypressed
simulati cu obiecte, o structuera de date , vector de obiecte sau arrays
2.ferestre. obiecte
3.liste . obiecte lista dubla inlantuita string: init, test vid, add , ins, del,view,lungime,lungime informatie,pozitie start si final, testare pozitie curenta, ordonare crescator si afisare, cautare

solutiiile exercitiilor pag 365



cuprins





lectia 1 365

2.semn{
i=1
p=1
s=0
semn=1
while i<=n do
s = s+semn*p*(2*i-1)
semna=-semn
}
14.perimetrul(l,L){
p=2*(l+L)
}
15.minimN(a,b,c){
if a <b and a<c return a
if b< a and b<c return b
if c<a and c<v return c
}
15.mediearitmetica(a,b){
ma=(a+b)/2
}
18.arie heron(a,b,c){
p= (a+b+c)/2
aria = sqrt(p*(p-a)*(p-b)*(p-c))
19.maxim(a,b){
if a>b then max =a else max=b
}
20.mediageometrica(a,b){
mg=sqrt(a*b)
}
21.calculariepatrat(l){
aria l*l;
}
22.calculamedieN(n,a1..n){
m=0
i=1
while i<=n do
m=m+a1
i=I+1
m=m/n
}
23.detmaxim(n,a1..n){
i=1
max =a1
while i<=n do
if ai >= max then ma=ai
i=i+1
}
24.factorial(n){
p=1
i=1
while i<=n do p=p*i
}
25.copiiidingrup(n,a1..n){
i=1
nf=nb=0
while i<=n do
if ai = true then
nf = nf+1
else
nb=nb+1
i=i+1
}

lectia 2 369 

1.perimetrulsiariatriunghiului{
real a,b,c,p,pe,ar
read a,b,c
pe = a+b+c
p=pe/2
ar = sqrt(p*(p-a)*(p-a)*(p-c)
}

2.viteza{
x0,t0,x,t,v real
read t0,x0,t,x
v=(x-x0)/(t-t0)
}

4.ariacercinfctdediametru{
pi = 3.1415926
real d,a
read d
a = pi* sqr(di/2)
}

6.aria = b*c 
ipotenuza = pitagora

8. vitezatransformari{
int v1,v2
read v1
v2 = round(5/18*v1)
}

11. pret total generat = suma (pret totale/ produs)
pret produse = cantitate * cost unitar


lectia 3 370

IF

1.formeazatriunghi{
real a,b,c
read a,b,c
if a<b+c and b<a+c and c<a+b and a>0 and b>0 and c>0 then write triunghi
else no
}

2.triunghi echilateral{
a,b,c real
ech,dre,iso bool
read a,b,c
if not a<b+c and b<a+c and c<a+b then
'nu'
else
ech = a=b and b=c 
iso = a=b or b=c or c=a
dre = sqr(a) = sqr(b)+sqr(c) or sqr(b)=
sqr(a)+sqr(c) or sqr(c)=sqr(a)+sqr(b))
if ech then ' echilateral
if iso then isosesc'
if drept then 'drept'
}

3.minmax{
a,b,min,max int
read a,b
if a<b then min =a ;max =b
else min=b; max=a
write min, max
}

4.alfabetic{
string n1,n2
read n1,n2
if n1<n2 then write n1, n2
else write n2,n1
}

5.divizibilitate{
a,b1,b2,b3 int
read a, b1, b2, b3
if a mod b1 = 0 and a mod b2 = 0 and a mod b3 = 0 then
write a , 'div cu nr ', b1, b2, b3
}

6.medii{
a,b,m,real
r char
read a,b
read r ;//1 sau 2
if r ==1 then
m = a+b/2 write m
else
if a * b > 0 then
m = sqr(a*b) write m
else 'error'
else delaty() 
}

7.calculperimarie{
a,b,c,ar,pe,p real
r string
read a,b,c
if r = 'aria' then
p = a+b+c/2
aria = sqr(p*(p-1)*(p-b)*(p-c)) write ar
else
p = a+ b + c
write p
}

8.ziua{
n int
read n
if n<a or n>7 then write 'err'
else
if n==1 then write 'luni'.....
}

9.ariecerc{
//a=pi*R*R
//r =l/2*pi
//r = d/2
pi = 3.1415
real a,r,l,d
r char
read r // 1 or 2
if r =1 or r = 'D' then
read d
r = d/2
a = pi*sqr(r)
else
if r=2 or r = 'L' then
read l
r = l/ 2 * pi
a  = pi * sqr(r)
write a
else delay()
}

10.profitintreprindere{
const pm = 50
int ve, ch, pr
read ve, ch
pr = ve - ch
if pr > pm then write '> minim'
else write ' <= minim
}

B.WHILE   

2.joccubilepemasadebiliard{
x,y,dx,dy int
x=40
y=12
dx=1
dy=1
while !keypressed do
gotoxy(x,y)
x=x+dx
y=y+dy
if x=1 or x=80 then dx=-dx
if y=1 or y=25 then dy=-dy
gotoxy(x,y) write 'o' 
delay(100)
}

3.jocdeplasarebila{
x,y int
char tasta
x=40
y=12
gotoxy(x,y)
write 'o'
tasta = '#'
while tasta <> 's' do
tasta = readkey 
gotoxy (x,y)
if tasta 'q' then y=y-1
if tasta 'q' then y=y+1
if tasta 'q' then x=x-1
if tasta 'q' then x=x+1
gotoxy(x,y)
write 'O'

}

4.jocpaleta{ pag 376 de revenit}

6.radical{
eps = 0.0001
x,an,an1 real
read x
an1 = 1
an = (an1+x/an1)/2

while abs(an-an1)>= eps do
an1=an
an=(an1+x/an1)/2
writre an1, sqrt(x)
}


7.maxdinlista{
int i,n,x,max
read n
read x
max = x
i=2
while i<=n do
read x
if x> max then max=x
i = i+1
}

8.deseneazacutii{
x1,x2,y1,y2,c,x,y int
read x1,y1,x2,y2 ,c
x=x1
while x<=x2 do
y=y1
while y<=y2 do
gotoxy(x,y)
y=y+1
x=x+1
}

10.nrprime{
x,d,rad int
pr bool
read x
if x=0 or x=1 then pr = f
else
if x mod 2 = 0 then 
 if x=2 then pr = t
else
pr = f
else
pr = t
d=3
rad = trunch(sqrt(x))
while (d<=rad and pr do
if x mod d = 0
then
pr = f
else
d=d+2
if pr then write 'da'
else write 'nu'
}

11.inversarenr{
n, ni int
read n
ni =0
while n>0 do
ni = 1- * ni + n mod 10
n = n div 10
write ni
}

12.transinbaza2{
n10 int
n2inv, n2 int
read n10
n2inv = 0
while n10 >=2 do  n2inv = 10* n2inv + n10 mod 2 +1
n10= n10 div 2
n2inv = n2inv * 10 + n10 + 1
n2 = 0
while n2inv <> 0 do
n2 = 10 * n2 + (n2inv - 1) mod 10
n2inv = n2inv div 10
write n2
}

 FOR
2.CALCULPRODUS{
n,i int
p rel
read n
p=1
for i = 1 to n do
p=p*(1-1/sqrt(i))
write p
} 

4.calculsumafactoriale{
i,n,s,fact int
read n
s = 0
i=1
fact = 1
for i = 1 to n do
fact = fact * i
s=s+fact
write s
}

5.reducereatermenior{
s = 0
semn = 1
for i = 1 to n do
s = s+ semn * i
semn =- semn
}

6.combinatie{
s = 0
semn = 1
fact = 1
for i =1 to n do
s = s+ semn*fact*i
semn=- semn
fact = fact * i
}

7.afisarenliniipelinia{
fori i =1 to n do
for j = n -i+ 1 downto 1 do
write j
}

8.sirena{
i int
while not keypressed do
for i =1 to 30 do
sound()
for i = 30 downto 1 do sound()
delay
nosound
}

9.piramidanoua{
i,j,n int
read n
for i =1 to n do
for j =1 to n-1 d write ' '
for j = 1 to 2*i-1 do write j
}


10.stangadreapta{
const l=12
c int
for c = 2 to 80 do
gotoxy(c-1,l)
write '  '
gotoxy(c,l)
writer 'o'
delay()
}


REPEAT

1.calculsumacurepeat{
n,i,s int
read n
s = 0
i = 2
repeat s=s+i
i=i+2 until i>2*n
write s
}

2.sunetlaintamplare{
repeat sound(100+random())
delay()
until keypressed
nosound
}

3.sunetdedurataaleatoare{
tasta = '#'
while <> tasta <> 's' do
repeat .. until tasta ='s'
}

4.inmultire{
m,n,i pr int
read m,n
pr = 0
for i = 1 to n do pr = pr+m
write m , n , pr

}


42.numerotarepaginicarte{
22 pagini a.n cu 35 de cifre
10^K pagini sunt necesare 1x9x10^0+2x9x10^1+...kx9x10^k-1
n-1(1x9x10^0+(k0-1)x9x10^k0-2) mod k0 = 0
p=(10^k0-1-1+(k0-1)x9x19^k0-2)div k0
}




lectia 4 383 

enum si subdomeniu

1.luna={ian ,feb , mar , apr, mai, iun, iul, aug, sep, oct, nov, dec}
anotimp={iarna, primavara,vara, toamna}
zi={lu, ma, mi , jo , vi , sa , du}

vactori

4. primelenrprime{
int x[20]
i,nd,nr int
p bool
read n
x[1] = 2
i = 1
nr = 1
repeat
nr = nr + 2
d = 2
p=t
while d<=trunc*sqrt(nr)) and p do
if nr mod d = 0 then p = f
else if d=2 then d=3 else d=d+2
if p then
inc(i)
x[i]=nr
until i = n

for i =1 to n do
write x[i]
}


matrice

2.influent{
i,j,n int
bit m[20][20]
ifl [20] int
max int
read n
for j =1 to n do
ifl[j]=0
for i=1 to n do
write m , i , j 
read m[i][j]
ifl[j]=ifl[j]+m[i][j]

max = ifl[1]
for j = 2 to n do
if ifl[j]> max then max=ifl[j]
write max
for j = 1 to n do
if ifl[j] = max then write j
}


3.patratmagic{
max = 20
int a [max][max]
sl,sd1,sd2,s,i,j,n int
sc [20] int
e bool

read n
s=n*(n*n+1) div 2
for i =1 to n do
for j = 1 to n do
write a , i , j 
read a[i,j]
sd1 = 0
sd2 = 0
for j =1 to n do sc[j]=0
i = 1
e = f
while i<=n and !e do
sl = 0
for j = 1 to n do
if i = j then sd1 = sd1 + A[i,j]
if i = n-j+1 then sd2 = sd2 + a[i,j]
sl = sl+a[i,j]
sc[j]=sc[j]+a[i,j]
if sl<>s or sd1>s or sd2>s then e = t
else inc(i)

if !e then
id sd1<> s pr sd2<>s then e = t
else
j=1
while !e and i<=n do
if sc[j]<>s then e=t else j++
if e then 'nu e'
else 'este'

}

4.pozitiak{
a[10] int
n,i,j,k,mm int
g bool
rean n
for i -1 to n do write a,i read a[i]
read k
i=1 
g = f
while !g and i<=n-1 do
mm=0
for j = 1 to n do if a[j]<a[i] then mm++
if mm=k-1 then g=t else i++
if g then
write i, a[i]
else write k
}

6.magazin{
max = 10
i,j,p,m,jo int
pret [max][max] int
min int
sch int

read m,p

for i = 1 to p do
for j -1 to m do
write i,j
read pret[i,j]
sch = 0
for i = 1 to p do
min = pret[i,1]
jo=1
for j =2 to m do
if pret[i,j] < min then
min = pret[i,j]
jo = j
write i , jo
sch ++
min++
write sch
}

8. c = a+b -c !

9. cmmdcannr{
i,n,a cmmdc int
read n
write a[i]
read cmmdc
for i = 1 to n do
write a, i
read a
while a <> cmmdc do
if a > cmmdc then a = a-cmmdc else cmmdc = cmmdc-1
write cmmdc
}


inregistrare p388
1.an 1000...2000; luna 1..12; zi 1..31; ora 0..23; min, sec 0..59
complex = record re, im : real
punct = record x,y : real

2.amestecarecartidejoc{ pag 389.....}

multime p389

1.multimidisjuncte{
p390 ...
}

recap

2. spatiere ={'.',',',''','"',';','?','!'}

26. impartirepolinoame{p 391}



lectia 5 392 

1.sumaRecursiva s(n int){
if n=1 then s= 1 
else s=s(n-1)+(2*n-1)
}

2.produsRecursiv fp(x vector, n int, pr int){
p int;
if n=1 then pr = x[1]
else
fp(x,n-1,p)
pr=x[n]*p
}

4.reverse(s string){
n byte
rs string
if s='' then reverse=s
else
n = length(s)
rs = copy(s,1,n-1)
reverse = s[n]+reverse(rs)
}

5.apartine (e int, x vector, n int){
if n = 1 then apartine = elem=x[n]
else apartine = elem=x[n] or apartine (e,x,n-1)
}

recap

2a. min(x,y){if x<y then min =x else min = y}
2b. lungime(s string){ lungime=ord(s[0])}
2c. copy(s string, p, l int){
t string, i int
t = ''
i = p
while i<min(p+l,lungime(s)) do
t = t+s[i]
i++
copy=t
}
2d.pos(sub, sir string){
i int
g = bool
i = 1
g = f
while i<= lungime(sir) and !g do
if subsir = copy(sir,i,lungime(sub)) then
g=t
else i++
if g then pos=1 else pos=0
}

3a. aduna(x,y N,z N){
i , aux int
t = 0 
for i = 99 downto 0 do
begin aux= x[i]+y[i]+t0
z[i] =aux mod 10
z[i]= aux div 10
}

3b.succesor(x N, x1 N){
i, aux int
t: 0..1
t =1
i = 99
while i>- 0 do
aux = x[i]+t
z[i]= aux mod 10
t = aux div 10
i--;
}

3c.scade(x,y N, z N){
i int
for i = 0 to 99 do z[i]=9-y[i]
succesor(z,z)
aduna(x,z,z)
}

13. reclama ( de revenit pag 395)





lectia  6 396 
2. platouri {
i =1 
p -1
while i<n do
if a[i-p] = a[i] then p++
i++
}

4.nr pitagoreice

a=2uv
b=uu-vv
c=uu+vv
i<=v<u

6. potcontinua(x vector, k int){
atac bool
atac = x[k] in [x[k-1]-2, x[k-1]+2, x[k-2]-1, x[k-2]+1
potcontinua = ! atac
}

8.generare{} pag 398 de revenit

9.attila si regele


lectia  8 399
1.circuit hamiltonian pag 399 de revenit
2.colorare vf graf...
3.pisicasisoarecele pag 401 de revenit



lectia 9 404
3. inlcuietesiruri pag 404 de revenit


lectia 12 404
3. listeobiect pg 405 de revenit

bibliografie 407



index 409




Comentarii

Postări populare de pe acest blog

program principal cpp

#include "clasa.h" #include <stdio.h> #include <conio.h> #include <stdlib.h> #include <string.h> #define DELAY 9000000 void delay() { for(long i=0;i<DELAY;i++); } //constructor cu initializare de la tastatura BigInt::BigInt() {char x; signed char t[400]; int i; printf("\nNumarul cu semn "); do s=getche(); while((s!='+')&&(s!='-')); n=0; do {x=getche(); t[n]=x-'0'; n++; } while((x>='0')&&(x<='9')); n--; for(i=0;i<n;i++) nr[i]=t[n-i-1]; } //constructor cu initializare prin parametri BigInt::BigInt(char semn,signed char numar[],int dim) {int i; s=semn; n=dim; for(i=0;i<n;i++) nr[i]=numar[n-i-1]; } //transform un int negativ in pozitiv int BigInt::Pozitiv(int x) {int a,vb; a=0; vb=0; while(vb==0) if((x+a)==0) vb=1; else a=a+1; x=a; return x; } //constructor dintr-un nr int obisnuit BigInt::BigInt(int x) {int i; if(x>=0) s='+'…

NUMERE PRIME ALGORITM C++

// NUMERE PRIME ALGORITM C++//  reediting from scratch //on this page is just the study for a next algoritm for generating the parime nr series like Fibonnaci or ....if possibile

74111121313417374414124343447 if u know the red part you can generate the orange part
1 0 1 111112222 1 1 23

o aplicatie php localitati romania

//APLICATIA SE REFERA LA BAZA DE DATE SIRUTA

//dragtable.js


/* dragtable v1.0 June 26, 2008 Dan Vanderkam, http://danvk.org/dragtable/ http://code.google.com/p/dragtable/ \Bsortabledraggable\B Instructions: - Download this file - Add <script src="dragtable.js"></script> to your HTML. - Add class="draggable" to any table you might like to reorder. - Drag the headers around to reorder them. This is code was based on: - Stuart Langridge's SortTable (kryogenix.org/code/browser/sorttable) - Mike Hall's draggable class (http://www.brainjar.com/dhtml/drag/) - A discussion of permuting table columns on comp.lang.javascript Licensed under the MIT license. */ // Here's the notice from Mike Hall's draggable script: //***************************************************************************** // Do not remove this notice. // // Copyright 2001 by Mike Hall. // See http…