Kovanci
V neki dezeli obstajajo kovanci za 50, 25, 10, 5 in 1 cent. Poljubni znesek lahko zato plačamo različno.
Na primer 11 centov lahko plačamo na 4 načine:
10 centov + 1 cent
5 centov + 5 centov + 1 cent
5 centov + 6 x 1 cent
11 x 1 cent
Sestavi metodo, ki bo za dano vsoto vrnila tabelo nizov z opisi vseh načinov, na katere lahko izpišemo znesek.
Metoda naj bo rekurzivna.
Metoda "poKolikoKovancev" dá zacetno kombinacijo (npr. znesek 106 bi razdelili na: 2x50 + 1x5 + 1x1) iz katere so potem izpeljane vse ostale z 'drobljenjem' najmanjsega kovanca trenutne kombinacije, ki je SE vecji od '1'. To se s pomocjo rekurzije (kot je zahtevano) izvede v metodi "Nacinov", kjer na podlagi vrednosti v dodatni tabeli (ki hrani kolicino kovancev - rezultat prve metode) dosezemo, da se vse kolicine kovancev vecjih od 1 spreminjajo (po EN kovanec) v manjse in na koncu ostane le se stevilo kovancev po '1', ki je enako zacetnemu znesku. Metoda "ZapisivTabelo" ne uporablja stevca kombinacij pac pa uporabi metodo 'Count' objekta 'ArrayList' kamor sicer zapisujemo tekoce kombinacije. ArrayList je kot nalasc za ta primer, ker gre za dinamicno tabelo kateri na zacetku NI potrebno dolociti stevila elementov - oziroma tako kot v nasem primeru, ko ne vemo vnaprej koliko kombinacij bomo vanjo zapisali...
V resitvi se torej le enkrat (NErekurzivno) ukvarjam s samim deljenjem zneska - tu dobim zacetne kolicine posameznih kovancev, ki jih potem (rekurzija) toliko casa prerazporejam (v tabeli kolicin 'k'), da na koncu ostane le se toliko kovancev po 1 cent kolikor znasa izvorni znesek (tj. ustavitveni pogoj). npr.: 103 = 2x50 + 3x1 >> enic ne morem 'zdrobiti', zato obdelam vdrugo tisti drugi kovanec za 50, torej 103 = 1x50 + 2x25 + 3x1 >> sedaj je na vrsti se DRUGI od kovancev za '50' 103 = 0x50 + 4x25 + 3x1 >> ker je zmanjkalo slednjih, je na vrsti EDEN od tistih po '25' - ta razpade na troje 103 = 0x50 + 3x25 + 2x10 + 1x5 + 3x1 itd.
class Program
{
public static void ZapisivTabelo (int[]kombinacija, int[]kovanci, ArrayList nacinov) {
string zaDodat = nacinov.Count+1 + ". nacin";
string zaDodat1 =
"\t"+ kombinacija[0] + "x" + kovanci[0]+ " " + kombinacija[1] + "x" + kovanci[1]
+ " " + kombinacija[2] + "x" + kovanci[2]+ " " + kombinacija[3] + "x" + kovanci[3]
+ " " + kombinacija[4] + "x" + kovanci[4];
nacinov.Add (zaDodat + zaDodat1); // Dodaja kombinacije v tabelo in jih
Console.WriteLine(zaDodat + zaDodat1); // (dodatno!) se izpisuje na konzoli
}
public static int[] poKolikoKovancev (int znesek, int[]kovanci) {
//Tule ugotavljamo zacetne kombinacije kovancev - npr.: 56 je 1x50 + 1x5 + 1x1
int indeks = 0, dolz = kovanci.Length-1;
int[]k = new int[5] { 0,0,0,0,0 };
while (indeks <= dolz) {
while (znesek >= kovanci[indeks]) // V tej zanki gre za odste-
{ // vanje kovancev dokler so
znesek -= kovanci[indeks];
k[indeks]++; // le-ti VECJI od preostanka
} // zneska. Obenem vecamo se
indeks++; // kolicino istih kovancev v
} // dodatni tabeli, ki jo
return k; // vrnemo kot rezultat.
}
public static int Nacinov (int znesek, int[]k, int[]kovanci, ArrayList nacinov) {
int zaDrobit = 4; // to je indeks ENEGA kovanca, ki ga zamenjata(jo) manjsi
if (k[k.Length-1] == znesek) {
return nacinov.Count; // Cilj: celoten znesek po en cent,
} else { // kar je tudi ustavitveni pogoj
for (int i = k.Length-2; i >= 0; i--) { // Ugotavljanje kovanca, ki ga
if (k[i]>0 ) {
zaDrobit = i; // je treba zamenjati z manjsima(i)
}
}
k[zaDrobit] = k[zaDrobit]-=1;// 'faktor' kovanca zmanjsamo za ena ostale pa...
if (zaDrobit == 0 || zaDrobit == 2) {
k[zaDrobit+1]+=2; // 50 ali 10
}
if (zaDrobit == 1) {
k[zaDrobit+2]+=1; // 25
k[zaDrobit+1]+=2;
}
if (zaDrobit == 3) {
k[zaDrobit+1]+=5; // 5
}
}
ZapisivTabelo (k, kovanci, nacinov); // Izpis tekoce kombinacije kovancev
return Nacinov (znesek, k, kovanci, nacinov); // Obdeluj naprej...
}
public static void Main(string[] args) {
Console.Write("Vnesi znesek: "); // vnos zeljenega
int znesek = int.Parse(Console.ReadLine()); // zneska
int[]kovanci = new int[5] {50,25,10,5,1};
int[]kolkKovancev = new int[5];
kolkKovancev = poKolikoKovancev (znesek, kovanci);
ArrayList nacinov = new ArrayList(); // Dinamicna tabela - brez velikosti
ZapisivTabelo (kolkKovancev, kovanci, nacinov); // Takoj lahko izpisemo 1. kombinacijo
Nacinov (znesek, kolkKovancev, kovanci, nacinov);
Console.WriteLine("\n\nZnesek: " + znesek + " razdelimo na "
+ nacinov.Count + " nacin/a/e/ov.");
// Sicer je ze vse izpisano - le se kontrola ene od vrednosti v tabeli moznih kombinacij (ArrayList):
Console.WriteLine("\n\nKombinacija s sredine tabele: " + nacinov[nacinov.Count/2]);
Console.Write("\nPritisni karkoli . . . ");
Console.ReadKey(true);
}
}