Clasa a V-a lecția 11 - 2 noi 2019

From Algopedia
Revision as of 13:32, 6 November 2019 by Mihai (talk | contribs) (Lecție)

Jump to: navigation, search

Anunț important

Cursul următor, din data 9 noiembrie, nu se va ține le sediul Nerdvana. În intervalul aferent, 13:00 - 15:00, va fi o rundă de concurs pe care o veți susține de acasă. În cazul în care aveți nelămuriri, vă rog să îmi scrieți.

Tema – rezolvări

Comentarii generale

  • Felicitări celor care au rezolvat problemele complet și corect: Alex Stanciu, Andrei Coman și Daria Bădoiu.
  • Avertisment: următorii copii nu au trimis tema deloc, nici pe varena.ro, nici pe email: Maria Dinu, Tudor Ștefan;
  • Avertisment: Tudor Ștefan. Este a doua lecție la care nu îmi trimiți tema. Dacă o ții tot așa, te voi invita să parcurgi lecțiile singur, acasă.
  • Avertisment: doi dintre voi aveți sursele identice la problema La școală: Andrei Grama și Mara Florian. Așa ceva nu este permis. Acest lucru se numește mai întâi de toate furt (intelectual, în acest caz): însușirea proprie a unui lucru care nu vă aparține. Este normal să nu știți să rezolvați unele probleme, de aceea veniți la curs. Însă, dacă voi faceți temele la comun, eu nu pot evalua situația voastră și voi nu veți învăța să vă descurcați singuri. Arătați-mi că ați încercat prin surse care nu merg și făcute de voi. Dacă aveți nevoie de ajutor, cereți pe grup, de aceea l-am făcut. Un coleg poate va răspunde, eu cu siguranță o voi face. Ajutorul pe care îl cereți nu înseamnă să postați sursa, ci să întrebați de ce vă dă o eroare sau ce vrea să spună textul problemei. Dacă e nevoie să vă lămuriți codul, adresați-vă mie, într-un mesaj privat.

La şcoală

Comentarii specifice

  • O parte dintre voi nu ați folosit funcția sqrt(). Este ok, am văzut mai bine că ați înțeles cum să o recreați cu ajutorul unei repetiții while.
  • Fișierele se deschid și se închid o singură dată în program. Dacă voi deschideți un fișiere în interiorul unui while, ce credeți că se întâmplă? Se va deschide de atâtea ori cât funcționează bucla. Evident va fi o problemă. Atenție aici: Matei Balaur, Briana Vasile.
  • Atenție la numele fișierelor. Dacă problema specifică numele ”lascoala.in”, atunci acesta trebuie să fie numele. Dacă introduceți spații în plus, nu va fi același fișier. Matei Balaur:, ai pus numele fișierelor ” la scoala . in” și ” la scoala . out”.
  • Când urcați problemele pe varena.ro trebuie să faceți upload la fișierul main.c. Unii dintre voi ați trimis fișierul cu extensia .cbp. Acela este proiectul de CodeBlocks, nu are legătură cu programul vostru C.
  • Comanda de afișare fprintf are 3 parametri sau argumente:
    fprintf(numele de fisier, textul de afișat, variabile)
    Dacă omiteți oricare dintre aceste, programul nu va funcționa corect. Atenție: Matei Balaur.

Problema La școală a fost dată la OJI 2002 clasa a 5a.

Punctul 1 - numărul de copii premiaţi

Cel mai mare pătrat perfect strict mai mic decît n este [{\sqrt  {n-1}}]^{2}. Pentru primul punct al problemei vom calcula

p = sqrt( n - 1 );

iar apoi, pentru a afla k, numărul copiilor nepremiaţi, vom calcula pătratul lui p:

k = p * p;

Numărul copiilor premiaţi este, deci, n - k.

Atenţie! O greşeală foarte comună, la acest punct, este să nu ne dăm seama că pătratul perfect este strict mai mic decît n. Aceasta înseamnă că dacă n este pătrat perfect va trebui să nu-l considerăm pe n, ci pătratul perfect imediat din-naintea lui.

Punctul 2 - copiii nepremiaţi

La punctul 2 se cere să afişăm numerele de la 1 la k în ordine descrescătoare, cîte p pe fiecare linie. Ştim să facem această afişare. Singura problemă constă în afişarea finalului de linie, '\n'. Pentru aceasta am putea să folosim două bucle while una într-alta: cea exterioară afişează toate liniile, una cîte una, iar cea interioară afişează o singură linie. Există însă o soluţie mai simplă: să observăm că o linie va începe întotdeauna cu un număr divizibil cu p. Drept pentru care putem testa înainte de a afişa un element dacă el se divide cu p, caz în care vom afişa un final de linie.

Iată o soluţie bazată pe aceste idei:

La școală
 #include <stdio.h>
 #include <math.h>

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

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

   p = sqrt( n - 1 );
   k = p * p;

   fout = fopen( "lascoala.out", "w" );
   fprintf( fout, "%d\n", n - k );
   while ( k > 0 ) {
     fprintf( fout, "%d ", k );
     k = k - 1;
     if ( k % p == 0 )
       fprintf( fout, "\n" );
   }
   fclose( fout );

   return 0;
 }

Balaur

Comentarii specifice

  • Matei Balaur:, aceeși problemă la numele de fișiere.

Problema Balaur a fost dată la OJI 2002 clasa a 5a.

Balaurul pierde un cap ziua şi cîştigă şase noaptea. Acţiunea se desfăşoară vreme de n zile. Atenţie, însă, deoarece noaptea numărul n nu se ia în considerare, deoarece problema cere să spunem cîte capete are balaurul după a na zi. Va trebui deci să adunăm cîte 6 capete pentru cele (n-1) nopţi şi să scădem un cap pentru cele n zile. Vom porni, desigur, cu cele 6 capete iniţiale. Rezultă formula:

capete = 6 + (n-1) * 6 - n = 6 + 6*n - 6 - n

Rezultă formula foarte simplă:

capete = 5*n

În realitate, după ce scriem problema în termeni matematici şi ducem pînă la capăt calculele, problema cere ca, dîndu-se n, să afişam 5*n.

Iată soluţia, banală:

Balaur
 #include <stdio.h>

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

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

   fout = fopen( "balaur.out", "w" );
   fprintf( fout, "%d\n", 5 * n );
   fclose( fout );

   return 0;
 }

Platformele

Problemă de logică: te afli pe o platformă la 200m înălțime. Platforma are un inel bine ancorat. Mai jos, la 100m de pămînt se află o platformă identică. Dispui de o frînghie de 150m și o foarfecă. Cum ajungi la pămînt?

Răspuns: tai frînghia în două bucăți, una de 50m și una de 100m. Faci un laț la un capăt al bucății de 50m, iar celălalt capăt îl înnozi de inelul platformei. Treci prin laț bucata de 100m (fiind în două ea va avea numai 50m, plus cei 50m ai frînghiei cu laț) și cobori pe platforma de dedesubt. Cînd ajungi jos tragi bucata de 100m din laț, o înnozi de inelul platformei și cobori pe pămînt.

Problemă radical

Există, oare, o rezolvare mai bună? Desigur! Vom folosi aceeași metodă pe care am folosit-o la rezolvarea problemei divizibilitate în lecția 3, care cerea să se afișeze numărul de numere divizibile cu k în intervalul [a, b].

Vom rezolva mai întîi o problemă mai simplă: să se spună cîte pătrate perfecte există între 1 și x. Acest număr, dacă ne gîndim puțin, este chiar {\sqrt  {x}}. Dar numărul de pătrate perfecte între a și b? El este numărul de pătrate perfecte între 1 și b, minus numărul de pătrate perfecte între 1 și a-1. Astfel obținem formula:

nrpp={\sqrt  {b}}-{\sqrt  {a-1}}

Iată cea mai eficientă variantă:

Numărul de pătrate perfecte între a și b varianta 3
 #include <stdio.h>
 #include <math.h>

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

   fin = fopen( "patrate.in", "r" );
   fscanf( fin, "%d%d", &a, &b );
   fclose( fin );
   n = sqrt( b );
   m = sqrt( a - 1 );
   fout = fopen( "patrate.out", "w" );
   fprintf( fout, "%d\n", n - m );
   fclose( fout );
   return 0;
 }

Concluzie: matematica este esențială în informatică, ea ducînd la cele mai bune soluții.

Lecție

Exerciții

Scrieți schema logică și programul C pentru următoarele probleme, folosind fișiere pentru citirea și scrierea datelor.

Număr conținut în alt număr

Să se spună de cîte ori un număr conține pe altul. Exemplu: 439453967 conține 39 de două ori, iar 2323232 conține 232 de 3 ori. Iată o variantă de algoritm. Acest algoritm nu funcționează într-un caz particular. Puteți spune cînd? Cum putem repara problema?

Apariții număr în număr
 #include <stdio.h>

 int main() {
   FILE *fin, *fout;
   int n, p, pc, p10, ap;

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

   // calculam numarul de cifre al lui p
   pc = p;
   p10 = 1;
   while ( pc > 0 ) {
     p10 = p10 * 10;
     pc = pc /10;
   }
   // comparam cu ultimele cifre ale lui n
   ap = 0;
   while ( n > 0 ) {
     if ( n % p10 == p )
       ap = ap + 1;
     n = n / 10;
   }

   fout = fopen( "aparitii.out", "w" );
   fprintf( fout, "%d\n", ap );
   fclose( fout );
   return 0;
 }

Număr cu cifre distincte

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ă.

Rezolvarea 1

O soluție posibilă este să luăm ultima cifră a numărului n, să o eliminăm din număr, iar apoi să verificăm că numărul rămas nu conține cifra. Dacă totul este în regulă reluăm procedeul cu numărul rămas. Repetăm pînă ce n rămîne de o singură cifră (care nu se poate repeta).

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

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

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

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

   nc = 0;
   while ( n > 9 && nc == 0 ) {
     cf = n % 10;
     nc = n / 10;
     while ( nc > 0 && nc % 10 != cf )
       nc = nc / 10;
     n = n / 10;
   }

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

   return 0;
 }

Rezolvarea 2

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ă). Această variantă trebuie rezolvată ca temă.


Secvențe

Definiție: denumim secvență un șir de numere. Exemplu: 34 20 4 0 12 5 8 7. Simplu?

Citirea unei secvențe

Deoarece nu avem unde păstra numerele unei secvențe, le vom citi, pe rînd, în aceeași variabilă. Pentru a ști cîte numere citim (cîte numere are secvența) de obicei vom citi mai întîi numărul de numere din secvență, n și apoi cele n numerele din secvență, într-o buclă WHILE-DO. Exemplu:

Citire secvență
 fscanf( fin, "%d", &n );
 i = 0;
 while ( i < n ) {
   fscanf( fin, "%d", &a );
   i = i + 1;
 }

Suma unei secvențe

Ca prim exemplu de lucru cu secvențe să calculăm suma a n numere citite la intrare:

Suma unei secvențe
 #include <stdio.h>

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

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

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

Exemple:

Fișierul suma.in Fișierul suma.out
3
4 2 6
12
5
25 10 8 0 4
47

Observații:

  • variabila i se numește contor, deoarece ea contorizează numărul de execuții al buclei WHILE-DO. Pentru a executa o buclă de n ori inițializăm contorul cu 0 și ne oprim cînd devine egal cu n. Preferăm această variantă, față de a porni cu i de la 1, deoarece ne obișnuiește pentru viitor să lucrăm corect cu vectori.
  • Variabila suma se numește acumulator, deoarece în ea se acumulează rezultatul, pe măsură ce citim secvența. Orice variabilă de tip acumulator trebuie inițializată înainte de a începe calculele! În acest caz, deoarece este o sumă, ea se va inițializa cu 0, deoarece 0 este elementul neutru la adunare. Dacă am fi calculat produsul secvenței am fi inițializat acumulatorul cu 1, deoarece 1 este elementul neutru la înmulțire.

Numărul de elemente pare din secvență

Să se afișeze cîte elemente pare se află într-o secvență

Numărul de numere pare dintr-o secvență
 #include <stdio.h>

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

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

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

Numărul de elemente zero și diferite de zero din secvență

Să se calculeze cîte numere zero apar într-o secvență, precum și cîte numere diferite de zero.

Numărul de elemente nule și nenule dintr-o secvență
 #include <stdio.h>

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

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

   fout = fopen( "zero.out", "w" );
   fprintf( fout, "%d %d", zero, n - zero );
   fclose( fout );
   return 0;
 }

Căutare număr în secvență

Să se spună dacă un număr e apare într-o secvență și pe ce poziție. Dacă e apare în secvență se va afișa poziția primei apariții a lui, între 0 și n - 1. În caz contrar se va afișa n.

Prima apariție a unui număr într-o secvență
 #include <stdio.h>

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

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

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

Observații:

  • Variabila poz are dublu rol. Pe de o parte ea memorează poziția primei apariții a numărului e în secvență. Pe de altă parte ea ne spune dacă am găsit numărul, astfel încît să ieșim din bucla WHILE-DO imediat ce am găsit numărul e. Variabilele care semnalează îndeplinirea unei condiții de oprire se numesc stegulețe, deci putem spune că variabila poz este un steguleț.

Tema

  • Cei care nu ați rezolvat problemele de la tema anterioară, La școală și Balaur, trebuie să le faceți și să le urcați pe varena.ro, la runda "Arhiva de probleme".
  • Să se rezolve problema Număr cu cifre distincte, în a doua variantă. Enunțul problemei este același: 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ă. Să se realizeze schemă logică și programul în C în CodeBlocks.
  • Tema 11: să se rezolve următoarele probleme (program C în CodeBlocks, trimis la vianuarena) în cadrul rundei de concurs:
  • 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.

Rezolvări aici [1]