Clasa a V-a lecția 13 - 16 noi 2019

From Algopedia
Jump to navigationJump to search

Comentarii generale

  • Chiar dacă unele probleme sunt mai grele, nu trebuie să vă descurajați. Procesul de învățare presupune să vă loviți de lucruri pe care nu le știți, ca să înțelegeți care vă este nivelul și unde trebuie plusați. Vă felicit pe toți care ați participat în concursul de săptămâna trecută, chiar dacă nu ați știut să le faceți.
  • Vă reamintesc că la acest cerc se studiază limbajul de programare C. Nu accept surse trimise în C++. Vreți să faceți C++, sunt convins că alți profesori vă pot acomoda cu asta. Dacă reușiți să faceți un cod în C++ și nu știți să îl scrieți și in C, înseamnă că nu știți algoritmul din spatele programului și l-ați copiat de undeva. Avertisment David Poterașu. La următoarea abatere, cartonaș roșu.
  • Dacă se întâmplă să sărim o lecție, asta nu înseamnă că voi aveți voie să nu vă faceți temele. O parte dintre voi ați ignorat tema și ați participat doar la o parte din concursuri. Avertisment: David Poterașu, Vladimir Gavriș și Mara Florian.

Tema – rezolvări lecția 11 - 2 noi 2019

Număr cu cifre distincte - rezolvarea 2

Să se spună dacă un număr are toate cifrele distincte. Exemplu: 439453967 nu are cifre distincte, cifrele 3 și 9 apar de două ori în număr; Numărul 4539 are cifre distincte, nici o cifră a sa nu se repetă.

O altă soluție ar putea fi să luăm toate cifrele de la 0 la 9 și să numărăm de cîte ori apar în numărul n. Ne oprim dacă găsim că o cifră apare de două sau mai multe ori (este OK să apară de zero ori sau o singură dată).

Iată o variantă posibilă pentru această soluție:

Număr cu cifre distincte varianta 2
 #include <stdio.h>

 int main() {
   FILE *fin, *fout;
   int n, cf, nc, ncf;

   fin = fopen( "distincte.in", "r" );
   fscanf( fin, "%d", &n );
   fclose( fin );

   cf = 0;
   ncf = 0;
   while ( cf < 10 && ncf < 2 ) {
     ncf = 0;
     nc = n;
     while ( nc > 0 ) {
       if ( nc % 10 == cf )
         ncf = ncf + 1;
       nc = nc / 10;
     }
     n = n / 10;
     cf = cf + 1;
   }

   fout = fopen( "distincte.out", "w" );
   if ( ncf < 2 )
     fprintf( fout, "Cifre distincte\n" );
   else
     fprintf( fout, "Cifre nedistincte\n" );
   fclose( fout );

   return 0;
 }

Care variantă este mai bună? Să analizăm. Prima variantă testează strict cifrele distincte ale numărului, oprindu-se cînd găsește o cifră care se repetă. Astfel, ea va testa maxim toate cele zece cifre. A doua variantă va testa din start toate cele zece cifre, cu excepția cazului cînd găsește o cifră care apare de două sau mai multe ori. Drept care a doua variantă va testa întotdeauna mai multe cifre decît prima variantă. Prima variantă este deci mai bună.


Pinochio

Rezolvați problema pinochio, OJI 2003 clasa a 5-a (schemă logică + program C în CodeBlocks, trimis la vianuarena).

Răspuns: vom împărți cele k zile în săptămîni întregi plus cîteva zile rămase. Astfel vom avea:

  • k / 7 săptămîni
  • k % 7 zile rămase în ultima săptămînă

Într-o săptămînă lui Pinochio îi crește nasul cu 5 * p - 2 centimetri. În ultima săptămînă, cea incompletă, avem două cazuri:

  • dacă zilele rămase, k % 7, sînt între 0 și 5 numărul de centimetri cu care crește nasul lui Pinochio în ultima săptămînă este (k % 7) * p
  • dacă zilele rămase sînt în număr de 6 avem și o zi de final de săptămînă, drept care numărul de centimetri cu care crește nasul lui Pinochio în ultima săptămînă este 5 * p - 1

Remarcați că nu este posibil ca numărul de zile rămase să fie 7, deoarece săptămîna ar fi plină. Algoritmul de mai jos implementează această soluție:

Pinochio - campion
 #include <stdio.h>

 int main() {
   FILE *fin, *fout;
   int n, p, k, cm;

   fin = fopen( "pinochio.in", "r" );
   fscanf( fin, "%d%d%d", &n, &p, &k );
   fclose( fin );

   cm = n + (5 * p - 2) * (k / 7);
   k = k % 7;
   if ( k == 6 )
     cm = cm + 5 * p - 1;
   else
     cm = cm + k * p;

   fout = fopen( "pinochio.out", "w" );
   fprintf( fout, "%d\n", cm );
   fclose( fout );

   return 0;
 }

Aceasta este și soluția comisiei. Există însă o soluție mai compactă, care face doar un calcul simplu, fără a folosi structuri alternative. Explicația mai jos, pentru cine dorește.

Să presupunem că nasul lui Pinochio crește în fiecare zi cu p centimetri. În acest caz nasul va avea în final

cm =  n + k * p

Mai departe trebuie să ajustăm pentru zilele de sîmbătă și duminică, pentru care trebuie să scădem p-1. Să le luam pe rînd. Mai întîi zilele de sîmbătă. Ele sînt zilele toate zilele z cu proprietățile:

(z-1) % 7 = 5, 1 ≤ z ≤ k

Scădem 5 din ambele părți ale primei egalități:

(z-1) % 7 - 5 = 0, 1 ≤ z ≤ k

Putem, de asemenea, să introducem 5 în paranteze:

(z-1-5) % 7 = 0, 1 ≤ z ≤ k

  (z-6) % 7 = 0, 1 ≤ z ≤ k

Deoarece vorbim de resturi modulo 7, putem aduna 7 la paranteză, pentru a nu avea numere mai mici ca zero:

(z-6+7) % 7 = 0, 1 ≤ z ≤ k

  (z+1) % 7 = 0, 1 ≤ z ≤ k

Acum adunăm 1 la fiecare membru al inegalității din dreapta:

(z+1) % 7 = 0, 2 ≤ z+1 ≤ k+1

Să notăm pe z+1 cu x. Rezultă că vrem să aflăm cîte numere x există cu proprietățile

x % 7 = 0, 2 ≤ x ≤ k+1

Dar aceasta este o problemă cunoscută tratată în lecția 3, este numărul de numere divizibile cu 7 din intervalul [2..k+1]. Acest număr este

nrsimbata = (k+1) / 7 - 1/7 = (k+1) / 7

În mod similar vom calcula numărul de zile de duminică:

nrduminica = k / 7

Ne amintim că pentru zilele de sîmbătă și de duminică trebuie să scădem p+1. Avem deci formula finala a numărului de centimetri:

cm = n + k * p - (p+1) * ((k / 7) + (k+1) / 7)

Programul care rezultă este ceva mai simplu:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, p, k, cm;

  fin = fopen( "pinochio.in", "r" );
  fscanf( fin, "%d%d%d", &n, &p, &k );
  fclose( fin );

  cm = n + k * p - (p + 1) * (k / 7 + (k + 1) / 7);

  fout = fopen( "pinochio.out", "w" );
  fprintf( fout, "%d\n", cm );
  fclose( fout );

  return 0;
}

Concluzia acestei soluții este că în multe situații matematica duce la soluții mai bune în informatică. Așa că aveți grijă să o învățați bine.

Poziții

Poziții (schemă logică + program C în CodeBlocks trimis la vianuarena): se citește o secvență de n numere. Să se spună cîte din numere sînt egale cu poziția lor în secvență. Primul număr este pe poziția 0, ultimul pe poziția n – 1. Exemple:

pozitii.in pozitii.out
4
0 3 2 5
2
10
7 1 2 3 2 5 9 7 3 9
6

Răspuns: problema este una introductivă în secvențe, deci nu foarte grea. Va trebui să folosim un contor pentru a număra poziția fiecărui număr citit. În algoritmul de mai jos el se numește i. De asemenea vom menține un al doilea contor care numără cîte numere sînt egale cu poziția lor. După citirea numărului curent din secvență îl vom compara cu contorul de poziție i și vom aduna 1 la poz dacă sînt egale. În final poz este chiar numărul pe care trebuie să îl afișăm.

Numere egale poziția lor
 #include <stdio.h>
 
 int main() {
   FILE *fin, *fout;
   int n, i, a, poz;
 
   fin = fopen( "pozitii.in", "r" );
   fscanf( fin, "%d", &n );
   poz = 0;
   i = 0;
   while ( i < n ) {
     fscanf( fin, "%d", &a );
     if ( a == i )
       poz = poz + 1;
     i = i + 1;
   }
   fclose( fin );
 
   fout = fopen( "pozitii.out", "w" );
   fprintf( fout, "%d", poz );
   fclose( fout );
   return 0;
 }

Cămila și bananele

Problemă de logică: dispunem de 3000 de banane pe care vrem să le transportăm din orașul A în orașul B aflate la 1000km distanță. Dispunem de o cămilă care poate să care maxim 1000 de banane. În timp ce mergea ea mănîncă o banană la fiecare kilometru. Care este numărul maxim de banane pe care le puteți duce din A în B și cum procedați? Puteți desigur să depozitați banane în orice loc de pe drum.

Răspuns: Pentru a transporta toate bananele la distanță de 1km ne trebuie 5 drumuri de un km: de două ori mergem dus-întors, iar a treia oară numai dus. Cămila va mînca 5 banane, ceea ce înseamnă că vom ajunge cu 2995 de banane. Dacă înaintăm încă un km vom mai pierde 5 banane. Situația rămîne la fel pînă cînd numărul de banane scade la 2000, moment în care nu vom mai avea nevoie de 5 drumuri ci doar de 3, pentru a transporta toate bananele. Unde vom fi ajuns la acel moment? La kilometrul 1000/5 adică 200. Se observă că putem să transportăm cele 3000 de banane direct la acel kilometru, tot 1000 de banane vom consuma. În continuare, pentru a transporta bananele 1km distanță ne va costa 3 banane pe transport. Pînă cînd? Pînă ce numărul de banane scade la 1001, adică după 999/3 = 333km. În acest moment lăsăm o banană în urmă, încărcăm 1000 de banane și mergem pînă la destinație, care se află la (1000-200-333)km, ceea ce înseamnă că vom ajunge cu 533 de banane. De observat că și al doilea drum, de 333km se poate face dintr-o bucată.

Concluzia: modul cel mai simplu de rezolvare este să transportăm mai întîi bananele la kilometrul 200, apoi le transportăm la kilometrul 533, iar apoi direct la destinație.

Tema – rezolvări lecția 12 - 9 noi 2019

Problema îngerași

Problema îngerași a fost dată la ONI 2005 clasa a 5a. Precum ați remarcat unii dintre voi, soluția problemei este cel mai mare divizor comun al înălțimilor norilor. Știe cineva de ce este așa? Trebuie să aveți grijă să calculați cel mai mare divizor comun folosind algoritmul lui Euclid, care folosește împărțiri, și nu cel cu diferențe, altfel veți depăși timpul. Iată o soluție:

Ingerasi
#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, i, a, r, cmmdc;

  fin = fopen( "ingerasi.in", "r" );
  fscanf( fin, "%d%d", &n, &cmmdc );
  i = 1;
  while (i < n ) {
    fscanf ( fin, "%d", &a );
    while ( a > 0 ) {
      r = cmmdc % a;
      cmmdc = a;
      a = r;
    }
    i = i + 1;
  }
  fclose( fin );

  fout = fopen( "ingerasi.out", "w" );
  fprintf( fout, "%d", cmmdc );
  fclose( fout );

  return 0;
}

Problema parola

Problema parola a fost dată la un concurs popular în 2012, Cupa Mărțișor. La prima vedere, pare o problemă grea, pentru că metoda de parcurgere a cifrelor nu este una la îndemână. Sunt convins că o parte dintre voi ați început să împărțiți numărul cu % 10 și să prelucrați cifrele, însă ați realizat repede că o astfel de soluție nu vă rezolvă problema pentru k > 1.

Soluția constă în 2 procedee clasice:

  • În loc să compunem numărul final, vom afișa pe rând fiecare cifră a numărului;
  • Determinarea numărului de cifre folosind puterea lui 10.

Pentru a afla numărul de cifre al unui număr, vom găsi cea mai mare putere a lui 10 care poate împărți numărul fără a returna valoarea 0, adică care va returna prima cifră a numărului. Exemplu: pentru nr = 13546, cea mai mare putere a lui 10 este 4, adică 10000. Așadar, pentru exemplul dat, numărul are 5 cifre.

Acum, putem afișa prima cifră a numărului foarte ușor. Apoi, putem afișa oricâte cifre de la începutul numărului prin reducerea puterii lui 10. Astfel putem afișa primele k cifre ale numărului a.

Restul problemei devine astfel banală. Pentru numărul b afișăm fiecare cifră de la coadă prin procedeul deja cunoscut. Continuăm să împărțim numărul a la puterea lui 10 și să afișăm cifra obținută. Apoi reducem puterea lui 10.

Iată o posibilă rezolvare:

Parola
#include <stdio.h>

int main() {
    FILE *fin, *fout;
    int k, a, b, i, putere10;

    fin = fopen( "parola.in", "r" );
    fout = fopen( "parola.out", "w" );
    fscanf( fin, "%d%d%d", &k, &a, &b );
    fclose( fin );

    putere10 = 1000000000;
    while ( putere10 > a )
        putere10 = putere10 / 10;
    i=0;
    while (i < k) {
        fprintf( fout, "%d", a / putere10 );
        a = a % putere10;
        putere10 = putere10 / 10;
        i = i + 1;
    }
    while ( putere10 > 0 || b > 0 ) { //folosim operatorul logic OR ( || ) întrucât trebuie să fim siguri că am parcurs toate cifrele celor două numere
        if ( b > 0 ) {
            fprintf( fout, "%d", b % 10 );
            b = b / 10;
        }
        if ( putere10 > 0 ) {
            fprintf( fout, "%d", a / putere10 );
            a = a % putere10;
            putere10 = putere10 / 10;
        }
    }
    fclose( fout );

    return 0;
}

Lecție

Instrucțiunea de incrementare/decrementare

Atunci cînd adunăm unu la o variabilă se cheamă că o incrementăm. De asemenea, cînd scădem unu, se cheamă că o decrementăm. Deoarece aceste două operații apar foarte frecvent limbajul C ne permite să le scriem mai scurt.

Instrucțiune Instrucțiune echivalentă
i = i + 1; i++;
i = i - 1; i--;

Instrucțiunea for

Precum am văzut în exemplele anterioare de multe ori avem nevoie să executăm o buclă WHILE-DO de n ori, folosind un contor. Aceasta este un tip particular de buclă WHILE-DO, și anume o buclă cu număr cunoscut de pași. Pentru acest tip de bucle limbajul C ne permite o prescurtare, folosind instrucțiunea for.

Schemă logică Implementare cu while Implementare cu for
Sl-bucla-for.gif
 i = 0;
 while ( i < n ) {
   ... execută corpul
       buclei...
   i = i + 1;
 }
 for ( i = 0; i < n; i++ ) {
   ... execută corpul
       buclei...
 }

Atenție! Observații importante:

  • Instrucțiunea de incrementare a contorului (i++) se execută întotdeauna la finalul buclei for, imediat înainte de revenirea la condiție.
  • Cele două implementări sînt absolut echivalente, nu este una mai bună ca cealaltă. În fapt, atunci cînd scrieți o instrucțiune for compilatorul o traduce automat în instrucțiunea echivalentă while. Nu este absolut nici o problemă dacă nu vreți să folosiți instrucțiunea for, este doar o opțiune mai succintă pentru cei ce vor să scrie mai puțin, dar nu este obligatorie.
  • La cercul nostru vom respecta următoarele convenții:
    • Vom folosi instrucțiunea for strict pentru buclele cu număr cunoscut de pași. Atunci cînd bucla WHILE-DO se poate executa de un număr necunoscut de ori vom folosi instrucțiunea mai generală while.
    • În interiorul unei instrucțiuni for nu avem voie să modificăm variabila contor a ciclului, adică i ! Dacă dorim să facem acest lucru vom folosi în loc o instrucțiune while.

Exerciții cu secvențe

Elementul maxim într-o secvență

Dată o secvență de n numere să se afișeze elementul cel mai mare (maxim) din secvență. Exemple:

maxim.in maxim.out
6
4 2 0 4 7 1
7
8
3 12 10 12 8 3 6 8
12

Rezolvare:

Numărul maxim în secvență
 #include <stdio.h>

 int main() {
   FILE *fin, *fout;
   int n, i, a, max;

   fin = fopen( "maxim.in", "r" );
   fscanf( fin, "%d", &n );
   fscanf( fin, "%d", &max );
   for ( i = 1; i < n; i++ ) {
     fscanf( fin, "%d", &a );
     if ( max < a )
       max = a;
   }
   fclose( fin );

   fout = fopen( "maxim.out", "w" );
   fprintf( fout, "%d", max );
   fclose( fout );
   return 0;
 }

Observații:

  • Elementul maxim se inițializează cu primul element al șirului nu cu valoarea zero. Întotdeauna vom inițializa maximul cu un element al secvenței. De ce?
    • Este bine să fim ordonați și consecvenți: max este doar un candidat la maxim, dintre elementele secvenței, pînă la final, cînd devine chiar maximul. Ce fel de candidat este el dacă este un străin, nici măcar nu face parte din secvență?
    • În viitor putem avea și elemente negative.
    • Dacă avem o greșeală în program detecția ei și corectura sînt mai grele atunci cînd max poate lua valori în afara elementelor din secvență.
  • Pentru a calcula elementul minim într-o secvență singurul lucru care se modifică în schema de mai sus este semnul comparației max < a, din mai mic < în mai mare >.

Secvență în ordine crescătoare

Dată o secvență cu n numere să se spună dacă cele n numere din secvență sînt in ordine crescătoare (fiecare număr este mai mic sau egal cu cel de după el).

crescatoare.in crescatoare.out
6
2 7 7 10 15 15
da
8
3 3 6 8 8 10 12 11
nu

Rezolvare:

Secvență crescătoare
 #include <stdio.h>

 int main() {
   FILE *fin, *fout;
   int n, i, a, b, cresc;

   fin = fopen( "crescatoare.in", "r" );
   fscanf( fin, "%d", &n );
   fscanf( fin, "%d", &a );
   cresc = 1;
   i = 1;
   while ( i < n && cresc == 1) {
     fscanf( fin, "%d", &b );
     if ( b < a )
       cresc = 0;
     a = b;
     i++;
   }
   fclose( fin );

   fout = fopen( "crescatoare.out", "w" );
   if ( cresc == 1 )
     fprintf( fout, "da\n" );
   else
     fprintf( fout, "nu\n" );
   fclose( fout );
   return 0;
 }

Observații:

  • Nu folosim instrucțiunea for deoarece nu se știe de cîte ori se va executa bucla while (nu avem un ciclu cu număr cunoscut de pași).
  • Trebuie să ținem minte elementul anterior în secvență, pentru a-l putea compara cu elementul curent. Vom vedea că în alte probleme vom avea nevoie să ținem minte două sau chiar și trei elemente anterioare.
  • Încercaţi să scrieţi algoritmul fără a folosi steguleţe.

Temă

  • Tema 13: să se rezolve următoarele probleme (schemă logică + program C în CodeBlocks, trimis la vianuarena):
  • Problemă de logică: ne aflăm în întuneric total (nu putem vedea nimic). Avem în față un pachet de 52 de cărți de joc. Ele sînt amestecate, dar se știe că 42 de cărți sînt cu fața în jos, iar 10 sînt cu fața în sus. Cum facem să împarțim cele 52 de cărți în două gramezi, astfel încît ambele grămezi să conțină un număr egal de cărți cu fața în sus? Explicați de ce soluția voastră funcționează, altfel nu vi se acordă punctajul!

Rezolvări aici [1]