Programmieren - alles kontrollieren 4.941 Themen, 20.715 Beiträge

Verfolgung starten Optionen

java rekursionsaufgabe

hategrown / 6 Antworten / Baumansicht Nickles

hi !
ich schreibe am donnerstag java klausur und bin grad ein wenig am üben und bekomme eine rekursionsaufgabe nicht raus : (zusammengefasst)

In Muenzland gibt es eine Währung die aus folgenden Münzen besteht: 7, 31 und 53 cent. mit diesen münzen ist jedoch nicht jeder beliebige betrag darstellbar, wie z.b. 61 cents;
schreiben sie eine java methode die für einen beliebigen betrag rekursiv ermittelt ob sich dieser durch diese drei münzen darstellen lässt.

kann mir wer helfen ?

danke

mfg hategrown

www.raiseyourvoice.de

bei Antwort benachrichtigen
Borlander hategrown „java rekursionsaufgabe“
Optionen

Ich würde eine Fkt mit einem Parameter für den Betrag die als zurückgibt ob selbiger aus den 3 Münzen darstellbar ist (das kommt jetzt sicher nicht überraschend). Diese Fkt kann sich dann (baumförmig) rekursiv selbst mit dem um die verschiedenen Münzwerte verringerten Betrag aufrufen, so lange bis der Betrag
Als erster Hinweis sollte das eigentlich reichen, würde ich das als Code schreiben hättest Du selbst nichts mehr zum Denken ;-)
Falls nicht, frag noch mal nach...


Gruß
Borlander

bei Antwort benachrichtigen
hategrown Nachtrag zu: „java rekursionsaufgabe“
Optionen

thx

hab zwar noch ewich rumgegrübelt aber habs noch hinbekommen danke

auf borlander is halt verlass, was kannst du noch alles für sprachen ?
hast mir ja mit assembler auch schon sehr weiterhelfen können


mfg
hategrown

bei Antwort benachrichtigen
mr.escape hategrown „thx hab zwar noch ewich rumgegrübelt aber habs noch hinbekommen danke auf...“
Optionen
hab zwar noch ewich rumgegrübelt aber habs noch hinbekommen
Richtig ohne iterative anteile? Dann zeig mal her, ich konnte auf die schnelle nur auf eine rekursiv/iterative mischvariante kommen. Würde gerne sehen, ob eine andere lösung "ohne" iteration möglich ist.
Man lernt ja nie aus! :)

mr.escape
"The man who trades freedom for security does not deserve nor will he ever receive either." - Benjamin Franklin"Wer seine Freiheit aufgibt, um Sicherheit zu erreichen, wird beides verlieren." - Georg Christoph Lichtenberg
bei Antwort benachrichtigen
Borlander mr.escape „ Richtig ohne iterative anteile? Dann zeig mal her, ich konnte auf die schnelle...“
Optionen

Zwar nicht in Java (hatte das JDK gerade nicht installiert, bin aber sowieso kein so großer Java-Fan...), aber am Algorithmus das allerdings nichts ändern:

function muenzland($betrag) {
  if($betrag     return false;
  elseif($betrag==0)
    return true;
  else
    return muenzland($betrag-7) || muenzland($betrag-31) || muenzland($betrag-53);
}



Gruß
Borlander
bei Antwort benachrichtigen
Borlander mr.escape „ Richtig ohne iterative anteile? Dann zeig mal her, ich konnte auf die schnelle...“
Optionen

Hab eben noch mal nebenbei eine iterative Lösung geschrieben:


function muenzland_iter($betrag) {
  for($b1 = $betrag; $b1>=0; $b1 -=7) {
    for($b2 = $b1; $b2>=0; $b2 -=31) {
      for($b3 = $b2; $b3>=0; $b3 -=53) {
        if($b3==0) {
          return true;
        }
      }
    }
  }
  return false;
}


Jetzt würde mich allerdings auch noch mal die gemischte Form interssieren ;-)
bei Antwort benachrichtigen
mr.escape Borlander „Hab eben noch mal nebenbei eine iterative Lösung geschrieben: function...“
Optionen

Ok, einmal gemischtes:

$muenzval = array(7, 31, 53);

function RecMuenze($betrag, $muenzind){
  $muenze=$muenzval[$muenzind];
  if(($betrag % $muenze)==0)
    return true;//passt
  if($muenzind     return false;//keine weitere münzgröße mehr
  $n=(int)($betrag/$muenze);
  for($i=$n; $i>=0; $i--)
    if(RecMuenze($betrag-$i*$muenze, $muenzind-1))
      return true;
  return false;
}

function muenzland($betrag) {
  return RecMuenze($betrag, sizeof($muenzval)-1);
}



mr.escape
"The man who trades freedom for security does not deserve nor will he ever receive either." - Benjamin Franklin"Wer seine Freiheit aufgibt, um Sicherheit zu erreichen, wird beides verlieren." - Georg Christoph Lichtenberg
bei Antwort benachrichtigen