Împărţirea a două numere mari

[•rEbyTer]

Împărţirea a două numere mari

După cum am scris în titlu, am nevoie de aşa ceva la naţională? Algoritmul trebuie să fie destul de complicat... (l-am încercat pe foaie, a luat ceva timp)

[•devilkind]

din cate stiu eu impartirea a doua numere mari se face cu cautare binara, nush daca se poate simula pur si simplu.

[•wefgef]

Pai ce are daca o faci ca pe hartie? Iese O(N^2)* 10.

[•devilkind]

m-am gandit si eu akuma cum poti sa simulezi impartirea asta, si esti sigur ca o(n^2*10) ?? din ce am gandit eu tre sa fac 10 inmultiri pe numere mari ptr a afla fiecare cifra a rezultatului... insa nu reusesc sa imi dau seama exact cam la ce complexitate se ridica chestia asta.

Wefgef ai implementat ambele variante sa vezi care merge mai bine??

[•bogdan2412]

Poti sa faci adunari la fiecare pas in loc de inmultiri si atunci faci N*10 pe fiecare cifra in loc de N^2*10 pe fiecare cifra

[•wefgef]

Da, am implementat ambele variante. Cautare binara sucks 

[•Marius]

Eu nu as putea sa scriu impartirea a doua numere mari intr-un concurs. Pur si simplu nu tin minte. Cautare binara rulz in cazul asta.

[•wefgef]

Pai nu tre sa tii minte. Faci ca pe hartie.