Scala „funktionale Funktion“ zur Bestimmung der Anzahl möglicher „Münzstückelungen“

sansuer

Mitglied
Guten Tag,

ich bin gerade dabei Scala zu lernen und stehe vor einem Problem. Ich kann einfach nicht den Fehler in meiner Funktion finden. Die Funktion soll funktional herausfinden wie oft die werte (aus der Liste) in den Betrag passen. Die Liste stellt zum Beispiel Münzen dar und der Betrag den wert von wo das ganzen abgezogen wird.

Kann mir jemand, bei meinem mit Sicherheit offensichtlichen Fehler, behilflich sein.
Danke schon mal.
:)

Code:
def münzStückl(werte: List[Int], betrag: Int): Int = {     def muenSt(l: List[Int], n: Int,b: Int): Int = {
      l match {
        case Nil =>  0 
        case _=> {
          if (b-l.head >= 0 )
             muenSt(l, n+1, b-l.head) 
           else if (b-l.head < 0) 
             muenSt(l.tail, n+1, b)
             else n
        }
      }
    }
    muenSt(werte, 1, betrag)
  }
 
Zuletzt bearbeitet:

Flown

Administrator
Mitarbeiter
Du hast genaugenommen 5 Fälle:
- Wenn der Betrag 0 ist => 0 liefern
- Wenn die Liste leer ist => 0 liefern
- Wenn die beiden obigen Fälle nicht eingetroffen sind und zusätzlich:
... Betrag = die erste Münze in Liste gilt => 1 + münzStückl(werte.tail, betrag)
... Betrag < die erste Münze in Liste gilt => münzStückl(werte.tail, betrag)
... Betrag > die erste MÜnze in Liste gilt => münzStückl(werte, betrag - werte.head) + münzStückl(werte.tail, betrag)

Wenn du noch Hilfe brauchst, dann sag bescheid!
 

sansuer

Mitglied
Danke für deine Hilfe. Aber eine Frage habe ich noch. Er gibt mir einen falschen Wert zurück wenn die Funktion fertig ist obwohl beim debuggen die Werte soweit stimmen. Quasi nur wenn sie fertig ist wird der Wert wieder überschrieben. Ich weiß jetzt auch nicht ob es ein unterschied zwischen Sala und anderen sprachen gibt.

Code:
/**
 * @author 
 */
object Münzstückelungen {
  def main(args: Array[String]): Unit = {
    val muenzList: List[Int] = List(1, 2, 5, 10).sorted
    val betrag: Int = 101
    //anzahl der Stückelungen
    var listRev = revRec(muenzList)
    var returnValue = münzStückl(listRev, betrag)
    print(returnValue)
    //    print(münzStückl(revRec(muenzList), betrag))
    // auflistung der stückelungen
    //    münzStückelungen(revRec(muenzList), betrag)
  }


  def revRec[A](list: List[A]): List[A] = {
    def rotRec[A](result: List[A], list: List[A]): List[A] = {
      list match {
        case Nil => result
        case (a :: b) => { rotRec(a :: result, b) }
      }
    }
    return rotRec(Nil, list)
  }

  def münzStückl(werte: List[Int], betrag: Int): Int = {
    def muenSt(l: List[Int], n: Int, b: Int): Int = {
      (l, b) match {
        case (Nil, 0) => 0
        case _ =>
          if (b == l.head) {
           muenSt(l.tail, n + 1, b - l.head)
          } else if (b < l.head) {
           muenSt(l.tail, n, b)
          } else if (b > l.head) {
           muenSt(l, n + 1, b - l.head)
          }
          return n
      }
    }
    muenSt(werte, 1, betrag)
  }

//  def münzStückelungen(werte: List[Int], betrag: Int): List[List[Int]] = {
//    val dim: List[List[Int]] = List()
//    dim
//  }
}
 
Zuletzt bearbeitet von einem Moderator:

Flown

Administrator
Mitarbeiter
Also ich hätte das auf jedenfall so gelöst:
Code:
def countChange(money: Int, coins: List[Int]): Int = {
  if (money == 0) 0
  else {
    coins match {
      case Nil => 0
      case x :: xs if money == x => 1 + countChange(money, xs)
      case x :: xs if money > x => countChange(money - x, coins) + countChange(money, xs)
      case _ :: xs => countChange(money, xs)
    }
  }
}

Funktional eine Liste umdrehen geht dann so:
Code:
def myReverse[A](list : List[A]) : List[A] =  list.foldLeft(List[A]())((l, x) => x :: l)
 
Zuletzt bearbeitet:

Flown

Administrator
Mitarbeiter
Warum versuchst du es nicht in den Debugger zu werfen, um zu sehen was los ist?

Aber zu deiner Erklärung:
Wenn der abgehobene Wert aus der Liste gleich dem Betrag ist, hat man eine Lösung gefunden (plus 1 zu allen Lösungen). Jetzt muss man nur noch ermitteln, ob die Summe in anderen Stückelungen erreicht werden kann (Methodenaufruf mit restlicher Liste).

Diese Lösung ist nicht Endrekursiv gelöst, aber das sollte kein Problem sein. Der Rückgabewert ist die Lösung.

Hoffe deine Frage damit beantwortet zu haben. Gibt es sonst noch was?
 
Zuletzt bearbeitet:

sansuer

Mitglied
Eine Sache hab ich noch.
Ich frage mich wie ich das ganze mit einer zwei Dimensionen List verbinden kann.

z.B : Das zählen der erwendetet coins.
 

sansuer

Mitglied
Ja natürlich.

Mein derzeitiger stand:


Code:
def münzStückelungen(werte: List[Int],rList: List
[List[Int]], betrag: Int): List
[List[Int]] = {   
    if (betrag == 0) List(List(0,0))
    else{
      werte match {
        case Nil => List(List(0,0))
        case x :: xs if betrag == x => münzStückelungen(xs, rList, betrag)
        case x :: xs if betrag > x => 
          if (rList.contains(x)) {
            rList.indexOf(x)+1
            münzStückelungen(werte, rList, betrag-x)
          }else {
            rList.++(List(List(x,1)))
          }
        case _ :: xs => münzStückelungen(werte, rList, betrag)
      }
    }
  }
 
Zuletzt bearbeitet:

Flown

Administrator
Mitarbeiter
Warum verwendest du nicht ein Set[List[Int]]?

Dann kannst du auch mit ein wenig Umbauen von meinem obigen Code Beispiel das rausholen:

Code:
def countChanges(money: Int, coins: List[Int]): Set[List[Int]] = {
  def cc(m: Int, c: List[Int], cur: List[Int]) : Set[List[Int]] = {
    if(m == 0) Set()
    else {
      c match {
        case Nil => Set()
        case x :: xs if m == x => Set(x :: cur) ++ cc(m, xs, cur)
        case x :: xs if m > x => cc(m-x, c, x :: cur) ++ cc(m, xs, cur)
        case _ :: xs => cc(m, xs, cur)
      }
    }
  }
  cc(money, coins, List())
}
 
Zuletzt bearbeitet:

sansuer

Mitglied
Weil ich bisher nichts davon wusste ;)

Ich hab erst am 13. angefangen mit Scala.
Wenn ich die Funktion richtig verstanden habe gibt diese jegliche Kombinationsmöglichkeit aus?
 

Neue Themen


Oben