01_jednoduche_algoritmy

-  převedení zlomku na společného jmenovatele C = a. jm1 = b . jm2 

-  např. 5 a 10 = 10 (a=2, b = 1) 

6 a 4 = 12 (a = 2 , b = 3) 

-  Pomocí největšího společného dělitele 

NSN(a,b) = a . b / NSD(a,b) 

Rozklad na prvočísla (dále jen rozklad)

-  hrubá síla – dělení všemi čísly; vylepšení – dělení prvočísly 

-  patří k náročným řešením zvláště pro násobení velkých prvočísel (využití u kryptografie), 

smysl má pro čísla, jež jsou násobky menších čísel 

 
vstupem je číslo u 
v = 2 
dokud je u různé od jedné 
    pokud je u dělitelné bezezbytku v,  
            vlož v do seznamu dělitelů 
            u = u / v 
    jinak 
            zvyš v o jedna 
v seznamu jsou všichni dělitele (někteří mohou být i 
několikrát)

Rozklad na prvočísla algoritmus 

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

NSD – všechna čísla, která jsou společná oběma rozkladům 
NSN – 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 NSD 

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