01_jednoduche_algoritmy

Využití rozkladu na pročísla pro výpočet NSD a NSN 

-  rozložená čísla lze použít ke stanovení NSD a NSN 

NSD – použije všechna čísla, která jsou společná oběma rozkladům 
NSN – použije všechna čísla, která jsou v rozkladech (společná pouze jednou) 

-  5 a 10   mají rozklady 5 a 2;5 ; NSD je tedy  5; NSN 2.5= 10 

6 a 4     mají rozklady 2;3 a 2;2; NSD je tedy 2; NSN 2 . 2 . 3 = 12 

 
algoritmus NSN 
vstupem jsou dva seznamy u a v seřazené podle velikosti 
nsn = 1 
nastav se na počátek seznamů 
opakuj dokud jsou v obou seznamech čísla 
      pokud jsou čísla v obou seznamech stejná 
             nsn = nsn * číslo v seznamu 
             posuň se v obou seznamech na další číslo 
      jinak 
             nsn = nsn * číslo ze seznamu s menší hodnotou 
             posuň se v seznamu s menší hodnotou na další číslo 
             se seznamem, ve kterém zbyly čísla opakuj 
       nsn = nsn * číslo ze seznamu 
       posuň se v seznamu na další pozici 
v nsn je výsledek 

Příklad řešení pro čísla 630 a 2772 

Euklidův algoritmus - NSD 

r 

u 

v 

2772 

630 

252 

630 

252 

126 

252 

126 

0 

126 

0 

nejmenší společný násobek = číslo . číslo / NSD = 2772 . 630 / 126 = 13860 

co 

číslo 

Poznámka 

Rozklad 

630 

2 

3 

3 

5 

7 

Rozklad 

2772 

2 

2 

3 

3 

7  11