Clasa a V-a lecția 8 - 12 oct 2019

From Algopedia
Jump to navigationJump to search

Tema - rezolvări

Rezolvări aici [1]

Lecție

<html5media height="720" width="1280">http://algopedia.ro/video/2019-2020/2019-10-12-clasa-5-lectie-info-08-720p.mp4</html5media>

Cum rezolvăm o problemă de algoritm

Atunci când rezolvați o problemă nu vă repeziți să scrieți programul C. Tot ce am făcut împreună are un scop. Urmăriți următoarele etape:

  1. Mai întâi gîndiți-vă la modul cum ați rezolva-o voi, "de mână". Pentru fiecare din ideile de rezolvare treceți prin etapele de mai jos.
  2. Elaborați regula observată într-o metodă. Asigurați-vă că știți să traduceți acea metodă în pași pe calculator. Dacă aveți nevoie să inversați ordinea cifrelor unui număr, știți pașii elementari pentru asta?
  3. Verificați că metoda funcționează pe câteva exemple, nu doar pe exemplul furnizat de problemă. Pentru aceasta creați-vă propriile exemple de test.
  4. Scrieți schema logică.
  5. Verificați schema logică pe exemple. Faceți corecturile necesare, dacă observați greșeli în metoda pe care ați gândit-o original. Verificați, de asemenea, că schema logică funcționează pe exemple la limită: când n este zero, sau unu, sau număr prim, etc. Rularea schemei logice se face ținând efectiv degetul pe săgeți până ajungeți la blocul de STOP. Păstrați un tabel cu valorile tuturor variabilelor la orice moment.
  6. Deschideți Code::Blocks și creați un proiect.
  7. Navigați la Project - Build Options și setați opțiunile -Wall și -O2.
  8. Introduceți programul C urmărind identic schema logică. Salvați cât mai des în timpul introducerii, folosind combinația CTRL-s.
  9. La final salvați din nou, apoi compilați apăsând butonul Build, cel cu rotița dințată. Nu apăsați Build and run!
  10. Urmăriți cu atenție mesajele din secțiunea de jos, atât erorile cât și avertismentele (warnings). Corectați sursa pentru a nu mai avea astfel de mesaje.
  11. Executați programul apăsând butonul Run, cel cu triunghiul play. Introduceți cât mai multe date, în execuții succesive, pentru a testa diverse cazuri. Testați cu precădere cazurile limită, 0, 1, etc.
  12. După ce aduceți corecții programului, modificați corespunzător și schema logică, apoi reluați testarea.

Exercițiul 1 - palindrom

Se citește un număr n. Să se spună dacă n este palindrom. Un număr este palindrom dacă prima lui cifră este egală cu ultima, a doua cu penultima și așa mai departe. Exemple de palindroame: 15351, 7337 sau 12233221.

Pentru a rezolva exerciţiul am observat următoarea proprietate: inversul unui număr palindrom este egal cu numărul original. Schema logică calculează inversul numărului n în variabila r şi apoi compară r cu originalul. Deoarece variabila n este modificată pe parcursul caculului, vom memora o copie a ei in variabila nc.

Palindrom
#include <stdio.h>

int main() {
  int n, nc, r;

  scanf( "%d", &n );
  nc = n;
  r = 0;
  while ( n > 0 ) {
    r = r * 10 + n % 10;
    n = n / 10;
  }
  if ( nc == r )
    printf( "%d este palindrom\n", nc );
  else
    printf( "%d nu este palindrom\n", nc );
  return 0;
}

Exerciţiul 2 - divizorii unui număr

Se citește un număr n, să se afișeze toți divizorii lui n. Spunem că d este divizor al lui n dacă n se împarte la d.

Pentru a rezolva exerciţiul vom varia un contor d de la 1 la n. El reprezintă potenţialii divizori ai lui n. Pentru fiecare valoare a lui d vom testa dacă n se împarte la d. Dacă da, vom afişa acel divizor.

Divizorii lui n
#include <stdio.h>

int main() {
  int n, d;

  scanf( "%d", &n );
  printf( "Divizorii lui %d sint:", n );
  d = 1;
  while ( d <= n ) {
    if ( n % d == 0 )
      printf( " %d", d );
    d = d + 1;
  }
  printf( "\n" );

  return 0;
}

Observație: între n/2 și n nu mai avem nici un divizor, deci am putea optimiza algoritmul punînd condiția while ( d <= n / 2 ) și afișînd n, ultimul divizor, separat, în afara buclei while

Modificare

O modificare ușoară a exerciţiului este: se citește un număr n. Să se afișeze toți divizorii impari ai lui n. Singura diferență este că vom adăuga 2 la d în loc de 1:

d ← d + 2

Operatori logici

Condițiile care apar în blocurile de decizie (romburi) și în instrucțiunile if și while din C pot fi compuse folosind următorii operatori logici: și, sau și not (în scheme logice), sau &&, || și ! În limbajul C. Iată exemple de folosire în următoarele exerciții:

Exerciţiul 3 - număr prim

Se citește un număr n. Să se spună dacă n este prim. Un număr este prim dacă nu se împarte decît la 1 și la el însuși.

Vom proceda similar cu afişarea divizorilor: vom căuta primul divizor al lui n, începînd cu 2. Dacă găsim un divizor numărul nu este prim. Dacă, în schimb, primul divizor găsit este chiar n, numărul este prim.

Număr prim
#include <stdio.h>

int main() {
  int n, d;

  scanf( "%d", &n );
  d = 2;
  while ( d < n && n % d > 0 )
    d = d + 1;
  if ( d == n )
    printf( "%d este prim\n", n );
  else
    printf( "%d nu este prim\n", n );

  return 0;
}

Observații:

  1. Avem cu adevărat nevoie de condiția d < n? Justificați răspunsul.
  2. Putem face mai puține iterații dacă observăm că dacă un număr nu are nici un divizor strict mai mare ca 1 dar mai mic sau egal cu radical din n atunci el nu va avea nici alți divizori mai mari decît radical din n dar mai mici decît n. Cum justificăm acest lucru? Putem, deci, înlocui condiția d < n cu d * d <= n. În acest caz va trebui să modificăm condiția finală de test de primalitate din d == n în d * d > n.

Iată algoritmul modificat:

Număr prim
#include <stdio.h>

int main() {
  int n, d;

  scanf( "%d", &n );
  d = 2;
  while ( d * d <= n && n % d > 0 )
    d = d + 1;
  if ( d * d > n )
    printf( "%d este prim\n", n );
  else
    printf( "%d nu este prim\n", n );

  return 0;
}

Exerciţiul 4 - numere prime pînă la n

Se citește un număr n. Să se afișeze toate numerele prime mai mici sau egale cu n.

Vom folosi exerciţiul anterior. Vom varia un contor p de la 2 pînă la n. Aceste numere pot sau nu să fie numere prime, drept pentru care vom testa fiecare din ele dacă este prim.

Numere prime pînă la n

Tema

  • Să se rezolve următoarele probleme (schemă logică + program C executat în CodeBlocks):
    • Să se afișeze toți divizorii impari ai lui n.
    • Se citește un număr n. Să se afișeze toate numerele prime mai mici sau egale cu n. Este vorba de ultima problemă din lecție.
    • Se citesc două numere, n și k. Să se afișeze toate numerele mai mici sau egale cu n care se divid cu k. Exemple: pentru n = 7 k = 2 se va afișa 2 4 6; pentru n = 25 k = 5 se va afișa 5 10 15 20 25.
    • Se citește un număr n. Să se afișeze toate numerele perfecte mai mici sau egale cu n. Un număr este perfect dacă este egal cu suma divizorilor lui strict mai mici ca el. Primul număr perfect este 6, deoarece 6 = 1 + 2 + 3. Următorul număr este 28 deoarece 28 = 1 + 2 + 4 + 7 + 14. Exemple: dacă n = 8 se va afișa 6. Dacă n = 30 se va afișa 6 28. Dacă n = 500 se va afișa 6 28 496.
  • Problemă de logică: ce linie urmează în secvență:
       1
      1 1
      2 1
    1 2 1 1
  1 1 1 2 2 1
  3 1 2 2 1 1
1 3 1 1 2 2 2 1

Rezolvări aici [2]