Clasa a VI-a lecția 22 - 28 feb 2019

Anunț

Ce reguli ale cercului nostru încalcă următorul program?

#include <fstream>

using namespace std;
const int nmax=1000005;
ifstream in("cmmp.in");
ofstream out("cmmp.out");

int cifre(long long n){
    int cnt=1;
    n/=10;
    while(n){
        n/=10;
        cnt++;
    }
    return cnt;
}

long long rasp[nmax];
int v[11];
long long k;

void fa(long long num){
    long long x=cifre(num),i,nr,j,num1=num;
    for(i=x; i>=1; i--){
        v[i]=num1%10;
        num1/=10;
    }
    for(i=1; i<=x; i++){
        nr=0;
        for(j=i; j<=x; j++){
            nr=nr*10+v[j];
            if(nr>nmax)
                break;
            if(rasp[nr]==-1)
                rasp[nr]=num;
        }
    }
}

int main()

{
    long long n,x,i;
    in>>n;
    for(i=1; i<=1000000; i++)
        rasp[i]=-1;
    for(k=1; k<=170000; k++)
        fa((long long)(k*k));
    for(i=1; i<=n; i++){
        in>>x;
        out<<rasp[x]<<' ';
    }
    return 0;

}

• for cu un break în el, să ieșim cînd ne convine.
• Variabile inițializate la declarare.
• Programare aproximativă - vectori declarați cu cinci în plus (în fapt codul este atît de neglijent încît declară vectorul de zece ori mai mare, plus încă 5, să fie).
• Citiri C++.
• Amestec groaznic de funcții, cu declarații de variabile.
• Cod negîndit de sus pînă jos, cu funcții inutile care fac programul mai ineficient. De exemplu, programul parcurge cifrele numărului de două ori, prima oară pentru numărarea lor, a doua oară pentru depunere în vector, ceea ce duce la dublarea numărului de împărțiri.
• Lene de gîndire - cifrele numărului sînt invers în vector, deși am vorbit despre numere mari.
• Aberații de genul (long long)(k*k) atunci cînd k este deja long long și cînd oricum, și dacă nu era, conversia nu ar fi funcționat deoarece înmulțirea se face înaintea conversiei.
• În general un cod oribil, neîngrijit, doar pentru a lua suta la varena.

Spiritul cercului este important

Programul de mai sus nu a fost scris pentru a fi văzut de mine. Dar a fost scris de unul dintre noi. Pot să accept unele poluări de cod, în graba concursului, cum ar fi citire/scriere în C++, cod neîngrijit, poate chiar și declarare de vectori cu 5 elemente în plus. Nu pot însă să accept, nici măcar în graba concursului, să încălcați principiile de bază ale programării structurate, folosind instrucțiunea break. Codul de mai sus ne spune că acel copil se simte, în fapt, mai confortabil scriind așa. Deci așa codează în mod uzual. Cineva care își insușește cerințele cercului nu are cum să scrie asemenea cod, nici măcar în grabă.

Dacă așa doriți să codați, nu aveți nevoie de IQ Academy. Vă puteți duce la toți dopatorii șefi, care dau cu for-ul și cărora puțin le pasă despre claritatea codului lor și implicit a algoritmului lor. Deci vă voi invita să plecați.

Tema - rezolvări

• Avertismente lui:
  • Cojocariu, care a trimis o rezolvare forță brută la numere24, o rezolvare de zero puncte la problema turnuri, la care se puteau lua lejer 40p, soluția din concurs la gazon, neterminată și nici o soluție la peridia. Cojocariu, nu sînt deloc mulțumit.
  • Iordache, care a trimis o rezolvare doar la numere24 și aceea de 12p. Iordache, temele nu sînt opționale.
  • Cadîr, care nu a trimis nimic la peridia, iar la gazon a trimis aceeași rezolvare ca și în concurs, de 26p, nevrînd să gîndească extra. Cadîr, mobilizează-te te rog, dacă vrei să ramîi cu noi!

Problema turnuri

Comentarii generale

1. Felicitări celor ce au reușit o soluție de excepție: Mocanu, Nicola, Fares, Tatomir.
2. Mențiuni speciale: Hossu, care a combinat drăguț căutările celor două puncte într-o singură parcurgere. Ilie, care a reușit o factorizare foarte drăguță la cerința doi, folosind o matrice de două linii.
3. Faptul că problema are două cerințe nu înseamnă că trebuie să scrieți două programe! Citirea este destul de lungă, de ce să o scrieți de două ori? De asemenea, dacă avem de căutat un șir de cuburi care începe fie cu galben fie cu albastru nu înseamnă că repetăm codul pentru cele două cazuri. Cine: Badea, Benescu, Chivu, Grecu, Mocanu, Mușat, Petcu, Rebengiuc, Ștefănescu, Togan, Asgari, Dobre, Ipate, Tatomir.
4. Unii din voi folosiți o sortare aiurită, pe care am mai văzut-o la olimpici. Este ineficientă. Nu o folosiți doar pentru că este mai simplu de memorat. Vreți simplu, nu ați găsit un loc bun la IQ Academy. Cine: Benescu, Burac, Petcu.
5. Unii dintre voi mă ajută cu comentarii. Vă mulțumesc! Cine: Grecu, Petcu, Rughiniș, Stoian, Voicu, Marcu, Nicu, Tatomir.
6. Unii dintre voi ați greșit la punctul unu. Care este un punct lejer de lucru cu secvențe, de clasa a cincea, care nici nu necesită vectori. Grav, trebuie să vă pună pe gînduri!
7. Unii dintre voi nu v-ați prins că înălțimile turnurilor pot depăși întregul. Atenție, este o eroare ușoară care vă poate pierde multe puncte (aici pierdeați doar 6).
8. Mulți dintre voi fie ați sortat cuburile, fie ați făcut ceva similar cu sortarea. Ea nu era necesară, puteați folosi un vector de frecvență.
9. Corectați avertismentele de variabile neinițializate! Ele sînt erori, de cele mai multe ori. Le văd foarte des în programele voastre, de multe ori sînt motive pentru care pierdeți puncte.
10. Avertismente celor ce nu au trimis nici o soluție la această problemă: Iordache.

Comentarii individuale

Grupa de dimineață

• Badea (100p-95p): Program rezonabil, idee bună, implementare cu mult cod care se repetă. Ai trimis două programe de 100p. Primul cu un sort aiurit, al doilea cu select sort. Fără sortări aiurite la temă, te rog! Vezi comentariul 4. Declari un vector ag[] pe care nu îl folosești. Duplici mult cod la citire, la sortare și la calculul turnului cel mai lung posibil, comentariul 3.
• Benescu (94p): Program rezonabil la prima cerință, dar foarte încîlcit la a doua, probabil că de aceea nu acoperi toate cazurile. M-ar fi ajutat mult un comentariu cu metoda folosită, bănuiesc că încerci să adaugi cuburi, pe rînd, căutînd mereu cel mai mare cub mai mic ca cel curent si de culoare diferită de cel curent, caz în care algoritmul este corect. Duplici cod la citire, comentariul 3.
• Burac (100p): Algoritm bun, cod foarte încîlcit cu repetiții și stegulețe. Punctul unu puțin încîlcit la condiția de așezare. Ai nevoie de doar două teste, ca cubul curent să fie mai mic decît cel anterior și culorile să difere. Tu faci o codare a culorilor care nu pare a folosi la nimic. La punctul doi faci o sortare aiurită, vezi comentariul 4. Nu folosi sortări aiurite, te rog. Dacă scrii cod încîlcit scrie te rog un comentariu cu metoda folosită, altfel nu pot decît să o bănuiesc. Văd stegulețe, nu sînt necesare.
• Calotă (80p-43p) : Program bine scris, ordonat, algoritmul la prima parte e bun, la partea a doua e greșit. Ar fi fost bine să îmi pui un comentariu cu metoda. De ce declari cîte o variabilă pe linie?
• Chivu (100p): Primul punct este rezonabil și ordonat. Comentariul 3, repeți cod la citire. Nu declara neglijent variabilele, tc (numărul de turnuri) nu are de ce să fie long long. Punctul doi este foarte bine, bravo.
• Cojocariu (10p): Peridia nimic, gazon rezolvarea din concurs. Temă făcută la minima rezistență. Te joci cu focul. La turnuri, codul tău nu funcționează nici pe exemplul din enunț. Codul conține printf-uri de depanare. Primul punct era banal, dar nu l-ai depanat. Nu te-ai prins că înălțimea poate depăși întregul. Logica primului punct e greșită, nu se poate intra niciodată pe ultimul else. Punctul doi pare rezonabil, dar nu l-ai depanat deloc. Cojocariu, ajung la capătul răbdării. Ești pe drumul sigur de a pierde calificarea la IQ Academy.
• Grecu (94p): Mulțumesc pentru comentarii! Program corect, care ar fi putut lua 100p. Motivul pentru care ratezi cîteva teste este pentru că nu te-ai prins că înălțimile turnurilor pot depăși întregul. Atenție la tipurile de întregi! Îți va trebui și la clasa a cincea! Ai mult cod repetat, la citire, sortare și căutare soluție punctul 2, vezi comentariul 3.
• Hossu (0p-83p): Un program bun! Cod destul de ordonat, fără repetiții grave (deși ai spre final două ramuri de if cu conținut identic). Însă ai combinat bine codul astfel încît să nu repeți citirea, iar căutarea funcționează pentru ambele puncte, interesant. Denumești maxv o variabilă care e de fapt un minim, nu face așa ceva te rog, e foarte greu de citit. Unul din motivele pentru care ratezi teste este că înălțimea unui turn poate depăși întregul. Atenție mai mare te rog, e o greșeală banală ce te poate costa mult la olimpiadă!
• Iordache (0p): nimic? Ce s-a întîmplat? Nu ai făcut trei dintre problemele de la temă, iar la prima n-ai făcut mare lucru.
• Mocanu (100p): O soluție foarte bună, bravo! Ai folosit un vector de frecvență, bravo din nou. Trebuie însă să mai lucrezi la încîlceală și la scurtarea codului, vezi soluția de mai jos. Repeți cod, vezi comentariul 3.
• Mușat (22p-41p): Un program bun ca idee, dar pe care nu l-ai depanat pînă la capăt și cu multe repetiții de cod, vezi comentariul 3. Prima parte este bine, o ratezi din cauză că înălțimea turnului poate depăși întregul. Atenție la erori de gîgă! A doua parte este încîlcită și cu același cod repetat de două ori. Dacă puneai măcar niște comentarii aș fi încercat să ți-l depanez. Nu uita că duplicarea de cod te duce la pierdere masivă de puncte.
• Nicola (44p-95p): Idee foarte bună la ambele puncte. Ai folosit vectori de frecvență, simplu și eficient. Ai grijă, nu te complica degeaba! Codul de căutare în vectorul de frecvență poate fi scris mult mai direct și mai simplu, vezi rezolvarea de mai jos.
• Petcu (100p): Mulțumesc pentru comentarii! Rezolvare foarte bună la primul punct, ordonată și clară. Dar nu aveai nevoie de vectori, nu-i așa? Repeți citirea, vezi comentariul 3. La punctul doi ideea este bună, sortare și apoi verificare cîte grupe de culoare avem (deși nu ai scris asta clar în comentarii). Dar sortarea este una aiurită, vezi comentariul 4. Foarte ineficientă, este doar ușor de reținut, te rog nu o folosi. Ar fi bine să-i spui și lui Victor să nu o mai predea.
• Rebengiuc (92p): Un program bun, ordonat, bravo! Ambele puncte rezolvate frumos, la punctul doi ai folosit vectori de frecvență, bravo! Nu deschide fișierele înainte să declari variabilele și nu inițializa variabile la declarare (fișierele). Repeți citirea, vezi comentariul 3. La punctul unu scrii cola + colb == BLUE + YELLOW cînd puteai scrie mai simplu cola != colb. Nu complica codul de dragul unei formule inutile :-) La punctul doi ideea de vectori de frecvență este bună, dar era suficient și mai simplu facă foloseai doar unul. Le fel, formulele sînt nenecesare, complică citirea codului. Cred că la primul punct ratezi teste pentru că nu testezi hmax pe ambele ramuri. Mai exact, un turn de un singur cub foarte mare (latura 500k) poate fi mai înalt decît un turn cu mai multe turnuri unul peste altul.
• Rughiniș (10p-89p): Mulțumesc pentru comentarii! Programul tău ar fi luat 100p dacă te prindeai că înălțimile turnurilor pot depăși întregul. Repeți cod la citire, vezi comentariul 3. Punctul unu e rezolvat OK, dar cu complicații. Nici nu aveai nevoie de vectori. Punctul doi este corect, bravo! Idee bună, implementare fără prea mari repetiții, în afara sortării.
• Stoian (72p): Mulțumesc pentru comentarii! La punctul unu ratezi testele 14 și 15 deoarece nu te-ai prins că înălțimile turnurilor pot depăși întregul. Greșeală banală care te-a costat multe puncte. Tot la punctul unu, la final de șir testezi înălțimea maximă, în afara buclei. Dar în loc să testezi val, tu testezi a. Atenție! Ai ratat multe teste la punctul 2 pentru că ai ignorat un avertisment de compilare, greșeală banală care te-a costat multe puncte: cînd sortezi, în interiorul buclei după i, inițializezi variabilele max și poz, dar nu și cc. Vei lua toate testele de punctul doi cu această modificare minoră. Atenție mai mare te rog! Variabila max este de fapt un minim, nu induce în eroare cititorul, este foarte grav. Cu modificările menționate mai sus vei lua 100p.
• Ștefănescu (12p-30p): Punctul unu este rezolvat corect, codul este clar și ordonat. Dar ai uitat două lucruri minore: nu testezi ultimul turn pentru înălțime maximă, la ieșirea din buclă. Și doi, cînd pornești un nou turn setezi h = 0;. Corect era h = lat;. Atenție mare la lucruri mărunte, pierzi puncte prea ușor! Nu declara variabile simple (fișiere) în afara lui main dacă nu ai nevoie. Ai lăsat printf-uri de depanare în cod, foarte periculos, poți lua TLE, ca acum. Repeți cod la citire, vezi comentariul 3. Ideea punctului 2 este bună, sortare și căutare interclasată. Dar implementarea e defectuoasă, intri în buclă infinită la interclasare. Am încercat să depanezi, dar neavînd comentarii îmi ia prea mult să înțeleg ce ai vrut să faci. Te rog să depanezi tu, folosind testele descărcabile.
• Togan: (94p): Ideea este foarte bună. Ai fi luat 100p cu ea dacă te prindeai că înălțimea turnurilor poate depăși întregul, greșeală de gîgă și de neatenție. Problema e alta: Togan, codul tău este foarte, dar foarte urît, pînă la necitibil! Scrii fără să gîndești! Încă ai probleme la nivel de clasa a cincea, să pui if-urile exclusive unul pe else-ul celuilalt! Vectorii sînt vraiște, ai un vector de frecvență declarat ca long long cînd putea fi char, nebunie! La primul punct folosești vectori cînd nu sînt necesari. La al doilea punct folosești doi vectori de frecvență cînd era deajuns unul. Repeți cod la citire, vezi comentariul 3.
• Voicu (40p-95p): Mulțumesc pentru comentarii! Idee bună, cod ordonat, bravo! Repeți citirea, ai multe repetiții și la punctul 2, vezi comentariul 3. Folosești sortare, nu este rău, dar se poate și fără.

Grupa de după-amiază

• Asgari (100p): Armin, tu scrii în comentarii: "Daca doriti refac codul cu sortare prin selectie, dar mi s-a parut mai interesant asa :)". Să vedem: deși folosești o funcție de bibliotecă pentru sortare, lucru pe care știi că îl interzic, măcar cîștigi ceva? Din borderoul de evaluare rezultă că codul tău este mai lung, mai lent și folosește mai multă memorie decît un cod care nu apelează funcția de sortare. Zici că e mai interesant? În ce fel? În faptul că este mai prost din toate punctele de vedere? Vrei ceva interesant? Scrie o soluție care nu folosește deloc sortare! Dar pentru asta trebuie să gîndești, nu poți să fii un simplu utilizator. Greu, nu? Acestea fiind zise, comentarii la cod:
  • Ai folosit struct în mod incorect, cum era de așteptat: o variabilă int și una char vor ocupa, în fapt, cît două int, dacă le pui în struct. Este exact motivul pentru care nu vă recomand să folosiți struct.
  • Membrii struct-ului sînt denumiți total necorespunzător, x și y, ei fiind de fapt o latură și o culoare.
  • li de tip List *, nu este deloc o listă, ci un vector. Cod care induce în eroare.
  • Funcția de comparație se putea scrie la fel de bine cu ceea ce cunoaștem și ceva mai clar: return (a < b) ? -1 : (a > b);
  • Repeți citirea. Este unul din motivele pentru care codul iese mai lung. Vezi comentariul 3.
  • La prima cerință ai un while care este de fapt un for pentru i de la 1 la n-1.
  • Scrii ++cnt, suma = b; cînd v-am interzis virgula, vorbind în mod explicit despre asta. Lene tipică de olimpic.
  • Dacă vrei să optimizezi acel cod, dacă gîndești în loc să utilizezi, în loc să scrii:

        if( b < a && color != next_color )
          suma += b;
        else
          ++cnt, suma = b;

Poți să observi că una din ramuri poate fi vidă dacă factorizăm adunarea la suma:

        if( b > a || color == next_color ) {
          ++cnt;
          suma = 0;
        }
        suma += b;

Armin: algoritmul tău este bun (dar nu cel mai bun), iar implementarea este rezonabilă. Dar insiști să faci pe șmecherul. În loc să ne impresionezi cu gîndirea și cu un algoritm și o implementare perfectă, folosești lucruri avansate pe care nu le cunoști bine, în vreme ce codul tău arată că nu știi tehnicile de bază și că nu gîndești bine algoritmul.

• Cadîr (72p-68p): Ai rezolvat punctul greu, dar nu pe cel ușor! Simpatic :-) Programul este ordonat și clar, bun. Nu repeți citirea, în fapt nu ai repetiții, foarte bine! Folosești corect sortarea prin selecție, bine, dar se poate și fără sortare. Ratezi teste din două motive:
  • Ai declarat h ca long long, dar nu și max. Scăpare din neatenție, foarte gravă!
  • Cînd pornești un nou cub, cînd nu poți așeza cubul pe cel din-nainte, scrii h = 0;. Corect era h = hcub[i];, deoarece avem un turn cu acea înălțime, nu de înălțime zero.
• Dobre (72p-84p): O soluție bună, destul de ordonată și disciplinată. Folosești corect sortarea. Ai o mică repetiție la citire, vezi comentariul 3. Ratezi cîteva teste pentru că nu ai observat că înălțimea turnului poate depăși întregul. O neatenție gravă, la olimpiadă poți să pierzi enorm de multe puncte din cauza asta!
• Fares (70p-80p): O soluție bună, solidă, cu cod rezonabil. Te-ai complicat în cîteva locuri. Cea mai mare complicație este faptul că, deși ai avut ideea corectă la punctul doi, vectori de frecvență, ai folosit doi, în loc de unul, iar ei sînt de tip întreg, cînd puteau să fie tip caracter. În partea a doua ai scris mult cod aproape identic. Tu voiai să găsești cel mai lung lanț de cuburi ce alternează ca culoare și ai scris cod aproape identic pentru două cazuri, cînd lanțul începe cu galben sau cu albastru.
• Ilie (100p): Un program ordonat și clar, care nu repetă cod. La punctul doi ai factorizat codul foarte drăguț, evitînd repetiția codului. Din păcate algoritmul nu este optim: în locul căutării cuburilor de la punctul doi puteai folosi un vector de frecvență, după laturile cubului.
• Ipate (94p-95p): Un program scurt și clar, în care metoda folosită se înțelege foarte bine. Cea mai mare obiecție este la punctul 2, unde algoritmul nu este optim: în locul sortării puteai folosi un vector de frecvență. În rest mai ai mici imperfecțiuni:
  • Dat fiind că nu te interesează ca culorile să fie codificate cu 1 și 2 ci doar să fie diferite între ele puteai, la punctul doi, la citire, să scrii pur și simplu h[i][1] = fgetc( fin );
  • La punctul doi la final calculezi un inalt care este inutil, nu e folosit nicăieri
  • Ai o mică repetiție de citire, între cele două puncte, vezi comentariul 3
• Marcu (72p): Mulțumesc pentru comentarii! O soluție scurtă, clară, ordonată, care se poate înțelege foarte repede. Ai rezolvat punctul 2, cel greu, dar nu punctul unu, simpatic! :-) Obiecția minoră este la punctul unu, unde ai uitat lucruri mărunte: atunci cînd nu poți așeza cubul pe masă trebuie să resetezi h: h=l[i];. Iar la finalul secvenței de cuburi trebuie să mai testezi o dată înălțimea, să nu fie maximă. Iar înălțimea, precum și maximul, pot depăși întregul, deci trebuie declarate long long. Mărunțișurile acestea ți-au furat multe puncte, trebuie neapărat să fii mai atentă! Cu aceste trei modificări vei lua 100p. Însă obiecția majoră este la punctul 2, unde algoritmul nu este optim: în locul sortării puteai folosi un vector de frecvență. O altă mică imperfecțiune, la punctul doi scrii if(l[i]<l[i-1] && c[i]!=c[i-1])//daca se poate plasa cubul k pe k-1, dar deoarece cuburile sînt sortate prima condiție este inutilă, este mereu adevărată.
• Nicu (p): Mulțumesc pentru comentarii! O soluție scurtă, clară, ordonată și ușor de înțeles. La punctul doi ai folosit sortarea prin selecție foarte corect. Se poate, însă, și fără, folosind un vector de frecvență. Ca mici obiecții de eleganță, la punctul unu, while-ul este de fapt un for. La fel și la punctul doi. Un program bun, bravo!
• Stancu (40p-38p): Ai rezolvat punctul unu foarte corect și ordonat. Este un program ușor de citit. Ai luat tot punctajul pentru acest punct. Inclusiv te-ai prins, cum ai scris și tu în comentariu, că înălțimea unui turn poate depăși întregul. Păcat că nu ai încercat mai serios să rezolvi și punctul 2
• Tatomir (100p): Mulțumesc pentru comentarii! O rezolvare scurtă, clară, concisă, ușor de citit și cu algoritm optim, bravo! Mici neeleganțe ce ar fi bine să le corectezi:
  • Repeți codul de citire, care este destul de semnificativ. Vezi comentariul 3.
  • Declari vectorul de frecvență de întregi, cînd putea fi de caractere, o risipă mare cînd e vorba de 500000 de elemente.
  • Refolosești maxx la punctul doi, ceea ce nu e bine deoarece el este de tip long long, iar pentru punctul doi e suficient un întreg.
  • Ai complicat codul codînd culorile ca -1 și 1. Puteai să le stochezi ca atare în vector, apoi căutai elemente diferite de ultima culoare, pe care o actualizai la fiecare cub adăugat la șir.
• Teodorescu (86p-90p): Program destul de clar și ușor de citit. Nu repeți cod, bun. Ar fi fost bun un comentariu în legătură cu metoda folosită la punctul doi. La punctul unu folosești degeaba un vector extra, cel de înălțimi. Nu aveai nevoie de el. La punctul doi ai rezolvat cu o metodă pătratică, nu este optim, vezi te rog soluția de mai jos, cu un vector de frecvență.

Problema peridia

Comentarii generale

1. Felicitări celor ce au reușit o rezolvare cu rotații, cu cod nerepetitiv, independent de direcție: Rebengiuc, Fares, Ilie, Marcu, Nicu.
2. Cei ce au încercat rotații, dar nu au reușit o implementare nerepetitivă, totuși, felicitări pentru încercare: Badea, Burac.
3. Mulți dintre voi au declarat un vector de un milion de elemente! Nu știu dacă v-a confuzat faptul că matricea avea un milion de elemente, sau pur și simplu ați greșit un zero, dar vectorul avea, din enunțul problemei, fie 100 000 de elemente dacă era un vector de frecvență, fie 10000 de elemente dacă țineați minte chiar elementele nenule din matrice. Este o eroare foarte gravă, din cauza căreia veți lua zero la o astfel de problemă la olimpiadă. A folosi de zece ori mai multă memorie decît este cazul este de neacceptat la IQ Academy!
4. În continuare, mulți din cei ce reușiți să treceți toate testele în concurs trimiteți aceeași sursă și la temă, în loc să continuați să gîndiți la ea, sau să căutați un algoritm sau un program mai bun. Este și cazul la peridia, unde cei care ați luat 100p în concurs ați trimis un program fie fără rotații, fie cu repetiții, fie cu conversii urîte de la litera direcției la codificarea ei. Foarte rău.

Rezolvări aici [1]

Lecție

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

Calculul multiplicității unui număr prim în n!

Matematicianul Adrien-Marie_Legendre a descoperit că multiplicitatea (exponentul) unui număr prim p care apare în descompunerea în factori primi a lui n! poate fi exprimată exact ca:

$Exp(p,n!)=\left\lfloor {\frac {n}{p}}\right\rfloor +\left\lfloor {\frac {n}{p^{2}}}\right\rfloor +\left\lfloor {\frac {n}{p^{3}}}\right\rfloor +\cdots =\sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor .$

Acest fapt se bazează pe numărarea factorilor p ai întregilor de la 1 la n. Numărul multiplilor lui p în numerele de la 1 la n este $\textstyle \left\lfloor {\frac {n}{p}}\right\rfloor$; dar această formulă numără numerele cu doi factori p o singură dată. De aceea trebuie să mai numărăm încă $\textstyle \left\lfloor {\frac {n}{p^{2}}}\right\rfloor$ factori ai lui p. În mod similar pentru trei, patru, cinci factori, pînă la infinit. Însă suma este finită deoarece p ⁱ este mai mic sau egal cu n într-un număr finit de valori ale lui i, drept care funcția parte întreagă va fi zero pentru toate celelalte valori.

Cînd scriem programul pentru calculul exponentului ne vom opri la acel i pentru care pⁱ > n.

Calculul multiplicității unui număr prim la o putere în n!

Este simplu de demonstrat că dacă avem un număr prim p la o putere k atunci multiplicitatea lui p^k în n! este

$Exp(p^{k},n!)={\frac {Exp(p,n!)}{k}}$

Calculul multiplicității unui număr oarecare în n!

Este simplu să arătăm că dacă avem un număr a a cărui descompunere în factori primi este

a = p₁^k₁ • p₂^k₂ • … • p_m^k_m

atunci multiplicitatea (exponentul) lui a în n! este

$Exp(a,n!)=min(Exp(p_{1}^{k_{1}},n!),Exp(p_{2}^{k_{2}},n!),\ldots ,Exp(p_{m}^{k_{m}},n!))$

sau

$Exp(a,n!)=min({\frac {Exp(p_{1},n!)}{k_{1}}},{\frac {Exp(p_{2},n!)}{k_{2}}},\ldots ,{\frac {Exp(p_{m},n!)}{k_{m}}})$

Temă

Tema 22 clasa a 6^a

• factk .campion 2004
• fact ONI 2006 clasa a 9^a
• melci ONI 2008 clasa a 6^a
• faleza ONI 2017 clasa a 6^a

Atenție! La această temă se vor adăuga problemele de la concursul ce va urma duminică.

Rezolvări aici: [2]