Clasele 9-10 lecția 16 - 21 ian 2015

From Algopedia
Jump to: navigation, search

Discutarea temei; noțiuni de bash scripting

Problema SCV admitea două soluții:

  • una bazată pe programare dinamică;
  • una prin metoda greedy (mai eficientă, de altfel).

Sunt convins că mulți din voi le-ați găsit pe ambele și ați fi vrut să le testați. În același timp, nu puteați trimite două surse fără să primiți penalizarea pentru două surse trimise. Ce-i de făcut?

Soluția este să testați programele unul cu celălalt. Aceasta este o practică bună și în concurs, cu condiția ca generatorul și rezolvarea naivă să fie ușor de implementat. Generați multe teste aleatoare și verificați că programele produc aceeași ieșire. Puteți face aceasta într-o buclă din shell, de exemplu:

for i in `seq 1 10`; do echo ==== Testul $i; ./gen parametri_pentru_generator > scv.in; rm -f scv.out; ./metoda1; mv scv.out /tmp; ./metoda2; diff /tmp/scv.out scv.out; done

Aici, ./gen este un generator pe care tot voi îl scrieți. Poate fi rudimentar.

Dacă doriți să lăsați scriptul să ruleze până când găsește vreo diferență, încercați:

i=0; while true; i=$((i+1)); do echo ==== Testul $i; ./gen parametri_pentru_generator > scv.in; rm -f scv.out; ./metoda1; mv scv.out /tmp; ./metoda2; diff /tmp/scv.out scv.out; if [ $? -eq 0 ]; then break; fi; done

Toate aceste comenzi pot fi scrise și pe mai multe linii sau puse într-un fișier cu extensia .sh. Dacă nu vă amintiți toate detaliile (nici eu nu le țin minte), man bash conține toate răspunsurile.

Programare dinamică

Vom încheia capitolul despre programare dinamică, urmând notele din lecțiile trecute.

Numere mari

Lucrul cu numere mari devine necesar atunci când datele problemei nu mai încap pe 64 de biți (long long sau unsigned long long). Numărul maxim ce poate fi reprezentat pe 64 de biți fără semn este 264 - 1, deci aproximativ 1,8 ⨯ 1019. Dincolo de această limită, ne trebuie o reprezentare proprie.

Reprezentare

În general, problema cere să tipăriți un număr în baza 10. De aceea, reprezentarea noastră internă va fi tot în baza 10, respectiv:

  • numărul de cifre ale numărului
    • decizie de design: stocăm exact numărul de cifre semnificative sau permitem zerouri la stânga?
  • un vector cu cifrele numărului
    • elementul de pe poziția i stochează cifra corespunzătoare lui 10i

Există și alte reprezentări, în funcție de necesități:

  • Dacă spațiul este o problemă, putem reprezenta câte o cifră pe patru biți (două cifre pe octet).
  • Tot acolo putem ajunge stocând numerele în baza 100. Atunci fiecare cifră din vector va reprezenta două cifre în baza 10.
  • Putem stoca numerele în orice altă bază (până la 255), dar în momentul afișării vom avea nevoie de timp și memorie suplimentară pentru a face conversia la baza 10.

Operații de implementat (după caz)

  • inițializarea cu 0
  • inițializarea cu o singură cifră
  • inițializarea cu un număr de mai multe cifre
  • adunarea cu un int
  • adunarea a două numere mari
  • înmulțirea cu o constantă
  • înmulțirea a două numere mari
    • Aceasta merită o discuție detaliată. Algoritmul naiv face O(n2) operații. Algoritmul lui Karatsuba este un algoritm divide et impera cu formula de recurență T(n) = 3 T(n/2) + n. Prin eliminarea recurenței obținem complexitatea O(nlog2 3</sup).
    • Pentru n = 10.000, algoritmul naiv face 100.000.000 de operații, iar algoritmul Karatsuba numai 2.200.000!
    • Iată și un program de benchmark. Rulați-l cu time ./benchmark 1000 0 pentru algoritmul naiv, respectiv time ./benchmark 1000 1 pentru algoritmul lui Karatsuba.
  • împărțirea cu o constantă
  • împărțirea a două numere mari
  • compararea
  • extragerea radicalului

Detalii de implementare

Încercați să evitați operațiile scumpe. Oricând puteți, înlocuiți o operație modulo 10 cu o înmulțire, un if sau altceva. Încercați să evitați și condițiile, dacă puteți.

Numărul de zerouri de la începutul numărului vă poate crea probleme. Acestea pot apărea, de exemplu, în urma scăderilor. Asigurați-vă că subrutinele voastre gestionează corect zerourile. De exemplu, dacă subrutina de comparare începe prin a compara numărul de cifre, ea va da un răspuns greșit la compararea lui 00123 cu 2345.

Probleme

  • Implementați algoritmul lui Karatsuba.
  • Extindeți algoritmul lui Karatsuba la trihotomie (împărțirea numerelor în trei segmente egale).
    • Câte înmulțiri sunt necesare?
    • Care este complexitatea recurentă a algoritmului? Dar cea nerecurentă?
    • Este algoritmul mai rapid decât cel al lui Karatsuba?

Temă