Problema con un algoritmo

Que tal comunidad siguiendo el curso de Martin Odersky pues hay una practica que en su tercer ejercicio propone el desarrollo de una funcion recursiva que devuelva el numero de veces distintas que puede dar el cambio (una cantidad que recibe como parametro) con un conjunto de monedas de determinada denominacion (en una lista de Enteros que representan la denominacion se reciben como parametro de esta funcion), y leyendo en san Google sobre Probabilidad y Estadistica, Algoritmos, y algunas cosas más mencionan mucho programación dinámica pero creo que la solución que me piden no va por ahí, pero la única idea que tengo es la siguiente pero no se que tan buena pueda ser y si la pueda implementar en Scala.

Utilizar n ciclos anidados para iterar sobre el conjunto de monedas es decir desde 0 hasta que (suma de n) < monto siendo n cada denominación de moneda:

Ejemplo:

 
monto 100 monedas 5,10,20,100

formas_diferentes=0
desde 0 hasta (suma de monedas 5) < monto
      desde 0 hasta (suma de monedas 10) < monto
            desde 0 hasta (suma de monedas de 20 < monto
                  desde 0 hasta (suma de monedas de 100 < monto
                       sumar cantidad de monedas * valor
                       si la suma anterior es igual al monto
                       incrementar formas_diferentes
                       fin si
                   fin desde
             fin desde
       fin desde
fin desde

Pero como lo veo es como usar fuerza bruta, aunque podria reducirlo (podar el arbol como lo llaman en algunos textos) y mandar a llamar de forma recursiva quitando una denominación en cada llamada recursiva no se si esta sea una solución la verdad ahi tengo dudas. Yo se que lo ideal es que lo resuelva por mi mismo pero ya le di muchas vueltas y no me queda. Pido disculpas por si alguien ya lo resolvio por si mismo pero creo que me falta capacidad para resolverlo.

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.

Yo aún no he hecho el tercer

Yo aún no he hecho el tercer ejercicio, pero hice los do anteriores siguiendo los pasos que escribí en este post hace tiempo:

Para entender la recursividad primero hay que entender la recursividad.

Y en en resumen es

1. Determinar las condiciones base. Por ejemplo, si la lista esta vacía el resultado es 0 y así.
2. Crear si hace falta parámetros de entrada donde puedas poner alguna variable de control, ejemplo en una suma, puedes crear una variable "total" donde vayas poniendo lo que vas sumando. También puedes ir restando y usarlo en la condición base. Muchas veces estos parámetros no hacen falta ( Obvio esta sería una función nueva a la que la original llama con los valores iniciales )
3. Llamar la función con los nuevos parámetros, incrementando, o decrementando los valores.

En este tercer ejercicio yo lo que he pensado ( sin profundizar ) es simplemente dividir entre la denominación y sumarle lo que regrese dividir en la siguiente:

cuantas :
 n = monto / denominaciones.head + cuantas( denominaciones.tail )

Algo por ahí :)

Recuerda que esta primera asignación se llama precisamente "Recursión" entonces, haz un esfuerzo extra por deshacerte de los loops.

Coin Change Algorithm

Hola , yo estoy en el mismo curso, y tambien he realizado los dos primeros ejercicios, y estoy por hacer el tercero, los ejercicios tienen base matematica, por lo cual primero investigue los algoritmos a los cuales estaban relacionados, trataba de hacerlos de manera "imperativa", y poco poco fui metiendo la recursividad.

Tal vez esto te pueda yudar

Coin_Change

Saludos

Imagen de paranoid_android

¿Donde generas la recursividad?

Sobre la recursividad.Si es una condición necesaria: ¿Cuál es el método que se llama a sí mismo y su condición para no ejecutarlo?
Si no es necesaria la recursividad. Alternativa: Si estás tratando de calcular cuantas monedas de cada tipo necesitas para devolver cambio, lo podrías hacer con divisiones me imagino.

Imagen de Cid

Creo que no lo coloque pero si lo mencion

Pues en esta parte creo que ahi la mencione

aunque podria reducirlo (podar el arbol como lo llaman en algunos textos) y mandar a llamar de forma recursiva quitando una denominación en cada llamada recursiva, con la condición de que si la lista esta vacia termine

Imagen de bferro

No usar sentencias de asignación

La idea con los ejercicios es seguir un estilo funcional puro, por lo que no deben usarse sentencias de asignación, evitando valores mutables.

Imagen de Cid

mmm no usar sentencias de asgnación

Bueno ok si es programacion funcional entonces bajo lo que @bferro expone debo de modificar la solución que logue hacer para el segundo problema ?. El segundo problema era econtrar la implementacion de una funcion que indicara si el numero y orden de parentesis dentro de una expresión estaba balanceado:

Aqui mi solución

def balance(chars: List[Char]): Boolean = {    
    var result = true
    var open = 0
    var close = 0
    def across(c: List[Char]): List[Char] = {      
      if(!c.isEmpty){        
        val e = c.head        
        if(e=='('){
          open+=1
        }
        if(e==')'){
          close+=1
          if(close>open){
            result = false
          }
        }
        across(c.tail)
      }else if(open>close){
        result = false
      }
      null
    }    
    across(chars)
    result
  }

aunque si pasa las pruebas creo que aun no llego a un grado de funcionalidad puro pues utilizo asignaciones. Alguna idea ?

las pruebas fueron :

test("'(if (zero? x) max (/ 1 x))' is balanced.") {
    assert(balance("(if (zero? x) max (/ 1 x))".toList))
  }

  test("'I told him ...' is balanced.") {
    assert(balance("I told him (that it's not (yet) done).\n(But he wasn't listening)".toList))
  }

  test("':-)' is unbalanced.") {
    assert(!balance(":-)".toList))
  }

  test("Counting is not enough.") {
    assert(!balance("())(".toList))
  }

Imagen de paranoid_android

Otra idea

Algo muy jalado al estilo shell ¿Abría alguna forma de extraer los paréntesis '(' en una cadena y ')' en otra cadena y comparar las longitudes?

Para evitar usar variables

Para evitar usar variables mutables lo que debes de hacer es sumarle el valor a lo que regresa la llamada a la función recursiva, o bien pasar un parametro extra y modificar ese parametro

Ejemplo, una función que cuente recursivamente la aparición de la letra 'a' en "abecedario"

// Pseudo:
cuenta( letra, list )  Int  =
    lista.estaVacia ? regresa  0
    lista.head == letra ? regresa cuenta( lista.tail ) +1
    regresa cuenta( lista.tail )

Por partes:

lista.estaVacia ? regresa  0

O sea, si la lista esta vacía no hay nada que contar. Ya sea por que así nos pasaron la lista o por efecto de la recursividad:

// la lista en cada llamada
1. ['a','b','c']
2. ['b','c']
3. ['c']
4. []

Luego:

lista.head == letra ? regresa cuenta( lista.tail ) +1

Si el primer elemento es el que buscamos, regresamos 1 + lo que resulte de la suma del resto.

Finalmente

regresa cuenta( lista.tail )

Si no esta vacía ni es la que buscamos, regresamos la cuenta del resto de la lista

Una vez teniendo claro el algoritmo, lo siguiente es codificarlo, en este caso en Scala :) y ( no es casualidad ) se parece mucho el algoritmo al código.

scala> def cuenta(  letra: Char,  cadena : List[Char] ) : Int  =
 |  if (cadena.isEmpty) 0 else  
 |  if (cadena.head == letra) cuenta( letra , cadena.tail ) + 1  else
 |  cuenta ( letra, cadena.tail )

cuenta: (letra: Char, cadena: List[Char])Int

scala> cuenta('a', "abcecedario".toList)
res1: Int = 2
scala> cuenta('z', "abcecedario".toList)
res2: Int = 0

Acá la implementación se parece muchísimo al algoritmo, porque pensé en el como una versión ligera de Scala, aún así se puede aplicar a Java por ejemplo:

    int cuenta( char c, List<Character> list ) {
        if ( list.isEmpty() ) return 0;
        if ( head(list) == c ) return cuenta(c, tail(list))+1;
        return cuenta(c, tail(list));
    }

Otra forma como dije al principio es agregar un parametro extra. En el ejemplo anterior la lista es este parametro extra que está sirviendo de acumulador, como otro ejemlo se puede hacer la sumatoria de un número así:

sumatoria( n,  acumulador )  =
   // condición base
    n == 0 ? regresa acumulador
   // sino  es 0 ( o menor que cero ) quitale uno y sumale a acumulador
    regresa sumatoria ( n -1 , acumulador +1 )

También se puede hacer sin acumulador, pero ya no serviría de ejemplo :P

En ambos casos no se está mutando el valor de la variable, sino que se está haciendo un nuevo calculo cada vez. A esto es a lo que se refiere sobre el modelo funcional puro, no se cambian los valores, sino que se crean nuevos.

Imagen de bferro

Usar funciones auxiliares

Los ejercicios también indican que es necesario que se disparen excepciones para algunos casos excepcionales (y valga la redundancia). Es el caso de las funciones sum y max de la primera asignación. La condición de lista vacía al comienzo, es similar al caso base de la recursividad en estas dos funciones, por lo que puede ser necesario que la recursividad se realice para una función que se anida dentro de la función que se pide.

Imagen de paranoid_android

Gracias por compartir

Esta muy padre el ejercicio

Imagen de Cid

Gracias a todos seguimos en

Gracias a todos seguimos en eso.
Entender recursion. (sigo en eso)
Analizare todas sus respuestas.
Saludos.