【C/C++练习题】剪绳子

《剑指Offer》面试题14：剪绳子

1 题目

给你一根长度为n绳子，请把绳子剪成m段（m、n都是整数，n>1并且m≥1）。每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]*k[1]*…*k[m]可能的最大乘积是多少？例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。

2 算法分析&问题分析

动态规划：适用于求问题的最优解。首先从上向下分析问题，要将一个大问题划分成两个子问题，遍历每一种方案并确定当前最优解，分别对子问题进一步划分求最优解，直到最小问题的最优解求出。将小问题的最优解回归，解出问题的最优解。

由于自上而下的递推公式会产生多个重复的子问题。因此选用自下而上迭代的方法，从已知条件求出最优解。

要使用一个数组来记录每一个子问题的最优解。

1. 绳长 n > 3，利用迭代方式进行动态规划

贪心算法：基于一个计算策略（有数学方法证明），每一步都是一个贪婪的选择。

1. 绳长 n >= 5 剪长度为3的绳子
2. 绳长 n == 4 剪成两段长度为2的绳子

3 代码分析

  

   

    

     

    
    

     

      #include "iostream"
     
    
   

    

     

    
    

     

      #include <cstring>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //动态规划求解
     
    
   

    

     

    
    

     

      //输入：绳子的长度 length
     
    
   

    

     

    
    

     

      //返回：最优解
     
    
   

    

     

    
    

     

      int max_to_cut(int length)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	//1.考虑特殊情况下的最优解
     
    
   

    

     

    
    

     
	if (length < 2) return 0;
     
    
   

    

     

    
    

     
	if (length == 2) return 1;
     
    
   

    

     

    
    

     
	if (length == 3) return 3;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	int* products = new int [length + 1];	//用于纪录所有子问题的最优解
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//2.设置已知小问题的最优解
     
    
   

    

     

    
    

     

      	products[1] = 1;
     
    
   

    

     

    
    

     

      	products[2] = 2;
     
    
   

    

     

    
    

     

      	products[3] = 3;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//3.迭代法进行动态规划
     
    
   

    

     

    
    

     
	for (int i = 4;i <= length;i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		int max = i;
     
    
   

    

     

    
    

     
		//遍历每一种可行的切割方案，选出最优
     
    
   

    

     

    
    

     
		for (int j = 1;j <= i/2; j++)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			int product = products[j] * products[i-j];
     
    
   

    

     

    
    

     
			if (max < product)
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     

      				max = product;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		//记录该问题的最优解
     
    
   

    

     

    
    

     

      		products[i] = max; 
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	delete [] products;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//4.返回最优解
     
    
   

    

     

    
    

     
	return products[length];
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //贪婪算法求解
     
    
   

    

     

    
    

     

      //输入：绳子的长度 length
     
    
   

    

     

    
    

     

      //返回：最优解
     
    
   

    

     

    
    

     

      int new_max_to_cut(int length)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	//1.考虑特殊情况下的最优解
     
    
   

    

     

    
    

     
	if (length < 2) return 0;
     
    
   

    

     

    
    

     
	if (length == 2) return 1;
     
    
   

    

     

    
    

     
	if (length == 3) return 3;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//2.尽可能剪长度为3的绳子
     
    
   

    

     

    
    

     
	int n_length3 = length/3;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//3.剩下长度为4的时候，不必要在剪断了
     
    
   

    

     

    
    

     
	if (length % 3 == 1)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		n_length3 -= 1;
     
    
   

    

     

    
    

     
		return (pow(3, n_length3) * pow(2, 2));	//返回最优解，长度为4的部分剪短成2+2
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//4.通常情况下，返回的最优解
     
    
   

    

     

    
    

     
	int n_length2 = length - n_length3*3;
     
    
   

    

     

    
    

     
	return (pow(3, n_length3) * n_length2);
     
    
   

    

     

    
    

     
	
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(int argc, char const *argv[])
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int n;
     
    
   

    

     

    
    

     

      	cin >> n;
     
    
   

    

     

    
    

     
	// cout << endl;
     
    
   

    

     

    
    

     

      	cout << max_to_cut(n) << endl;
     
    
   

    

     

    
    

     

      	cout << new_max_to_cut(n) << endl;
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

4 运行结果

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/98431603