C++ Bc. 45

Z GeoWikiCZ
Přejít na: navigace, hledání

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 \times3^j\times5^k, kde i,j,k \ge 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\times2, p\times3 a p\times5 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\times3=3\times2).

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ší ]