„Programozás/Algoritmusok” változatai közötti eltérés

Táblázat kitölrésének logikája, plusz újabb javás kód a 2008-as diából
(ki++ helyett k++)
(Táblázat kitölrésének logikája, plusz újabb javás kód a 2008-as diából)
} while(x > 0); // amíg van mit kirakni
return érmék; // 0..db-1 -ig lesz a megoldás, utána 0-k
}
</pre>
A táblázat kitöltésének logikája:
Olyan kiszámítási sorrendet kell megállapítani, amelyre teljesül, hogy amikor az (X, i) rész-
problémát számítjuk, akkor ennek összetevőit már korábban kiszámítottuk. Mivel az (X, 1)
részproblémáknak nincs összetevőjük, ezért közvetlenül kiszámíthatóak, azaz a táblázat első
sorát számíthatjuk eloször. Ha i > 1, akkor az (X i) részprobléma összetevoi az (X, i − 1) és
(X − pi , i − 1), ezért az i-edik sor bármely elemét ki tudjuk számítani, ha már kiszámítottuk
az i − 1-edik sor minden elemét. Tehát a táblázat-kitöltés sorrendje: soronként (alulról felfelé), ̋
balról-jobbra haladó lehet.
<pre>
public class PenzValt1{
public static int[] Valto(int E, int[] P){
int n=P.length;
int MaxE=1000;
boolean VT[][]=new boolean[E+1][n+1];
int i,x;
for (x=1; x<=E; x++) //inicializálás
VT[x][0]=false;
VT[0][0]=true;
VT[P[0]][0]=true;
for (i=1; i<n; i++)
for (x=1; x<=E; x++)
VT[x][i]=P[i]==x ||
VT[x][i-1] ||
x>=P[i] && VT[x-P[i]][i-1];
int db=0; x=E; i=n-1;
if (!VT[E][n-1]) return null;
int C[]=new int[n];
do{ //megoldás visszafejtés
while (i>=0 && VT[x][i])
i--;
C[db++]=++i;
x-=P[i];
}while(x>0);
for (i=db; i<n; i++)
C[i]=0;
return C;
}
}
</pre>
Névtelen felhasználó