如何获得memoized cut rod aux output算法的正确答案？ [英] How do i get correct answer of memoized cut rod aux output algorithm?

问题描述

我没有得到切割杆辅助算法实现的正确输出，我使用visual studio 2010实现Memoized Cut rod aux功能....



< pre lang =c ++> int max_val = 0 ;

int max（ int a， int b）
{
return （a> b）？a：b;
}
int cut_rod_aux（ int ， int ， int ）;
int cut_rod（ int ， int ）;

最有可能的错误出现在这部分代码中

  int  cut_rod_aux（ int  price []， int  n， int  r []）
 {
  if （r [n]> =  0 ）
 {
  return  r [n]; 
 cout<<   aux r =<< r<< endl ; 
} 
 如果（n ==  0 ）
 {
 max_val =  0 ; 
 cout<<   aux max val = 0<< endl; 
} 
  else  
 { / *  最可能是错误区域* /  
 max_val =  0 ; 
  for （ int  i =  1 ; i< n;> 
 {
 max_val = max（max_val，price [i] + cut_rod_aux（price，ni，r））; 
 cout<<   aux max val：<<< max_val<< endl; 
} 
 } 
 
r [n] = max_val; 
  return  max_val; 
} 
  int  cut_rod（ int  price []， int  n）
 {
  int  * r =  new   int  [n]; 
  for （ int  i =  0 ; i< n;> {
 r [i] =  0 ; 
 cout<<   i =<< i<<   r =<< r [i]<< endl; 
} 
  return  cut_rod_aux（price，n，r）; 
} 
  int  _tmain（ int  argc，_TCHAR * argv []）
 {
  int  arr [] = { 1 ， 5 ， 8 ， 9 ， 10 ， 17 ， 17 ， 20 }; 
 cout<<   output<< cut_rod（arr， 8 ）LT;< ENDL; 
  / *  输出应为22​​，根据coreman book * /  
 < span class =code-keyword> return   0 ; 
} 
 

我尝试过：



正确的输出应该是22，而不是20 ...

解决方案

你应该学会使用调试器尽快。而不是猜测你的代码在做什么，现在是时候看到你的代码执行并确保它完成你期望的。



调试器允许你跟踪执行逐行检查变量，你会看到有一点它会停止你所期望的。

在Visual Studio 2010中掌握调试 - 初学者指南 [ ^ ]

http://docs.oracle.com/javase/7/docs/technotes/tools/windows/jdb.html [ ^ ]

https://www.jetbrains.com/idea/help/debugging-your-first-java-application.html [ ^ ]



这条线至少可以说是奇怪的。缺少一段代码？

  for （ int  i =  1 ; i< n; >  

I not getting correct output for cut rod aux algorithm implementation, I am using visual studio 2010 for implementation of Memoized Cut rod aux function....

int max_val=0;

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

Most probably error is in this section of code

int cut_rod_aux(int price[], int n, int r[])
   {
        if(r[n]>=0)
          {
               return r[n];
                cout<<"aux r="<<r<<endl;
          }
        if (n==0)
          {
                max_val=0;
                cout<<"aux max val = 0"<<endl;
          }
        else
         {   /*most probably error area*/
              max_val = 0;
              for(int i=1; i<n;>
              {
                         max_val=max(max_val, price[i]+cut_rod_aux(price, n-i,r));
                         cout<<"aux max val: "<<max_val<<endl;
                  }
          }

       r[n]=max_val;
       return max_val;
   }
   int cut_rod(int price[], int n)
   {
        int *r = new int[n];
        for(int i=0; i<n;>                {
                r[i]=0;
                cout<<"i="<<i<<" r="<<r[i]<<endl;
            }
       return cut_rod_aux(price,n,r);
   }
   int _tmain(int argc, _TCHAR* argv[])
   {
          int arr[]={1, 5, 8, 9, 10, 17, 17, 20};
           cout<<"output "<<cut_rod(arr, 8)<<endl;
          /*output should be 22, as per coreman book*/
       return 0;
   }

What I have tried:

The correct output should be 22, instead it is giving 20...

解决方案

You should learn to use the debugger as soon as possible. Rather than guessing what your code is doing, It is time to see your code executing and ensuring that it does what you expect.

The debugger allow you to follow the execution line by line, inspect variables and you will see that there is a point where it stop doing what you expect.
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
http://docs.oracle.com/javase/7/docs/technotes/tools/windows/jdb.html[^]
https://www.jetbrains.com/idea/help/debugging-your-first-java-application.html[^]

This line is weird to say the least. piece of code missing ?

for(int i=1; i<n;>

这篇关于如何获得memoized cut rod aux output算法的正确答案？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！