Algoritmi si structuri de date.pdf

7/25/2019 Algoritmi si structuri de date.pdf

1/402

ALGORITMI SI STRUCTURI DE DATE 1

Note de Laborator

(uz intern - draft v1.8)

Adrian Rabaea


2/402


3/402

Cuprins

1 Exercitii simple 11.1 Algoritmi elementari . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1.1 Acest numar este prim? . . . . . . . . . . . . . . . . . . . . 11.1.2 Lista numerelor prime . . . . . . . . . . . . . . . . . . . . . 21.1.3 Descompunere n factori primi . . . . . . . . . . . . . . . . 21.1.4 Cel mai mare divizor comun . . . . . . . . . . . . . . . . . . 31.1.5 Cel mai mic multiplu comun . . . . . . . . . . . . . . . . . 41.1.6 Cel mai mic multiplu comun, optimizat . . . . . . . . . . . 51.1.7 Calculul puterilor . . . . . . . . . . . . . . . . . . . . . . . . 71.1.8 Calculul puterilor, optimizat . . . . . . . . . . . . . . . . . 71.1.9 Calculul factorialului . . . . . . . . . . . . . . . . . . . . . . 81.1.10 Calculul combinarilor . . . . . . . . . . . . . . . . . . . . . 81.1.11 Numarul lui Catalan Cn=

1n+1

Cn2n . . . . . . . . . . . . . . 101.1.12 Produsul a doua polinoame . . . . . . . . . . . . . . . . . . 11

1.1.13 Schema lui Horner . . . . . . . . . . . . . . . . . . . . . . . 121.1.14 Calculul valorii unui polinom . . . . . . . . . . . . . . . . . 131.1.15 Puterea unui polinom . . . . . . . . . . . . . . . . . . . . . 131.1.16 Derivata unui polinom . . . . . . . . . . . . . . . . . . . . . 141.1.17 Derivata de ordinulk a unui polinom . . . . . . . . . . . . . 151.1.18 Derivata de ordinulk a functiei f(x) =Pn(x)ex . . . . . . 161.1.19 Ordinul unei permutari . . . . . . . . . . . . . . . . . . . . 171.1.20 Suma puterilor radacinilor ecuatiei de grad 2 . . . . . . . . 191.1.21 Suma puterilor radacinilor ecuatiei de grad 3 . . . . . . . . 191.1.22 Sirul lui Fibonacci si proportia de aur . . . . . . . . . . . 201.1.23 Descompunere Fibonacci . . . . . . . . . . . . . . . . . . . 211.1.24 Numarul permutarilor idempotente . . . . . . . . . . . . . . 221.1.25 Fractie continua: determinarea coeficientilor . . . . . . . . . 22

1.1.26 Fractie continua: determinarea fractiei initiale . . . . . . . . 231.1.27 Generare polinom cu radacini fractionare date . . . . . . . 241.1.28 Radacini rationale . . . . . . . . . . . . . . . . . . . . . . . 251.1.29 Numarul divizorilor unui numar natural . . . . . . . . . . . 261.1.30 Functia lui Euler . . . . . . . . . . . . . . . . . . . . . . . . 27

iii


4/402


5/402

2.2.7 Numerele lui Bell cu numere mari . . . . . . . . . . . . . . 84

2.2.8 Partitiile unui numar natural cu numere mari . . . . . . . . 882.2.9 Recurenta Catalan Cn =n

k=1 Ck1Cnk unde C0 = 1, cunumere mari . . . . . . . . . . . . . . . . . . . . . . . . . . 90

2.2.10 Recurenta: En = E2En1+E3En2+ ... + En1E2 undeE1= E2= 1 cu numere mari . . . . . . . . . . . . . . . . . 93

2.2.11 Calcul f(n) =n

k=0 CknFk cu numere mari . . . . . . . . . 96

2.2.12 Calcul f(n) =n

k=0 Ckn2

kFk cu numere mari . . . . . . . . 99

2.2.13 Fractie continua: determinarea fractiei initiale cu numere mari103

2.2.14 Numarul permutarilor idempotente, cu numere mari . . . . 105

3 OJI 2002 clasa a IX-a 109

3.1 Poarta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

3.1.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 1103.1.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 110

3.1.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 110

3.2 Mouse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

3.2.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 113

3.2.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 113

3.2.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 113


4.1 Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117


4.1.2 Rezolvare detaliata * . . . . . . . . . . . . . . . . . . . . . . 1194.1.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 119

4.2 Numere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121



4.2.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 122


5.1 Expresie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125



5.1.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 1275.2 Reactivi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132



5.2.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 134


6/402

6 OJI 2005 clasa a IX-a 1376.1 Numere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

6.1.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 1386.1.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 1386.1.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 138

6.2 MaxD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1396.2.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 1406.2.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 1416.2.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 141

7 OJI 2006 clasa a IX-a 1457.1 Flori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145


7.1.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 1477.2 Pluton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150


8 ONI 2000 clasa a IX-a 1578.1 Algoritm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

8.1.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 1608.1.2 Rezolvare detaliata * . . . . . . . . . . . . . . . . . . . . . . 1608.1.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 162

8.2 Cod de identificare . . . . . . . . . . . . . . . . . . . . . . . . . . . 164


8.3 Comoara . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1698.3.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 1708.3.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 1718.3.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 171

8.4 Cuburi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1738.4.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 1758.4.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 1758.4.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 175

8.5 Fibo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1778.5.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 178

8.5.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 1788.5.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 178

8.6 Kommando . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1818.6.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 1838.6.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 183


7/402

8.6.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 183

9 ONI 2001 clasa a IX-a 1959.1 Ferma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195


9.2 Fractii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2009.2.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 2009.2.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 2019.2.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 201

9.3 Tablou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2029.3.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 2029.3.2 Rezolvare detaliata * . . . . . . . . . . . . . . . . . . . . . . 203

9.3.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 2049.4 Competitie dificila . . . . . . . . . . . . . . . . . . . . . . . . . . . 205


9.5 Cuvinte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2089.5.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 2099.5.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 2099.5.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 209

9.6 Grup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2119.6.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 2129.6.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 213

9.6.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 213

10 ONI 2002 clasa a IX-a 21510.1 Pentagon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215


10.2 Pod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21810.2.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 21910.2.2 Rezolvare detaliata * . . . . . . . . . . . . . . . . . . . . . . 22110.2.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 225

10.3 Suma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22910.3.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 230

10.3.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 23110.3.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 231

10.4 Becuri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23210.4.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 23310.4.2 Rezolvare detaliata * . . . . . . . . . . . . . . . . . . . . . . 233


8/402

10.4.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 23810.5 D iscuri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242


10.6 Cod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24610.6.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 24710.6.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 24810.6.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 248

11 ONI 2003 clasa a IX-a 25111.1 Seti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251


11.1.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 25211.2 S caune . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256


11.3 C ircular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26111.3.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 26211.3.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 26311.3.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 263

11.4 C riptare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26611.4.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 26811.4.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 268

11.4.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 27011.5 M asina . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27111.5.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 27211.5.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 27311.5.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 273

11.6 Operatii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27411.6.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 27511.6.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 27611.6.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 276

12 ONI 2004 clasa a IX-a 27912.1 C oduri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279


12.1.2 Rezolvare detaliata * . . . . . . . . . . . . . . . . . . . . . . 28012.1.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 281

12.2 L ogic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28112.2.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 28312.2.2 Rezolvare detaliata * . . . . . . . . . . . . . . . . . . . . . . 283


9/402

12.2.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 28712.3 Poligon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289

12.3.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 29012.3.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . 29112.3.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 291

12.4 S ablon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29512.4.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 29612.4.2 Rezolvare detaliata * . . . . . . . . . . . . . . . . . . . . . . 29712.4.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 297

12.5 S ir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29912.5.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 30012.5.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 30012.5.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 300

12.6 Snipers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30112.6.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 30212.6.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 30312.6.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 303

13 ONI 2005 clasa a IX-a 30713.1 Bifo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307


13.2 Romeo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31713.2.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 31913.2.2 Rezolvare detaliata * . . . . . . . . . . . . . . . . . . . . . . 321

13.2.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 32113.3 Seceta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322


13.4 Biblos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33513.4.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 33613.4.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 33713.4.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 337

13.5 Joc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34013.5.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 34213.5.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 344

13.5.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 34413.6 Pal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350



10/402

x

14 ONI 2006 clasa a IX-a 35714.1 Factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357


14.2 L imba j . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36014.2.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 36114.2.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 36214.2.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 362

14.3 Panouri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36814.3.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 36914.3.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 37014.3.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 370

14.4 Pereti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374


14.5 Sant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37714.5.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 37914.5.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 37914.5.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 379

14.6 Zumzi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38114.6.1 Indicatii de rezolvare * . . . . . . . . . . . . . . . . . . . . . 38314.6.2 Rezolvare detaliata . . . . . . . . . . . . . . . . . . . . . . . 38414.6.3 Codul sursa * . . . . . . . . . . . . . . . . . . . . . . . . . . 385


11/402

Capitolul 1

Exercitii simple

1.1 Algoritmi elementari

1.1.1 Acest numar este prim?

import java.io.*;

class nrPrim {

public static void main (String[]args) throws IOException {long x;

BufferedReader br = new BufferedReader(

new InputStreamReader(System.in));

System.out.print("x = "); x=Long.parseLong(br.readLine());

if(estePrim(x)) System.out.println(x+" este PRIM");

else System.out.println(x+" NU este PRIM");

}

static boolean estePrim(long nr) {

if((nr==0)||(nr==1)) return false;

if((nr==2)||(nr==3)) return true;

if(nr%2==0) return false;

long d=3;while((nr%d!=0)&&(d*d


12/402

2 CAPITOLUL 1. EXERCITII SIMPLE

1.1.2 Lista numerelor prime

import java.io.*;

class NumerePrimeLista

{

public static void main(String[]args)throws IOException

{

BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));

int n;

System.out.println("Dim. lista:"); n=Integer.parseInt(stdin.readLine());

int[] prim=new int[n];

prim[0]=2;

prim[1]=3;

int k=1; // pozitia in lista a ultimului numar prim plasat

int nr=5; // nr este urmatorul numar prim ?

int j,primj;// parcurg lista

while(k


13/402

1.1. ALGORITMI ELEMENTARI 3

static void descFact(long nr)

{

long d=2;

if((nr==0)||(nr==1))

{

System.out.println(nr);

return;

}

while(nr%d==0)

{

System.out.print(d+" ");

nr=nr/d;

}

d=3;while((d*d


14/402


}

static long cmmdc(long a, long b)

{

long d,i,c,r;

if (a>b) {d=a; i=b;} else {d=b; i=a;}

while (i != 0)

{

c=d/i; // nu se foloseste !

r=d%i;

d=i;

i=r;

}

return d;

}}

1.1.5 Cel mai mic multiplu comun

import java.io.*;

class Cmmmc1

{

public static void main (String[]args) throws IOException

{

long x,y;BufferedReader br = new BufferedReader(



System.out.print("y = "); y=Long.parseLong(br.readLine());

System.out.println("cmmmc("+x+","+y+") = "+cmmmc(x,y));

}

static long cmmmc(long a, long b)

{

int d;

int nrda,nrdb;

long p,pa,pb;

p=1;

d=2;

nrda=0; pa=1;

while(a%d==0) { nrda++; pa=pa*d; a=a/d;}


15/402


nrdb=0; pb=1;

while(b%d==0) { nrdb++; pb=pb*d; b=b/d;}

if(pa+pb>0)

if(pa>pb) p=p*pa; else p=p*pb;

d=3;

while((d*dpb) p=p*pa; else p=p*pb;

d=d+2;}

System.out.println("p="+p+" si A RAMAS a="+a+" b="+b);

if(a==b) p=p*a; // ex: a=2*17 b=3*17

else p=p*a*b; // ex: a=2*3 b=2*5

return p;

}

}

1.1.6 Cel mai mic multiplu comun, optimizat

import java.io.*;

class Cmmmc2

{


{

long x,y;




System.out.print("y = "); y=Long.parseLong(br.readLine());

// x=2*2*2;

// y=2*3*3*3*3;

System.out.println("cmmmc("+x+","+y+") = "+cmmmc(x,y));}

static long cmmmc(long a, long b)

{


16/402


int d;

int nrda,nrdb;

long p,pa,pb,maxab, minab;

p=1;

d=2;

nrda=0; pa=1;

while(a%d==0) { nrda++; pa=pa*d; a=a/d;}

nrdb=0; pb=1;

while(b%d==0) { nrdb++; pb=pb*d; b=b/d;}

if(pa+pb>0)

if(pa>pb) p=p*pa; else p=p*pb;

d=3;

while((d*dpb) p=p*pa; else p=p*pb;

d=d+2;// ex: a=2*3 b=2*9 ???

}

// System.out.println("Ultimul divizor incercat este d="+max(2,(d-2)));

// System.out.println("p="+p+" si A RAMAS a="+a+" b="+b);

maxab=max(a,b);minab=min(a,b);

if(maxab>1) // a ramas ceva in a sau b

if(a==b) p=p*a; // ex: a=2*17 b=3*17

else if(maxab%minab!=0) p=p*a*b; // ex: a=2*3 b=2*5

else// ex: a=2*3 b=2*9

{

p=p*minab;

a=a/minab;

b=b/minab;

p=p*a*b; // cel mai mic este 1

}

return p;

}

static long max(long a, long b) { if(a>b) return a; else return b; }

static long min(long a, long b) { if(a


17/402


1.1.7 Calculul puterilor

import java.io.*;

class Putere

{


{

int a,n;



System.out.print("a = "); a=Integer.parseInt(br.readLine());

System.out.print("n = "); n=Integer.parseInt(br.readLine());

System.out.println("putere("+a+","+n+") = "+putere(a,n));

}

static long putere(int a,int n)

{

int k;

long p;

p=1;

for(k=1;k


18/402


{

int k;

long p, a2k;

p=1;

a2k=a;

while(n!=0)

{

if(n%2==1) p=p*a2k;

a2k=a2k*a2k;

n=n/2;

}

return p;

}

}

1.1.9 Calculul factorialului

import java.io.*;

class Factorial

{


{

int n;


new InputStreamReader(System.in));System.out.print("n = "); n=Integer.parseInt(br.readLine());

System.out.println(n+"! = "+factorial(n));

}

static long factorial(int n)

{

int k;

long p;

p=1;

for(k=1;k


19/402


import java.io.*;

class Combinari

{


{

int n,k;




System.out.print("k = "); k=Integer.parseInt(br.readLine());

System.out.println("combinari("+n+","+k+") = "+comb(n,k));

}

static long comb(int n,int k)

{int i,j,d;

if(k>n/2) k=n-k; // o mica optimizare !

int[] x=new int[k+1];

int[] y=new int[k+1];

for(i=1;i


20/402


}

return d;

}

}

1.1.11 Numarul lui Catalan Cn= 1n+1

Cn2n

import java.io.*;

class Catalan

{


{

int n,k;BufferedReader br = new BufferedReader(



System.out.println("catalan("+n+") = "+catalan(n));

}

static long catalan(int n)

{

int i,j,d;

int[] x=new int[n+1];

int[] y=new int[n+1];

for(i=2;i


21/402


if(a>b) {d=a; i=b;} else {d=b; i=a;}

while (i != 0)

{


r=d%i;

d=i;

i=r;

}

return d;

}

}

1.1.12 Produsul a doua polinoame

class ProdusPolinoame

{

public static void main(String[] args)

{

int gradp=1;

int gradq=2;

int[] p=new int[gradp+1];

int[] q=new int[gradq+1];

p[gradp]=1;

p[0]=1;afisv("p = ",p);

q[gradq]=1;

q[1]=2;

q[0]=1;

afisv("q = ",q);

int[] pq=prodPol(p,q);

afisv("p * q = ",pq);

}

static int[] prodPol(int[] a, int[] b)

{int i,j;

int na=a.length-1;

int nb=b.length-1;

int nc=na+nb;


22/402


int[] c=new int[nc+1];

for(i=0;i=0;i--)

{

System.out.print("p["+i+"]=");

p[i]=Integer.parseInt(br.readLine());

}

System.out.print("a = ");

int a=Integer.parseInt(br.readLine());

int[] q=new int[n+1];

q[n]=p[n];for(int k=n-1;k>=0;k--) q[k]=q[k+1]*a+p[k];

for(int k=n;k>0;k--) System.out.print(q[k]+" ");

System.out.println("\n"+"r="+q[0]);


23/402


}// main

}// class

1.1.14 Calculul valorii unui polinom

import java.io.*; // in schema lui Horner restul=r=p(a)

class ValoarePolinom

{

public static void main(String[] args) throws IOException

{

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

System.out.print("Gradul polinomului P(X): ");

int n=Integer.parseInt(br.readLine());int[] p=new int[n+1];

for(int i=n;i>=0;i--)

{

System.out.print("p["+i+"]=");

p[i]=Integer.parseInt(br.readLine());

}

System.out.print("a = ");

int a=Integer.parseInt(br.readLine());

int r=p[n];

for(int k=n-1;k>=0;k--) r=r*a+p[k];

System.out.println("p("+a+")="+r);

}

}

1.1.15 Puterea unui polinom

class PuterePolinom

{


{

int gradp=1; // gradul polinomului p

int m=15; // puterea la care se ridica polinomul p

int k;

int[] p=new int[gradp+1];

int[] pk={1};

p[gradp]=1;


24/402


p[0]=1;

afisv("p^"+0+" = ",pk);

for(k=1;k


25/402


p[gradp]=2;

p[2]=3;

p[1]=4;

p[0]=5;

afisv("p = ",p);

afisv("p = ",derivPol(p));

}

static int[] derivPol(int[] a)

{

int i,j;

int na=a.length-1; // gradul polinomului

int nb=na-1; // gradul derivatei

int[] b=new int[nb+1];for(i=1;i=0;i--) System.out.print(x[i]+" ");

System.out.println();}

}

1.1.17 Derivata de ordinul k a unui polinom

class Derivata_kPolinom

{


{

int gradp=3; // gradul polinomului p

int[] p=new int[gradp+1];int k=3; // ordinul derivatei

p[gradp]=2;

p[2]=3;

p[1]=4;


26/402


p[0]=5;

afisv("p = ",p);

int[] pk=p;

afisv("p^("+0+") = ",pk);

for(int i=1;i


27/402


p[gradp]=1;

p[0]=0;

afisv("p = ",p);

long[] pk=p;

afisv("f^("+0+") ==> q = ",pk);

for(int i=1;i


28/402


{

int r,i;

StreamTokenizer st = new StreamTokenizer(new BufferedReader(

new FileReader("permutare.in")));

PrintWriter out = new PrintWriter(new BufferedWriter(

new FileWriter("permutare.out")));

st.nextToken();n=(int)st.nval;

p=new int[n+1];

pr=new int[n+1];

for(i=1;i


29/402


}

return ok;

}

}

1.1.20 Suma puterilor radacinilor ecuatiei de grad 2

class SnEc2

{


{

int a,b,c;

int n=10;int s,p;

a=1;

b=1;

c = 2 ; / / 1 1 2 = = > x ^ 2 + x + 1 = 0

s=-b/a;

p=c/a;

long[] ss=new long[n+1];

ss[1]=s;

ss[2]=s*s-2*p;

int k;

for(k=3;k


30/402


c=11;

d=-6; // ==> x^3-6x^2+11x-6=0 ==> 1, 2, 3

s1=-b/a;

s2=c/a;

s3=-d/a;

s[0]=3;

s[1]=s1;

s[2]=s1*s1-2*s2;

System.out.println("s1="+s1+" s2="+s2+" s3="+s3);

for(k=3;k


31/402


}

1.1.23 Descompunere Fibonacci

import java.io.*;

class DescompunereFibonacci

{

static int n=92; // cel mai mare numar Fibonacci care incape pe LONG!

static long[] f=new long[n+1];


{

long x; // x=1234567890123456789L; cel mult!BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

System.out.print("x = ");

x=Long.parseLong(br.readLine());

long y;

int iy;

int k;

int nrt=0;

f[0]=0;

f[1]=1;

f[2]=1;

for(k=3;k


32/402


}

}

1.1.24 Numarul permutarilor idempotente

import java.io.*; // numarul permutarilor idempotente p^2 = e in S_n

class PermIdempotente

{

static int n;


{

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

System.out.print("n = "); n = Integer.parseInt(br.readLine());

int[] np = new int[n+1];

np[0]=1;

np[1]=1;

for(int i=2;i


33/402


while(i!=0) // pentru calculul dimensiunii vectorului b

{

c=d/i; r=d%i; n++; d=i; i=r;

}

int[] b=new int[n];

int poz=0;

d=p; i=q;

while(i!=0) // pentru calculul coeficientilor vectorului b

{

c=d/i; r=d%i; b[poz]=c; poz++; d=i; i=r;

}

return b;

}

}

1.1.26 Fractie continua: determinarea fractiei initiale

class FractieContinua2

{


{

int p,q;

int[] b={2,1,2,1,3};

p=calcA(b); q=calcB(b);

System.out.println(p+"/"+q);}//main

static int calcA(int[] b)

{

int n=b.length-1;

int[] A=new int[b.length];

A[0]=b[0];

A[1]=b[0]*b[1]+1;

for(int k=2;k


34/402


B[0]=1;

B[1]=b[1];

for(int k=2;kb_i X - a_i

{

int n=a.length;

int[] p={-a[0],b[0]},// p=b[0] X -a[0]q={13,13}; // q=initializat "aiurea" pentru dimensiune !

// afisv(p);

for(int k=1;k


35/402


int i,j,k;

for(k=0;k


36/402


{

int n=a.length-1,k,s=0;

for(k=0;k


37/402


p=p*(nrd+1);

d=3;

while(d*d1) p*=2;

return p;

}

}

1.1.30 Functia lui Euler

class EulerFunctia

{

public static void main(String [] args)

{

int n=12;

System.out.println(n+" --> "+fi(n));

}

static int fi(int n)

{

int card=0;

for(int k=1;kb) { d=a; i=b; } else { d=b; i=a; }while(i!=0) { c=d/i;r=d%i; d=i; i=r; }

return d;

}

}


38/402


1.1.31 Formula de calcul pentru functia lui Euler

class EulerCalcul

{


{

int n=12;

System.out.println(n+" --> "+calculEuler(n));

}

static int calculEuler(int nr)

{

int d;

int nrd;int p=1,nrr=nr;

d=2;

nrd=0;

while(nr%d==0)

{

nrd++;

nr=nr/d;

}

if(nrd>0) { p=p*(d-1); nrr=nrr/d; }

d=3;while(d*d0) { p=p*(d-1); nrr=nrr/d; }

d=d+2;

}

if(nr>1) { p=p*(nr-1); nrr=nrr/nr; }

return p*nrr;

}

}

1.1.32 Ghiceste numarul

Se alege un numar natural ntre 1 si n. Calculatorul ntreaba cum este fatade mijlocul extremelor curente (de la fiecare pas). Numarul se ghiceste n maxim1 + [log2(n)] pasi (ntrebari).


39/402


import java.io.*;

class GhicesteNr

{

static int nrIncercare=0;


{

int n=-1; // alege un numar intre 1 ... n

while (n


40/402


{

scrieText("Cum este fata de "+m+" ?");

scrieText("1 = mai mic; 2 = mai mare; 3 = EGAL raspuns: ");

raspuns = getInt();

}

return raspuns;

} // propun()

static void scrieText(String s)

{

System.out.print("\n"+s);

System.out.flush();

}

public static String getString() throws IOException{

InputStreamReader isr = new InputStreamReader(System.in);

BufferedReader br = new BufferedReader(isr);

String s = br.readLine(); return s;

} // getString()

public static int getInt() throws IOException

{

String s = getString();

return Integer.parseInt(s);

}

}

1.1.33 Calculul functiei arcsin

Dezvoltarea n serie a functiei este urmatoarea:

arcsin(x) = x +1

2

x3

3 +

1

2

3

4

x5

5 + ... +

1

2

3

4...

2n 32n 2

x2n1

2n 1+ ...= t1+ t2+ t3+ ... + tn+ ...

Se poate observa ca:

t1= x si tk+1= x

x

(2k

1)

(2k

1)

2k(2k+ 1) tk pentru k1

Vom calcula o suma finita (adaugam termeni pana cand modulul diferenteia doi termeni consecutivi este inferior unei valori date si fara a depasi numarulnMax de termeni din serie).


41/402


class ArcSinus

{

static double dif;

static int k;


{

double x=Math.sin(Math.toRadians(-60)),eps=1.0e-15;

int nMax=100000;

System.out.println("arcsin("+x+") = "+

Math.toDegrees(arcSinus(x,eps,nMax))+"\t"+dif+"\t"+k);

}

static double arcSinus(double x, double eps, int nMax)

{double tk=x,s=tk,tk1=0;

dif=0;

k=1;

do

{

tk1=tk*x*x*(2*k-1)*(2*k-1)/(4*k*k+2*k);

s+=tk1;

dif=Math.abs(tk1-tk);

tk=tk1;

k++;

} while((dif>eps)&&(kb>0

{ // inlocuiesc resturile de la sfarsit spre inceput !!!

static final int NMAX=20;

static int[] r = new int[NMAX],

c = new int[NMAX],

alfa = new int[NMAX],beta = new int[NMAX];


{


42/402


int a=221,b=29;

//int a=614, b=513;

if(a>b) {r[0]=a; r[1]=b;} else {r[0]=b; r[1]=a;}

int k=0;

do

{

k++;

c[k]=r[k-1]/r[k];

r[k+1]=r[k-1]%r[k];

System.out.println(r[k-1]+"="+c[k]+"*"+r[k]+"+"+r[k+1]);

} while (r[k+1]!=0);

int cmmdc=r[k];

System.out.print("cmmdc("+a+","+b+") = "+cmmdc);

int n=k-1;

alfa[n]=1;beta[n]=-c[n];

for(int i=n-1;i>=1;i--)

{

alfa[i]=beta[i+1];

beta[i]=alfa[i+1]-c[i]*beta[i+1];

}

System.out.println(" = ("+alfa[1]+")*"+r[0]+" + ("+beta[1]+")*"+r[1]);

}

}

/* OBS:

initializari: r[0]=max(a,b); r[1]=min(a,b);algoritm: r[0] = r[1]c[1]+r[2]

r[1] = r[2]c[2]+r[3]

r[2] = r[3]c[3]+r[4]

...

r[n-2] = r[n-1]c[n-1]+r[n] cmmdc(a,b)=r[n]

r[n-1] = r[n]c[n]+0 (gata!!!) ===============

*/

1.2 Calculul unor sume si produse

1.2.1 Calculul functiei arcsin


43/402

1.2. CALCULUL UNOR SUME SI PRODUSE 33

1.2.2 Calcul f(n) =

n

k=012kCnn+k

class SP01

{

public static void main(String[]args)

{

int n=10;

int k, s, p;

s=0;

for(k=0;k


44/402


}

p=1;

for(i=1;ib) {d=a;i=b;} else {d=b;i=a;}

while (i!=0) { c=d/i; r=d%i; d=i; i=r; }

return d;

}

}

1.2.3 Calcul f(n) =

n1k=0C

k

n1nn1k(k+ 1)!

class SP02

{


{

int n=4;

int s, p, k;

s=0;

for(k=0;kn/2) k=n-k;

int i,j,d;

int[] x=new int[k+1];int[] y=new int[k+1];

for(i=1;i


45/402


for(i=1;i


46/402


{


{

int n=5;

int s, p, k;

s=0;


int i,j,d;



for(i=1;i


47/402


static int putere(int a,int n)

{

int k;

int p;

p=1;

for(k=1;k=3;k--)

{

xn=-k*xv;

s+=xn;xv=xn;

}

System.out.println("f("+n+") = "+s);

System.out.println("MaxLong= "+Long.MAX_VALUE);

}

}

1.2.6 Calcul s(n,m) =

m1k=0 C

k

m(1)k(m k)n

s(n, m) reprezinta numarul functiilor surjective f :{1, 2,...,n} {1, 2,...,m}.

class SP05{

public static void main (String[]args)

{

int n;


48/402


int m=5;

int k, s;

for(n=1;n


49/402


if(a>b) {d=a;i=b;} else{d=b;i=a;}

while(i!=0){ c=d/i; r=d%i; d=i; i=r; }

return d;

}

}

1.2.7 Calcul f(m,n,1,...,n) = (C1m

)1 ...

Cnm+n1

n

class SP06

{


{

int m=2;int n=3;

int k;

int[] lam=new int[n+1];

int rez;

lam[1]=1;

lam[2]=3;

lam[3]=2;

rez=1;

for(k=0;k


50/402


for(j=1;j


51/402


for(i=1;i


52/402


1.2.9 Calcul f(n) = 12n

n

k=0(1)kCkn2k(2n k)!

class SP08

{


{

int n=4;

int s,k;

s=0;

for(k=0;k


53/402


x[i]=x[i]/d;

if(y[j]==1) break;

}

rez=1;


while(i!=0) { c=d/i; r=d%i; d=i; i=r; }

return d;

}}

1.2.10 Numerele Stirling de speta a II-a

Fie S(n, m) numarul modalitatilor de partitionare a unei multimi cu n ele-mente n m submultimi nevide (de exemplu, plasare numerelor{1, 2,...,n} n mcutii identice si nenumerotate astfel ncat nici o cutie sa nu fie goala!). Acest numarndeplineste urmatoarea relatie de recurenta:

S(n + 1, m) = S(n, m) + mS(n, m) unde S(n, n) = S(n, 1) = 1.

Scrieti un program care sa calculeze, de exemplu, S(11, 2).

class SP09

{


{

int n=11,m=2; // n >= m

int i, j, jmin;

long t1,t2;

int[][] a=new int[n+1][m+1];

t1=System.currentTimeMillis();

for(i=1;i


54/402


}

System.out.println(a[n][m]);


System.out.println("Timp = "+(t2-t1));

}

static int min(int a, int b)

{

if(a


55/402


static int comb(int n,int k)

{

int i,j,d;

int rez;



for(i=1;i


56/402



{

int n=12,m=3;

int[][] p=new int[n+1][n+1];

int nsol;

int i,j,k;

p[1][1]=1;

for(i=2;i


57/402


class SP12

{


{

int n=17,i,k;

int p;

int s;

int[] c=new int[n+1];

c[0]=1;

for(i=1;i


58/402


s=s+p;

}

e[i]=s;

System.out.println(i+" : "+e[i]);

}

}

}

1.2.15 Numerele Stirling de speta a II-a

Fie S(n, m) numarul modalitatilor de partitionare a unei multimi cu n ele-mente n m submultimi nevide (de exemplu, plasare numerelor{1, 2,...,n} n mcutii identice si nenumerotate astfel ncat nici o cutie sa nu fie goala!). Acest numar

se poate calcula cu formula:

S(n, m) = 1

m!

m1k=0

(1)kCkm(m k)n.


class SP14

{


{

int n=11,m=2;

int s, p, k;s=0;


int i,j,d;




59/402


for(i=1;i


60/402


1.2.16 Calculf(n) =

n

k=0Ck

nFk

class SP15

{

static int n=15;

static int[] f=new int[n+1];


{

int k,i;

f[0]=0;

f[1]=1;

for(k=2;k


61/402


if(y[j]==1) break;

}

rez=1;


while(i!=0) { c=d/i; r=d%i; d=i; i=r;}

return d;

}

}

1.2.17 Calculf(n) =

n

k=0Ck

n2kFk

class SP16

{

static int n=15;

static int[] f=new int[n+1];


{ int k,i;

f[0]=0;

f[1]=1;

for(k=2;k


62/402


}

static int comb(int n,int k)

{

if(k>n/2) k=n-k;

int i,j,d;

int rez;



for(i=1;i


63/402

Capitolul 2

Simularea operatiilor cu

numere mari

2.1 Operatii cu numere mari

2.1.1 Vectorul cifrelor unui numar

class NrV

{ public static void main(String[] args)

{

int nr=232425;

int[] x=nrv(nr);

afisv(x);

}

static void afisv(int[] x)

{

int nx=x.length;

int i;

for(i=nx-1;i>=0;i--) System.out.print(x[i]);

System.out.println();}

static int[] nrv(int nr)

{

53


64/402

54 CAPITOLUL 2. SIMULAREA OPERATIILOR CU NUMERE MARI

int nc;

int nrrez=nr;

nc=0;

while(nr!=0) {nc++; nr=nr/10;}

int[] x=new int[nc];

nr=nrrez;

nc=0;

while(nr!=0)

{

x[nc]=nr%10;

nc++;

nr=nr/10;

}

return x;

}}

2.1.2 Adunarea numerelor mari

class SumaNrMari

{


{

int[] x=nrv(123); afisv(x);

int[] y=nrv(456); afisv(y);int[] z=suma(x,y);

afisv(z);

}


{

int nx=x.length;

int i;


System.out.println();

}

static int[] nrv(int nr){

int nc;

int nrrez=nr;

nc=0;


65/402

2.1. OPERATII CU NUMERE MARI 55

while(nr!=0) { nc++; nr=nr/10; }


nr=nrrez;

nc=0;

while(nr!=0)

{

x[nc]=nr%10;

nc++;

nr=nr/10;

}

return x;

}

static int[] suma(int[] x,int[] y)

{int k,s,t;

int nx=x.length;

int ny=y.length;

int nz;

if(nx>ny) nz=nx+1; else nz=ny+1;

int[] z=new int[nz];

t=0;

for(k=0;k


66/402


class ProdusNrMari

{


{

int[] x=nrv(12); afisv(x);

int[] y=nrv(9); afisv(y);

int[] z=produs(x,y);

afisv(z);

}


{

int nx=x.length;

int i;

for(i=nx-1;i>=0;i--) System.out.print(x[i]);System.out.println();

}


{

int nc;

int nrrez=nr;

nc=0;



nr=nrrez;

nc=0;while(nr!=0)

{

x[nc]=nr%10;

nc++;

nr=nr/10;

}

return x;

}

static int[] produs(int[] x,int[] y)

{

int i,j,t,s;

int nx=x.length;int ny=y.length;

int nz=nx+ny;

int[][] a=new int[ny][nx+ny];

int[] z=new int[nx+ny];


67/402


for(j=0;j


68/402


{

int nx=x.length;

int i;



}


{

int nc;

int nrrez=nr;

nc=0;



nr=nrrez;nc=0;

while(nr!=0)

{

x[nc]=nr%10;

nc++;

nr=nr/10;

}

return x;

}

static int[] impartLa2(int[] a)

{ int na,nb,k,t=0;

na=a.length-1;

if(a[na]==1) nb=na-1; else nb=na;

int[] b=new int[nb+1];

if(na==nb)

for(k=na;k>=0;k--)

{

a[k]+=10*t;

b[k]=a[k]/2;

t=a[k]%2;

}

else

{t=a[na];

for(k=na-1;k>=0;k--)

{

a[k]+=10*t;


69/402


b[k]=a[k]/2;

t=a[k]%2;

}

}

return b;

}

}

2.1.5 Functia putere cu numere mari

import java.io.*;

class PutereNRMari

{public static void main (String[]args) throws IOException

{

int a,n;



System.out.print("a = "); a=Integer.parseInt(br.readLine());


System.out.print("putere("+a+","+n+") = "); afisv(putere(a,n));

}


{ int nc;

int nrrez=nr;

nc=0;



nr=nrrez;

nc=0;

while(nr!=0)

{

x[nc]=nr%10;

nc++;

nr=nr/10;

}return x;

}

static int[] putere(int a,int n)


70/402


{

int k;

int[] p;

p=nrv(1);

for(k=1;k=0;i--) System.out.print(x[i]);


}


{

int i,j,t,s;

int nx=x.length;

int ny=y.length;

int nz=nx+ny;

int [][] a=new int[ny][nx+ny];


for(j=0;j


71/402


}

if(z[nz-1]!=0)return z;

else

{

int[] zz=new int[nz-1];

for(j=0;j


72/402


}

static int[] int[] factorial(int n)

{

int k;

int[] p;

p=nrv(1);

for(k=1;k=0;i--) System.out.print(x[i]);


}


{

int i,j,t,s;

int nx=x.length;

int ny=y.length;

int nz=nx+ny;


int[] z=new int[nx+ny];for(j=0;j


73/402


s=s+t;

z[j]=s%10;

t=s/10;

}

if(z[nz-1]!=0)return z;

else

{


for(j=0;jn/2) k=n-k; // o mica optimizare !



for(i=1;i


74/402


x[i]=x[i]/d;

y[j]=y[j]/d;

if(y[j]==1) break;

}

int[] p=nrv(1);

for(i=1;ib) {d=a; i=b;} else {d=b; i=a;}

while (i != 0)

{c=d/i; // nu se foloseste !

r=d%i;

d=i;

i=r;

}

return d;

}


{

int nc;

int nrrez=nr;nc=0;



nr=nrrez;

nc=0;

while(nr!=0)

{

x[nc]=nr%10;

nc++;

nr=nr/10;

}

return x;

}


{

int nx=x.length;


75/402


int i;



}


{

int i,j,t,s;

int nx=x.length;

int ny=y.length;

int nz=nx+ny;



for(j=0;j


76/402


2.2 Sume si produse cu numere mari

2.2.1 Numarul lui Catalan Cn= 1n+1

Cn2n cu numere mari

import java.io.*;

class CatalanNrMari

{


{

int n,k;



System.out.print("catalan("+n+") = "); afisv(catalan(n));

}

static int[] catalan(int n)

{

int i,j,d;

int[] x=new int[n+1];

int[] y=new int[n+1];

for(i=2;i


77/402

2.2. SUME SI PRODUSE CU NUMERE MARI 67

while (i != 0)

{


r=d%i;

d=i;

i=r;

}

return d;

}


{

int nc;

int nrrez=nr;

nc=0;while(nr!=0) {nc++; nr=nr/10;}


nr=nrrez;

nc=0;

while(nr!=0)

{

x[nc]=nr%10;

nc++;

nr=nr/10;

}

return x;

}


{

int nx=x.length;

int i;



}


{

int i,j,t,s;

int nx=x.length;int ny=y.length;

int nz=nx+ny;




78/402


79/402


{

s=nrv(0);

for(k=0;k=0;k--)

{

a[k]+=10*t;

b[k]=a[k]/2;

t=a[k]%2;

}

}

return b;

}

static int[] suma(int[] x, int[] y){

int i,j,t;

int ncx=x.length;

int ncy=y.length;


80/402


int ncz;

if(ncx>ncy) ncz=ncx+1; else ncz=ncy+1;

int[] xx=new int[ncz];

int[] yy=new int[ncz];

int[] z=new int[ncz];

for(i=0;i


81/402


{

z[j]=0;

for(i=0;i


82/402


static int[] comb (int n, int k)

{

int[] rez;

int i,j;

int d;



for(i=1;i


83/402


int k;

s=nrv(0);

for(k=0;k


84/402


{

z[j]=t;

for(i=0;i


85/402


int d,i,c,r;

if(a>b) {d=a;i=b;}else {d=b;i=a;}

while(i!=0){c=d/i;r=d%i;d=i;i=r;}

return d;

}

static int[] putere(int a,int n)

{

int k;int[]p;

p=nrv(1);

for(k=1;k


86/402


int[] zz=new int [nz-1];

for(i=0;i


87/402


int[] yy=new int[ncz];

int[] z=new int[ncz];

for(i=0;i


88/402


z[j]=z[j]+t;

t=z[j]/10;

z[j]=z[j]%10;

}

if(z[m+n-1]!= 0) return z;

else

{

int[] zz=new int[m+n-1];

for(i=0;i=0;i--) System.out.print(x[i]);

System.out.print(" ---> "+x.length+" cifre");


}


{

int nrrez=nr;

int nc=0;

while(nr!=0) { nc++; nr=nr/10; }int[]x=new int [nc];

nr=nrrez;

nc=0;

while(nr!=0) { x[nc]=nr%10; nc++; nr=nr/10; }

return x;

}

static int[] putere (int a, int n)

{

int[] rez;

int k;

rez=nrv(1);

for(k=1;k


89/402


{

int[] rez;

int i,j;

int d;



for(i=1;i


90/402


lam[1]=5;

lam[2]=6;

lam[3]=7;

lam[4]=8;

lam[5]=9;

rez=nr2v(1);

for(k=0;k


91/402


while (i!=0) { c=d/i; r=d%i; d=i; i=r; }

return d;

}

static int[] nr2v(int nr)

{

int nrr=nr,nc=0,i;


int[] nrv=new int[nc];

nr=nrr;

for(i=0;i


92/402


return zz;

}

}


{

int i;

for(i=x.length-1;i>=0;i--) System.out.print(x[i]);


}

}

2.2.6 Numerele Stirling de speta a II-a cu numere mari

Fie S(n, m) numarul modalitatilor de partitionare a unei multimi cu n ele-mente n m submultimi nevide (de exemplu, plasare numerelor{1, 2,...,n} n mcutii identice si nenumerotate astfel ncat nici o cutie sa nu fie goala!). Acest numarndeplineste urmatoarea relatie de recurenta:

S(n + 1, m) = S(n, m) + mS(n, m) unde S(n, n) = S(n, 1) = 1.


class SP09NrMari

{


{ int n=123,m=45;

int i,j;

long t1,t2;

int[][][] a=new int[n+1][n+1][1];


for(i=1;i


93/402


static int[] suma(int[]x,int[]y)

{

int nx=x.length, ny=y.length, i,min,max,t;

if(nx>ny) { min=ny; max=nx; } else { min=nx; max=ny; }

int[] z=new int[max+1];

t=0;

for(i=0;i


94/402


{

int nx=x.length, ny=y.length, i,j,t,s;



for(j=0;j


95/402


class SP10NrMari

{


{

int n=71;

int k,i;

int[][] b=new int[n+1][1];

int[] prod={1};

b[0]=nr2v(1);

for(i=1;i


96/402



for(i=0;i


97/402


for(i=0;i=0;i--) System.out.print(x[i]);


}

static int[] comb(int n,int k)

{

int i,j,d;int[] rez;



for(i=1;i


98/402


2.2.8 Partitiile unui numar natural cu numere mari

FieP(n, m) numarul modalitatilor de partitionare a numarului naturaln casuma de m numere naturale fara a se tine cont de ordinea acestora n suma (nscrierean = a1+ a2+ ... + am presupunem a1a2...am1). Acest numarndeplineste urmatoarea relatie de recurenta:

P(n + k, k) = P(n, 1) + P(n, 2) + ... + P(n, k) unde P(n, n) =P(n, 1) = 1.

Scrieti un program care sa calculeze, de exemplu, P(123, 45).

class SP11NrMari

{


{int n=123,m=45;

int[][][] p=new int[n+1][n+1][1];

int[] nsol;

int i,j,k;

p[1][1]=nr2v(1);

for(i=2;i


99/402


int[] xx=new int[nz];

int[] yy=new int[nz];

for(i=0;i


100/402


a[j][j+nx]=t;

}

t=0;

for(j=0;j


101/402


for(i=1;i


102/402


}


{

int nx=x.length;

int i;


System.out.println(" --> "+x.length+" cifre");

}


{

int nc;

int nrrez=nr;

nc=0;while(nr!=0) {nc++; nr=nr/10;}


nr=nrrez;

nc=0;


return x;

}

static int[] inmnr(int[] x, int[] y)

{

int nx=x.length;

int ny=y.length;int i,j,t,s;


int[][] a=new int [ny][nx+ny];

for(j=0;j


103/402


s=0;

for(i=0;i


104/402


static int[] suma(int[] x, int[] y)

{

int nx=x.length;

int ny=y.length;

int min,max,t,k;

if(nx>ny){max=nx;min=ny;}else{max=ny;min=nx;}

int[] z=new int[max+1];

t=0;

for(k=0;k


105/402


System.out.println(" --> "+x.length);

}

static int[] nr2v(int nr) // ok

{

int nc;

int nrrez=nr;

nc=0;



nr=nrrez;

nc=0;

while(nr!=0)

{

x[nc]=nr%10;nc++;

nr=nr/10;

}

return x;

}

static int[] inmnr(int[] x, int[] y)

{

int nx=x.length;

int ny=y.length;

int i,j,t,s;

int[] z=new int[nx+ny];int[][] a=new int [ny][nx+ny];

for(j=0;j


106/402


s=s+t;

z[j]=s%10;

t=s/10;

}

if(z[nx+ny-1]!=0) return z;

else

{

int[] zz=new int[nx+ny-1];

for(i=0;i


107/402



{

int nx=x.length;

int ny=y.length;

int nz;

if(nx>ny) nz=nx+1; else nz=ny+1;

int t,i;




for(i=0;i


108/402


{

t=0;

for(i=0;i


109/402


for(j=2;j


110/402


int[][] x=new int[n+1][1];

int[] prod={1};

for(i=1;i


111/402



{

int nrr=nr,nc=0,i;



nr=nrr;

for(i=0;i


112/402


static void afisv(int[]x)

{

int i;



}

static int[] comb(int n,int k)

{

if(k>n/2) k=n-k; // o mica optimizare !

int i,j,d;

int[] rez;



for(i=1;i


113/402


}

2.2.13 Fractie continua: determinarea fractiei initiale cu nu-mere mari

class FractieContinua2NrMari

{


{

int[] p,q;

int[] b={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25};

p=calcA(b);

q=calcB(b);afisv(p); System.out.println("/"); afisv(q);

}

static int[] calcA(int[] b)

{

int n=b.length-1;

int[][] A=new int[b.length][1];

A[0]=nrv(b[0]);

A[1]=suma(nrv(b[0]*b[1]),nrv(1));

for(int k=2;k


114/402


}


{

int nc;

int nrrez=nr;

nc=0;



nr=nrrez;

nc=0;


return x;

}


{

int k,s,t;

int nx=x.length;

int ny=y.length;

int nz;

if(nx>ny)nz=nx+1; else nz=ny+1;


t=0;

for(k=0;k


115/402


int nx=x.length;

int ny=y.length;

int nz=nx+ny;



for(j=0;j


116/402



{


System.out.print("n = "); n = Integer.parseInt(br.readLine());

int[][] np = new int[n+1][1];

np[0]=nr2v(1);

np[1]=nr2v(1);

for(int i=2;iny) nz=nx+1; else nz=ny+1;

int t,i;




for(i=0;i


117/402


{

int nrr=nr,nc=0,i;



nr=nrr;

for(i=0;i


118/402




}

}


119/402

Capitolul 3

OJI 2002 clasa a IX-a

3.1 Poarta

Se considera harta universului ca fiind o matrice cu 250 de linii si 250 decoloane. In fiecare celula se gaseste o asa numita poarta stelara, iar n anumitecelule se gasesc echipaje ale portii stelare.

La o deplasare, un echipaj se poate deplasa din locul n care se afla n oricarealt loc n care se gaseste o a doua poarta, n cazul nostru n orice alta pozitie dinmatrice.

Nu se permite situarea simultana a mai mult de un echipaj ntr-o celula. Laun moment dat un singur echipaj se poate deplasa de la o poarta stelara la alta.

CerintaDandu-se un numarp (1 < p


120/402

110 CAPITOLUL 3. OJI 2002 CLASA A IX-A

pozitiile initiale ale celor p echipaje sunt distincte doua cate doua;

pozitiile finale ale celor p echipaje sunt distincte doua cate doua.

Exemplupoarta.in poarta.out3 41 2 3 46 5 3 93 4 1 2

Timp maxim de executare: 1 secunda/test

3.1.1 Indicatii de rezolvare *

Fie NrStationare numarul echipajelor stationare (care au pozitiile initialesi finale egale) si NrCircuite numarul circuitelor grafului orientat format astfel:nodurile sunt echipa jele si exista arc de la echipajul i la echipajul j daca si numai

daca pozitia finala a echipajului i coincide cu pozitia initiala a echipajului j .Atunci NrMinDeplasari=p+NrCircuite-NrStationare.

3.1.2 Rezolvare detaliata

3.1.3 Codul sursa *

import java.io.*;

class Poarta

{static int p,nmd,nc=0,ns=0;

static int[] xi,yi,xf,yf;

static boolean[] ea; // EsteAnalizat deja


121/402

3.1. POARTA 111


{

StreamTokenizer st=new StreamTokenizer(

new BufferedReader(new FileReader("poarta10.in")));

st.nextToken(); p=(int)st.nval;

xi=new int[p+1];

yi=new int[p+1];

xf=new int[p+1];

yf=new int[p+1];

ea=new boolean[p+1]; // implicit este false

int i;

for(i=1;i


122/402


static int succesor(int j) // j --> k

{

int k;

for(k=1;k


123/402

3.2. MOUSE 113

mouse.in mouse.out2 4 7 211 2 6 3 1 13 4 1 2 2 1

2 21 21 31 42 4

Explicatie

Timp maxim de executare: 1 secunda/test


Daca m si n sunt pare atunci numarul de camarute vizitate este mn1iar cantitatea de hrana maxima culeasa este suma cantitatilor de hrana din toatecamarutele cu exceptia celei care are cea mai mica cantitate si se afla pe liniai sicoloana j si i+j este numar impar. Traseul este determinat de o parcurgere peverticala sau orizontala si ocolirea acelei camarute.

Daca m este impar atunci numarul de camarute vizitate este mn iar canti-tatea de hrana maxima culeasa este suma cantitatilor de hrana din toate camarutele.Traseul este determinat de o parcurgere pe orizontala.

Analog pentru situatia n care n este impar.

3.2.2 Rezolvare detaliata

3.2.3 Codul sursa *

import java.io.*;class Mouse

{

static int m,n,imin,jmin,min,s;

static int [][]a;


124/402


static PrintWriter out;


{

int i,j;


new BufferedReader(new FileReader("mouse4.in")));

out=new PrintWriter(new BufferedWriter(new FileWriter("mouse.out")));

st.nextToken();m=(int)st.nval;

st.nextToken();n=(int)st.nval;

a=new int[m+1][n+1];

for(i=1;i


125/402

3.2. MOUSE 115

j=1;

out.println(m*n+" "+s);

while(j+1


126/402


out.println((i+1)+" " +(j+1));

i=i+2;

while (i


127/402

Capitolul 4

OJI 2003 clasa a IX-a

4.1 Text

Vasile lucreaza intens la un editor de texte. Un text este format din unul saumai multe paragrafe. Orice paragraf se termina cu Enter si oricare doua cuvinteconsecutive din acelasi paragraf sunt separate prin spatii (unul sau mai multe). Infunctie de modul de setare a paginii, numarul maxim de caractere care ncap npagina pe o linie este unic determinat (Max).

Functia pe care Vasile trebuie sa o implementeze acum este alinierea n paginaa fiecarui paragraf din text la stanga si la dreapta. Pentru aceasta el va trebui samparta fiecare paragraf n linii separate de lungimeMax (fiecare linie terminata

cu Enter).Impartirea se realizeaza punand numarul maxim posibil de cuvinte pe fiecare

linie, fara mpartirea cuvintelor n silabe.

Pentru aliniere stanga-dreapta, Vasile trebuie sa repartizeze spatii n moduniform ntre cuvintele de pe fiecare linie, astfel ncat ultimul caracter de pelinie sa fie diferit de spatiu, iar numarul total de caractere de pe linie sa fie egalcu Max. Exceptie face numai ultima linie din paragraf, care ramane aliniata lastanga (cuvintele fiind separate printr-un singur spatiu, chiar daca linia nu esteplina).

In general, este putin probabil ca alinierea sa fie realizabila prin plasareaaceluiasi numar de spatii ntre oricare doua cuvinte consecutive de pe linie. Vasileconsidera ca este mai elegant ca, daca ntre unele cuvinte consecutive trebuie plasat

un spatiu n plus fata de alte perechi de cuvinte consecutive, acestea sa fie plasatela nceputul liniei.

CerintaScrieti un program care sa citeasca lungimea unei linii si textul dat si care sa

alinieze textul la stanga si la dreapta.

117


128/402


Date de intrare

Fisierul de intrare text.in contine pe prima linie Max, lungimea maxima aunui rand. Pe urmatoarele linii este scris textul.

Date de iesire

Fisierul de iesire text.outcontine textul aliniat stanga-dreapta.

Restrictii si precizuri

2Max1000. Lungimea maxima a oricarui cuvant din text este 25 caractere si nu depaseste

Max.

Lungimea unui paragraf nu depaseste 1000 de caractere. Solutia este unica.Exemple

text.in text.out20 Vasile are multeVasile are multe bomboane bune. bomboane bune.

Explicatie

Pe prima linie au fost plasate cate 3 spatii ntre cuvintele consecutive.

text.in text.out20 Ana are mere.Ana are mere. Ion are multe pereIon are multe pere galbene? galbene?

Explicatie

Intre I on si are exista 2 spatii, ntre are si multe - 2 spatii, iar ntre multesi pere - 1 spatiu.

Observati ca paragraful Ana are mere. (care are lungimea mai mica decat20) a ramas aliniat la stanga, iar ultima linie din fiecare paragraf ramane aliniatala stanga, cuvintele consecutive fiind separate printr-un singur spatiu.

Timp maxim de executare: 1 secunda/test.


Fiecare paragraf se preia ntr-un vector de string-uri, elementele vectorului

continand cuvintele din paragraf. Se parcurge acest vector, ncepand cu primapozitie, determinand cel mai mare indice i1care permite plasarea cuvintelor de pepozitiile 1,...,i1pe acelasi rand. Se destribuie spatiile disponibile, conform cerinteiproblemei si se afiseaza aceasta linie. Se continua prelucrarea vectorului ncepandcu pozitiai1+ 1, si asa mai departe!


129/402

4.1. TEXT 119

4.1.2 Rezolvare detaliata *

21

E cerul sus

Ca niste-ntinse brate

N-au crengile de ce sa se agate

0000:0000 32 31 0D 0A 45 20 63 65 72 75 6C 20 73 75 73 0D

0000:0010 0A 43 61 20 6E 69 73 74 65 2D 6E 74 69 6E 73 65

0000:0020 20 62 72 61 74 65 0D 0A 4E 2D 61 75 20 63 72 65

0000:0030 6E 67 69 6C 65 20 64 65 20 63 65 20 73 61 20 73

0000:0040 65 20 61 67 61 74 65 0D 0A 1A

Sfarsitul de fisier (EOF) este marcat prin 1A.Sfarsitul de linie (EOL) este marcat prin 0D0A.

4.1.3 Codul sursa *

import java.io.*;

class Text

{

static int Max, nc;

static String[] s=new String[501]; // cuvintele din paragraf

static int[] lgc=new int[501]; // numarul caracterelor cuvintelorstatic int[] nsp=new int[501]; // numarul spatiilor dupa cuvant

static int cs=0, cd=0; // cs=cuvant stanga, cd=cuvant dreapta

static int lglin=0;

static PrintWriter out;


{

out=new PrintWriter(new BufferedWriter(new FileWriter("text.out")));


new BufferedReader(new FileReader("text.in")));

st.eolIsSignificant(true);

st.nextToken(); Max=(int)st.nval;st.nextToken(); // preia EOL-ul existent dupa Max

while(st.nextToken()!=StreamTokenizer.TT_EOF)

{

nc=0;


130/402


do

{

s[++nc]=st.sval.toString();

} while(st.nextToken()!=StreamTokenizer.TT_EOL);

rezolva();

}

out.close();

}

static void rezolva() throws IOException

{

cs=0; // primul cuvant din linie (din stanga)

cd=0; // ultimul cuvant din linie (din stanga)

while(cd

7/25/2019 A

Algoritmi si structuri de date.pdf

Documents

Transcript of Algoritmi si structuri de date.pdf