C++ Bc. 45: Porovnání verzí
mBez shrnutí editace |
mBez shrnutí editace |
||
(Není zobrazena jedna mezilehlá verze od stejného uživatele.) | |||
Řádek 5: | Řádek 5: | ||
'''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 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 | '''Algoritmus 2:''' Z definice plyne, že pro každé Hammingovo číslo <math>p</math> jsou jsou čísla <math>p\times2</math>, <math>p\times3</math> a <math>p\times5</math> 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ř. <math>6=2\times3=3\times2</math>). | ||
Porovnání | Porovnání časů pro vyhledání 1500-tého čísla algoritmem 1 a algoritmem 2. | ||
<pre> | <pre> |
Aktuální verze z 8. 2. 2011, 20:12
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