[infostudents] Re: Algotheorie Task 2
- From: Alexander Nutz <alex_nutz@xxxxxx>
- To: infostudents@xxxxxxxxxxxxx
- Date: Sun, 21 Dec 2008 22:17:47 +0100
Hallo,
im Anhang ist ein Mini-Programm, dass ich zur 2 geschrieben habe - ist
recht simpel, tut aber glaub ich schon, was es soll und verwendet auch
die Tabelle, wie vorgeschlagen.
(ist C-Sharp Code, der eigentliche Code müsste aber fast identisch unter
Java laufen..)
Die Idee:
Lege eine Bool-Tabelle der Größe Zahlbetrag+1 an mit der Bedeutung
table[i]=true gdw ich kann betrag i bezahlen
initialisiere mit den vorgegebenen Werten
so lange sich noch was ändert addiere auf jeden true-Eintrag in der
Tabelle jeden Münzwert drauf und trage das Ergebnis wieder in der
Tabelle ein.
gib den x-ten Eintrag aus
Was denkt ihr?
Grüße
alex
SilSie@xxxxxx schrieb:
Hi,
wenn du zuerst die große Münze "abfragst", findest du vielleicht nicht
immer eine Lösung, obwohl man den Betrag auszahlen könnte... siehe
dazu Vorlesung über Greedy Algorithmen.
Das schwere ist ja, dass wirklich jede Kombination von Münzen den
Betrag ergeben könnte. Wenn man gleich den Betrag der größten abzieht,
lässt man schon viele Möglichkeiten aus.
Gruß,
Silvan
Jonas Gehring schrieb:
Hi,
Ich würde mal so anfangen: Für den Betrag testen ob er größer als eine Münze
ist (am besten mit der größten anfangen). Falls ja, dann rekursiv die Methode
für Betrag-Münze aufrufen. Wenn "ja" zurückkommt, "ja" zurückgeben, ansonsten
es mit der nächstkleineren Münze versuchen. Wenn der Betrag gleich ist, dann
nat. sofort "ja" zurückgeben.
"Dynamisch" kann man das Ganze z.B. so machen, indem man vor jeder Rückgabe
den Wert in einer Tabelle bzw. in einem Array speichert und dieses bei jedem
Aufruf zuerst abfragt.
Gruß,
Jonas
On Wednesday 17 December 2008 22:25:18 Silvan S. wrote:
Hi,
ich finde die Aufgabe keineswegs trivial. Wenn du dort "Ist dem nicht so
probieren wir der Reihe nach den ganzen Array mit Münzwerten durch. "
bist, was genau willst du dann machen? Nur auf Teilbarkeit überprüfen?
Das reicht doch überhaupt nicht... Es könnte doch -jede- beliebige
Kombination von Münzen den gewünschten Betrag x ergeben...
Gruß,
Silvan
don.vito.c@xxxxxx schrieb:
Hallo Lista,
ich habe mir jetzt eine Menge Gedanken gemacht zu der Aufgabe, aber
ich komme nicht dahinter, warum wir das mit einem Array machen sollen.
Die Aufgabe ist ja eigentlich Erstsemester-mäßig. Ich finde es ist
nämlich viel einfacher, einfach die kleinste Zahl im Array mit den
Münzwerten zu nehmen und zu testen ob sie die andere Zahl teilt. Ist
dem so, so sind wir fertig. Ist dem nicht so probieren wir der Reihe
nach den ganzen Array mit Münzwerten durch.
Vielleicht kann mir ja mal einer von euch sagen wozu man hier einen
Array von Wahrheitswerten bilden soll. Ich finde da keinen wirklich
guten rekursiven Ansatz.
Gruß,
Cornelius---
Sent through the Infostudents Mailinglist
List Archive:
//www.freelists.org/archives/infostudents/
Subscribe / Unsubscribe:
//www.freelists.org/list/infostudents
---
Sent through the Infostudents Mailinglist
List Archive:
//www.freelists.org/archives/infostudents/
Subscribe / Unsubscribe:
//www.freelists.org/list/infostudents
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ATDynProg1
{
class Program
{
static void Main(string[] args)
{
bool[] table;
int[] coins;
int toBePaid = 102; //(der zu zahlende wert)
int numberOfCoins = 2; //Anzahl der verschiedenen Münzwerte
coins = new int[numberOfCoins];
table = new bool[toBePaid+1];
coins[0] = 7;
coins[1] = 4;
//coins[2] = 15;
//Tabelle initialisieren (mit den Münzwerten)
for (int i = 0; i < numberOfCoins; i++)
{
table[coins[i]] = true;
}
//für jeden true-Eintrag in table und für jeden Münzwert,
addiere beide,
//mache ergebnis true, halte, wenn sich nichts mehr ändert
bool changed = true;
while (changed && (table[toBePaid]==false))
{
changed = false;
for (int i = 1; i < table.Length; i++)
{
if (table[i])
{
for (int j = 0; j < numberOfCoins; j++)
{
int z = i + coins[j];
if (z <= toBePaid)
{
if (!table[z])
changed = true;
table[z] = true;
}
}
}
}
}
Console.WriteLine(table[toBePaid]);
Console.ReadLine();
}
}
}
Other related posts:
