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

Verze z 8. 2. 2011, 14:32

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}\times 3^{j}\times 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=2\times 3=3\times 2$ ).

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

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

@@ Řádek 1: / Řádek 1: @@
-[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, ...
+[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 \times3^j\times5^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.
@@ Řá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 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).
+'''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ř. <math>6=2\times3=3\times2</math>).
-Porovnejte čas 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.
 [ [[C++ Bc. | Zpět]] | [[C++ Bc. 45 cpp | C++]] | [[C++ Bc. 46|Další]] ]
 [[Kategorie:Programování]]
 [[Kategorie:C++]]