Sesiunea iulie
Rezolvare subiecte admitere
Rezolvarea propusa de Facultate:
Subiectul I
1. #include <iostream> using namespace std; /* Explicatie Turnul de inaltime n este obligatoriu singur (altfel, intre doua turnuri de inaltime n trebuie sa existe un turn de inaltime n+1, care e prea inalt). Excluzand turnul de inaltime n, putem avea cel mult 2 turnuri de inaltime n-1 (trei sau mai multe turnuri de inaltime n-1 duc la doua sau mai multe turnuri de inaltime n) de o parte si de alta a turnului de inaltime n (intre ele trebuie sa existe cel putin un turn de inaltime mai mare). La stanga turnului de inaltime n se vor construi maximul de turnuri (conform cerintelor problemei) cu cel mai inalt turn avand inaltimea n-1. (Similar pentru constructia de la dreapta turnului de inaltime n.) Obtinem deci urmatoarea constructie recursiva: sirul de turnuri este format dintr-un turn de inaltime n aflat la mijloc, iar de fiecare parte avem un sir de turnuri care este identic cu constructia ce conduce la cel mai inalt turn la inaltime n-1. Ca urmare, avem recurentele: nrTurnuri(n) = 2*nrTurnuri(n-1) + 1 nrMonede(n) = 2*nrMonede(n-1) + n Terminarea recurentelor se face la n=1: nrTurnuri(1) = 1 nrMonede(1) = 1 Implementarea se poate face recursiv; recursia poate fi desfacuta iterativ. */ // Varianta recursiva: int nrTurnuri(int n) { if(n==1) return 1; return 2*nrTurnuri(n-1) + 1; } int nrMonede(int n) { if(n==1) return 1; return 2*nrMonede(n-1) + n; } void turnuri_apelFRec(int n, int& nrT, int& nrM) { nrT = nrTurnuri(n); nrM = nrMonede(n); } // Numarul de turnuri este dat de formula: //nrTurnuri(n) = 1 + 2 + 2^2 + ... + 2^(n-1) // Numarul de monede este dat de formula: //nrMonede(n) = n + (n-1)*2 + (n-2)*2^2 + ... + 1*2^(n-1) void turnuri(int n, int &nrTurnuri, int &nrMonede) { nrMonede = 0; nrTurnuri = 0; int putere = 1; for (int inaltime = n; inaltime >= 1; inaltime--){ nrTurnuri = nrTurnuri + putere; // numarul turnurilor creste cu urmatoraea putere a lui 2 nrMonede = nrMonede + putere * inaltime; // in fiecare turn avem "inaltime" monede putere = putere * 2; } } // Se pot folosi si formulele pt. numar total de turnuri / monede // Formula pt. nr. turnuri:: // nrTurnuri(n) = 1 + 2 + 2^2 + ... + 2^(n-1) = 2^n -1 // Formula pt. nr. monede: // nrMonede(n) = n + (n-1)*2 + (n-2)*2^2 + ... + 1*2^(n-1) = // = (1 + 2 + 2^2 + ... + 2^(n-1)) + (1 + 2 + 2^2 + ... + 2^(n-2)) + ... + (1 + 2) + 1 = // = (2^n-1) + (2^(n-1)-1) + ... + (2^2-1) + (2-1) = // = (2^n + 2^(n-1) + ... + 2^2 + 2) - n = // = (2^n + 2^(n-1) + ... + 2^2 + 2 + 1) - (n + 1) = // = (2^(n+1) - 1) - (n + 1) = // = 2^(n+1) - n - 2 void turnuri_Formula(int n, int &nrTurnuri, int &nrMonede) { int putere = 1; for (int i = 1; i <= n; i++){ putere = putere * 2; } nrTurnuri = putere - 1; nrMonede = putere*2 - n - 2; } //------------------------------------------------------------------------------ // Programul principal e doar pentru test si // nu a fost luat in calcul la notare int main(){ int n, nrTurnuri, nrMonede; cout << "Introduceti inaltimea celui mai inalt turn: "; cin >> n; turnuri(n, nrTurnuri, nrMonede); cout << "nr. turnuri: " << nrTurnuri << endl; cout << "nr. monede: " << nrMonede << endl; turnuri_apelFRec(n, nrTurnuri, nrMonede); cout << "nr. turnuri: " << nrTurnuri << endl; cout << "nr. monede: " << nrMonede << endl; turnuri_Formula(n, nrTurnuri, nrMonede); cout << "nr. turnuri: " << nrTurnuri << endl; cout << "nr. monede: " << nrMonede << endl; return 0; }
2.
#include <iostream> using namespace std; // se construieste vectorul de aparitii a cifrelor in baza p pentru un numar x // se determina pe rand cifrele in baza q ale numarului x // daca cifra curenta nu apare in reprezentarea in baza p atunci numarul x nu este magic // altfel se incrementeaza valoarea corespunzatoare cifrei in vectorul de cifre // daca in vectorul de cifre a ramas valoarea 1 pentru anumite cifre, acele cifre apar in // reprezentarea in baza p si nu apar in reprezentarea in baza q, deci numarul nu este magic bool nrMagic(int x, int p, int q){ //verifica daca x este magic in raport cu bazele p si q int cifre[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; int copie = x; while (copie != 0){ //stabilim multimea cifrelor lui x in baza p int uc = copie % p; // uc - ultima cifra (in baza p) cifre[uc] = 1; copie = copie / p; } copie = x; while (copie != 0){ //determinam cifrele lui x in baza q int uc = copie % q; if (cifre[uc] == 0) //daca cifra curenta (in baza q) nu e folosita in baza p return false; cifre[uc]++; copie = copie / q; } for (int i = 0; i < 10; i++){ if (cifre[i] == 1) //daca cifra i e folosita in baza p, dar nu e folosita in baza q return false; } return true; } void sirNrMagice(int p, int q, int n, int &k, int sir[]){ k = 0; for (int i = 1; i < n; i++){ if (nrMagic(i, p, q)) sir[k++] = i; } } //------------------------------------------------------------------------------ // Functia de afisare si programul principal sunt doar pentru test si // nu au fost luate in calcul la notare //afiseaza pe ecran elementele unui sir x cu n numere intregi void tiparesteSir(int n, int x[]){ for (int i = 0; i < n; i++) cout << x[i] << " "; cout << endl; } int main(){ int n; cout << "Introduceti numarul n: "; cin >> n; int p; cout << "Introduceti baza p: "; cin >> p; int q; cout << "Introduceti baza q: "; cin >> q; int sir[10000]; int k = 0; sirNrMagice(p, q, n, k, sir); tiparesteSir(k, sir); return 0; }
3.
#include <iostream> using namespace std; void insereazaPuteri(int &n, int a[]){ for (int i = n - 1; i >= 0; i--){ a[2 * i] = a[i]; int aux1 = a[i]; int aux2 = 1; while (aux1 > 1){ aux1 = aux1 / 2; aux2 = aux2 * 2; } a[2 * i + 1] = aux2; } n = 2 * n; } //------------------------------------------------------------------------------ // Functiile de citire si afisare si programul principal sunt doar pentru test si // nu au fost luate in calcul la notare //citeste de la tastaura elementele unui sir x cu n numere intregi void citesteSir(int& n, int x[]){ cout << "Dati lungimea sirului: "; cin >> n; cout << "Dati elementele sirului: "; for (int i = 0; i < n; i++) cin >> x[i]; } //afiseaza pe ecran elementele unui sir x cu n numere intregi void tiparesteSir(int n, int x[]){ for (int i = 0; i < n; i++) cout << x[i] << " "; cout << endl; } int main(){ int a[10000]; int n; cout << "Sirul a\n "; citesteSir(n,a); insereazaPuteri(n,a); cout << "Sirul dupa inserare este \n "; tiparesteSir(n,a); cout << endl; return 0; }
Subiectul II
#include <iostream>
using namespace std; int F(int a, int b){ int c = 1; while (b > 0){ if (b % 2 == 1){ c = c * a % 10; } a = a * a % 10; b = b / 2; } return c; } int Frec(int a, int b){ if (b == 0) return 1; else{ if (b % 2 == 1) return a * Frec(a * a % 10, b / 2) % 10; else return Frec(a * a % 10, b / 2) % 10; } } //------------------------------------------------------------------------------ // Programul principal este doar pentru test // si nu a fost luat in calcul la notare int main(){ int n,k; cout << "Dati numarul "; cin >> n; cout << "\n si puterea "; cin >> k; cout << "Ultima cifra a lui " << n << "^" << k << " este: " << Frec(n,k); return 0; }
Subiectul III
#include <iostream> using namespace std; // Observatie: in aceasta solutie am folosit indexare de la 0 void ceaMaiLungaInsula(int n, int a[], int &nr, int &maxInc, int &maxSf){ maxInc = -1; maxSf = -1; nr = 0; int i = 0; // Sarim intai peste continentul de plecare while ((i < n) && (a[i] > 0)){ i = i + 1; } // procesarea insulelor while (i < n){ // sarim peste ocean (pana la inceputul uscatului) while ((i < n) && (a[i] == 0)){ i = i + 1; } // cautam finalul bucatii de uscat int inceput = i; while ((i < n) && (a[i] > 0)){ i = i + 1; } if (i < n){ // daca nu am gasit de fapt continentul final nr++; int sfarsit = i - 1; if (maxSf - maxInc <= sfarsit - inceput){ maxInc = inceput; maxSf = sfarsit; } } } } bool proprMunte(int inceput, int sfarsit, int a[]) { int i = inceput; // urcam while ((i < sfarsit) && (a[i] < a[i + 1])){ i = i + 1; } // i e acum pe varful muntelui. bool munte = ((i > inceput) && (i < sfarsit)); if (munte){ // coboram while ((i < sfarsit) && (a[i] > a[i + 1])){ i = i + 1; } // e ok doar daca panta de coborare se termina in mare munte = (i == sfarsit); } return munte; } bool suntDistincte(int n, int a[]) { bool distincte = true; int i = 0; while ((distincte) && (i < n)){ // sarim peste ocean while ((i < n) && (a[i] == 0)){ i = i + 1; } int j = i + 1; while ((j < n) && (a[i] != a[j])){ j = j + 1; } distincte = (j == n); i = i + 1; } return distincte; } void celMaiFrecvent(int n, int a[], int &inaltime, int &k){ // frecventele altitudinilor // determinam: frec[i] - frecventa altitudinii i int frecv[30000]; for (int i = 0; i < 30000; i++){ frecv[i] = 0; } for (int i = 0; i < n; i++){ frecv[a[i]]++; } // determminam max - altitudinea cea mai frecventa // frecv[max] - frecventa lui max int max = 1; for (int i = 1; i < 30000; i++) { // pornim cu i=1 pentru ca nu ne intereseaza frecventa punctelor de altitudine 0 if (frecv[i] > frecv[max]){ max = i; } } inaltime = max; k = frecv[max]; } int main(){ int n; int a[10005]; cout << "n = "; cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; int nr = 0; int inceput = -1; int sfarsit = -1; // determinarea celei mai mari insule ceaMaiLungaInsula(n, a, nr, inceput, sfarsit); if (nr == 0) cout << "Nu exista insule " << endl; else{ cout << "Cea mai lunga insula incepe la punctul " << inceput << " si se intinde pana la " << sfarsit << endl; // stabilirea proprietatii de insula tip munte if (proprMunte(inceput, sfarsit, a)) cout << " Este munte " << endl; else cout << " Nu este munte " << endl; // stabilirea daca altitudinile sunt distincte if (suntDistincte(n, a)) cout << "Altitudinile sunt distincte"; else{ //si in caz negativ a celei mai frecvente altitudini cout << "Altitudinile nu sunt distincte " << endl; int altitudine = 0; int frecventa = -1; celMaiFrecvent(n, a, altitudine, frecventa); cout << "Altitudinea cea mai frecventa este: " << altitudine << " si apare de " << frecventa << " ori."; } } return 0; }