Hola buenas, queria pediros ayuda porque estoy un poco atascado. Resulta que estoy de erasmus en italia y tengo un examen el jueves de Algoritmo y estructura de Datos y estoy haciendo examenes anteriores para practicar. Me he topado con uno que no me sale(bueno hay mas de uno) y no se como hacerlo. He estado en tutoria, pero entre que no entiendo bien como se tiene que hacer el ejercicio y lo que me dice la tía esta en italiano,no me entero. El problema dice así.
A lo lago de un rio hay n puestos indicados con 0,1,.....n. En cada uno se puede alquilar una barca que puede ser devuelta en otro puesto.Es imposible ir en contra corriente. EL coste de la alquilar una barca de un punto de partida(i) a un punto de llegada es(j), y se denota por C(i,j). Es posible que para ir de i a j sea más economico efectuar algunos cambios de barca a lo largo del rio, que alquilar una unica canoa. Si se alguila una nueva en los puestos k1<k2... <kl el coste total del alquiler sera C(i,k1)+c(k1,k2)+....+C(kl,j). El coste minimo para ir del puesto i al puesto j es indicado por S(i,j)
1) calcular una funcion recursiva que calcule cada par de i,j. En particular se quiere S(0,n-1)
2) Una funcion no recursiva que calcule S(i,j). En particular S(0,n-1). (Tecnica de programacion dinamica)
Sugerencia para la solucion:
El subproblema generico es establecer el coste minimo S(i,j) que necesitas pagar para ir del puesto i al puesto j con i<j. Este valor puede ser calculado como el minimo de C(i,j) (es decir el coste directo para ir de i a j sin paradas intermedias) y el minimo entre la suma minima para ir del puesto i al puesto j con puestos intermerdios k=i+1,....j-1.
| 0 , si i >j
S(i,j) |
| min{ min.k=i+1,...j-1{S(i,k),S(k,j)}, C[i,j]} en otro caso.
Observación; la matriz de programación debe ser construida de abaajo hacia arriba.
Bueno yo he hecho para el apartado 1) este código que se lo he enseñado a la tía y me dice que esta bien, pero que la verdad no acabo de comprender puesto que siempre me sale la solución de una la primera diagonal...
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void construirMatriz(int **m,int tam);
void imprimirMatriz(int **m,int tam);
int minRecorrido(int **m,int i,int j);
int main(int argc,char **argv){
int **m;
int n,i,j,result,x;
srand(time(0));
printf("Tamanio:");
scanf("%d",&n);
fflush(stdin);
m=(int**)malloc(sizeof(int*)*n);
for(x=0;x<n;x++)
m[x]=(int*)malloc(sizeof(int)*n);
construirMatriz(m,n);
imprimirMatriz(m,n);
printf("Introduzca i(tenga en cuenta el tamaño de la matriz):");
scanf("%d",&i);
fflush(stdin);
printf("Introduzca j(tenga en cuenta el tamaño de la matriz):");
scanf("%d",&j);
fflush(stdin);
result=minRecorrido(m,i,j);
/*if(m[i][j]<result)
result=m[i][j];
*/
printf("El coste menor para ir de %d a %d es de %d.",i,j,result);
getchar();
}
void construirMatriz(int **m,int tam){
int i,j;
for(i=0;i<tam;i++){
for(j=0;j<tam;j++){
if(i>=j)
m[i][j]=0;
else
m[i][j]=rand()%20;
}
}
}
void imprimirMatriz(int **m,int tam){
int i,j;
for(i=0;i<tam;i++){
for(j=0;j<tam;j++)
printf("%d\t",m[i][j]);
printf("\n");
}
}
int minRecorrido(int **m,int i,int j){
int k,result,min=99999;
if(i>=j)
return 0;
if(j-1==i)
return m[i][j];
else{
for(k=i+1;k<=j-1;k++){
result=minRecorrido(m,i,k)+minRecorrido(m,k,j);
if(result<min)
min=result;
}
return min;
}
}
Para el 2 no se como hacerlo , ella me ha planteado (hecho esto):
for(i=n-2;i>0;i++){
for(j=i+1;j<n;j++){
min=999999;
for(k=i+1;k<j-1;k++){
r=C[i,k]+C[k,j];
if(r<min)
min=r;
}
}
}
Que creo que esta mal porque k va a valer lo mismo que j nunca va hacer la iteracion.
¿Me podeis dar ayudar?,comentar código , cualquier cosa es bien recibida
PD;No aparece bien la denicion recursiva del enunciado se supone que S(i,j) se abren llaves y aparcen los 2 casos
