Clasa a V-a lecția 13 - 2 nov 2017

From Algopedia
Jump to: navigation, search

Tema – rezolvări

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.

Rezolvări aici [1]

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 [2]