„Programozás/Algoritmusok” változatai közötti eltérés
Tartalom törölve Tartalom hozzáadva
Formázás |
Kommentezés |
||
506. sor:
===<!--19. -->Pénzváltási probléma egy megoldásának előállítása táblázat-kitöltéssel===
:'''
<pre>
int[] PénzVáltás(int E, int P[n]){
537. sor:
</pre>
:'''A táblázat kitöltésének logikája:'''
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ő
544. sor:
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.
:'''Java kód'''
<pre>
public class PenzValt1{
552 ⟶ 553 sor:
int i,x;
for (x=1; x<=E; x++) //inicializálás
VT[x][0]=false; //0 sor végig false
VT[0][0]=true; //semmit, érmék nélkül ki lehet rakni
VT[P[0]][0]=true; //inicializálás vége
for (i=1; i<n; i++) //kitöltjük a táblázatot az összes lehetséges P-re balról-jobbra
for (x=1; x<=E; x++) //kitöltjük a táblázatot az összes lehetséges X-re alulról-fölfele
'''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;
| |||