Articole

PIRNOG THEODOR IOAN
Colegiul Național “B. P. Hasdeu”, 10A

Determinarea primalității unui număr reprezintă o sarcină de lucru pe care o putem întâlni atât la probleme simple, cât și la probleme cu un grad ridicat de dificiultate, cum ar fi cele de olimpiadă. Este foarte important să observăm resursele disponibile atunci când rezolvăm o astfel de problemă. În cazul în care avem destulă memorie la dispoziție, putem utiliza ciurul lui Eratostene, fie el sub forma unui vector bool, fie utilizând <bitset>. Există însă cazuri în care memoria nu ne permite să folosim astfel de structuri, prin urmare, vom fi nevoiți să ne gândim la o altă metodă pentru determinarea primalității unui număr. Probabil că, mulți vor tinde să utilizeze următorul algoritm: (Vezi poza I)

Este un algoritm simplu, ușor de înțeles, dar care nu este foarte eficient. Avem nevoie de ceva mai bun.

Orice număr întreg, x ∈ ℤ, îl putem scrie sub forma 6k + p, unde p ∈ {-1, 0, 1, 2, 3, 4}, k ∈ ℤ. Acest lucru ne va ajuta foarte mult. Să ne folosim de acestă informație:

• dacă p ∈ {0, 2, 4}, atunci x = 6k, 6k + 2 sau 6k + 4 <=> x = 2 * 3k, x = 2 * (3k + 1) sau x = 2 * (3k + 2) => x este divizibil cu 2 => x nu este prim. (1)

• dacă p ∈ {3}, atunci x = 6k + 3 <=> x = 3 * (2k + 1) => x este divizibil cu 3 => x nu este prim. (2)

Rămânem, deci, cu p = +- 1 => x = 6k +- 1, despre care dorim să aflăm dacă este prim. Haideți să aruncăm o privire asupra perechilor de forma (6k – 1, 6k + 1), k ≥ 1: (5, 7), (11, 13), (17, 19), (23, 25), … Pentru aceste numere, vom încerca să găsim divizori pentru a verifica dacă sunt numere prime sau nu. Divizorii acestor numere vor fi tot de forma 6k +- 1, întrucât, dacă x ar fi divizibil cu un număr scris sub forma (1), atunci ar fi multiplu de 2, deci nu poate fi prim (analog pentru multiplii de 3, conform a ceea ce am zis la (2)). Observăm că, modulul diferenței dintre cei 2 termeni ai unei perechi (6k – 1, 6k + 1), k ≥ 1, este mereu 2, iar modulul diferenței dintre oricare 2 termeni aflați pe prima poziție în perechi consecutive va fi mereu 6, datorită 6k. De observat este că, numerele prime 2 și 3 nu pot fi scrise sub forma 6k – 1 sau 6k + 1, k ≥ 1, deci va trebui să ne ocupăm separat de ele. Acestea fiind spuse, să aruncăm o privire asupra noului test de primalitate: (Vezi poza II)

O problemă care necesită un astfel de algoritm este #hard_prime , în care soluția se încadrează în timp și memorie folosind acest algoritm. Spor la lucru!

Deci, se stie ca Among us mare este el:
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣤⣤⣤⣤⣤⣶⣦⣤⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⡿⠛⠉⠙⠛⠛⠛⠛⠻⢿⣿⣷⣤⡀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣼⣿⠋⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠈⢻⣿⣿⡄⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣸⣿⡏⠀⠀⠀⣠⣶⣾⣿⣿⣿⠿⠿⠿⢿⣿⣿⣿⣄⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠁⠀⠀⢰⣿⣿⣯⠁⠀⠀⠀⠀⠀⠀⠀⠈⠙⢿⣷⡄⠀
⠀⠀⣀⣤⣴⣶⣶⣿⡟⠀⠀⠀⢸⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣷⠀
⠀⢰⣿⡟⠋⠉⣹⣿⡇⠀⠀⠀⠘⣿⣿⣿⣿⣷⣦⣤⣤⣤⣶⣶⣶⣶⣿⣿⣿⠀
⠀⢸⣿⡇⠀⠀⣿⣿⡇⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃⠀
⠀⣸⣿⡇⠀⠀⣿⣿⡇⠀⠀⠀⠀⠀⠉⠻⠿⣿⣿⣿⣿⡿⠿⠿⠛⢻⣿⡇⠀⠀
⠀⣿⣿⠁⠀⠀⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣧⠀⠀
⠀⣿⣿⠀⠀⠀⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⠀⠀
⠀⣿⣿⠀⠀⠀⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⠀⠀
⠀⢿⣿⡆⠀⠀⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⡇⠀⠀
⠀⠸⣿⣧⡀⠀⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⠃⠀⠀
⠀⠀⠛⢿⣿⣿⣿⣿⣇⠀⠀⠀⠀⠀⣰⣿⣿⣷⣶⣶⣶⣶⠶⠀⢠⣿⣿⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠀⠀⠀⠀⠀⣿⣿⡇⠀⣽⣿⡏⠁⠀⠀⢸⣿⡇⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠀⠀⠀⠀⠀⣿⣿⡇⠀⢹⣿⡆⠀⠀⠀⣸⣿⠇⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢿⣿⣦⣄⣀⣠⣴⣿⣿⠁⠀⠈⠻⣿⣿⣿⣿⡿⠏⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠈⠛⠻⠿⠿⠿⠿⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

si ca bebita among us sete el:
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣴⣶⣿⣿⣷⣶⣄⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣾⣿⣿⡿⢿⣿⣿⣿⣿⣿⣿⣿⣷⣦⡀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⣿⡟⠁⣰⣿⣿⣿⡿⠿⠻⠿⣿⣿⣿⣿⣧⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣾⣿⣿⠏⠀⣴⣿⣿⣿⠉⠀⠀⠀⠀⠀⠈⢻⣿⣿⣇⠀⠀⠀
⠀⠀⠀⠀⢀⣠⣼⣿⣿⡏⠀⢠⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠈⣿⣿⣿⡀⠀⠀
⠀⠀⠀⣰⣿⣿⣿⣿⣿⡇⠀⢸⣿⣿⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⡇⠀⠀
⠀⠀⢰⣿⣿⡿⣿⣿⣿⡇⠀⠘⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⢀⣸⣿⣿⣿⠁⠀⠀
⠀⠀⣿⣿⣿⠁⣿⣿⣿⡇⠀⠀⠻⣿⣿⣿⣷⣶⣶⣶⣶⣶⣿⣿⣿⣿⠃⠀⠀⠀
⠀⢰⣿⣿⡇⠀⣿⣿⣿⠀⠀⠀⠀⠈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⠁⠀⠀⠀⠀
⠀⢸⣿⣿⡇⠀⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠉⠛⠛⠛⠉⢉⣿⣿⠀⠀⠀⠀⠀⠀
⠀⢸⣿⣿⣇⠀⣿⣿⣿⠀⠀⠀⠀⠀⢀⣤⣤⣤⡀⠀⠀⢸⣿⣿⣿⣷⣦⠀⠀⠀
⠀⠀⢻⣿⣿⣶⣿⣿⣿⠀⠀⠀⠀⠀⠈⠻⣿⣿⣿⣦⡀⠀⠉⠉⠻⣿⣿⡇⠀⠀
⠀⠀⠀⠛⠿⣿⣿⣿⣿⣷⣤⡀⠀⠀⠀⠀⠈⠹⣿⣿⣇⣀⠀⣠⣾⣿⣿⡇⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣦⣤⣤⣤⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⡟⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠻⢿⣿⣿⣿⣿⣿⣿⠿⠋⠉⠛⠋⠉⠉⠁⠀⠀⠀⠀

si ca cel mai ⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛ nu este bebita. ⬛🟥🟥🟥🟥⬛⬛🟥⬛⬛🟥⬛⬛🟥🟥🟥🟥⬛ ⬛🟥⬛⬛⬛⬛⬛🟥⬛⬛🟥⬛⬛🟥⬛⬛⬛⬛ ⬛🟥🟥🟥🟥⬛⬛🟥⬛⬛🟥⬛⬛🟥🟥🟥🟥⬛ ⬛⬛⬛⬛🟥⬛⬛🟥⬛⬛🟥⬛⬛⬛⬛⬛🟥⬛ ⬛⬛⬛⬛🟥⬛⬛🟥⬛⬛🟥⬛⬛⬛⬛⬛🟥⬛ ⬛🟥🟥🟥🟥⬛⬛🟥🟥🟥🟥⬛⬛🟥🟥🟥🟥⬛ ⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛⬛

/*#include <iostream>
#include <cmath>
using namespace std;

int main()
{ int n,z,p,c; cin>>n; z=0; p=1; while(n>0){ c=n%10; n=int(n/10); if (c%3==0){ z=z+p*(9-c); p=p*10; } } cout<<z; return 0;
}
*/

/*
#include <iostream>
#include <cmath>
using namespace std;

int main()
{

int n,s; cin>>n; s=-1; while (n>0){ if(n%10>s){ s=n%10;} else{ s=11;} n=int(n/10); } cout<<s; return 0;

}
*/

#include <iostream>
#include <cmath>
using namespace std;

int main()
{

int n,k,p,nr; cin>>n>>k; nr=0; p=1; while (n!=0 && k!=0){ if(n%2==0){ nr=nr+n%10*p; p=p*10; }else { k=k-1; } n=int(n/10); } cout<<nr; return 0;

}

#include <iostream>
using namespace std;
int cmmdc(int a,int b){
if(b==0){return a;}
else{return cmmdc(b,a%b);}
}
void dei(int a¹⁰⁰¹,int st, int dr){ if(st==dr){cout<<a[dr]<<” “;} else{ int m=(st+dr)/2; dei(a,m+1,dr); dei(a,st,m); }
}
int main(){
int a¹⁰⁰¹,n;
cin>>n;
for(int i=1;i<=n;i++){cin>>a[i];}
dei(a,1,n);

}

Acest articol conține o listă cu subiecte date la examenul de bacalaureat, clasificate în funcție de problema ce presupune analiza algoritmilor pseudocod. Lista poate fi filtrată după an, categoria problemei și tipul structurii repetitive utilizate.

---

Structura repetitivă	Categorie	An	Link vechi	URL
Pentru	Divizibilitate	2021	2021, toamna	https://www.pbinfo.ro/resurse/9dc152/examene/2021/august/E_d_Informatica_2021_sp_MI_C_var_04_LRO.pdf
Pentru descrescător	Afișare valori	2021	2021, vara	https://www.pbinfo.ro/resurse/9dc152/examene/2021/iunie-iulie/E_d_Informatica_2021_sp_MI_C_var_01_LRO.pdf
Cât timp	Afișări de caractere	2021	2021, sesiunea specială	https://www.pbinfo.ro/resurse/9dc152/examene/2021/ses_speciala/E_d_Informatica_2021_sp_MI_C_var_07.pdf
Repetă	Cifre	2021	2021, simulare	https://www.pbinfo.ro/resurse/9dc152/examene/2021/simulare/E_d_Informatica_2021_sp_MI_C_var_Simulare_LRO.pdf
Pentru	Afișare valori	2021	2021, Test antrenament 12	https://www.pbinfo.ro/resurse/9dc152/examene/2021/antrenament/E_d_Informatica_2021_sp_MI_C_Test_12.pdf
Cât timp	Afișări de caractere	2021	2021, Test antrenament 11	https://www.pbinfo.ro/resurse/9dc152/examene/2021/antrenament/E_d_Informatica_2021_sp_MI_C_Test_11.pdf
Cât timp	Afișări de caractere	2021	2021, Test antrenament 10	https://www.pbinfo.ro/resurse/9dc152/examene/2021/antrenament/E_d_Informatica_2021_sp_MI_C_Test_10.pdf
Pentru	Afișări de caractere	2021	2021, Test antrenament 9	https://www.pbinfo.ro/resurse/9dc152/examene/2021/antrenament/E_d_Informatica_2021_sp_MI_C_Test_09.pdf
Pentru	Calcul expresie	2021	2021, Test antrenament 8	https://www.pbinfo.ro/resurse/9dc152/examene/2021/antrenament/E_d_Informatica_2021_sp_MI_C_Test_08.pdf
Cât timp	Cifre	2021	2021, Test antrenament 7	https://www.pbinfo.ro/resurse/9dc152/examene/2021/antrenament/E_d_Informatica_2021_sp_MI_C_Test_07.pdf
Cât timp	Cifre	2021	2021, Test antrenament 6	https://www.pbinfo.ro/resurse/9dc152/examene/2021/antrenament/E_d_Informatica_2021_sp_MI_C_Test_06.pdf
Repetă	Cifre	2021	2021, Test antrenament 5	https://www.pbinfo.ro/resurse/9dc152/examene/2021/antrenament/E_d_Informatica_2021_sp_MI_C_Test_05.pdf
Cât timp	Cifre	2021	2021, Test antrenament 4	https://www.pbinfo.ro/resurse/9dc152/examene/2021/antrenament/E_d_Informatica_2021_sp_MI_C_Test_04.pdf
Cât timp	Cifre	2021	2021, Test antrenament 3	https://www.pbinfo.ro/resurse/9dc152/examene/2021/antrenament/E_d_Informatica_2021_sp_MI_C_Test_03.pdf
Cât timp	Cifre	2021	2021, Test antrenament 2	https://www.pbinfo.ro/resurse/9dc152/examene/2021/antrenament/E_d_Informatica_2021_sp_MI_C_Test_02.pdf
Repetă	Cifre	2021	2021, Test antrenament 1	https://www.pbinfo.ro/resurse/9dc152/examene/2021/antrenament/E_d_Informatica_2021_sp_MI_C_Test_01.pdf
Repetă	Cifre	2020	2020, toamna	https://www.pbinfo.ro/resurse/9dc152/examene/2020/E_d_Informatica_2020_sp_MI_C_var_05_LRO.pdf
Repetă	Cifre	2020	2020, vara	https://www.pbinfo.ro/resurse/9dc152/examene/2020/E_d_Informatica_2020_sp_MI_C_var_06_LRO.pdf
Pentru	Cifre	2020	2020, sesiunea specială COVID	https://www.pbinfo.ro/resurse/9dc152/examene/2020/E_d_Informatica_2020_sp_MI_C_var_02_LRO.pdf
Cât timp, Pentru	Cifre	2020	2020, test antrenament 1 – cifre	https://www.pbinfo.ro/resurse/9dc152/examene/2020/1-18/E_d_Informatica_2020_sp_MI_C_var_test_01.pdf
Repetă	Cifre	2020	2020, test antrenament 2 – cifre	https://www.pbinfo.ro/resurse/9dc152/examene/2020/1-18/E_d_Informatica_2020_sp_MI_C_var_test_02.pdf
Repetă	Cifre	2020	2020, test antrenament 3 – cifre	https://www.pbinfo.ro/resurse/9dc152/examene/2020/1-18/E_d_Informatica_2020_sp_MI_C_var_test_03.pdf
Cât timp, Repetă	Cifre	2020	2020, test antrenament 4 – cifre	https://www.pbinfo.ro/resurse/9dc152/examene/2020/1-18/E_d_Informatica_2020_sp_MI_C_var_test_04.pdf
Cât timp	Divizibilitate	2020	2020, test antrenament 5	https://www.pbinfo.ro/resurse/9dc152/examene/2020/1-18/E_d_Informatica_2020_sp_MI_C_var_test_05.pdf
Cât timp	Diverse	2020	2020, test antrenament 6	https://www.pbinfo.ro/resurse/9dc152/examene/2020/1-18/E_d_Informatica_2020_sp_MI_C_var_test_06.pdf
Cât timp	Cifre	2020	2020, test antrenament 7	https://www.pbinfo.ro/resurse/9dc152/examene/2020/1-18/E_d_Informatica_2020_sp_MI_C_var_test_07.pdf
Repetă	Cifre	2020	2020, test antrenament 8	https://www.pbinfo.ro/resurse/9dc152/examene/2020/1-18/E_d_Informatica_2020_sp_MI_C_var_test_08.pdf
Pentru	Afișare valori	2020	2020, test antrenament 9	https://www.pbinfo.ro/resurse/9dc152/examene/2020/1-18/E_d_Informatica_2020_sp_MI_C_var_test_09.pdf
Repetă	Diverse	2020	2020, test antrenament 10	https://www.pbinfo.ro/resurse/9dc152/examene/2020/1-18/E_d_Informatica_2020_sp_MI_C_var_test_10.pdf
Repetă	Cifre	2020	2020, test antrenament 11	https://www.pbinfo.ro/resurse/9dc152/examene/2020/1-18/E_d_Informatica_2020_sp_MI_C_var_test_11.pdf
Cât timp	Cifre	2020	2020, test antrenament 12	https://www.pbinfo.ro/resurse/9dc152/examene/2020/1-18/E_d_Informatica_2020_sp_MI_C_var_test_12.pdf
Cât timp	Cifre, Citiri succesive	2020	2020, test antrenament 13	https://www.pbinfo.ro/resurse/9dc152/examene/2020/1-18/E_d_Informatica_2020_sp_MI_C_var_test_13.pdf
Repetă	Cifre	2020	2020, test antrenament 14	https://www.pbinfo.ro/resurse/9dc152/examene/2020/1-18/E_d_Informatica_2020_sp_MI_C_var_test_14.pdf
Pentru combinat	Diverse	2020	2020, test antrenament 15	https://www.pbinfo.ro/resurse/9dc152/examene/2020/1-18/E_d_Informatica_2020_sp_MI_C_var_test_15.pdf
Repetă	Cifre	2020	2020, test antrenament 16	https://www.pbinfo.ro/resurse/9dc152/examene/2020/1-18/E_d_Informatica_2020_sp_MI_C_var_test_16.pdf
Cât timp	Diverse	2020	2020, test antrenament 17	https://www.pbinfo.ro/resurse/9dc152/examene/2020/1-18/E_d_Informatica_2020_sp_MI_C_var_test_17.pdf
Pentru combinat	Afișare valori	2020	2020, test antrenament 18	https://www.pbinfo.ro/resurse/9dc152/examene/2020/1-18/E_d_Informatica_2020_sp_MI_C_var_test_18.pdf
Cât timp	Cifre	2020	2020, test antrenament 19	https://www.pbinfo.ro/resurse/9dc152/examene/2020/19-20/E_d_Informatica_2020_sp_MI_C_var_test_19.pdf
Cât timp	Divizibilitate	2020	2020, test antrenament 20	https://www.pbinfo.ro/resurse/9dc152/examene/2020/19-20/E_d_Informatica_2020_sp_MI_C_var_test_20.pdf
Cât timp	Cifre	2019	2019, toamna – cifre	https://www.pbinfo.ro/resurse/9dc152/examene/2019/2019-august-septembrie/E_d_Informatica_2019_sp_MI_C_var_02_LRO.pdf
Cât timp	Divizibilitate	2019	2019, vara – divizibilitate	https://www.pbinfo.ro/resurse/9dc152/examene/2019/2019-iunie-iulie/E_d_Informatica_2019_sp_SN_C_var_04_LRO.pdf
Cât timp	Cifre	2019	2019, sesiunea specială – cifre	https://www.pbinfo.ro/resurse/9dc152/examene/2019/2019-speciala/E_d_Informatica_2019_sp_MI_C_var_01_LRO.pdf
Cât timp	Cifre	2019	2019, simulare martie – cifre	https://www.pbinfo.ro/resurse/9dc152/examene/2019/simulare/E_d_Informatica_2019_sp_MI_C_var_simulare_LRO.pdf
Cât timp	Diverse	2018	2018, vara, subiect rezervă – diverse	https://www.pbinfo.ro/resurse/9dc152/examene/2018-iunie/E_d_Informatica_C_sp_SN_2018_var_08_LRO.pdf
Cât timp	Divizibilitate	2018	2018, sesiunea specială – divizibilitate	https://www.pbinfo.ro/resurse/9dc152/examene/2018-special/E_d_Informatica_C_sp_MI_2018_var_09_LRO.pdf
Repetă	Cifre	2018	2018, toamna – cifre	https://www.pbinfo.ro/resurse/9dc152/examene/2018-iunie/E_d_Informatica_C_sp_SN_2018_var_08_LRO.pdf
Repetă, Pentru	Cifre	2018	2018, vara – cifre	https://www.pbinfo.ro/resurse/9dc152/examene/2018-iunie/E_d_Informatica_C_sp_SN_2018_var_02_LRO.pdf
Cât timp	Citiri succesive	2017	2017, toamna – citiri succesive	https://www.pbinfo.ro/resurse/9dc152/examene/2017-august/E_d_Informatica_C_sp_MI_2017_var_07_LRO.pdf
Pentru	Afișări de caractere	2017	2017, vara	https://www.pbinfo.ro/resurse/9dc152/examene/2017-iunie/E_d_Informatica_C_sp_MI_2017_var_04_LRO.pdf
Pentru	Calcul expresie	2017	2017, vara, rezervă – calcul expresie	https://www.pbinfo.ro/resurse/9dc152/examene/2017-iunie/E_d_Informatica_C_sp_MI_2017_var_05_LRO.pdf
Pentru, Cât timp	Divizibilitate	2017	2017, sesiunea specială – divizibilitate	https://www.pbinfo.ro/resurse/9dc152/examene/2017-special/E_d_Informatica_C_sp_MI_2017_var_03_LRO.pdf
Cât timp	Divizibilitate	2016	2016, vara – divizibilitate	https://www.pbinfo.ro/resurse/9dc152/examene/2016-iunie/E_d_informatica_C_sp_MI_2016_var_10_LRO.pdf
Cât timp	Cifre	2016	2016, sesiunea specială – cifre	https://www.pbinfo.ro/resurse/9dc152/examene/2016-special/E_d_informatica_C_sp_MI_2016_var_04_LRO.pdf
Pentru	Divizibilitate	2016	2016, toamna – divizibilitate	https://www.pbinfo.ro/resurse/9dc152/examene/2016-august/E_d_informatica_C_sp_MI_2016_var_09_LRO.pdf
Cât timp	Afișare valori	2015	2015, toamna – afișare valori	https://www.pbinfo.ro/resurse/9dc152/examene/2015-august/E_d_informatica_C_sp_MI_2015_var_02_LRO.pdf
Cât timp	Divizibilitate	2015	2015, vara – divizibilitate	https://www.pbinfo.ro/resurse/9dc152/examene/2015-iunie/E_d_informatica_C_sp_MI_2015_var_09_LRO.pdf
Cât timp	Simulare operații	2015	2015, simulare bacalaureat – simulare operație	https://www.pbinfo.ro/resurse/9dc152/examene/2015-simulare-bac/E_d_informatica_C_sp_MI_2015_var_simulare_LRO.pdf
Pentru	Cifre	2015	2015, sesiunea specială – cifre	https://www.pbinfo.ro/resurse/9dc152/examene/2015-special/E_d_informatica_C_sp_MI_2015_var_05_LRO.pdf
Cât timp	Cifre	2014	2014, sesiunea specială – cifre	https://www.pbinfo.ro/resurse/9dc152/examene/2014/E_d_Informatica_C_sp_MI_2014_var_02_LRO.pdf
Cât timp	Divizibilitate	2014	2014, vara – divizibilitate	https://www.pbinfo.ro/resurse/9dc152/examene/2014/E_d_Informatica_C_sp_MI_2014_var_04_LRO.pdf
Repetă	Fibonacci	2014	2014, toamna – Fibonacci	https://www.pbinfo.ro/resurse/9dc152/examene/2014/E_d_Informatica_C_sp_MI_2014_var_10_LRO.pdf
Pentru	Cifre	2013	2013, vara – cifre	https://www.pbinfo.ro/resurse/9dc152/examene/2013/E_d_Informatica_C_sp_MI_var_02_LRO.pdf
Pentru	Cifre	2013	2013, vara – cifre	https://www.pbinfo.ro/resurse/9dc152/examene/2013/E_d_Informatica_C_sp_MI_var_06_LRO.pdf
Cât timp	Cifre	2012	2012, vara – cifre	https://www.pbinfo.ro/resurse/9dc152/examene/2012/E_d_Informatica_C_sp_MI_var_01_LRO.pdf
Pentru	Calcul expresie	2012	2012, toamna – calcul expresie	https://www.pbinfo.ro/resurse/9dc152/examene/2012/E_d_Informatica_C_sp_MI_var_04_LRO.pdf
Cât timp	Afișare valori	2011	2011, vara – afișare valori	https://www.pbinfo.ro/resurse/9dc152/examene/2011/Proba_E_d_Informatica_C_sp_MI_var_09.pdf
Cât timp	Cifre	2011	2011, toamna – cifre	https://www.pbinfo.ro/resurse/9dc152/examene/2011/Proba_E_d_Informatica_C_sp_MI_var_03.pdf
Repetă	Cifre	2010	2010, vara – cifre	https://www.pbinfo.ro/resurse/9dc152/examene/2010/Proba_E_d_Informatica_C_sp_MI_INT_subiect_10.pdf
Pentru	Diverse	2010	2010, toamna – diverse	https://www.pbinfo.ro/resurse/9dc152/examene/2010/Proba_E_d_Informatica_C_sp_MI_INT_subiect_10.pdf
Cât timp	Cifre	2009	Varianta 1, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_001.pdf
Cât timp	Citiri succesive	2009	Varianta 2, 2009 – citiri succesive	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_002.pdf
Cât timp	Citiri succesive	2009	Varianta 3, 2009 – citiri succesive	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_003.pdf
Cât timp	Cifre	2009	Varianta 6, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_006.pdf
Cât timp	Cifre	2009	Varianta 8, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_008.pdf
Cât timp	Cifre	2009	Varianta 9, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_009.pdf
Cât timp	Cifre	2009	Varianta 10, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_010.pdf
Cât timp	Cifre	2009	Varianta 11, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_011.pdf
Cât timp	Cifre	2009	Varianta 12, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_012.pdf
Cât timp	Cifre	2009	Varianta 14, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_014.pdf
Cât timp	Afișări de caractere	2009	Varianta 17, 2009 – afișări de caractere	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_017.pdf
Cât timp	Afișări de caractere	2009	Varianta 18, 2009 – afișări de caractere	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_018.pdf
Cât timp	Cifre	2009	Varianta 20, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_020.pdf
Cât timp	Divizibilitate	2009	Varianta 24, 2009 – divizibilitate	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_024.pdf
Cât timp	Divizibilitate	2009	Varianta 25, 2009 – divizibilitate	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_025.pdf
Cât timp	Simulare operații	2009	Varianta 27, 2009 – simulare operație	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_027.pdf
Cât timp	Numere reale	2009	Varianta 28, 2009 – numere reale	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_028.pdf
Cât timp	Diverse	2009	Varianta 29, 2009 – diverse	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_029.pdf
Cât timp	Cifre	2009	Varianta 30, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_030.pdf
Cât timp	Simulare operații	2009	Varianta 31, 2009 – simulare operație	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_031.pdf
Cât timp	Afișare valori	2009	Varianta 32, 2009 – afișare valori	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_032.pdf
Cât timp	Cifre	2009	Varianta 34, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_034.pdf
Cât timp	Divizibilitate	2009	Varianta 35, 2009 – divizibilitate	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_035.pdf
Cât timp	Citiri succesive, Cifre	2009	Varianta 36, 2009 – citiri succesive, cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_036.pdf
Cât timp	Cifre	2009	Varianta 37, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_037.pdf
Cât timp	Cifre	2009	Varianta 39, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_039.pdf
Cât timp	Divizibilitate	2009	Varianta 40, 2009 – divizibilitate	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_040.pdf
Cât timp	Divizibilitate	2009	Varianta 41, 2009 – divizibilitate	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_041.pdf
Cât timp	Diverse	2009	Varianta 42, 2009 – diverse	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_042.pdf
Cât timp	Divizibilitate	2009	Varianta 43, 2009 – divizibilitate	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_043.pdf
Cât timp	Cifre	2009	Varianta 44, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_044.pdf
Cât timp	Diverse	2009	Varianta 45, 2009 – diverse	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_045.pdf
Cât timp	Cifre	2009	Varianta 46, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_046.pdf
Cât timp	Cifre	2009	Varianta 49, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_049.pdf
Cât timp	Cifre, Factorial	2009	Varianta 54, 2009 – cifre, factorial	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_054.pdf
Cât timp	Divizibilitate	2009	Varianta 57, 2009 – divizibilitate	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_057.pdf
Cât timp	Cifre	2009	Varianta 58, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_058.pdf
Cât timp	Cifre	2009	Varianta 60, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_060.pdf
Cât timp	Cifre	2009	Varianta 61, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_061.pdf
Cât timp	Cifre	2009	Varianta 67, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_067.pdf
Cât timp	Simulare operații	2009	Varianta 70, 2009 – simulare operații	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_070.pdf
Cât timp	Cifre	2009	Varianta 74, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_074.pdf
Cât timp	Divizibilitate	2009	Varianta 76, 2009 – divizibilitate	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_076.pdf
Cât timp	Citiri succesive	2009	Varianta 77, 2009 – citiri succesive	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_077.pdf
Cât timp	Citiri succesive	2009	Varianta 78, 2009 – citiri succesive	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_078.pdf
Cât timp	Divizibilitate	2009	Varianta 79, 2009 – divizibilitate	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_079.pdf
Cât timp	Cifre	2009	Varianta 80, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_080.pdf
Cât timp	Cifre	2009	Varianta 83, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_083.pdf
Cât timp	Cifre	2009	Varianta 84, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_084.pdf
Cât timp	Cifre	2009	Varianta 85, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_085.pdf
Cât timp	Divizibilitate	2009	Varianta 87, 2009 – divizibilitate	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_087.pdf
Cât timp	Cifre	2009	Varianta 88, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_088.pdf
Cât timp	Cifre	2009	Varianta 89, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_089.pdf
Cât timp	Afișare valori	2009	Varianta 90, 2009 – afișări valori	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_090.pdf
Cât timp	Calcul expresie	2009	Varianta 93, 2009 – calcul expresie	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_093.pdf
Cât timp	Cifre	2009	Varianta 94, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_094.pdf
Cât timp	Cifre	2009	Varianta 95, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_095.pdf
Cât timp	Simulare operații	2009	Varianta 98, 2009 – simulare operație	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_098.pdf
Cât timp	Cifre	2009	Varianta 100, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_100.pdf
Repetă	Simulare operație	2009	Varianta 21, 2009 – simulare operație	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_021.pdf
Repetă	Diverse	2009	Varianta 23, 2009 – diverse	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_023.pdf
Repetă	Cifre	2009	Varianta 47, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_047.pdf
Repetă	Cifre	2009	Varianta 51, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_051.pdf
Repetă	Cifre	2009	Varianta 53, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_053.pdf
Repetă	Cifre	2009	Varianta 56, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_056.pdf
Repetă	Cifre	2009	Varianta 59, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_059.pdf
Repetă	Cifre	2009	Varianta 65, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_065.pdf
Repetă	Citiri succesive	2009	Varianta 66, 2009 – citiri succesive	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_066.pdf
Repetă	Cifre	2009	Varianta 69, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_069.pdf
Repetă	Citiri succesive, Cifre	2009	Varianta 75, 2009 – citiri succesive, cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_075.pdf
Repetă	Numere reale	2009	Varianta 91, 2009 – numere reale	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_091.pdf
Repetă, Cât timp	Cifre	2009	Varianta 5, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_005.pdf
Repetă, Cât timp	Cifre	2009	Varianta 62, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_062.pdf
Pentru	Cifre	2009	Varianta 13, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_013.pdf
Pentru	Calcul expresie	2009	Varianta 15, 2009 – calcul de expresie	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_015.pdf
Pentru	Afișări de caractere	2009	Varianta 16, 2009 – afișări de caractere	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_016.pdf
Pentru	Cifre	2009	Varianta 19, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_019.pdf
Pentru	Divizibilitate	2009	Varianta 22, 2009 – divizibilitate	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_022.pdf
Pentru	Afișare valori	2009	Varianta 26, 2009 – afișare de valori	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_026.pdf
Pentru	Calcul expresie	2009	Varianta 33, 2009 – calcul expresie	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_033.pdf
Pentru	Cifre	2009	Varianta 48, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_048.pdf
Pentru	Cifre	2009	Varianta 50, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_050.pdf
Pentru	Zerouri	2009	Varianta 52, 2009 – zerouri	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_052.pdf
Pentru	Cifre	2009	Varianta 55, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_055.pdf
Pentru	Divizibilitate	2009	Varianta 63, 2009 – divizibilitate	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_063.pdf
Pentru	Afișare valori	2009	Varianta 64, 2009 – afișări de valori	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_064.pdf
Pentru	Citiri succesive, Divizibilitate	2009	Varianta 68, 2009 – citiri succesive, divizibilitate	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_068.pdf
Pentru	Cifre	2009	Varianta 71, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_071.pdf
Pentru	Afișări de caractere	2009	Varianta 72, 2009 – afișări caractere	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_072.pdf
Pentru	Diverse	2009	Varianta 73, 2009 – diverse	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_073.pdf
Pentru	Calcul expresie	2009	Varianta 81, 2009 – calcul expresie	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_081.pdf
Pentru	Citiri succesive, Cifre	2009	Varianta 82, 2009 – citiri succesive, cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_082.pdf
Pentru	Afișare valori	2009	Varianta 86, 2009 – afișări valori	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_086.pdf
Pentru	Citiri succesive	2009	Varianta 92, 2009 – citiri succesive	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_092.pdf
Pentru	Diverse	2009	Varianta 99, 2009 – diverse	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_099.pdf
Pentru descrescător	Afișare valori	2009	Varianta 4, 2009 – afișare valori	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_004.pdf
Pentru descrescător	Cifre	2009	Varianta 7, 2009 – cifre	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_007.pdf
Pentru combinat	Calcul expresie	2009	Varianta 38, 2009 – calcul expresii	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_038.pdf
Pentru combinat	Citiri succesive	2009	Varianta 96, 2009 – afișare valori	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_096.pdf
Pentru combinat	Afișare valori	2009	Varianta 97, 2009 – citiri succesive	http://bacinfo.cnlr.ro/subiecte-bac/2009/e_info_intensiv_c_si_097.pdf

Citiți mai întâi Generarea aranjamentelor!

Introducere

Consideram o mulțime cu A cu n elemente. Prin combinări de k elemente din A înțelegem submulțimile cu k elemente ale multimii A. Numărul acestor combinări este \(C_n^k = \frac{A_n^k}{P_k}\). Mai multe formule pentru calculul numărului de combinări pot fi găsite în acest articol.

Acest articol prezintă un algoritm backtracking pentru determinarea în ordine lexicografică a combinărilor de k elemente ale mulțimii A={1 , 2 , ... , n}, elemente dintr-o combinare fiind generate în ordine crescătoare. El poate fi adaptat pentru determinarea combinărilor de k elemente ale unei mulțimi oarecare de n elemente.

Deoarece în algoritmul recursiv general apare funcția Back() cu parametrul k, pentru a păstra notațiile din algoritm vom considera în continuare combinările de k elemente luate câte p.

Soluția 1

Condiții

Ca orice rezolvare cu algoritmul backtracking, începem prin a preciza semnificația vectorului soluție. Astfel, x[] reprezintă o combinare. În consecință, el va respecta următoarele condiții:

• elemenele vectorului sunt valori între 1 și n;
• elementele nu se repetă;
• elementele sunt ordonate crescător
• vectorul se completează element cu element. Când va avea p elemente, reprezintă o combinare completă, care urmează a fi afișată.

Formal, exprimăm proprietățile de mai sus astfel:

• condiții externe: \( x[k] \in \left\{ 1,2, \ldots, n \right\} \);
• condiții interne:
  • \(x[k] \notin \left\{ x[ 1 ],x[ 2 ], \ldots, x[ k-1 ] \right\}\), pentru \( k \in \left\{2,3, \ldots, n \right \} \)
  • \(x[k] > x[k-1]\), pentru \( k \in \left\{2,3, \ldots, n \right \} \)
• condiții de existență a soluției: \(k = p\)

Observăm (din nou) că în verificarea condițiilor interne intervine doar elementul x[k] (cel care este verificat) și elementele deja generate (x[1], x[2], … , x[k-1]).

Observăm că aceste condiții sunt cele de la generarea aranjamentelor, la care se adaugă condiția internă legată de ordinea elementelor din vector. În consecință, programul va fi cel de la aranjamente, cu completarea funcției OK().

Sursa C++

#include <iostream>
using namespace std;

int x[10] , n , p;

void Afis(int k)
{
    for(int j = 1 ; j <= k ; j ++)
        cout << x[j] << " ";
    cout << endl;
}

bool OK(int k){
    for(int i = 1 ; i < k ; ++ i)
        if(x[k] == x[i])
            return false;
    if(k > 1)
		if(x[k] <= x[k-1])
			return false;
    return true;
}

bool Solutie(int k)
{
    return k == p;
}

void back(int k){
    for(int i = 1 ; i <= n ; ++ i)
    {
        x[k] = i;
        if(OK(k))
            if(Solutie(k))
                Afis(k);
            else
                back(k + 1);
    }
}
int main(){
    cin >> n >> p;
    back(1);
    return 0;
}

Soluția 2

Rafinarea condițiilor

Condițiile de mai sus pot fi îmbunătățite, făcând următoarele observații:

1. cele două condiții interne pot fi reduse la una singură. Dacă pentru fiecare \( k \) are loc relația \(x[k] > x[k-1]\) atunci are loc și condiția \(x[k] \notin \left\{ x[ 1 ],x[ 2 ], \ldots, x[ k-1 ] \right\}\);
   Condițiile devin:
   • condiții externe: \( x[k] \in \left\{ 1,2, \ldots, n \right\} \);
   • condiții interne: \(x[k] > x[k-1]\), pentru \( k > 1 \)
   • condiții de existență a soluției: \(k = p\)
2. condiția internă poate fi transformată în condiție externă. Dacă \(x[k] > x[k-1]\) atunci valorile pe care le poate lua \(x[k]\) (condiții externe) sunt \( \left\{ x[k-1] + 1, \ldots, n \right\} \). Condițiile devin:
   • condiții externe: \( x[k] \in \left\{ x[k-1] +1 , x[k-1] +2, \ldots, n \right\} \);
   • condiții interne: nu există
   • condiții de existență a soluției: \(k = p\)

Cazul \(k = 1\) este unul special. Valorile pe care le poate lua sunt \(\left\{ 1 , 2 , 3 , \ldots \right\} \). Pentru a fi condițiile externe de mai sus corecte în în acest caz, este necesară inițializarea x[ 0 ] = 0, înaintea începerii generării.

Sursă C++

#include <iostream>
using namespace std;

int x[10] , n , p;

void Afis(int k)
{
    for(int j = 1 ; j <= k ; j ++)
        cout << x[j] << " ";
    cout << endl;
}

void back(int k){
    for(int i = x[k-1] + 1 ; i <= n ; ++ i)
    {
        x[k] = i;
		if(k == p)
			Afis(k);
		else
			back(k + 1);
    }
}
int main(){
    cin >> n >> p;
    x[0] = 0;
    back(1);
    return 0;
}

Probleme

combinari combinari2 siruri SubmDiv cifre_c subimp2

Citește și

• Prezentare generală
• Generarea permutărilor
• Generarea aranjamentelor

• Generarea submulțimilor

Citiți mai întâi Generarea permutărilor!

Introducere

Considerăm o mulțime cu n elemente. Prin aranjamente de k elemente din acea mulțime înțelegem șirurile de k elemente din ea. Două șiruri diferă prin valorile elementelor sau prin ordinea acestora.

Numărul acestor șiruri este aranjamente de n luate câte k, adică \(A_n^k = n \cdot (n-1) \cdot \ldots \cdot(n – k +1) \).

Acest articol prezintă algoritmul de generare în ordine lexicografică a aranjamentelor de k elemente ale mulțimii {1, 2, ..., n}. El poate fi ușor modificat pentru a genera aranjamentele unei mulțimi cu elemente oarecare.

Metoda folosită va fi backtracking, varianta recursivă. Deoarece în algoritmul de generare folosit intervine variabila k, ca parametru al funcției Back(), vom considera în continuare aranjamentele de n elemente luate câte p.

Exemplu

Pentru n = 4 și p = 3 vom avea 4 * 3 * 2 = 24 de aranajamente. Lista completă a acestora este:

1 2 3		2 1 3		3 1 2		4 1 2
1 2 4		2 1 4		3 1 4		4 1 3
1 3 2		2 3 1		3 2 1		4 2 1
1 3 4		2 3 4		3 2 4		4 2 3
1 4 2		2 4 1		3 4 1		4 3 1
1 4 3		2 4 3		3 4 2		4 3 2

Condiții

În rezolvarea problemei intervine vectorul soluție, x[]. Acesta reprezintă un aranjament candidat, care va deveni la un moment dat un aranjament de p elemente complet. Proprietățile vectorului soluție sunt cele specifice aranjamentelor:

• elementele sunt din mulțimea dată, adică numere intre 1 și n;
• elementele nu se repetă;
• vectorul se completează element cu element. Când va avea p elemente, reprezintă un aranjament complet, care urmează a fi afișat.

Formal, exprimăm proprietățile de mai sus astfel:

• condiții externe: \( x[k] \in \left\{ 1,2, \ldots, n \right\} \);
• condiții interne: \(x[k] \notin \left\{ x[ 1 ],x[ 2 ], \ldots, x[ k-1 ] \right\}\), pentru \( k \in \left\{2,3, \ldots, n \right \} \)
• condiții de existență a soluției: \(k = p\)

Sursă C++

Următorul program afișează pe ecran aranjamantele de n alemente luate câte p, în ordine lexicografică, folosind un algoritm recursiv:

#include <iostream>
using namespace std;

int x[10] , n , p;

void Afis(int k)
{
    for(int j = 1 ; j <= k ; j ++)
        cout << x[j] << " ";
    cout << endl;
}

bool OK(int k){
    for(int i = 1 ; i < k ; ++ i)
        if(x[k] == x[i])
            return false;
    return true;
}

bool Solutie(int k)
{
    return k == p;
}

void Back(int k){
    for(int i = 1 ; i <= n ; ++ i)
    {
        x[k] = i;
        if(OK(k))
            if(Solutie(k))
                Afis(k);
            else
                Back(k + 1);
    }
}
int main(){
    cin >> n >> p;
    Back(1);
    return 0;
}

Se poate observa că atât condițiile descrise mai sus, cât și algoritmul de generare sunt foarte asemănătoare cu cele de la generarea permutărilor.

Acest lucru se datorează faptului că, la ambele probleme, vectorii soluție identici în ceea ce privește conținutul: șiruri de elemente diferite cuprinse între 1 și n. Diferă numai lungimea lor – momentul când vectorul soluție x[] conține o soluție completă:

• la problema permutărilor un vector soluție final are n elemente (toate elementele mulțimii date, într-o anumită ordine);
• la problema aranjamentelor un vector soluție final are p elemente (p elemente dintre cele n ale mulțimii date, într-o anumită ordine).

La fel ca în cazul generării permutărilor, și pentru această problemă se pot scrie soluții iterative, precum și soluții în care verificarea condițiilor interne să se facă cu un vector caracteristic, evitându-se parcurgerile repetate ale vectorului soluție.

Probleme propuse

196 3159

Citește și

• Prezentare generală
• Generarea permutărilor

• Generarea combinărilor
• Generarea submulțimilor

Tipul char este folosit pentru lucrul cu caractere. O dată de acest tip va reprezenta un singur caracter. Pentru a stoca mai multe caractere vom folosi un tablou cu elemente char sau un string.

Variabile de tip char

O variabilă de tip char se declară astfel:

char C;

Valoarea unei variabile de tip char (sau signed char) este un număr natural cuprins între -128 și 127. Valorile cuprinse între 0 și 127 corespund caracterelor din codul ASCII.

Similar, datele de tip unsigned char au valori între 0 și 255. Observăm că ambele tipuri conțin valorile care corespund caracterelor din codul ASCII.

Literali

Un literal (valoare) de tip char este un caracter din codul ASCII, delimitat de caractere apostrof ‘.

Putem inițializa o variabilă de tip char atribuindu-i un literal de tip char sau o valoare numerică. Dacă valoarea numerică nu aparține intervalului de valori corespunzător, aceasta va fi trunchiată.

char C;
C = 'A';
C = 65;

Atenție! “ – ghilimele delimitează șiruri de caractere. Un șir de caractere format dintr-un singur caracter nu este același lucru cu un caracter.
“A” ≠ ‘A’!

Afișarea și citirea

Deși datele de tip char memorează numere întregi, la citirea și afișarea lor se va lucra cu caractere.

Afișarea

char C = 'A';
cout << C; // A
C = 65;
cout << C; // A

Afișarea unei date de tip char se face astfel:

• dacă valoarea este din codul ASCII, se va afișa caracterul corespunzător. Pentru caracterele neimprimabile efectul depinde de caracter și de mediul în care se lucrează (este posibil să nu se afișeze nimic sau să se afișeze diverse simboluri).
• dacă valoarea este din afara codului ASCII, efectul depinde de mediul în care se lucrează.

Citirea

char C;
cin >> C;
...

În urma citirii de la tastatură unei variabile de tip char, aceasta va reprezenta caracterul introdus. Dacă se introduc mai multe caractere, se va citi doar primul dintre ele.

Exemple

char x;
cin >> x; // introducem A
cout << x; // A

char x;
cin >> x; // introducem 145
cout << x; // 1

char x, y;
cin >> x >> y; // introducem A B
cout << x << endl; // A 
cout << y << endl; // B	

char x, y;
cin >> x >> y; // introducem AB
cout << x << endl; // A 
cout << y << endl; // B

char x, y;
cin >> x >> y; // introducem ABC
cout << x << endl; // A 
cout << y << endl; // B

char x, y;
cin >> x >> y; // introducem 65 66
cout << x << endl; // 6
cout << y << endl; // 5

Operații. Conversii de tip

Valorile de tip char pot fi convertite la alte tipuri.

char x;
x = 65; // conversie implicită de la int la char
cout << x; // A
cout << (int) x; // 65
int n = 65;
cout << (char) n; //A

Cu datele de tip char se pot face toate operațiile uzuale cu numere. Valoarea de tip char va fi convertită implicit la int, apoi se vor face operațiile.

char x = 'A';
cout << x + 1; // 66
cout << (char)(x + 1); // B

char x = 'A';
x ++;
cout << x; // B

Transformarea între litere mari și mici

O problemă frecventă este determinarea, pentru o literă mare, a literei mici corespunzătoare, sau invers. Rezolvarea se bazează pe faptul că, în codul ASCII, literele mari sunt poziționate înaintea celor mici, iar diferența dintre codul ASCII a unei litere mici și codul ASCII a literei mari corespunzătoare este aceeași pentru toate literele (32).

Transformarea se va face scăzând această valoare din litera mică, sau adunând-o la litere mare:

int dif = 'a' - 'A'; // 32
char x = 'k';
x = x - dif;
cout << x; // K

C++ ne permite să considerăm o valoare de un anumit tip da fiind de alt tip. Aceasta se numește conversie de tip.

În C++ sunt două feluri de conversii de tip:

• conversia implicită
• conversia explicită

Conversia implicită

Conversia implicită intervine de la sine când într-o operație avem operanzi de tipuri diferite. Compilatorul consideră automat ambele date de același tip pentru a putea efectua operația.

Conversia implicită se face doar dacă operanzii sunt de tipuri compatibile – vezi mai jos o listă de compatibilități pentru tipurile numerice. Dacă tipurile nu sunt compatibile obținem eroare de sintaxă!

Exemple

Conversie de la int la double

#include <iostream>
using namespace std;

int main()
{
    int n = 5;
    double x;

    /// conversie de la int la double
    x = n;

    cout << "n = " << n << endl;
    cout << "x = " << x << endl;
	return 0;
}

n = 5
x = 5

Conversie de la double la int

#include <iostream>
using namespace std;

int main()
{
    int n;
    double x = 5.75;

    /// conversie de la double la int

    n = x;

    cout << "n = " << n << endl;
    cout << "x = " << x << endl;
	return 0;
}

n = 5
x = 5.75

Deoarece o dată de tip int memorează numere întregi, în timpul conversiei zecimalele valorii lui x s-au pierdut.

Pierderea de date în timpul conversiei

Așa cum am văzut în exemplul anterior, conversia de tip poate duce la pierderea (trunchierea) unor date. Acest lucru nu este neapărat rău, dar trebuie să fim conștienți de această situație.

În fapt, conversia este de două feluri:

• promovare – conversie de la un tip de date inferior la unul superior; nu produce pierdere de date!
• retrogradare – conversie de la un tip de date superior la unul inferior; poate produce pierdere de date!

În primul exemplu de mai sus a avut loc o promovare de la int la double, iar în al doilea exemplu a avut loc o retrogradare de la double la int. Cea de-a doua a condus la pierderea unor date.

În situațiile în care este posibil, compilatorul realizează conversiile implicite prin promovare.

De exemplu, rezultatul expresiei 2 + 1.5 va fi 3.5, nu 3. Are loc promovarea valorii 2 la tipul double, nu retrogradarea lui 1.5 la int, ceea ce ar fi însemnat pierderi de date!

Conversia explicită

Conversia explicită a datelor înseamnă modificarea manuală, de către programator, a tipurilor de date folosite într-o expresie. Se mai numește și type casting.

Operatorul de conversie explicită

Are sintaxa:

(TIP) expresie

sau

TIP(expresie)

Observații

• este un operator unar;
• are prioritate mare;
• rezultatul său este rezultatul expresiei, considerat de tipul de date TIP;
• în varianta a doua TIP trebuie să fie un nume de tip format dintr-un singur cuvânt. Astfel, expresia unsigned int(expresie) este greșită.

Exemplu

char c='A';
cout << (int) c << endl; // 65
cout << char(97) << endl; // a

Notă: Limbajul C++ oferă și următorii operatori de conversie: static_cast, dynamic_cast, const_cast și reinterpret_cast.

Câteva reguli privind conversia

• dacă se convertește un întreg negativ la un tip fără semn rezultatul va fi complementul în baza 2 a valorii inițiale, datorită modului de reprezentare a valorilor întregi. Astfel, -1 devine cea mai mare valoare a tipului fără semn, -2 devine a doua cea mai mare valoare, etc.
• la conversia unei valori numerice la tiplul bool rezultatul va fi:
  • true, dacă valoarea inițială este nenulă;
  • false, dacă valoarea inițială este 0;
• la conversia unei valori de tip float, double la un tip întreg, valoare se va trunchia, pierzându-se partea zecimală. Dacă rezultatul nu se încadrează în limitele tipului întreg, comportamentul programului devine impredictibil.

Regulile de mai sus se aplică atât pentru conversia implicită, cât și pentru cea explicită.

Exemplu: media aritmetică

Să presupunem că dorim să determinăm media aritmetică trei numere întregi. Desigur, răspunsul este suma numerelor împărțită la 3, dar trebuie ținut cont de faptul că împărțirea a doi întregi este câtul împărțirii. Pentru a obține media corectă va trebui să facem anumite conversii.

Exemplu 1 – conversie implicită

int a , b,  c;
cin >> a >> b >> c;
int S = a + b + c;
/// cout << S / 3; // gresit - impartire intreaga
cout << S / 3.0;

A avut loc conversia implicită a lui S la double (promovare).

Exemplu 2 – conversie implicită

int a , b,  c;
cin >> a >> b >> c;
int S = a + b + c;
cout << 1.0 * S / 3;

A avut loc conversia implicită a lui S, apoi a lui 3, la double (promovări).

Exemplu 3 – conversie explicită

int a , b,  c;
cin >> a >> b >> c;
int S = a + b + c;
cout << (double)S / 3;

Mai întâi se convertește explicit valoarea lui S la double, apoi are loc conversia implicită la double a lui 3.

Evitarea depășirii de tip

În numeroase situații avem operații cu date de tip int, dar rezultatul depășește limita maximă (sau minimă) a acestui tip. Astfel se produce depășirea de tip – overflow. Soluția este utilizarea unor conversii prin care operațiile se realizează într-un tip de date mai larg, de exemplu long long.

Exemplu:

int n = 1000000;
cout << n * n << endl; /// posibil -727379968 - overflow
cout << 1LL * n * n << endl; /// corect 1000000000000
cout << (long long) n * n << endl; /// corect

La realizarea conversiilor trebuie ținut cont de precedența operatorilor. De exemplu, secvența de mai jos nu obține rezultatul corect.

int n = 1000000;
cout << 1LL * n + n * n << endl;
cout << (long long)n + n * n << endl;

Mai multe detalii despre conversii sunt diponibile aici: en.cppreference.com/w/cpp/language/implicit_conversion.

Definiție

Operatorul condițional este singurul operator ternar (cu trei operanzi) din C++. Sintaxa lui este:

ExpresieConditionala ? Expresie1 : Expresie2

și se evaluează astfel:

• se evaluează ExpresieConditionala. Rezultatul său va fi convertit implicit la bool.
• dacă rezultatul lui ExpresieConditionala este true, se evaluează Expresie1 și rezultatul său va fi rezultatul operației ?
• dacă rezultatul lui ExpresieConditionala este false, se evaluează Expresie2 și rezultatul său va fi rezultatul operației ?

Expresie2 și Expresie3 trebuie să aibă rezultate de același tip, sau de tipuri compatibile.

Exemplu

int x;
cin >> x;
cout << (x % 2 == 0? "par" : "impar");

Observații

• Operatorul ? poate fi înlocuit cu instrucțiunea if. Secvența de mai sus poate fi rescrisă astfel:
  

  int x;
  
  cin >> x;
  
  if (x % 2 == 0)
  	cout << “par”;
  
  else
  	cout << “impar”;

• Operațiile condiționale pot fi imbricate:
  

  cout << (x > 0? “pozitiv” : x == 0 ? “nul” : “negativ”);

• Rezultatele celor două expresii care reprezintă rezultatele posibile trebuie să fie de același tip sau de tipuri compatibile. Următoarea secvență nu este corectă;
  

  int x;
  
  cin >> x;
  
  cout << (x == 1? 1 : “diferit de 1”); // error: operands to ?: have different types ‘int’ and ‘const char*’

• Dacă expresiile Expresie1 și Expresie2 sunt de tip lvalue (de exemplu, variabile), rezultatul operației este chiar data corespunzătoare, nu valoarea ei, care poate fi apoi supusă unei atribuiri:
  

  int x = 1, y = 2, a = 10;
  
  ((a % 2 == 0) ? x : y) = 5;
  
  cout << x << “ “ << y << endl; // 5 2

Cea mai fecventă eroare este să uităm prioritatea operatorilor. Operatorul condițional are prioritate scăzută și este probabil să facem diverse erori!