View source for Clasa a V-a lecția 5 S3

= Lectie =
== Programarea structurată ==
Programarea structurată este un mod de a scrie scheme logice care îmbunătățește claritatea, citibilitatea, calitatea și ușurința modificării ulterioare. Denumirea vine de la ''Programarea cu structuri''. Mai exact, programarea structurată ne limitează modul în care putem folosi și îmbina blocurile. Ele pot fi aranjate în trei feluri distincte, conform unor modele numite structuri. Aceste structuri sunt:
* Structura liniară (de calcul)
* structura alternativă (decizională)
* structura repetitivă (ciclică)

=== Structura liniară ===
Se mai numește și structură de calcul. Ea constă dintr-o înșiruire de blocuri de calcul și blocuri de citire/scriere. Aceste blocuri se vor executa in ordinea in care ele apar in structura.
[[Image:sl-structura-liniara.gif|frame|none|Structura liniară]]
=== Exemple ===
==== Extragerea ultimei cifre ====
Să se afișeze ultima cifră a unui număr n, folosind operatorul '%', respectiv restul împărțirii la 10. Am demonstrat că restul împărțirii la 10 este ultima cifră a unui număr.
[[Image:sl-ultima-cifra.gif|frame|none|Ultima cifră a lui n]]
<syntaxhighlight>
// implementare c++
#include <iostream>
using namespace std;
int main (){
  int n;
  int cf;
  cin >> n;
  cf = n % 10;
  cout << cf;
  return 0;
}
</syntaxhighlight>

=== Structura alternativă ===
Structura alternativă este compusă dintr-un bloc de decizie, două ramuri de execuție, ''DA'' și ''NU'', care se reunesc la final. Blocul de decizie contine o expresie logica. Daca expresia logica ( cond ) are valoarea  True atunci se vor executa intructiunile de pe ramura ''DA'' altfel se vor executa intructiunile de pe ramura ''NU''.
[[Image:sl-structura-alternativa.gif|frame|none|Structura alternativă]]

Pseudocod
 daca conditie atunci
   set_instructiuni1
 altfel
   set_instructiuni2
<syntaxhighlight>
if (conditie ){
  set_instructiuni1;
}
else {
  set_instructiuni1;
}
</syntaxhighlight>

=== Exemple ===
==== Testul de divizibilitate ====
Testul de divizibilitate <tt>n</tt> cu <tt>k</tt>, discuție cele două metode, prima folosind operatorul <tt>%</tt>, a doua folosind operatorul <tt>/</tt>.

{|
| [[Image:sl-n-div-k-var-1.gif|frame|none|n divizibil cu k, varianta 1]]
| [[Image:sl-n-div-k-var-2.gif|frame|none|n divizibil cu k, varianta 2]]
|}
<syntaxhighlight>
// implementare c++
#include <iostream>
using namespace std;
int main (){
  int n, k;
 
  cin >> n >> k;
  if ( n % k == 0 )
    cout << n <<" se divide la" << k;
  else
   cout << n <<" nu se divide la" << k;
  return 0;
}
</syntaxhighlight>

==== Extragerea primei cifre ====
Se citește n, un număr natural strict mai mic decît 100. Să se afișeze prima cifră a lui n. [[Image:prima-cifra.gif|frame|none|Prima cifră a lui n, n < 100]]
<syntaxhighlight>
// implementare in c++
#include <iostream>
using namespace std;
int main (){
  int n, c;

  cin >> n;
  if ( n < 10 )
    c = n ;
  else
   c = n / 10;
   cout << c;
  return 0;
}
</syntaxhighlight>

=== Laturile unui triunghi ( doar pentru liceu ) ===
Se citesc trei numere, a, b și c. Să se spună dacă pot fi laturile unui triunghi. [[Image:laturi-triunghi.gif|frame|none|a, b, c pot fi laturile unui triunghi?]]
<syntaxhighlight>
// implementare in c++
#include <iostream>
using namespace std;
int main (){
  int a, b, c;

  cin >> a >> b >> c;
  if ( a + b > c )
    if ( b + c > a )
      if ( a + c > b )
        cout << "pot form triunghi";
      else
        cout << "nu pot forma triunghi";
    else
        cout << "nu pot forma triunghi";
  else
        cout << "nu pot forma triunghi";
  return 0;
}
</syntaxhighlight>

=== Strîngeri de mînă ===
Avem <tt>n</tt> oameni care dau mîna fiecare cu fiecare o singură dată. În total sînt <tt>k</tt> strîngeri de mînă. Să se scrie o schemă logică care citește <tt>k</tt> (numărul de strîngeri de mînă), apoi calculează și afișează <tt>n</tt> (numărul de oameni). [[Image:sl-stringeri-de-mina.gif|frame|none|n oameni dau mîna. Sînt k strîngeri de mînă. Dîndu-se k să se calculeze n.]]

=== Maximul a trei numere ===
Se citesc trei numere, <tt>a</tt>, <tt>b</tt> și <tt>c</tt>. Să se afișeze valoarea maximă.
{|
| valign="top"| [[Image:sl-max-3-nr-1.gif|frame|none|maximul a trei numere, varianta 1]]
| valign="top"| [[Image:sl-max-3-nr-2.gif|frame|none|maximul a trei numere, varianta 2]]
|}
<syntaxhighlight>
// implementare in c++ ( pentru algoritmul din a doua schema )
#include <iostream>
using namespace std;
int main (){
  int a, b, c, maxim;

  cin >> a >> b >> c;
  maxim = a;
  if ( b > maxim )
    maxim = b;
  if( c > maxim )
    maxim = c;
  cout << maxim;
  return 0;
}
</syntaxhighlight>

=== Sortarea a 3 numere ===
* Se citesc trei numere, a, b și c. Să se afișeze în ordine crescătoare. Exemplu: dacă a = 8, b = 4, c = 12, se va afișa 4 8 12.

[[Image:sl-sortare-3-nr.gif|frame|none|Afișare a, b și c în ordine crescătoare, varianta 1]]
[[Image:sl-3-nr-crescatoare-var-2.gif|frame|none|Afișare a, b și c în ordine crescătoare, varianta 2]]

Am discutat la clasa de asemenea inca 2 metode de sortare, pe care le putem folosi si in situatia in care avem mai mult de 3 numere:
- metoda interschimbarii directe
- metoda bulelor
==== Metoda interschimbarii directe ====
<syntaxhighlight>
intreg a, b, c, aux
read a, b, c

if ( a > b ) than
  aux = a
  a = b;
  b = aux
if ( a > c ) than
  aux = a
  a = c;
  c = aux
if ( b > c ) than
  aux = b
  b = c;
  c = aux
write a, b, c
</syntaxhighlight>

==== Metoda bulelor ====
<syntaxhighlight>
intreg a, b, c, aux
cieste a, b, c

if ( a > b ) atunci
  aux = a
  a = b;
  b = aux
if ( b > c ) atunci
  aux = b
  b = c;
  c = aux
if ( a > b ) atunci
  aux = a
  a = b;
  b = aux
scrie a, b, c
</syntaxhighlight>

=== Cifre impare ===
Se citește un număr <tt>n</tt>. Se știe că <tt>1 &le; n < 100</tt>. Să se spună dacă toate cifrele lui <tt>n</tt> sînt impare.
{|
| valign="top"| [[Image:sl-cifre-impare-1.gif|frame|none|Toate cifrele lui n sînt impare, varianta 1]]
| valign="top"| [[Image:sl-cifre-impare-2.gif|frame|none|Toate cifrele lui n sînt impare, varianta 2]]
|}

=== Numere divizibile cu K din [a,b] ===
Se citesc trei numere naturale, <tt>a</tt>, <tt>b</tt> și <tt>k</tt>. Să se afișeze numărul de numere divizibile cu <tt>k</tt> în intervalul <tt>[a, b]</tt> (inclusiv <tt>a</tt> și <tt>b</tt>). [[Image:div-cu-k.gif|frame|none|Cîte numere divizibile cu k se află în intervalul [a, b]?]]

== Exerciții 2==
Exerciții de folosire a structurilor liniară și alternativă folosind - Pseudocod

=== Diferenta dintre max si min ===
Să se scrie un program  care citeşte de la tastatură trei numere naturale și determină diferenţa dintre cel mai mare şi cel mai mic numar.
<syntaxhighlight>
intreg a, b, c
citeste a, b, c
min=a
max=a
daca ( min > b ) atunci
  min = b
daca ( min > c ) atunci
  min = c
daca ( max < b ) atunci
  max = b
daca ( max < c ) atunci
  max = c
scrie  max - min;
</syntaxhighlight>

=== Cate cifre pare are n? ===
Se citește de la tastatură un număr natural de 3 cifre. Să se determine 
câte cifre impare conține.

<syntaxhighlight>
int n, contor;
citeste n
contor = 0
daca ( n mod 2 != 0 ) atunci
  contor = contor + 1
daca( n div 10 mod 2 != 0 )
  contor = contor + 1
daca ( n div 100 mod 2 != 0 )
  contor = contor + 1
scrie contor
</syntaxhighlight>

=== Au 2 numere acelasi semn? ===
Să se scrie un program care citeşte de la tastatură două numere întregi şi verifică dacă cele doua numere au acelaşi semn.
<syntaxhighlight>
intreg a,b
citeste a, b
daca ( a < 0 ) atunci
  daca ( b < 0 ) atunci
     scrie "au acelasi semn"
  altfel 
      scrie "nu au acelasi semn"
altfel
   daca ( b >= 0 ) atunci
      scrie "au acelasi semn"
   altel
      scrie "nu au acelasi semn"
</syntaxhighlight>

SAU

<syntaxhighlight>
intregi a, b
citeste a, b
daca ( ( a < 0 ) AND ( b < 0 ) ) OR ( ( a >= 0 AND b >= 0 ) ) atunci
    scrie "au acelasi semn"
altfel 
    scrie "nu au acelasi semn"   
</syntaxhighlight>

SAU

<syntaxhighlight>
intregi a, b
citeste a, b
daca  ( a < 0 AND b >= 0 ) OR ( a >= 0 AND b < 0 )  atunci
    scrie "nu au acelasi semn"
altfel 
    scrie "au acelasi semn"
</syntaxhighlight>

== Tema 4 Laborator ==
===N are ultimele 2 cifre consecutive?===
* Să se spună dacă un număr n are ultimele două cifre consecutive, în ordine crescătoare. Exemple: 312, 4523 și 1 sînt numere care au ultimele două cifre consecutive. 215, 4321 și 7 nu au ultimele două cifre consecutive crescător.

===N copii se pot aseza in forma de patrat===
* Varianta1: să se spună dacă n copii se pot așeza în formă de pătrat plin. Exemplu: Nouă copii se pot așeza în formă de pătrat astfel: 
 x x x
 x x x
 x x x

* Varianta2: să se spună dacă n copii se pot așeza în formă de pătrat gol ( pe laturile unui patrat. In imaginile de mai sus vom considera ca locuri posibile doar conturul patratului. De exemplu 12 copii se pot aseza sub forma unui patrat gol astfel:
 x x x x 
 x     x
 x     x
 x x x x

===An bisect===
* Scrieți o schemă logică care să determine dacă un an este bisect. Un an este bisect dacă este divizibil cu 4, cu excepția anilor divizibili cu 100, care nu sînt bisecți, cu excepția anilor divizibili cu 400 care sînt bisecți. Exemple: 2012 este an bisect, 1900 nu a fost an bisect, 2000 a fost an bisect.

=== Tema Pbinfo ===
'''Usor'''
*[https://www.pbinfo.ro/probleme/2765/checkcolor checkcolor]
*[https://www.pbinfo.ro/probleme/448/ciford ciford] - ordonarea cifrelor unui numar de 3 cifre
*[https://www.pbinfo.ro/probleme/447/cifmid cifmid] - afisare cifra din mijloc ca valoare
*[https://www.pbinfo.ro/probleme/559/5numere 5numere] - suma celor mai mari 3 numere din 5 date
*[https://www.pbinfo.ro/probleme/3275/nrsumcifmax  nrsumcifmax] - afisarea tuturor numerelor egale cu max din 3 numere
'''Mediu '''
*[https://www.pbinfo.ro/probleme/1943/bacterie bacterie]
*[https://www.pbinfo.ro/probleme/2908/planta planta]
*[https://www.pbinfo.ro/probleme/3207/cercuri cercuri]
*[https://www.pbinfo.ro/probleme/3925/rest1 rest1]
*[https://www.pbinfo.ro/probleme/382/aproapek aproapek]
'''Dificil'''
*[https://www.pbinfo.ro/probleme/1002/paginare paginare]
*[https://www.pbinfo.ro/probleme/1934/catalin-si-elfii-magici catalin-si-elfii-magici]
=== Tema codeforces ===
* https://codeforces.com/contest/476/problem/A
* https://codeforces.com/contest/742/problem/A
* https://codeforces.com/contest/670/problem/A

===Probleme de pe campion ===
* [http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1067 triunghi1]