C++ Bc. 45

Z GeoWikiCZ

Hammingova čísla jsou čísla, která jsou dělitelná pouze prvočísly 2, 3 a 5, jinak řečeno je lze zapsat ve tvaru , kde 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 jsou jsou čísla , a 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ř. ).

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