C++ Bc. 45: Porovnání verzí
mBez shrnutí editace |
mBez shrnutí editace |
||
Řádek 8: | Řádek 8: | ||
Porovnání času pro vyhledání 1500-tého čísla algoritmem 1 a algoritmem 2. | Porovnání času pro vyhledání 1500-tého čísla algoritmem 1 a algoritmem 2. | ||
<pre> | |||
$ 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 | |||
</pre> | |||
[ [[C++ Bc. | Zpět]] | [[C++ Bc. 45 cpp | C++]] | [[C++ Bc. 46|Další]] ] | [ [[C++ Bc. | Zpět]] | [[C++ Bc. 45 cpp | C++]] | [[C++ Bc. 46|Další]] ] | ||
[[Kategorie:Programování]] | [[Kategorie:Programování]] | ||
[[Kategorie:C++]] | [[Kategorie:C++]] |
Verze z 8. 2. 2011, 14:36
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 p jsou jsou čísla p*2, p*3 a p*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ř. ).
Porovnání času 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