Clasa a V-a lecția 17 - 14 dec 2019

From Algopedia
Jump to navigationJump to search

Anunțuri

Cursul din 21 decembrie 2019 va începe la ora 10:00 și va consta într-un concurs de 3 ore. Concursul este o recapitulare din tot ceea ce am făcut la cerc până acum. De asemenea, are caracter eliminatoriu. Prezența este obligatorie!

Tema - comentarii

  • În principiu, temele au fost foarte buna. Felicitări tuturor celor care au trimis rezolvări la toate problemele: Andrei Coman, Andrei Grama, Briana Vasile, Daria Bădoiu, David Poterașu, Vlad Mișcoci și Vladimir Gavriș.
  • Îi menționăm și pe cei care au abordat cu succes parțial tema: Cristina Boabeș și Luca Zamfir.
  • Avertisment pentru cei care nu au abordat deloc tema: Alex Stanciu și Mara Florian. Pentru Mara, acesta este un ultimatum.
  • Nu știu de unde ați deprins următoarea scriere:
 fprintf(fout, "%d\n", nrrgrad1); 
 fprintf(fout, "%d\n", nrrgrad2);
 fprintf(fout, "%d\n", nrrgrad3);
 fprintf(fout, "%d\n", nrb);
 fprintf(fout, "%d\n", nrf);
 fprintf(fout, "%d\n", nrc);

De ce nu scrieți într-o singură comandă?

 fprintf(fout, "%d\n%d\n%d\n%d\n%d\n%d\n", nrrgrad1, nrrgrad2, nrrgrad3, nrb, nrf, nrc);
  • Nu mai lăsați avertismentele netratate. Nu trebuie să aveți warning la compilare. Mai multă atenție Daria.
  • În continuare nu indentați programele. Este foarte dificil să urmărești un cod neindentat. De asemenea, vă face să păreți amatori. Corectați acest obicei. Indentarea este bună! Atenție David Poterașu.

Concurs - rezolvare

Problema seif2

Problema seif2

Răspuns: problema cere, în fapt, să se calculeze maximul dintre concatenările numerelor consecutive, două cîte două, într-o secvență de numere naturale. Cum vom rezolva această problemă? Esența ei constă în concatenarea a două numere, x și y. O metodă posibilă este să adăugăm zerouri la coada lui x și apoi să îl adunăm pe y. Va trebui să adunăm atîtea zerouri cîte cifre are y. Drept care îl vom împărți pe y la zece și pentru fiecare împărțire vom înmulți x cu zece. Ne vom opri cînd y nu mai are cifre, adică atunci cînd devine zero. Trebuie să avem grijă la cazul particular cînd y este zero, caz în care trebuie totuși să înmulțim x cu zece, o singură dată.

Iată o rezolvare posibilă bazată pe aceste idei:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, i, x, y, yc, max;

  fin = fopen( "seif2.in", "r" );
  fscanf( fin, "%d%d", &n, &x ); // citim numarul de numere si primul numar
  max = x;
  for ( i = 1; i < n; i++ ) {    // citim si prelucram urmatoarele n-1 numere
    fscanf( fin, "%d", &y );
    yc = y / 10;       // yc este copie a lui y pe care o putem distruge

    // pentru fiecare cifra a lui yc adaugam un zero la coada lui x
    x = x * 10;
    while ( yc > 0 ) {
      x = x * 10;
      yc = yc / 10;
    }
    // daca il adunam pe y la x astfel modificat vom avea lipirea numerelor
    x = x + y;

    if ( x > max ) // numarul lipit il comparam cu maximul
      max = x;
    x = y;
  }
  fclose( fin );

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

  return 0;
}

Tema - rezolvări

Problema case

Problema case a fost dată la OJI 2006, clasa a 5-a.

Răspuns: este o problemă cu secvențe, destul de ușoară. Este o problemă din categoria celor în care ni se spune exact ce avem de făcut, cu instrucțiuni detaliate. Vom citi n numere de patru cifre. Vom separa cele patru cifre, apoi vom face diverse acțiuni pentru fiecare cifră:

  • Prima cifră adună 1 la contorul rudelor de gradul 1 dacă valoarea ei este 1, la contorul rudelor de gradul 2 dacă valoarea ei este 2, sau la contorul rudelor de gradul 3 dacă valoarea ei este 3.
  • A doua cifră se adună ca atare la suma numărului de bărbați.
  • A treia cifră se adună la suma numărului de femei.
  • A patra cifră se adună la suma numărului de copii.

În final vom afișa cele șase numere, fiecare pe linia lui. Banal. Iată un program posibil:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, i, cod, cf, rude1, rude2, rude3, barbati, femei, copii;

  fin = fopen( "case.in", "r" );
  fscanf( fin, "%d", &n );
  rude1 = 0; // la inceput toate sumele sint zero
  rude2 = 0;
  rude3 = 0;
  barbati = 0;
  femei = 0;
  copii = 0;
  for ( i = 0; i < n; i++ ) {
    fscanf( fin, "%d", &cod );
    cf = cod / 1000; // extragem prima cifra a numarului
    if ( cf == 1 )
      rude1++;
    else if ( cf == 2 )
      rude2++;
    else
      rude3++;
    barbati = barbati + cod / 100 % 10; // a doua cifra a numarului
    femei = femei + cod / 10 % 10;      // a treia cifra a numarului
    copii = copii + cod % 10;           // a patra cifra anumarului
  }
  fclose( fin );

  fout = fopen( "case.out", "w" );
  fprintf( fout, "%d\n%d\n%d\n%d\n%d\n%d\n", rude1, rude2, rude3,
           barbati, femei, copii);
  fclose( fout );

  return 0;
}

Problema ucif

Problema ucif a fost dată la OJI 2005 clasa a 5-a.

Răspuns: dacă încercăm să rezolvăm problema direct, calculînd expresia și afișînd ultima cifră a numărului rezultat avem o problemă: numărul este atît de mare încît nu încape într-un întreg. Ce facem în acest caz? Avem două soluții, una de observație și una matematică. Să le luăm pe rînd.

Varianta observării cazurilor posibile

Cum am rezolva această problemă pe hîrtie, pentru k=10, de exemplu? Chiar vom înmulți toate acele numere mari? Desigur că nu. Vom înmulți doar ultima cifră, deoarece doar de ea este nevoie. Mai mult, vom observa că ultima cifră se repetă destul de repede, prin înmulțiri repetate. De exemplu:

0 * 0 = 0
1 * 1 = 1

deci ori de cîte ori vom ridica la putere 0 el rămîne 0, la fel și 1.

2 * 2 = 4
4 * 2 = 8
8 * 2 = 16
16 * 2 = 32

Observăm că prin ridicare la putere ultima cifră va fi 2, 4, 8, 6, apoi se va relua, 2, 4, 8, ...

Similar, pentru toate cifrele vom obține repetiții după patru, două, sau o singură înmulțire. Drept care este deajuns să testăm restul împărțirii exponentului la patru, doi, sau unu pentru a ști ultima cifră. În fapt, putem considera că toate repetițiile sînt după patru înmulțiri, pentru a simplifica programul.

Iată o soluție bazată pe această idee:

// Solutie: unele cifre se repeta prin inmultire dupa patru inmultiri.
// Altele dupa doar doua. Iar altele dupa o singura inmultire. Observam
// ca le putem considera pe toate ca si cind s-ar repeta dupa patru
// inmultiri. Vom testa, deci, restul impartirii la patru al puterii.
#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, i, j, s, p, cf;

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

  s = 0;
  for ( i = 1; i <= n; i++ ) {
    cf = i % 10; // ultima cifra a lui i^i
    // calculam produsul cf * cf * ... * cf de (i-1) % 4 ori
    p = cf;
    for ( j = 1; j <= (i-1) % 4; j++ )
      p = p * cf;
    s = s + p % 10;
  }

  fout = fopen( "ucif.out", "w" );
  fprintf( fout, "%d\n", s % 10 );
  fclose( fout );

  return 0;
}

Varianta matematică

Problema admite o variantă ușor modificată a rezolvării directe, cu o mică întorsătură. Vom calcula suma cerută, dar ea va fi foarte mare, drept care nu va încăpea într-o variabilă întreagă. Și atunci ne folosim de o proprietate matematică a resturilor:

(a * b) % c = ((a % c) * (b % c)) % c

Nu vom demonstra aici acest lucru, deoarece ține de matematică și se cheamă aritmetica resturilor. Cum folosim această proprietate? Atunci cînd calculăm un produs kk vom avea grijă ca la fiecare înmulțire cu k să o efectuăm modulo 10, păstrînd doar ultima cifră.

Ce învățăminte tragem de aici? Că informatica fără matematică nu se poate.

Iată o rezolvare posibilă:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, i, j, s, p;

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

  s = 0;
  for ( i = 1; i <= n; i++ ) {
    p = 1;
    for ( j = 0; j < i; j++ )
      p = (p * i) % 10;
    s = s + p;
  }

  fout = fopen( "ucif.out", "w" );
  fprintf( fout, "%d\n", s % 10 );
  fclose( fout );

  return 0;
}


Lecție

Concurs: o întrecere colegială. Simulăm un concurs, dar cu reguli relaxate. Mai exact, dupa ce vă străduiți la maxim și simțiți că v-ați împotmolit aveți voie:

  • să puneți întrebări
  • să cereți ajutorul instructorului

Iată concursul: Concurs clasa a 5-a

Temă

Tema 17: să se rezolve următoarele probleme (program C trimis la vianuarena):

  • regele (cerc Vianu 2014 clasa a 5a)
  • plaja2 (cerc Vianu 2014 clasa a 5a)
  • gardul (OJI 2003 clasa a 6a)

Cei care ați trimis deja rezolvări la concurs aveți grijă să le retrimiteți în cadrul temei.

Rezolvări aici [1]