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

From Algopedia
Jump to navigationJump to 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.

Rezolvări aici [1]

Lecție

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

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