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



## sansuer (15. Mai 2015)

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.


```
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)
  }
```


----------



## Flown (15. Mai 2015)

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 (17. Mai 2015)

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. 


```
/**
 * @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
//  }
}
```


----------



## Flown (17. Mai 2015)

Also ich hätte das auf jedenfall so gelöst:

```
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:

```
def myReverse[A](list : List[A]) : List[A] =  list.foldLeft(List[A]())((l, x) => x :: l)
```


----------



## sansuer (17. Mai 2015)

Dieses 1+ countChange(..). Was macht das genau, ist das der counter. Wie funktioniert das?


----------



## Flown (18. Mai 2015)

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?


----------



## sansuer (18. Mai 2015)

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.


----------



## Flown (18. Mai 2015)

Was hast du denn bis jetzt versucht? Ohne Eigeninitiaitve läuft nichts.


----------



## sansuer (18. Mai 2015)

Ja natürlich. 

Mein derzeitiger stand:



```
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)
      }
    }
  }
```


----------



## Flown (18. Mai 2015)

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

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


```
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())
}
```


----------



## sansuer (19. Mai 2015)

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?


----------



## Flown (19. Mai 2015)

Jede Kombination die deine Zielbetrag ergeben.


----------

