DIOFANTOVA LINEÁRNÍ ROVNICE

PROBLÉM
Vyřešit Diofantovu lineární rovnici znamená najít podmnožinu množiny přirozených čísel {A.1,...,A.N}, jejíž součet je roven T.

ALGORITMUS
Algoritmus DIOPHANT najde řešení Diofantovy lineární rovnice téměř vždy pro N<=500 a A.I<=2*10**9

IMPLEMENTACE
Jednotka: vnitřní podprogram
 
Globální proměnné: pole A.1,...,A.N přirozených čísel
 
Parametry: přirozená čísla N a T
 
Výsledek: zobrazí řešení Diofantovy lineární rovnice, tedy podmnožinu množiny A., jejíž součet je roven T. Po nalezení řešení je výpočet okamžitě ukončen příkazem exit
 
Vazby: vnitřní procedura QUICKSORT
 

DIOPHANT: procedure expose A.
parse arg N, T
call QUICKSORT N
Ls.1 = A.1
do I = 2 to N
  Im1 = I - 1; Ls.I = A.I + Ls.Im1
end
if A.1 <= T & T <= Ls.N then do
  S = 1; Stack.1 = N T
  do while S > 0
    parse var Stack.S R T V; S = S - 1
    do K = 1 while Ls.K < T; end
    if Ls.K = T then call EXIST V, K, 1
    do while A.R > T; R = R - 1; end
    if A.R = T then call EXIST V, R, R
    do L = K to R while A.1 <= T - A.L
      D = V A.L; S = S + 1
      Stack.S = (L - 1) (T - A.L) D
    end
  end
end
say "Řešení neexistuje"
exit
 
EXIST: procedure expose A.
parse arg V, B, E
do J = B to E by -1; V = V A.J; end
say "Solution:" V
exit

 

POROVNÁNÍ
Pro N = 100; T = 25557 a pole A. vytvořené příkazy:

Seed = RANDOM(1, 1, 481989)
do J = 1 to N
  A.J = RANDOM(1, 1000)
end

jsem porovnal algoritmy pro řešení problému součtu podmnožin a můj algoritmus DIOPHANT pro řešení Diofantovy rovnice.

Poznámky:
Provádění EXACT_SUBSET_SUM jsem násilně ukončil po půl hodině běhu. Pro běh APPROX_SUBSET_SUM jsem zvolil hodnotu Epsilon = 0.5

 

Součet podmnožin - porovnání algoritmů
Algoritmus Suma prvků Doba výpočtu
GS 25554      0.05 
DPS 25557   240.24 
APPROX_SUBSET_SUM 25436    12.31 
DIOPHANT 25557      0.82 

 

SOUVISLOSTI

Literatura
Zábrodský V. Má smysl řešit Diofantovu lineární rovnici?
Zábrodský V. Problém dvou loupežníků
BAJT, říjen 1993 (36), s. 134-136


Obálka Obsah Index Hlavní stránka

změněno 8. srpna 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.