Clasa a VI-a lecția 3 - 4 oct 2018

From Algopedia
Jump to navigationJump to search

Comentarii temă

Comentarii problema numărare

Comentarii generale

  • Generalizarea la rezolvarea problemei cuvinte nu a fost evidentă. Acestea fiind spuse:
  • Ea nu se făcea adăugînd cîte un steguleț pentru fiecare lucru de numărat. Pentru aceasta avem deja contoare. Gîndiți-vă la o generalizare în care numărăm 20 de lucruri diferite, nu doar cuvinte și numere.
  • În nici un caz nu se făcea adăugînd bucle while pentru fiecare lucru de numărat. Acela e cu totul alt stil de program, care nu e ușor generalizabil pentru probleme mai grele.
  • Și în nici un caz nu se generaliza uitîndu-ne la două caractere consecutive, este neelegant și ineficient.
  • Felicitări celor ce au reușit o generalizare a rezolvării problemei cuvinte: Cadîr, Ipate, Marcu
  • Rușine celor ce încă nu știu să citească o secvență: Benescu, Iordache, Cadîr, Teodorescu

Comentarii individuale

Grupa de dimineață

  • Benescu: cod dezordonat și urîțel. Ai testat caracterul in condiția lui while să nu fie EOF apoi imediat l-ai aruncat și ai citit altul. Greșeală de începutul clasei a cincea. Ai folosit cu totul altceva decît o generalizare la problema cuvinte.
  • Calotă: implementare corectă, ordonată, bun. Gîndești puțin încîlcit, variabila ok trebuia folosită altfel. Vezi soluția de mai jos.
  • Cojocaru: ai scris direct programul, fără să te gîndești serios la metodă, înainte. De aceea nu funcționează. Sugestie: gîndește-te cum ai face "de mînă" înainte să scrii programul.
  • Coman: Nu trimite la arhivă. Prima submisie e dezordonată, ultima are sens. Face multe teste pe caracter, vezi soluția de mai jos.
  • Chivu: indentarea. Folosește te rog stilul Java din Code::Blocks, vezi setările de Code::Blocks. Codul tău este lung artificial și mai greu de urmărit. Generalizare cu mai multe stegulețe, vezi soluția mai jos.
  • Dumitrescu: soluție corectă, dar cu while în while, nu e o generalizare a problemei cuvinte. Vezi soluția de mai jos.
  • Hossu: program făcut de tine, bravo, așa! Este cam dezordonat, cu teste cam ciudate. Te uiți la două caractere consecutive, nu e o generalizare la problema cuvinte. Vezi soluția de mai jos.
  • Iordache: ai testat caracterul in condiția lui while să nu fie EOF apoi imediat l-ai aruncat și ai citit altul. Greșeală de începutul clasei a cincea. Testul (c=='\t' || c=='\n' || c==' ' || c>'9' || c<'0') este totuna cu (c>'9' || c<'0').
  • Mocanu: intrarea nu conține caractere mari, citește enunțul cu atenție! Soluție dură, cu vectori nenecesari. Dacă ai în mînă un ciocan, toate obiectele din jur îți par cuie, nu-i așa? Vezi soluția de mai jos.
  • Rebengiuc: cum te pot recunoaște în arhivă? Te crezi Einstein? Să te iei de mînă cu Harry Olarul. Mulțumesc pentru comentarii. Sursă ordonată, dar generalizare cu două stegulețe. Vezi soluția de mai jos.
  • Rughiniș: bune comentariile, altfel te bănuiam de pescuit sportiv. Ce oare poate să însemne b+=(0-((0-((1-n)-2))-3)+1)/2;? Ai o gîndire puțin încîlcită, trebuie să lucrezi la simplificarea lucrurilor.
  • Stancu: soluție corectă, dar cu while în while, nu e o generalizare a problemei cuvinte. Vezi soluția de mai jos.
  • Stoian: o soluție ușor dezordonată, cu multe teste. Vezi te rog soluția de mai jos și încearcă să îți faci un plan pe hîrtie, înainte să te apuci de programare. Sugestie: gîndește-te cum ai face "de mînă".
  • Ștefănescu: soluție corectă, dar cu while în while, nu e o generalizare a problemei cuvinte. Vezi soluția de mai jos. Nu e nevoie să scrii 'a'-0 <= c e OK să scrii simplu 'a' <= c.
  • Voicu: o soluție simplă, în aparență. Însă maschezi multele teste cu definiții de macro-uri. În realitate este o soluție destul de lungă. Parțial pentru că folosești comparația a două caractere consecutive, ceea ce nu e o generalizare a rezolvării problemei cuvinte. Soluția ta e greu de generalizat pentru probleme mai grele. Vezi soluția de mai jos.

Grupa de după-amiază

  • Cadîr: ai testat caracterul in condiția lui while să nu fie EOF apoi imediat l-ai aruncat și ai citit altul. Greșeală de începutul clasei a cincea. Ce se întîmplă cu valoarea 2 a lui ok, de ce ai folosit valorile 0, 1 și 3? :-) Felicitări, ai generalizat corect problema cuvinte.
  • Dobre: ai muncit, patru surse, dar ai reușit, bravo. Atenție la condiții de genul c == ' ' && c != EOF. Cum ar putea să fie un caracter și spațiu și EOF în același timp? Soluție cu while în while, nu e o generalizare a rezolvării la problema cuvinte. Vezi soluția de mai jos.
  • Ilie: un spațiu nu valorează la fel cît un '\n', nu? :-) Rezolvare corectă și ordonată. Folosește te rog stilul Java din Code::Blocks, vezi setările de Code::Blocks pe algopedia. Pune acolada pe aceeași linie cu instrucțiunea, codul e mai ușor de citit așa. Soluție ce compară două caractere consecutive, nu e cea dorită. Vezi te rog soluția de mai jos.
  • Ipate: nu scrie 0<=c-'0'. Scrie mai simplu c<='0'. Ideea cu variabila arata este bună, dar ai folosit-o un pic complicat. Numeri cuvinte atît la început cît și la sfîrșitul lor. Ai fost aproape de soluția bună, vezi mai jos.
  • Marcu: o soluție perfectă. Bravo!
  • Nicu: soluție ordonată, bun. Dar folosește while în while, nu e o generalizare la problema cuvinte. Vezi soluția de mai jos.
  • Tatomir: o generalizare cu două stegulețe, rezonabilă. Codul iese cam lung. Vezi soluția de mai jos, cu un singur steguleț.
  • Teodorescu: Ai testat caracterul in condiția lui while să nu fie EOF apoi imediat l-ai aruncat și ai citit altul. Greșeală de începutul clasei a cincea. Ai folosit cu totul altceva decît o generalizare la problema cuvinte, folosești while în while. E de înțeles, nu ai fost la IQ Academy anul trecut. Vezi te rog soluția de mai jos. Nu înțeleg repetiția buclei care înghite la intrare litere mici și nici nu înțeleg de ce ai nevoie de un steguleț. Mai multă ordonare și eleganță, te rog.

Comentarii problema numere5

Comentarii generale

  • Problema este grea. De ce oare? Pentru că necesită cunoștințe de matematică reale, nu cele de olimpiadă.
  • V-am spus lecția trecută că nu aveați nevoie de teste, cu excepția unui calcul de maxim la final. Vedeți o soluție fără teste mai jos. La IQ Academy sîntem perfecționiști, nu vrem doar să luăm 100p.
  • Calculele se simplificau dacă ați fi numărat numerele și grupele de la 0, cum se întîmplă mai mereu în matematică.
  • Atenție, mulți dintre voi ați ratat un test. Aveați nevoie fie de tipul long long, fie de unsigned. În clasa a șasea trebuie să fiți foarte atenți la ce tipuri de întregi folosim!

Comentarii individuale

Grupa de dimineață

  • Aizic: nimic?
  • Badea: o soluție matematică. Puțin necizelată și cu multe teste, dar solidă, bravo. Vezi soluția de mai jos.
  • Burac: ideea este foarte bună, calcule fără prea multe teste. Te-ai încurcat în calcule, vezi soluția de mai jos, te va descurca :-)
  • Cemârtan: nimic?
  • Cojocariu: aproape ți-a mers, te-ai încurcat la punctul doi. O soluție bună. Vezi și o soluție mai elegantă mai jos.
  • Dragomir: o soluție bună, bravo! Matematica necesară este grea pentru începutul clasei a cincea. Vezi și soluția de mai jos.
  • Dumitrescu: v-am spus lecția trecută că este necesară o soluție matematică. Soluțiile cu bucle vor depăși timpul, precum ai văzut. Atenție, nu vei putea fără matematică!
  • Grecu: bravo, o soluție bună, matematică, nu e ușor pentru clasa a cincea. Ai picat un test deoarece trebuia să folosești fie tipul long long fie tipul unsigned.
  • Mușat: nu închizi fișiere. Greșeală de clasa a cincea la început. Soluție ordonată, cu calcule. Faci multe teste, se poate simplifica prin ceva mai multă matematică. Vezi soluția de mai jos.
  • Nicola: O soluție foarte bună, matematică, bravo! Ai picat un test deoarece trebuia să folosești fie tipul long long fie tipul unsigned. Funcțiile au rolul de a evita duplicarea codului. Dacă te uiți atent, cele două calcule seamănă foarte mult, funcția și programul principal: rotațiile numerelor vor fi în direcții diferite, în restul totul e la fel.
  • Petcu: o soluție bună, matematică. Ar fi bine să încerci să îți simplifici modul de a gîndi - fie el matematic sau informatic. Ești un pic dezordonată. Multe din calculele tale se simplificau dacă lucrai cu numere de la zero, nu de la unu. Vezi mai jos o soluție elegantă. Ai picat un test deoarece trebuia să folosești fie tipul long long fie tipul unsigned.
  • Ștefănescu: temele trebuie scrise în limbajul C. Găsești explicația acestui fapt în regulile cercului, pe algopedia. Încercarea de rezolvare este bună, nu ai reușit să duci calculele pînă la capăt. Vezi soluția de mai jos.
  • Togan: o soluție bună, matematică. Multe din calculele tale se simplificau dacă lucrai cu numere de la zero, nu de la unu. Felicitări pentru faptul că te-ai prins că trebuie să folosești tipul long long! Vezi mai jos o soluție mai elegantă.
  • Voicu: o soluție bună, concisă, matematică, felicitări. O puteai simplifica dacă lucrai cu numere de la zero și foloseai modulo k. Vezi soluția de mai jos.

Grupa de după-amiază

  • Asgari: funcțiile au sens pentru a nu repeta cod. Tu ai cod foarte apropiat în funcție și în main. Dacă observai că calculele sînt aproape identice (diferind doar un semn) foloseai funcțiile corect. Decît să folosești funcții fără să le înțelegi mai bine duceai pînă la capăt matematica. Ea duce la o soluție fără funcții, precum vei vedea mai jos. Dacă duceai calculele pînă la capăt funcția ar fi avut o singură linie. E greu să justifici o funcție de o singură linie.
  • Fares: funcțiile au sens pentru a nu repeta cod. Fares, ți se pare că nu repeți cod? Cele două funcții au cod aproape identic, dacă duci matematica pînă la capăt. Dacă nu înțelegi rostul funcțiilor, e preferabil să nu le folosești. Folosește matematica și creierul mai bine, căci undeva ai greșit la calcule. O soluție bună, însă, care încearcă o rezolvare matematică, dar cu foarte multe teste, vezi soluția de mai jos, fără teste.
  • Marcu: o soluție bună, matematică și destul de scurtă. Ai picat un test deoarece trebuia să folosești fie tipul long long fie tipul unsigned. Vezi soluția de mai jos.
  • Simon: încercarea bună, nu ai dus calculele pînă la capăt. Puteai să verifici de mînă că nu funcționează. Nu folosi vianuarena pe post de verificator al soluțiilor tale. Creează-ți singur teste, e singurul mod în care vei învăța informatică cu adevărat.
  • Stancu: nimic?
  • Tatomir: o rezolvare foarte bună, bravo! Te-ai prins și că îți trebuie long long. Singurul lucru care se poate îmbunătăți este că toate if-urile se pot elimina folosind modulo, în afara ultimului. Vezi și soluția de mai jos.
  • Teodorescu: v-am spus lecția trecută că este necesară o soluție matematică. Soluțiile cu bucle vor depăși timpul, precum ai văzut. Atenție, nu vei putea fără matematică!

Tema - rezolvări

Rezolvări aici [1]

Lecție - continuare recapitulare

<html5media height="720" width="1280">https://www.algopedia.ro/video/2018-2019/2018-10-04-clasa-6-lectie-info-03-720p.mp4</html5media>

Recapitulare probleme de bază:

Algoritmul lui Euclid

Algoritmul lui Euclid pentru cmmdc.

#include <stdio.h>

int main() {
  int a, b, r;

  scanf( "%d%d", &a, &b );
  while ( b > 0 ) {
    r = a % b;
    a = b;
    b = r;
  }
  printf( "%d\n", a );

  return 0;
}

Ce complexitate are acest algoritm? Să vedem:

Vom urmări ce se întîmplă cu suma a + b după execuția a două bucle:

inițial: S0 = a + b
după iterația 1 în while: a devine b și b devine a % b
după iterația 2 în while: a devine a % b și b devine b % (a % b), deci suma lor va fi S1 = a % b + b % (a % b)

Vom demonstra că S123·S0, adică suma a + b se reduce cu 33%.

Presupunem că a > b, deoarece, în caz contrar, după prima iterație a buclei while relația va deveni adevărată și va rămîne adevărată pe tot parcursul algoritmului. Avem două cazuri posibile:

1. a < 2b (a este mic)

În acest caz:

a % b = a - b

De asemenea, putem împărți relația la 2 și obținem:

a/2 < b

Combinînd relațiile:

a % b < a - a/2

și deci sumele:

S0 = a + b > a + a/2 = 32·a
S1 = a % b + b % (a % b) < a % b + a % b = 2·(a % b) < a

Combinînd cele două relații obținem relația dorită:

S1 < 23·S0


2. a ≥ 2b (a este mare)

În acest caz:

a % b < b

și deci sumele:

S0 = a + b ≥ 2b + b = 3b
S1 = a % b + b % (a % b) < a % b + a % b = 2·(a % b) < 2b

Combinînd cele două relații obținem din nou relația dorită:

S1 < 23·S0


Deoarece suma a + b se împarte la 32 la fiecare două iterații ale buclei while, rezultă, conform celor discutate în lecțiile anterioare, că algoritmul lui Euclid are complexitate O(log(a+b)). În realitate se poate demonstra o scădere mai rapidă a acestei sume folosind numere Fibonacci.

Considerente practice: algoritmul lui Euclid va face cel mult 48 de împărțiri pe numere de tip int și cel mult 93 de de împărțiri pe numere de tip long long.

Atenție: circulă printre elevi un algoritm pe bază de scăderi repetate. Este un algoritm ineficient care are complexitate O(a + b). Nu-l folosiți. La olimpiadă veți pica teste cu TLE.

Calcul divizori

Calculul divizorilor unui număr. Putem avea nevoie doar să îi număram, sau chiar să îi calculăm pentru un calcul ulterior sau pentru afișare. Similar cu descompunerea în factori primi.

Varianta 1 - calcul

#include <stdio.h>

int main() {
  int n, p, div, nrdiv;

  scanf( "%d", &n );
  nrdiv = 1;
  div = 2;
  while ( div * div <= n ) {
    p = 0;
    while ( n % div == 0 ) {
      ++p;
      n = n / div;
    }
    nrdiv = nrdiv * (p + 1);
    ++div;
  }
  if ( n > 1 )
    nrdiv = nrdiv * 2;
  printf( "%d\n", nrdiv );

  return 0;
}

Ce complexitate are acest algoritm? Să observăm următoarele:

  • Bucla exterioară se va executa de cel mult ori
  • Bucla interioară nu poate crește numărul de calcule, ci doar să îl reducă
  • Cazul cel mai rău este cînd n este prim

Complexitatea va fi .

Atenție: algoritmul trivial în care condiția primei bucle este while ( div <= n ) (sau, similar, while ( div <= n/2 )) are complexitate O(n)! Dacă le veți folosi la concursuri veți pica teste cu TLE.

Varianta 2 - numărare

Această soluție poate fi folosită pentru afișarea sau lucrul cu divizorii numărului.

#include <stdio.h>

int main() {
  int n, div, nrdiv;

  scanf( "%d", &n );
  nrdiv = 2;
  div = 2;

  while ( div * div < n ) {
    if ( n % div == 0 )
      nrdiv = nrdiv + 2;
    ++div;
  }
  if ( div * div == n )
    ++nrdiv;

  printf( "%d\n", nrdiv );

  return 0;
}

Ce complexitate are acest algoritm? Bucla exterioară se va executa de ori, deci complexitatea va fi .

Atenție: algoritmul trivial în care condiția primei bucle este while ( div <= n ) (sau, similar, while ( div <= n/2 )) are complexitate O(n)! Dacă le veți folosi la concursuri veți pica teste cu TLE.

Comparație variante

Care din cele două variante de calcul al numărului de divizori este mai rapidă? Din punct de vedere al complexității ele sînt echivalente. Pe cazul cel mai rău, cînd n este prim, ele vor fi aproximativ la fel de rapide. Prima variantă este mai rapidă pe numere neprime, pe cazul mediu ea făcînd mult mai puține operații. Avantajul variantei doi este că ne poate calcula efectiv divizorii, în vreme ce prima variantă doar îi numără.

Temă

Tema 3 clasa a 6a

  • tir1 dată la olimpiada pe școală 2014 clasa a șasea la Tudor Vianu
  • suma dată la .campion 2006

Rezolvări aici [2]