C++ Bc. 45

Hammingova čísla jsou čísla, která jsou dělitelná pouze prvočísly 2, 3 a 5, jinak řečeno je lze zapsat ve tvaru $2^{i}\times 3^{j}\times 5^{k}$, kde $i,j,k\geq 0.$ Hammingova čísla tvoří posloupnost 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, ...

Napište program, který vypočte n-té Hammingovo číslo, pro n=150.

Algoritmus 1: Procházejte postupně přirozená čísla od 1 a testujte, zda jsou Hammingovými čísly tak dlouho, až najdete požadavané n-té číslo.

Algoritmus 2: Z definice plyne, že pro každé Hammingovo číslo $p$ jsou jsou čísla $p\times 2$, $p\times 3$ a $p\times 5$ také Hammingovými čísly. Vytvoříme pole h o n složkách a na začátek vložíme hodnotu 1 (první Hammingovo číslo). Pro dvou-, tří- a pětinásobky definujeme indexy i2, i3 a i5, které inicializujeme na hodnotu 0 (index prvního Hammingova čísla). Minimum z hodnot h[i2]*2, h[i3]*3 a h[i5]*5 je dalším Hammingovým číslem, které přidáme do pole h. Index i2 nebo i3 nebo i5, který vedl na výpočet dalšího Hammingova čísla zvýšíme o 1 (to může obecně platit pro více než jeden index, protože např. $6=2\times 3=3\times 2$).

Porovnání časů pro vyhledání 1500-tého čísla algoritmem 1 a algoritmem 2.

$ time ./hamming1
1500-te Hammingovo cislo je 859963392

real	0m29.439s
user	0m29.370s
sys	0m0.044s

$ time ./hamming2
1500-te Hammingovo cislo je 859963392

real	0m0.002s
user	0m0.004s
sys	0m0.000s

[ Zpět | C++ | Další ]