Algoritmos

1) Podemos saber si existe una subestructura óptima para los subproblemas si a partir de esta podemos encontrar la solución óptima al problema. Para esto básicamente se define una recursión para solucionar el problema:

Previamente hay que llenar datos con -1

int solucion(int n, int s)

{

if(datos[n][s] != -1) //si se ha guardado algun valor retornelo

return datos[n][s];

if(s == 0)

return INF; //INF se refiere a un numero muy grande

if(n == 0)

return 0;

int respuesta = 0;

for(int i = 1;i <= n;i++)

respuesta = max(respuesta, min(solucion(n-i, s)+1, solucion(i, s-1)+1));

datos[n][s] = respuesta; //Guardar el valor para usarlo despues

return rtn;

}

Lo importante esta en esta línea que define la recursión:

respuesta = max(respuesta, min(solucion(n-i, s)+1, solucion(i, s-1)+1));

Esto implica que se ha encontrado una subestructura optima, la explicación de la recursión es, cual es el menor valor que necesito para adivinar los números entre un rango de n con s adivinanzas, es el mínimo entre encontrar un numero entre un rango 0 a n-i con s adivinanzas +1 (porque estar ahí me implica una operación) y encontrar un numero en un rango 0 a i con s-1 adivinanzas +1; por ultimo como necesitamos asegurar que todos los números en el rango podrán ser encontrados necesitamos el mayor entre todas las posibles respuestas.

b) La ecuación de recurrencia es:

S representa el número de adivinanzas. Si s es 0 implica que ya no se pueden hacer adivinanzas es decir que el jugador pierde, n representa el rango de números que va de 0 a n si n es 0 no se necesita adivinar más pues ya no hay más números.

c) Solución en C++

#include <iostream>

#include <algorithm>

using namespace::std;

int adivinan[1003][21]; //Matriz de tamaño rango de numeros y numero maximo de adivinanzas

void Dinamica(){

int aux=0;

//Para todas las posibles soluciones

for(int i=0;i<1003;i++){

for(int j=0;j<21;j++){

adivinan[i][j] = INT_MAX;//Maximo entero

//No se necesita adivinar

if(i==0){

adivinan[i][j] = 0;

continue;

}

for(int k=0;k<i;++k)

{

aux = j==0 ? INT_MAX : adivinan[i-k-1][j-1]+1;

if(k+1 == i)

aux = 0;

adivinan[i][j] = min(adivinan[i][j], max(max(1,adivinan[k][j]+1), aux));

}

}

}

}

int main()

{

int casos;

int n,s;

Dinamica();

cin>>casos;

while(casos--)

{

cin>>n>>s;

...