C++ Bc. 45: Porovnání verzí

Verze z 8. 2. 2011, 14:29

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}3^{j}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*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ř. 6=2x3=3x2).

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

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

@@ Řádek 1: / Řádek 1: @@
-[ [[C++ Bc. | Zpět]] | [[C++ Bc. 44 cpp | C++]] | [[C++ Bc. 46|Další]] ]
+[http://en.wikipedia.org/wiki/Regular_number '''Hammingova čísla'''] jsou čísla, která jsou dělitelná pouze prvočísly 2, 3 a 5, jinak řečeno je lze zapsat ve tvaru <math>2^i 3^j 5^k</math>, kde  <math>i,j,k \ge 0.</math>  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ř. 6=2x3=3x2).
+Porovnejte čas pro vyhledání 1500-tého čísla algoritmem 1 a algoritmem 2.
+[ [[C++ Bc. | Zpět]] | [[C++ Bc. 45 cpp | C++]] | [[C++ Bc. 46|Další]] ]
 [[Kategorie:Programování]]
 [[Kategorie:C++]]