Recent, a apărut o astfel de sarcină:
Având un număr pozitiv, trebuie să-i găsim pe toți divizii, cu excepția lui.
Problema este să scriem cât mai repede posibil algoritmul și bineînțeles
corectă.
Prima idee era să rezolve numerele mai mici, verificând divizibilitatea, dar complet
căutarea nu a dat limite largi de aplicare, deja pentru rezolvarea problemei, de exemplu, pentru
, Acest algoritm a funcționat foarte mult, după mai multe modificări
Am ajuns aici este un astfel de algoritm, limita superioară pentru complexitate în cel mai rău caz.
Algoritmul umple vectorul cu un număr de numere.
void find_divs (int n, vector
divs.push_back (1);
Există vreo modalitate de îmbunătățire a algoritmului? Sau există metode mai rapide pentru a rezolva această problemă?
Re: Gasirea tuturor divizoarelor unui numar
Există vreo modalitate de îmbunătățire a algoritmului?
Mai întâi trebuie să o rezolvi. Verificați ce obțineți pentru 12 și 36.
Sau există metode mai rapide pentru a rezolva această problemă?
Mai întâi, obțineți factorizarea numărului de intrare în factorii prime. Apoi treceți prin toate combinațiile de multiplicatori simpli.
Re: Gasirea tuturor divizoarelor unui numar
Mai întâi trebuie să o rezolvi. Verificați ce obțineți pentru 12 și 36.
Da, algoritmul nu funcționează corect). Cred că este corect:
void find_divs (int n, vector
divs.push_back (1);
Mai întâi, obțineți factorizarea numărului de intrare în factorii prime. Apoi treceți prin toate combinațiile de multiplicatori simpli.
Da, a existat o astfel de idee, ar fi nevoie de câteva iterații pentru a sorta combinații, cum, în acest caz, pentru a evalua complexitatea algoritmului? Există vreo formulă pentru calcularea numărului de factori prime ai unui număr. Sau cel puțin este necesar să se estimeze limita superioară, adică găsiți un număr care se descompune într-un număr maxim de factori prim.
Articole similare
Trimiteți-le prietenilor: