Clasa a VI-a lecția 8 - 8 nov 2018

From Algopedia
Revision as of 10:29, 19 March 2021 by Cristian (talk | contribs) (→‎Lecție - numere mari)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Tema - comentarii

Nu am avut timp să corectez rezolvările voastre. M-am uitat însă pe multe din ele și acestea sînt comentariile generale:

  • Majoritatea dintre voi tratați cu seriozitate cursul și vă străduiți să rezolvați temele.
  • Cîțiva dintre voi nu se străduie și se vede. Trimiteți surse făcute de mîntuială, doar pentru a nu vă da avertismente că nu faceți tema. Un exemplu este Remus Rughiniș, care la problema john a trimis o singură sursă în care scrie fin=fopen("john.in","w");. Este un program neglijent și evident nedepanat, dacă deschide fișierul de intrare în mod scriere, nici nu pare că ai încercat să îl depanezi. În aceeași situație se află Nicu Cemârtan care nu a lucrat nimic suplimentar trimițînd doar sursa la problema leo pe care aproape o terminase în concurs, Mihai Coman care în afară de ceea ce a lucrat în clasă la problema leo nu a mai făcut aproape nimic, Albert Aizic care nici nu a încercat să aducă sursa de la concurs la leo dincolo de 36p, lăsînd-o identică, David Stancu care chiar și după multe discuții nu a înțeles ciurul lui Eratostene, Denisa Dragomir care trimite surse repezite, neatente, în care ciurul este declarat de 100 de milioane de elemente deși enunțul spune un milion - greșeli de începător, cum să încapă un vector de 100 milioane de long long (altă inutilitate, int era suficient) cînd el va ocupa 800 milioane de octeți, iar problema ne oferă 6 milioane.
  • Sînt nevoit cu părere de rău să dau un avertisment serios celor de mai sus. Sînteți codașii temelor, nu lucrați suficient și se simte, rămîneți în urmă. Faceți greșeli de neatenție, grabă, repezeală. Înțeleg surse cu greșeli finuțe, de indici, de timp, etc. Dar să nu vă calculați memoria, să folosiți long long aiurea, să deschideți fișiere de intrare în mod citire sau să închideți de două ori același fișier, acestea sînt greșeli din cauza faptului că nu lucrați.

Vă reamintesc: voi ați vrut să fiți aici. IQ Academy nu înseamnă să greșim zerouri în plus la declararea vectorilor. Puneți mîna și lucrați.

Rezolvări aici [1]

Lecție - numere mari

<html5media height="720" width="1280">https://www.algopedia.ro/video/2018-2019/2018-11-08-clasa-6-lectie-info-08-720p.mp4</html5media> Unele probleme necesită lucrul cu numere mai mari decît ne permite tipul long long (cu aproximație 18 cifre zecimale, mai exact 264). Ce facem în acest caz? Stocăm aceste numere în vectori, cîte o cifră în fiecare element al vectorului. În continuare voi prezenta cîteva probleme clasice cu astfel de numere.

Reprezentare

Numerele mari se reprezintă într-un vector, ultima lor cifra pe prima poziție a vectorului, penultima pe a doua poziție, și așa mai departe. De exemplu, numărul 24537 se reprezintă astfel:

Reprezentarea în vector a unui număr mare

Observați că am reprezentat vectorul invers, de la dreapta la stînga, pentru ușurința citirii numărului. De ce reprezentăm cifrele numărului de la coadă la cap? Deoarece atunci cînd numerele cresc sau se micșorează cifrele lor nu trebuie deplasate în vector pentru a rămîne aliniate la începutul vectorului.

Observăm că vectorul v are ca elemente cifre, adică întregi cuprinși între 0 și 9. Pentru a folosi cît mai puțină memorie vom folosi cel mai mic întreg existent în limbajul C și anume tipul caracter. Să nu uităm că tipul caracter poate fi văzut atît ca și caracter cît și ca un întreg pe opt biți, cuprins între -128 și 127. Această reprezentare a numerelor mari se numește reprezentarea în zecimal despachetat:

char v[100];

Pentru cei curioși există și reprezentarea zecimal împachetat, în care reprezentăm două cifre zecimale pe caracter, respectiv o cifră pe primii 4 biți și o cifră pe ultimii patru biți. În această lecție nu vom vorbi despre această reprezentare.

De asemenea, pentru un număr mare trebuie să ținem minte și numărul său de cifre. În exemplul nostru acesta este 5. Printre olimpici circulă o versiune de numere mari în care numărul de cifre este memorat chiar în primul element al vectorului, v[0]. Aceasta nu este o idee bună din mai multe motive:

  • Dacă numărul mare are mai mult de 255 de cifre vom depăși tipul unsigned char.
  • Amestecă un număr de cifre cu cifrele însele, punînd la grămadă mere cu dovlecei.
  • Codul devine mai greu citibil.

Ca ultimă mențiune, trebuie să avem grijă ca cifrele nefolosite din vector să fie setate la zero. Acest lucru este foarte important atunci cînd numărul poate să crească, cum ar fi la adunare, sau înmulțire.

Afișare

Cum afișăm un număr mare? Afișînd toate cifrele sale de la final de vector spre început. Avem însă un caz particular: numărul zero. Convenția de reprezentare a unui număr mare este ca prima lui cifră (cea mai semnificativă) să fie nenulă. În cazul lui zero acest lucru nu se poate. De aceea numărul mare zero va fi reprezentat ca avînd zero cifre. De aceea, la afișare nu vom afișa nimic, deoarece vom încerca să afișăm zero cifre. Acesta este cazul particular la afișare, dacă numărul mare are zero cifre vom afișa zero. Iată codul de afișare a unui număr mare:

  if ( n == 0 )
    fprintf( fout, "0\n" );
  else {
    for ( i = n; i > 0; i-- )
      fputc( '0' + v[i-1], fout );
    fputc( '\n', fout );
  }

Adunarea unui număr mic la unul mare

Fie v un număr mare cu n cifre. Dorim să adunăm la el un număr "mic", a. Pentru aceasta vom proceda similar cu procedura de adunare "de mînă": vom aduna a la prima cifră a numărului, vom stoca pe prima poziție ultima cifră a acestui număr, apoi vom calcula transportul prin împărțire la zece. Acest transport se adună la a doua cifră, stocînd ultima cifră a rezultatului pe a doua poziție și calculînd noul transport prin împărțire la zece. Diferența față de adunarea "de mînă" este că transportul poate fi mai mare decît 9. Iată secvența de cod care adună numărul mare (n, v) cu numărul a:

  i = 0;
  while ( a > 0 ) {
    a += v[i];
    v[i] = a % 10;
    a /= 10;
    i++;
  }
  if ( i > n )
    n = i;

Scăderea unui număr mic din unul mare

Scăderea unui număr mic din unul mare este similară cu adunarea. Transportul va fi negativ. Trebuie însă să fim atenți la un lucru: operația % (modulo) în C nu se comportă ca la matematică. La matematică restul împărțirii a două numere este pozitiv sau zero. În C restul împărțirii unui număr negativ la unul pozitiv este negativ sau zero. De aceea codul trebuie modificat față de adunare pentru a calcula restul pozitiv al împărțirii la zece. De asemenea trebuie să avem grijă să scădem numărul de cifre, dacă este cazul. Vom păstra în nn poziția ultimei cifre diferite de zero. Iată secvența de cod care scade numărul mic a din numărul mare (n, v):

  a = -a;
  i = 0;
  while ( a < 0 ) {
    a += v[i];
    v[i] = a % 10;
    a /= 10;
    if ( v[i] < 0 ) {
      v[i] += 10;
      a--;
    }
    i++;
  }
  // ajustam numarul de cifre, deoarece primele cifre pot fi zero
  while ( n > 0 && v[n-1] == 0 )
    n--;

Atenție: programul de mai sus presupune că numărul mic este mai mic sau egal cu numărul mare.

Adunarea a două numere mari

Adunarea a două numere mari este similară cu adunarea unui număr mare cu unul mic. Vom folosi un transport și vom aduna cifră cu cifră cele două numere mari. În final vom testa dacă mai avem transport. Dacă avem el este maxim o cifră (demonstrați). Iată secvența de cod care adună numărul mare (n2, v2) la (n1, v1) depunînd rezultatul tot în (n1, v1):

  n1 = n1 < n2 ? n2 : n1;
  t = 0;
  for ( i = 0; i < n1; i++ ) {
    t = t + v1[i] + v2[i];
    v1[i] = t % 10;
    t /= 10;
  }
  if ( t > 0 ) {
    v1[i] = t;
    n1++;
  }

Scăderea a două numere mari

Scăderea a două numere mari este similară cu scăderea unui număr mare din unul mic. Vom folosi un transport negativ și vom scădea cifră cu cifră cele două numere mari. După ce se termină cifrele numărului de scăzut vom continua scăderea pînă ce transportul devine zero. Ca și la scăderea unui număr mic va trebui să avem grijă să scădem numărul de cifre dacă este cazul. Iată secvența de cod care scade numărul mare (n2, v2) din numărul mare (n1, v1):

  t = i = 0;
  while ( i < n2 || t < 0 ) {
    t = t + v1[i] - v2[i];
    v1[i] = t % 10;
    t /= 10;
    if ( v1[i] < 0 ) {
      v1[i] += 10;
      t--;
    }
    i++;
  }
  // ajustam numarul de cifre, deoarece primele cifre pot fi zero
  while ( n1 > 0 && v1[n1-1] == 0 )
    n1--;

Atenție: programul de mai sus presupune că numărul (n2, v2) este mai mic sau egal cu numărul (n1, v1).

Înmulțirea unui număr mare cu unul mic

Înmulțirea unui număr mare cu unul mic este similară cu adunarea unui număr mare cu unul mic. Vom folosi un transport la care adunăm cifra curentă înmulțită cu numărul mic. Ultima cifră a transportului se stochează în cifra curentă, iar transportul se împarte la zece, apoi trecem la cifra următoare. După ce se termină cifrele numărului mare vom continua procedura pînă ce transportul devine zero. Trebuie să avem grijă să actualizăm numărul de cifre dacă este cazul. Iată secvența de cod care înmulțește numărul mic a cu numărul mare (n, v):

  t = i = 0;
  while ( i < n || t > 0 ) {
    t = t + a * v[i];
    v[i] = t % 10;
    t /= 10;
    i++;
  }

  if ( i > n )
    n = i;

Împărțirea unui număr mare la unul mic

Împărțirea unui număr mare la unul mic se face invers față de celelalte operații de pînă acum. Vom parcurge numărul mare de la cea mai semnificativă cifră (cifra cu indicen - 1) către cifra de indice zero (prima din vector). Vom avea un rest curent; vom adăuga fiecare cifră a numărului mare la coada restului, înmulțind restul cu zece și adunînd cifra. Împărțind restul curent la numărul mic obținem încă o cifră din cît, pe care o putem suprascrie peste cifra din numărul mare. La final vom avea cîtul în numărul mare, iar ultimul rest este chiar restul împărțirii. Este posibil ca cîtul să aibă mai puține cifre decît numărul original, drept care va trebui să reducem numărul de cifre căutînd prima sa cifră nenulă. Iată secvența de cod care împarte numărul mare (n, v) la numărul mic a:

  t = 0;
  for ( i = n - 1; i >= 0; i-- ) {
    t = t * 10 + v[i];
    v[i] = t / a;
    t %= a;
  }
  // ajustam numarul de cifre, deoarece primele cifre pot fi zero
  while ( n > 0 && v[n-1] == 0 )
    n--;

Temă

Tema 8, clasa a 6a

  • fib problemă de adunare a două numere mari
  • ANAF problemă de operații între numere mari și numere mici
  • cod dată la ONI 2016 clasa a 6a

Rezolvări aici [2]