Programa as vezes retorna lixo de memoria [RESOLVIDO]

volckster
(usa Ubuntu)

Enviado em 03/11/2020 - 15:00h

Eu preciso passar o pseudo codigo anexado como imagem para o C++, esse algoritmo é o problema de Corte de Hastes, eu consegui passar todo o algoritmo para o C++ porem quando eu executo o algoritmo ele as vezes mostra a resposta certa esperada que é 30, e as vezes retorna lixo de memoria (acredito eu que seja lixo de memoria posso estar errado) eu procurei varias vezes no codigo para encontrar onde esta o problema porem nao encontrei, gostaria que alguem pudesse me ajudar a encontra-lo, desde ja agradeço


#include <iostream>
#include <limits.h>
using namespace std;

int max(int a, int b) { return (a > b)? a : b;}

int MemoizedCutRodAux(int p[],int n,int r[])
{
int aux;

if (r[n] >= 0)
{
return r[n];
}

if (n == 0)
{
aux=0;
}

else
{
aux=INT_MIN;

for(int i=1;i<=n;i++)
{
aux= max(aux,p[i-1]+MemoizedCutRodAux(p,n-i,r));
}
}

r[n]=aux;

return aux;
}

int MemoizedCutRod(int preco[],int n)
{
int r[n];

for(int i=0;i<n;i++)
{
r[i]= INT_MIN;
}

return MemoizedCutRodAux(preco,n,r);
}


int main()
{
int Vetor[] = {1, 5, 8, 9, 10, 17, 17, 20,24,30};
int tamanho = sizeof(Vetor)/sizeof(Vetor[0]);
cout<<"Maximo valor obtido é "<<MemoizedCutRod(Vetor, tamanho);
return 0;
}

leandropscardua
(usa Ubuntu)

Enviado em 03/11/2020 - 18:03h

Bom, não rodei o código, mas parece q o problema pode estar na linha
for(int i=1;i<=n;i++)
Um dos dois loops parece estar incorreto de acordo c o pseudo código. Duas sugestões:
1. O linux tem um debugador p c e c++, o gdb. Se estiver quebrando mto a cabeça p encontrar o erro rodeo nele
2. Mude seu programa p pegar o vetor pela linha de comando. Daí vc cria vários arquivos c vetores de entrada e outro c nome semelhante mas c a saída desejada. Depois vc roda o programa pegando cada entrada e compara a saída esperada c o resultado obtido. Assim vc cria um script p testar automaticamente seu teste e cada vez q vc fizer alguma mudança é só rodar a massa de testes automaticamente.

volckster
(usa Ubuntu)

Enviado em 03/11/2020 - 21:44h

consegui encontrar o problema, realmente estava nas respetiçoes, e nao somente em uma e sim nas 2 repetiçoes, e tambem na criaçao do vetor int r[n], o correto seria int r[n+1] e em seguida a repetiçao para preenche-lo ficaria

for(int i=0;i<n+1;i++)
{
r[i]= INT_MIN;
}

e na segunda repetiçao o erro estava na criaçao do indice int i=1, eu estava fazendo assim pois no pseudo codigo estava assim, mas inicializando ele com zero e mundando a condiçao para i<n o codigo funciona de maneira correta, e na hora de passar parametro para recursao em aux= max(aux,p[i-1]+MemoizedCutRodAux(p,n-i,r)); eu usava p[i-1] pois eu precisava acessar a primeira posiçao do vetor, porem agora com i inicializando com 0 eu nao preciso subtrair 1 e com isso eu tbm preciso mudar o argumento a seguir que era n-i para n-i-1, assim obtendo o resultado esperado, entao essa repetiçao ficaria correto da seguinte maneira:

for(int i=0;i<n;i++)
{
aux= max(aux,p[i]+MemoizedCutRodAux(p,n-i-1,r));
}

assim o codigo sempre que executado me retorna o resultado esperado parar sua finalidade, obrigado pela ajuda pude encontrar o erro com a dica que voce me deu, obrigado