La concursul Mate Info UBB, ediția 2021 a fost dat următorul exercițiu:
Fie \(b_nb_{n-1}…b_0\) reprezentarea binară a numărului natural \(B\), \(2021 ≤ B ≤ 2021^{2021}\). Care dintre următoarele afirmații sunt adevărate?
A. Dacă valoarea expresiei \(b_0-b_1+b_2-b_3+…..+(-1)^n *b_n\) este zero, atunci \(B\) este divizibil cu \(3\)
B. Dacă valoarea expresiei \(b_0-b_1+b_2-b_3+…..+(-1)^n *b_n\) este divizibilă cu \(3\), atunci \(B\) este divizibil cu \(3\)
C. \(B\) este divizibil cu \(3\) dacă suma cifrelor binare este divizibilă cu \(3\), dar nu cu \(9\)
D. Dacă \(B\) este divizibil cu \(3\), atunci valoarea expresiei \(b_0-b_1+b_2-b_3+…..+(-1)^n *b_n\) este divizibilă cu \(3\)
Răspunsul corect este: A, B, D.
Varianta C. se elimină imediat, deoarece reprezentarea binară a lui 3
este 11
, iar suma cifrelor binare este 2
, nedivizibil cu 3
.
Pentru a demonstra că afirmațiile A., B. și D. sunt adevărate vom demonstra următoarea afirmație, mai generală.
Teoremă: Fie \(N\) un număr natural a cărui reprezentare în baza \(B\) este \(b_nb_{n-1}…b_0\). Numărul \(N\) este divizibil cu \(B+1\) dacă și numai dacă expresia \(E = b_0-b_1+b_2-b_3+…..+(-1)^n *b_n\) este divizibilă \(B+1\).
Pentru a demonstra teorema de mai sus, vom demonstra mai întâi următoarea lemă:
Lemă: Fie \(P\) un număr natural. Atunci \(P^{2k}\) este de forma \(X \cdot (P+1)+1\), iar \(P^{2k+1}\) este de forma \(Y \cdot (P+1)-1\)
Demonstrația lemei se face prin inducție. Mai întâi să observăm că \(P^{0} = 1 = 0 \cdot (P+1) + 1\), iar \(P^{1} = P = 1 \cdot (P+1) – 1\).
Dacă \(P^{2k} = X \cdot (P+1)+1\), atunci \(P^{2k+1} = P \cdot P^{2p} \\= P \cdot (X \cdot (P+1)+1) \\= P \cdot X \cdot (P+1)+P \\= P \cdot X \cdot (P+1)+P + 1 – 1 \\= (P \cdot X+1)\cdot(P+1)-1 \\= Y \cdot (P+1) -1\)
Similar, dacă \(P^{2k+1} = Y \cdot (P+1)-1\), atunci \(P^{2k+2} = P \cdot P^{2k+1} \\= P \cdot (Y \cdot (P+1) -1) \\= P \cdot Y \cdot (P + 1) – P \\= P \cdot Y \cdot (P + 1) – P – 1 + 1 \\= P \cdot Y \cdot (P + 1) – (P + 1) + 1 \\= (P \cdot Y -1) \cdot (P + 1) + 1 \\= X \cdot (P+1) + 1\)
Demonstrația teoremei Dacă \(b_nb_{n-1}…b_0\) este reprezentarea în baza \(B\) a lui \(N\), atunci
$$N=b_0 \cdot B^0 + b_1 \cdot B^1 + b_2 \cdot B^2 + b_3 \cdot B^3 + … + b_n \cdot B^n$$
Deoarece puterile lui \(B\) sunt de forma precizată în lemă, obținem:
$$\begin{aligned} N &= b_0 \cdot ((B+1) \cdot f_0 + 1) + b_1 \cdot ((B+1) \cdot f_1 – 1) + b_2 \cdot ((B+1) \cdot f_2 + 1) + b_3 \cdot ((B+1) \cdot f_3 – 1) + \cdots + b_n \cdot ((B+1) \cdot f_n + (-1)^n) \\
& = ((B+1) \cdot b_0 \cdot f_0 + b_0) + ((B+1) \cdot b_1 \cdot f_1 – b_1) + ((B+1) \cdot b_2 \cdot f_2 + b_2) + ((B+1) \cdot b_3 \cdot f_3 – b_3) + \cdots + ((B+1) \cdot b_n \cdot f_n + (-1)^n \cdot b_n)\\
& = (B+1) \cdot b_0 \cdot f_0 + (B+1) \cdot b_1 \cdot f_1 + (B+1) \cdot b_2 \cdot f_2 + (B+1) \cdot b_3 \cdot f_3 + \cdots + (B+1) \cdot b_n \cdot f_n + b_0 – b_1 + b_2 – b_3 + \cdots + (-1)^n \cdot b_n\\
& = (B+1) \cdot ( b_0 \cdot f_0 + \cdot f_1 + b_2 \cdot f_2 + \cdot b_3 \cdot f_3 + \cdots + \cdot b_n \cdot f_n) + b_0 – b_1 + b_2 – b_3 + \cdots + (-1)^n \cdot b_n\\
& = (B+1) \cdot M + b_0 – b_1 + b_2 – b_3 + \cdots + (-1)^n \cdot b_n\\
\end{aligned}$$
Deoarece \((B+1) \cdot M\) este divizibil cu \(B+1\), deducem că \(N\) este divizibil cu \(B+1\) dacă și numai dacă \(b_0 – b_1 + b_2 – b_3 + \cdots + (-1)^n \cdot b_n\) este divizibil cu \(B+1\)!
Observații:
Exercițiul de mai sus este un caz particular al teoremei, în care \(B = 2\).
Expresia \(E\) poate fi scrisă și \(E = (b_0 + b_2 + …) – (b_1 + b_3 + …)\) – diferența dintre suma cifrelor de rang par și suma cifrelor de rang impar. Dacă \(B=10\), proprietatea de mai sus este “Criteriul de divizibilitate cu 11
”.
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 |
---|---|---|---|---|
Repetă | Cifre, Divizibilitate | 2022 | 2022, sesiunea specială | https://www.pbinfo.ro/resurse/9dc152/examene/2022/E_d_informatica_2022_sp_MI_C_var_04_LRO.pdf |
Cât timp | Cifre | 2022 | 2022, simulare | https://www.pbinfo.ro/resurse/9dc152/examene/2022/E_d_informatica_2022_sp_MI_C_var_simulare_LRO.pdf |
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!
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
.
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:
1
și n
;p
elemente, reprezintă o combinare completă, care urmează a fi afișată.Formal, exprimăm proprietățile de mai sus astfel:
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()
.
#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; }
Condițiile de mai sus pot fi îmbunătățite, făcând următoarele observații:
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.
#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; }
combinari combinari2 siruri SubmDiv cifre_c subimp2
Citiți mai întâi Generarea permutărilor!
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
.
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
Î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:
1
și n
;p
elemente, reprezintă un aranjament complet, care urmează a fi afișat.Formal, exprimăm proprietățile de mai sus astfel:
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ă:
n
elemente (toate elementele mulțimii date, într-o anumită ordine);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.
196 3159
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
.
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.
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’
!
Deși datele de tip char
memorează numere întregi, la citirea și afișarea lor se va lucra cu caractere.
char C = 'A'; cout << C; // A C = 65; cout << C; // A
Afișarea unei date de tip char
se face astfel:
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.
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
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
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ă 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ă!
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.
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:
Î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ă a datelor înseamnă modificarea manuală, de către programator, a tipurilor de date folosite într-o expresie. Se mai numește și type casting.
Are sintaxa:
(TIP) expresie
sau
TIP(expresie)
Observații
expresiei
, considerat de tipul de date TIP
;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
.
-1
devine cea mai mare valoare a tipului fără semn, -2
devine a doua cea mai mare valoare, etc.bool
rezultatul va fi:
true
, dacă valoarea inițială este nenulă;false
, dacă valoarea inițială este 0
;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ă.
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.
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).
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).
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
.
Î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.
Operatorul condițional este singurul operator ternar (cu trei operanzi) din C++. Sintaxa lui este:
ExpresieConditionala ? Expresie1 : Expresie2
și se evaluează astfel:
ExpresieConditionala
. Rezultatul său va fi convertit implicit la bool
.ExpresieConditionala
este true
, se evaluează Expresie1
și rezultatul său va fi rezultatul operației ?
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.
int x; cin >> x; cout << (x % 2 == 0? "par" : "impar");
?
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”;
cout << (x > 0? “pozitiv” : x == 0 ? “nul” : “negativ”);
int x;
cin >> x;
cout << (x == 1? 1 : “diferit de 1”); // error: operands to ?: have different types ‘int’ and ‘const char*’
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!
În general, incrementarea unei date înseamnă mărirea valorii sale, de obicei cu 1
, iar decrementarea unei date înseamnă micșorarea valorii sale.
Aceste operații sunt foarte frecvente. De aceea, numeroase limbaje de programare (inclusiv C/C++, Java, Javascript, C#, PHP) pun la dispoziția programatorilor operatori care fac tocmai acest lucru.
Operatorul de incrementare este ++
, iar cel de decrementare este --
. Sunt operatori unari și se pot aplica doar datelor (variabile sau operații care au rezultat de tip lvalue
– element de tablou, câmp al unei structuri, etc.).
Operatorii de incrementare/decrementare nu se pot aplica pentru constante sau pentru operații care au ca rezultat valori (operații aritmetice, comparații, etc.).
De regulă, operatorii unari sunt prefixați (sunt plasați înaintea operandului, de exemplu - x
). Operatorii de incrementare și decrementare pot fi atât prefixați ( se scriu înaintea operandului), cât și postfixați (se scriu după operand). Efectul lor este același (incrementarea/decrementarea operandului), dar rezultatul diferă.
Operația de incrementare a variabilei X
poate fi:
X ++
. Efectul expresiei este mărirea valorii lui X
cu 1
, iar rezultatul operației este valoarea inițială a lui X
.++ X
. Efectul expresiei este mărirea valorii lui X
cu 1
, iar rezultatul operației este chiar variabila X
(cu valoarea mărită, bineînțeles).int x = 5 , y = 10; y = x ++; // y primeste valoare lui (x++), adica valoarea initiala a lui x cout << x << " " << y; // 6 5
int x = 5 , y = 10; y = ++ x; // y primeste valoare lui (++x), adica valoarea marita a lui x cout << x << " " << y; // 6 6
lvalue
– de exemplu i se poate aplica din nou operatorul de incrementare sau cel de decrementare.Exemple:
int x = 5 , y = 10; y = (++ x) ++; // x devine 7, y devine 6 cout << x << " " << y;
int x = 5 , y = 10; y = ++ (x ++); // eroare, rezultatul lui x ++ nu este lvalue cout << x << " " << y;
int x = 5 , y = 10; y = ++ ++ x; // x devine 7, y devine y cout << x << " " << y;
Postincrementarea are prioritate mai mare decât preincrementarea (vezi aici prioritatea operatorilor). Din acest motiv următoarea secvență este greșită sintactic.
int x = 5 , y = 10; y = ++ x ++; // eroare; prioritate are x ++, dar rezultatul sau nu este lvalue cout << x << " " << y;
Decrementarea respectă toate proprietățile incrementării, cu observația că valoarea datei asupra căreia se aplică se va micșora cu 1
.
Operația de decrementare a variabilei X
poate fi:
X --
. Efectul expresiei este micșorarea valorii lui X
cu 1
, iar rezultatul operației este valoarea inițială a lui X
.-- X
. Efectul expresiei este micșorarea valorii lui X
cu 1
, iar rezultatul operației este chiar variabila X
.Înlănțuirea metodelor (method chaining) este un stil de programare ce poate fi utilizat în contextul programării orientate pe obiecte. Constă în faptul că metodele vor avea ca rezultat obiecte. În acest mod apelurile metodelor pot fi înlănțuite într-o singură instrucțiune, evitând declararea unor variabile care să stocheze rezultate intermediare.
O situație particulară este cascadarea metodelor. Constă în faptul că metodele returnează tocmai obiectul curent (instanța curentă). Astfel apelurile lor sunt înlănțuite, făcând programul ușor de înțeles și evitând “efortul” necesar pentru alegerea unor nume pentru variabile.
Cascadarea metodelor este posibilă în C++ datorită pointerului this
– pointer la obiectul curent. Pentru a realiza cascadarea trebuie îndeplinite următoarele:
this
, adică * this
.Un exemplu C++ binecunoscut este operatorul de inserție în flux <<
, care are ca rezultat obiectul din stânga. Acest fapt permite scrie unei instrucțiuni de forma:
cout << a << " " << b;
Ea este echivalentă cu următoarea secvență:
cout << a; cout << " "; cout << b;
Programul de mai jos este o rezolvare pentru problema #sum00 (suma a două numere):
#include <iostream> using namespace std; class T{ private: int a , b; public: T & Citire(){ cin >> a >> b; return * this; } T & Suma(){ cout << a + b; return * this; } }; int main() { T().Citire().Suma(); return 0; }
Considerăm următoarele două clase:
class A{ private: int n; public: A & Citire(){ cin >> n; return * this; } A & Afisare(){ cout << n << endl; return * this; } A & Dublare(){ n *= 2; return * this; } }; class B{ private: int n; public: B Citire(){ cin >> n; return * this; } B Afisare(){ cout << n << endl; return * this; } B Dublare(){ n *= 2; return * this; } };
Ele diferă doar prin faptul că metodele clasei A
returnează însuși obiectul curent, în timp ce metodele clasei B
returnează o copie a obiectului curent.
Următoarele două secvențe vor afișa același lucru, deși mecanismele sunt diferite:
Cascadare
A().Citire().Dublare().Afisare();
Înlănțuire (fără cascadare)
B().Citire().Dublare().Afisare();
Diferențele sunt vizibile în următoarele exemple:
Cascadare
A x; x.Citire().Dublare(); x.Afisare();
Dacă se citește 2
, se va afișa 4
. Toate apelurile se aplică la același obiect, și anume x
.
Înlănțuire (fără cascadare)
B y; y.Citire().Dublare(); y.Afisare();
Dacă se citește 2
, se va afișa 2
. Metoda y.Citire()
va citi în câmpul n
valoarea 2
, dar va returna o copie a lui y
, asupra căreia se va aplica apelul Dublare()
. Se va dubla câmpul n
din copie, câmpul n
din y
râmânând nemodificat!
Cuvântul polimorfism se referă la proprietatea unor substanțe, ființe, obiecte de a avea mai multe forme.
În contextul programării orientate pe obiecte, polimorfismul se referă la posibilitatea claselor de a avea mai multe metode cu același nume, dar cu efecte și rezultate diferite.
În C++ polimorfismul poate fi implementat prin:
Supraîncărcarea funcțiilor și operatorilor sunt tratate în acest articol: www.pbinfo.ro/articole/25851/supraincarcarea-functiilor-si-a-operatorilor.
Suprascrierea funcțiilor (overriding) se referă la situația ca într-o ierarhie de clase să avem metode cu același nume, dar cu efecte diferite. Considerăm clasele Animal
și Caine
.
#include<iostream> using namespace std; class Animal{ public: void vorbeste() { cout << "Animalul vorbeste." << endl; } }; class Caine: public Animal{ public: void vorbeste() { cout << "Cainele latra." << endl; } }; int main(){ Caine C; Animal A; C.vorbeste(); A.vorbeste(); C.Animal::vorbeste(); // A.Caine::vorbeste(); // imposibil }
În exemplul anterior:
Caine
este derivată din clasa Animal
;C
este de tip Caine
, obiectul A
este de tip Animal
; ambele sunt obiecte statice;vorbeste()
este disponibilă în ambele clase, fiind suprascrisă în clasa derivatăvorbeste()
C.Animal::vorbeste();
– invers nu este posibil!Constatăm că pentru obiectele referite static accesarea metodelor suprascrise este rezolvată elegant, putând accesa orice metodă disponibilă în obiectul curent (proprie obiectului curent sau proprie aflate mai “sus” în ierarhie).
Să vedem cum putem accesa membri claselor de bază/derivată în cazul pointerilor. Folosind clasele definite mai sus, considerăm următorul exemplu:
Caine C; Animal A; Animal * p; p = & A; p->vorbeste(); // Animalul vorbeste. p = & C; p->vorbeste(); // Animalul vorbeste. (?!?) Caine * q; q = & C; q->vorbeste(); // q = & A; // imposibil
Constatăm că:
q
) poate memora doar adresa unui obiect al acesteia;p
) poate memora atât adresa unui obiect al clasei de bază, cât și adresa unui obiect al clasei derivate;C++ oferă un mecanism prin care se alege metoda accesată printr-un pointer dinamic, la execuția programului, în funcție de clasa din care face obiectul referit de pointer (de bază sau derivată). Acest mecanism este reprezentat de funcțiile virtuale.
Declararea unei funcții (metode) virtuale este precedată de cuvântul C++ rezervat virtual
în clasa de bază:
virtual tipRezultat metoda(parametri)
Exemplu:
#include<iostream> using namespace std; class Animal{ public: virtual void vorbeste() { cout << "Animalul vorbeste." << endl; } }; class Caine: public Animal{ public: void vorbeste() { cout << "Cainele latra." << endl; } }; int main(){ Caine C; Animal A; Animal * p; p = & A; p->vorbeste(); // Animalul vorbeste. p = & C; p->vorbeste(); // Cainele latra. (!) }
Constatăm că:
p
este declarat pointer la clasa de bază;p
poate memora fie adresa unui obiect din clasa de bază, fie adresa unui obiect din clasa derivată;