Lista de probleme 10

Pornind de la numărul 1,orice număr natural se poate obţine aplicând repetat în mod convenabil operaţii din cele de mai jos:

• înmulţire cu 3
• adunare cu 1
• scădere cu 1

Cunoscând numărul natural n,să se tipărească şirul de operaţii prin care se poate ajunge de la numărul iniţial 1 la numărul final n.

Pornind de la numărul 1, orice număr natural n se poate obţine aplicând în mod repetat şi convenabil operaţii dintre cele de mai jos:

• înmulţire cu 3 (operaţie codificată cu 3);
• adunare cu 5 (operaţie codificată cu 5);
• adunare cu 7 (operaţie codificată cu 7);
• împărţire la 9 (operaţie codificată cu 9).

Cunoscând numărul natural n, să se tipărească şirul de operaţii prin care se poate ajunge de la numărul iniţial 1 la numărul final n.

Se dă o matrice cu numere naturale nenule, pătratică, cu liniile şi coloanele numerotate de la 1 la N. Fiecare număr din matrice reprezintă înălţimea unui pilon plasat în acea poziţie.

Putem plasa un observator “sub” matrice (adică pe o poziţie i j cu i > N şi 1 ≤ j ≤ N), de unde poate vedea în 3 direcţii:

• nord (pe coloana j);
• nord-vest (elemente din matrice de pe poziţii is,js cu i - is = j - js, dacă există astfel de elemente);
• nord-est (elemente din matrice de pe poziţii is,js cu i - is = js - j, dacă există astfel de elemente);

Se cunoaşte configuraţia matricei şi mai multe poziţii posibile ale observatorului. Să se determine, pentru fiecare poziţie, numărul de piloni pe care îi vede observatorul plasat acolo.

La ora de matematică Georgică a învăţat să evalueze expresii aritmetice. Pentru a verifica acest lucru profesorul de informatică îi propune lui Georgică să evalueze expresii aritmetice de forma:

A o₁ B o₂ C

Unde A, B, C sunt operanzi, iar o₁ şi o₂ operatori.

Valorile permise operanzilor pot fi numai termeni din şirul x₁ , x₂ , …, x_n , iar operatorii pot fi numai caracterele + (adunare) şi * (înmulţire).

Profesorul îi pune la dispoziţie lui Georgică o valoare numerică V şi îi cere să determine valorile operanzilor A, B şi C pentru care expresia are valoarea V.

Scrieţi un program, care pentru V, n, x₁ , x₂ , …, x_n şi o₁ , o₂ , date determină indicii corespunzători termenilor din şirul x₁ , x₂ , …, x_n ce corespund valorilor operanzilor A, B şi C pentru ca expresia dată să aibă valoarea V.

La ora de matematică Georgică a învăţat o nouă operaţie: ridicarea la putere. În timpul orei de informatică aprofundează această noţiune considerând două numere naturale m şi n, cu acelaşi număr de cifre şi calculând:

a) puterea p = ab , unde a este ultima cifră a lui m, iar b este ultima cifră a lui n;
b) suma s a tuturor puterilor de forma xy, unde x şi y sunt cifre din m, respectiv n de pe aceeaşi poziţie.

Scrieţi un program, care pentru două numere naturale date m şi n determină:

a) puterea p definită în enunţ;
b) suma s definită în enunţ.

După descoperirea vieţii pe planeta Marte, cercetătorii pământeni au început activitatea de studiere a fiinţelor vii marţiene. Prima constatare a fost că este o legătură strânsă între modul de formare a acestora şi numerele naturale. Astfel, unei specii i s-a asociat un număr natural mai mare decât 1. Mai mult, oricare două specii se pot compune, rezultând altă specie. Numărul asociat noii specii este dat de produsul numerelor asociate celor două specii care se compun. Astfel, modalitatea de obţinere a unei specii nu este unică (o specie ce are asociat numărul 12 se poate obţine compunând specia 2 cu specia 6, sau specia 3 cu specia 4). Evident, unele specii se pot obţine prin compunerea altora (ex. 12) dar unele nu se pot obţine prin compunere. Pe acestea din urmă le vom numi atomi (de exemplu specia ce are asociat codul 7 este atom, şi mai sunt şi altele). O specie se poate compune cu ea însăşi rezultând altă specie (de exemplu, prin compunerea speciei 3 cu ea însăşi se obţine specia 9). De asemenea, dacă specia X se poate obţine prin compunerea speciilor Y şi Z spunem că X are în compoziţie pe Y şi pe Z. Mai mulţi cercetători au recoltat probe obţinând astfel o listă de coduri ale speciilor pe care le-au observat.

Scrieţi un program care, pe baza codurilor din lista formată, să determine:
a) numărul de atomi din listă;
b) numărul de specii din listă care nu pot avea în compoziţie niciun atom dintre cei aflaţi în listă;

Se dă o permutare P a mulțimii {1,2, … ,N}. Se mai dau Q întrebări specificate prin câte un număr D.

Dacă D este pozitiv trebuie să determinăm a D-a permutare care succede lexicografic P iar dacă D este negativ, a D-a permutare care precede lexicografic P.

În Bistriţa sunt N copii, fiecare dintre ei având un număr preferat Xi . Copii se aşează pe un rând, cu poziţiile numerotate de la 1 la N. După ce copii s-au aşezat, profesoara de educaţie fizică le cere să execute M mişcări de tipul (a, b), cu semnificaţia că îşi vor schimba ordinea copiii care se află între poziţiile a şi b, inclusiv.

Să se răspundă la Q întrebări de tipul p, cu semnificaţia: care este numărul preferat al copilului, care se află pe poziţia p, după executarea mişcărilor cerute de profesoara de educaţie fizică.

Călinuţa tocmai a găsit o foaie de hârtie pe care este desenat un graf orientat aciclic cu N noduri şi M arce, fiecare arc având o distanţă de valoare întreagă. Dându-se N, M şi cele M arce cu distanţele dintre ele, trebuie să calculaţi pentru Călinuţa distanţa minimă dintre fiecare două noduri.

Natasha a descoperit un nou joc pe calculator. Pe un suport se află N biluțe pe care este scris câte un număr si . Jocul constă în alegerea unei biluțe, biluță care se va ridica de pe suport și va pluti în aer pentru si secunde, apoi se va așeza din nou pe poziția ei în suport. În momentul în care o biluță atinge suportul, prima biluță bst din stânga ei și prima biluță bdr din dreapta ei (care nu s-au așezat pe suport în același moment de timp) se vor ridica în aer, fiecare plutind pentru sst , respectiv sdr secunde, după care se vor reașeza în suport, fiecare pe poziția ei. Această mișcare a biluțelor continuă până când Natasha se plictisește și închide calculatorul. Dar asta nu e tot. În timp ce Natasha urmărește mișcarea biluțelor, ea trebuie să răspundă la M întrebări de forma: “Este biluța bk la momentul de timp tk pe suport sau în aer?”.

Pentru fiecare din cele M întrebări, răspundeți cu 1 dacă biluța b este pe suport, sau cu 0 dacă biluța este în aer.