gustavo el programador

[carlostex]

hola, esto no tiene que ver con videojuegos pero si con programación y algoritmia. Tengo el siguiente problema.
(ver imagen adjunta)
He intentado resolverlo en los ratos que tuve librey tambien con unos amigos, pero no lo consegui, aver si alguien se le ocurre algo.
Es todo un reto.

[endaramiz]

Hola. Lo he resuelto con una técnica no muy eficiente: backtraking. Esto se encarga de probar todos los casos. Pero la gracia consiste en que cuando una rama del árbol no te interesa (intuyes que no va a dar un buen resultado) puede volver hacia atrás y dejar de comprobar todos esos casos. Por ejemplo yo "podo" (creo que es el término) los números que tienen un 0 después de un dígito que no es 0 ( Gus no conoce el 0). En este caso, también puedes hacer poda cuando ves que el número ya supera lo que tiene que sumar, ya que la suma final será igual o superior a la actual. Aunque los cálculos para saber cuando hay que hacer poda tienen que ser eficientes, sino es contraproducente. Te lo dejo como ejercicio. Ya dirás que tal te sale.

Si te gusta el tema, puedes apuntarte a webs como OIE que tienen enunciados y un corrector automático (el odiado por muchos Jutge xD). Aunque quizás ya conozcas alguna (los enunciados suelen ser como la imagen que has subido).

Siento el retraso.

Código: Seleccionar todo

#include <iostream>
#include <vector>
using namespace std;

typedef vector<int> Vi;

const int DigsGus[]= {0,1,1,2,3};
const int NDigGus = 5;

bool suma_n(const Vi& v, int n) {
    int suma = 0;
    for (int i = 0; i < v.size(); i++) {
        suma += v[i];
    }
    return suma == n;
}

int numerosGus(Vi& v, int i, int n) {
    if (i == n) {
        return suma_n(v, n);
    }
    int nums = 0;
    int j = 0;
    if (v[max(i-1,0)] != 0) ++j;
    while (j < NDigGus) {
        v[i] = DigsGus[j];
        nums += numerosGus(v, i+1, n);
        ++j;
    }
    return nums;
}

int main() {
    int n;
    while (cin >> n) {
        Vi v(n,0);
        cout << numerosGus(v, 0, n) << endl;
    }
}

PD: si no entiendes algo del código, no dudes en preguntar y haré una explicación más profunda (no la he hecho ahora porque no sé tu nivel).

[Juanxo]

vivan esas clases de algoritmica!! estaba claro que era bactracking... lo unico una duda: para que usas el 0? simplemente no hace falta tenerlo en cuenta a la hora de hacer los calculos, ya que no conoce el 0 ni ninguno más allá del 5

EDITO: Voy a probar otro punto de vista. Mezcla de voraces y bactracking. Simplemente es ir cogiendo los numeros en orden (1,2,3,4,5) e ir añadiendo el numero actual a la suma, hasta que llegue al numero o me pase, momento en el que doy un paso atras en recursividad y cojo el siguiente:
por ejemplo para 3 sería
1
11
111 /* Es 3 luego paro y vuelvo atras */
112 /* Me he pasado, lo descarto y vuelvo atras */
12 /* Es 3 me vale, vuelvo atras */
121 /* Me he pasado, para atrás */
2
21 /* Me vale */

ad infinitum xD

EDITO LO EDITADO: He terminado mi algoritmo. Aquí pongo todo el código. He añadido lo de david para comparar llamadas recursivas y tiempo de ejecución.
En cuanto a diferencias, el tuyo está mejor porque no dependes de variables externas, a diferencia del mío.

Código: Seleccionar todo

#include <vector>
#include <iostream>
#include <time.h>

typedef std::vector<int> Vi;

int valores[4] = {1,1,2,3};
int numeros_conocidos[4] = {1,4,2,3};

void numeros_gustavo(int& iteraciones,int& numeros, int numero_a_calcular, Vi& numeros_usados, int& suma)
{
  int pos_actual = 0;
  while(pos_actual < 4 && suma + valores[pos_actual] <= numero_a_calcular)
  {
   
    // Anotar
    numeros_usados.push_back(numeros_conocidos[pos_actual]);
    suma += valores[pos_actual];

    numeros_gustavo(++iteraciones,numeros,numero_a_calcular, numeros_usados, suma);
     
    //Desanotar
    suma -= valores[pos_actual];
    numeros_usados.pop_back();
    pos_actual++;
  }
  if (suma == numero_a_calcular)
  {
    numeros++;
    pos_actual = 4;
  }
}

const int DigsGus[]= {0,1,1,2,3};
const int NDigGus = 5;

bool suma_n(const Vi& v, int n) {
  int suma = 0;
  for (int i = 0; i < v.size(); i++) {
    suma += v[i];
  }
  return suma == n;
}

int numerosGus(int& iteraciones, Vi& v, int i, int n) {
  if (i == n) {
    return suma_n(v, n);
  }
  int nums = 0;
  int j = 0;
  if (v[std::max(i-1,0)] != 0) ++j;
  while (j < NDigGus) {
    v[i] = DigsGus[j];
    nums += numerosGus(++iteraciones,v, i+1, n);
    ++j;
  }
  return nums;
}


int main(int argc, char* argv[])
{
  int numero_a_calcular;
  time_t tiempo, differ;
  while( std::cin >> numero_a_calcular)
  {
    int numeros = 0, numeros2 = 0;
   
    int suma_acumulada = 0;
    int iteraciones = 0, iteraciones2 = 0;

    Vi numeros_usados, numeros_usados2(numero_a_calcular, 0);
    numeros_usados.reserve(numero_a_calcular + 10);

   
    tiempo = time(NULL);
    numeros_gustavo(iteraciones,numeros, numero_a_calcular, numeros_usados, suma_acumulada );
    differ = time(NULL) - tiempo;
    std::cout << "ITERACIONES Juan: " << iteraciones << " NUMEROS: " << numeros <<
      " TIEMPO: " << differ << std::endl;

    tiempo = time(NULL);
    numeros2 = numerosGus(iteraciones2, numeros_usados2, 0, numero_a_calcular);
    differ = time(NULL) - tiempo;
    std::cout << "ITERACIONES David: "<< iteraciones2 <<  " NUMEROS: " << numeros2 <<
      " TIEMPO: " << differ << std::endl;
  }
}


[carlostex]

Gracias por responder, ya tenia pensado una solucion, muy parecida a las dos, por fuerza bruta, pero no habia podido implementarla ni en matlab por falta de tiempo.
Es este caso la mejor solución es la que se pueda pensar e implementar mas rapido, pues para resolver ese problema teniamos como media hora.

[endaramiz]

vivan esas clases de algoritmica!! estaba claro que era bactracking... lo unico una duda: para que usas el 0? simplemente no hace falta tenerlo en cuenta a la hora de hacer los calculos, ya que no conoce el 0 ni ninguno más allá del 5

EDITO: Voy a probar otro punto de vista. Mezcla de voraces y bactracking. Simplemente es ir cogiendo los numeros en orden (1,2,3,4,5) e ir añadiendo el numero actual a la suma, hasta que llegue al numero o me pase, momento en el que doy un paso atras en recursividad y cojo el siguiente:
por ejemplo para 3 sería
1
11
111 /* Es 3 luego paro y vuelvo atras */
112 /* Me he pasado, lo descarto y vuelvo atras */
12 /* Es 3 me vale, vuelvo atras */
121 /* Me he pasado, para atrás */
2
21 /* Me vale */

ad infinitum xD

EDITO LO EDITADO: He terminado mi algoritmo. Aquí pongo todo el código. He añadido lo de david para comparar llamadas recursivas y tiempo de ejecución.
En cuanto a diferencias, el tuyo está mejor porque no dependes de variables externas, a diferencia del mío.

Código: Seleccionar todo

#include <vector>
#include <iostream>
#include <time.h>

typedef std::vector<int> Vi;

int valores[4] = {1,1,2,3};
int numeros_conocidos[4] = {1,4,2,3};

void numeros_gustavo(int& iteraciones,int& numeros, int numero_a_calcular, Vi& numeros_usados, int& suma)
{
  int pos_actual = 0;
  while(pos_actual < 4 && suma + valores[pos_actual] <= numero_a_calcular)
  {
   
    // Anotar
    numeros_usados.push_back(numeros_conocidos[pos_actual]);
    suma += valores[pos_actual];

    numeros_gustavo(++iteraciones,numeros,numero_a_calcular, numeros_usados, suma);
     
    //Desanotar
    suma -= valores[pos_actual];
    numeros_usados.pop_back();
    pos_actual++;
  }
  if (suma == numero_a_calcular)
  {
    numeros++;
    pos_actual = 4;
  }
}

const int DigsGus[]= {0,1,1,2,3};
const int NDigGus = 5;

bool suma_n(const Vi& v, int n) {
  int suma = 0;
  for (int i = 0; i < v.size(); i++) {
    suma += v[i];
  }
  return suma == n;
}

int numerosGus(int& iteraciones, Vi& v, int i, int n) {
  if (i == n) {
    return suma_n(v, n);
  }
  int nums = 0;
  int j = 0;
  if (v[std::max(i-1,0)] != 0) ++j;
  while (j < NDigGus) {
    v[i] = DigsGus[j];
    nums += numerosGus(++iteraciones,v, i+1, n);
    ++j;
  }
  return nums;
}


int main(int argc, char* argv[])
{
  int numero_a_calcular;
  time_t tiempo, differ;
  while( std::cin >> numero_a_calcular)
  {
    int numeros = 0, numeros2 = 0;
   
    int suma_acumulada = 0;
    int iteraciones = 0, iteraciones2 = 0;

    Vi numeros_usados, numeros_usados2(numero_a_calcular, 0);
    numeros_usados.reserve(numero_a_calcular + 10);

   
    tiempo = time(NULL);
    numeros_gustavo(iteraciones,numeros, numero_a_calcular, numeros_usados, suma_acumulada );
    differ = time(NULL) - tiempo;
    std::cout << "ITERACIONES Juan: " << iteraciones << " NUMEROS: " << numeros <<
      " TIEMPO: " << differ << std::endl;

    tiempo = time(NULL);
    numeros2 = numerosGus(iteraciones2, numeros_usados2, 0, numero_a_calcular);
    differ = time(NULL) - tiempo;
    std::cout << "ITERACIONES David: "<< iteraciones2 <<  " NUMEROS: " << numeros2 <<
      " TIEMPO: " << differ << std::endl;
  }
}


Bueno, a simple vista parece que el tuyo hará menos ciclos, tampoco importa mucho si en un programa de estos hay variables globales. Aunque la idea de mi código era hacer una base para que luego lo mejorase xD