Capitolul 6: Probleme diverse

1. Scrieţi un program care calculează aⁿ folosind o funcţie recursivă (a număr nenul, n număr natural).

2. Scrieţi un program care să genereze al n-lea termen din şirul lui Fibonacci, folosind o funcţie recursivă. Amintim că şirul lui Fibonacci se defineşte astfel:

0, 1, 1, 2, 3, 5, 8,..., a(k), a(k+1),a(k)+a(k+1),...

3. Să se scrie programul care să afişeze toate numerele de trei cifre , care satisfac relaţia : fracţia  are valoare întreagă.

(Concursul de informatica pentru gimnaziu - 1994

Faza judeteana , Clasa a VII-a)

4. Scrieţi programul care să transforme fracţia a/b într-o fracţie ireductibilă ştiind că numărătorul şi numitorul acesteia sunt numere naturale.

5. Un reprezentant al civilizaţiei STOG întâlneşte un vechi prieten din galaxia FLEX căruia îi aminteşte că îi datorează o sumă de bani pe care i-o comunică sub forma unui şir de cifre. Flexianul nu îşi aminteşte că îi datorează această sumă şi îi spune ce sumă ştie el că-i datorează sub forma unui alt şir de cifre. Cunoscând suma indicată de stogian şi numărul de degete pe care le folosesc la numărat fiecare dintre cei doi indivizi, să se afişeze suma pe care a arătat-o flexianul.

Exemplu:

136

nr. degete stogian=10

nr. degete flexian=8

Răspuns:

210

(Concursul Marele Premiu “PACO” ‘96

Clasa a VI-a)                                                             

6.  Se citeşte de la tastatură un număr natural n. Să se determine numărul maxim obţinut prin eliminarea din numărul dat a r cifre, r fiind un număr natural precizat. Este permisă schimbarea ordinii cifrelor în numărul considerat.

7. Se citeşte de la tastatură un număr natural n. Să se determine numărul maxim obţinut prin eliminarea din numărul dat a r cifre, r fiind un număr natural precizat. Nu este permisă schimbarea ordinii cifrelor în numărul considerat.

(Concursul Marele Premiu “PACO” ‘96

Clasa a V-a)                                                             

8. Scrieţi un program care să afişeze toate combinaţiile de numere prime distincte şi ordonate crescător, mai mici sau egale decât un număr natural n şi a căror sumă este numărul n.

Ex.       n=4 - imposibil

            n=5 - 5=2+3; 5=5

            n=6 - imposibil

            n=23 - 23=2+3+5+13;23=2+4+7+11;23=3+7+13;23=5+7+11;23=23

(Tabăra Naţională de Informatică 1995

Clasa a V-a)

9.   Doi prieteni inventează o modalitate de a codifica nişte mesaje alcătuite numai din majuscule şi spaţii înlocuind cu litera S fiecare consoană ce este urmată în acelaşi cuvânt de o vocală şi, dupa fiecare vocală ce are în faţa sa în cuvântul necodificat o consoană, adăugând grupul format din consoana precedentă şi vocala O.

       Exemplu:

            MASCA à SAMOSSACO

a) Se citeşte de la tastatură un text şi se tipăreşte textul codificat;

b) Se citeşte de la tastatură un text codificat şi se cere textul original.

(Concurs naţional de informatică - Lugoj 1995)

10. La marginea unui regat puternic, trăia un vrăjitor care avea o comoară ce depăşea cu mult ca valoare chiar şi bogăţiile regelui. Într-o vreme, vrăjitorul, plictisindu-se de ocupaţiile sale obişnuite şi dorind să-şi găsească o distracţie pe măsura puterii sale, dădu sfoară în ţară că o bună parte din comoara sa va putea fi luată de cel care va şti să o câştige. Comoara vrăjitorului era formată din n grămezi de aur (fiecare grămadă conţinând un număr oarecare de monede). Cel care dorea să obţină aur din comoara vrăjitorului trebuia să respecte regulile impuse de acesta, care erau următoarele:

1)  aurul trebuia cărat de exact n slujitori (tot atâţia câte grămezi);

2)  cel care vroia aurul putea ca din cele n grămezi să aleagă un număr astfel încât:

n    dacă alege o grămadă, trebuie să ia toate monedele din acea grămadă

n    numărul total de monede rezultat din toate grămezile alese trebuie să se poată împărţi exact la cei n slujitori care le vor căra;

3)  numărul total de monede din grămezile alese trebuie să fie maxim posibil, altfel dacă vrăjitorul îi arăta celui care a ales că putea să facă o alegere mai bună, acesta nu mai primea nimic.

Dându-se numărul n de grămezi şi în acelaşi timp de slujitori, numărul nr[i] de monede din fiecare grămadă i (1<=i<=n) trebuie găsită mulţimea grămezilor care trebuie alese.

Intrare: Un set de date este alcătuit dintr-o linie pe care se află numărul n (de slujitori şi de grămezi) n<=100, urmată de n linii fiecare linie conţinând numărul nr[i] de monede din grămada i.

Ieşire:  La ieşire trebuie să se afişeze la terminal numărul total de monede obţinut şi grămezile alese.

Exemplu

            Dacă fişierul de intrare este:

7

11

4

336

34

356

218

537

            Atunci ieşirea trebuie să fie:

Numărul total de monede: 1274

Grămezile alese:

1

3

4

5

7

(Concursul Marele Premiu "PACO" '95

Clasa a VII-a)

11. O subsecvenţă a unui şir de numere este un şir care se obţine ştergând zero sau mai multe elemente din şirul iniţial. Elementele care se şterg nu trebuie să fie neapărat pe poziţii consecutive în şir. De exemplu, din şirul 2, 4, 3, 1, 2, 1 se poate obţine subsecvenţa 2, 3, 2, 1 prin ştergerea lui 4 şi a primului 1 din şirul iniţial. Dându-se două şiruri X₁, X₂, ..., X_n şi Y₁, Y₂, ...Y_m, o subsecvenţă comună a celor două şiruri este un şir care este subsecvenţă şi pentru primul şir şi pentru al doilea. Problema constă în a găsi o subsecvenţă de lungime maximă a două şiruri date:

La intrare se vor furniza:

n    numărul natural n (n<=100) reprezentând lungimea primului şir şi apoi cele n numere componente ale acestuia

n    numărul natural m (m<=100) reprezentând lungimea celui de-al doilea şir şi apoi cele m elemente componente ale acestuia.

Trebuie să se afişeze pe ecran lungimea subsecvenţei maxime şi o astfel de subsecvenţă.

Exemplu:

n=7

1 2 3 2 4 1 2

m=6

2 4 3 1 2 1

Se obţin:           Lungimea 4

                        Subsecvenţa comună 2 3 2 1.  

(Olimpiada Naţională de Informatică 1995

Clasa a VIII-a)

12. Un geam dreptunghiular cu lăţimea m şi înălţimea n (m,n<=1000 numere naturale date) este realizat cu o tehnologie specială, astfel încât, dacă este lovit cu un obiect ascuţit într-un punct de coordonate x,y, se va fisura până la margini pe o direcţie orizontală şi una verticală, paralele cu marginile dreptunghiului.

De exemplu:

            Cunoscându-se numărul de lovituri l (l<=20) aplicate geamului şi coordonatele fiecărei lovituri considerate faţă de colţul din stânga jos al dreptunghiului iniţial date în ordinea în care au fost aplicate, să se aleagă dintre bucăţile de geam dreptunghiulare rezultate pe cea de arie maximă tipărind aria sa.

Exemplu: pentru m=11, n=4, l=2 şi punctele de lovire (4,3) şi (1,1) se obţine rezultatul:

Dreptunghiul maximal rămas are aria de 21 de unităţi.

(Concursul Marele Premiu "PACO" '96 Clasa a VIII-a)