学堂在线-程序设计基础-第六章

2022-08-29 20:54:29

文章目录

第六章 递推与动态规划

6.1 兔子数列问题

  先设定递推初值；再按照公式进行递推（常用循环实现）。

代码实现

//斐波那契数列 
#include <iostream>
using namespace std;

int main() 
{
	int n; 
	cout << "求第几个月的兔子个数： " ;
	cin >> n ;
	
	int dang_yue = 1;
	int shang_yue = 1;
	int qian_yue = 1;
	for (int i = 2; i < n; i ++)
	{
		dang_yue = qian_yue + shang_yue;
		qian_yue = shang_yue;
		shang_yue = dang_yue;
	} 
 
	cout << "第" << n << "个月的兔子总数为：" << dang_yue << endl; 
	return 0;
}

6.2 分鱼问题

6.2.2 从 A 到 E 递推-代码实现

//分鱼问题 
#include <iostream>
using namespace std;

int main() 
{
	int num[5]={0};
	for (num[0] = 1; ; num[0]++)
	{
		if (num[0] % 5 != 1)
			continue;
		int i;
		for (i = 1; i <= 4; i++)
		{
			num[i] = num[i-1] / 5 * 4;
			if (num[i] % 5 != 1)
				break;
		}
		if (i <= 4)
			continue;
		break;
	}
	for(int i = 0; i < 5; i++)
	cout << num[i] << " " << endl; 
	return 0;
}

6.2.3 从 E 到 A 递推-代码实现

  通过逻辑分析，优化枚举初值和枚举步长，提高代码运行效率

//分鱼问题 
#include <iostream>
using namespace std;

int main() 
{
	int num[5]={0};
	for (num[0] = 16; ; num[0]+=20)
	{
		int i;
		for (i = 0; i <4; i++)
		{
			if (num[i]%4!=0)
				break;
			num[i+1]=num[i]/4*5+1;
		}
		if (i <4)
			continue;
		break;
	}
	for(int i = 0; i < 5; i++)
	cout << num[i] << " " << endl; 
	return 0;
}

不用数组辅助-代码实现

  不用数组，反而没法用循环简化代码，不知道有没有其他更好的实现方式。

//分鱼问题 
#include <iostream>
using namespace std;

int main() 
{
	int num_a,num_b,num_c,num_d,num_e=0;
	for (num_e = 16; ; num_e+=20)
	{
		if (num_e%4!=0)
			continue;
		num_d=num_e/4*5+1;
		if (num_d%4!=0)
			continue;
		num_c=num_d/4*5+1;
		if (num_c%4!=0)
			continue;
		num_b=num_c/4*5+1;
		if (num_b%4!=0)
			continue;
		num_a=num_b/4*5+1;
		break;
	}
	cout << num_a << "\n" << num_b << "\n"
		 << num_c << "\n" << num_d << "\n"
		 << num_e << endl; 
	return 0;
}

6.3 橱窗的插画问题

  求最优值问题：

  • 首先用枚举法，枚举出所有的情况，对于每个情况计算美感和并保存最大值；
  • 由于枚举法，每次计算中有许多重复计算，所以用一个数组存储一些部分插花方案的美感值，采用递归法计算，可以省去一部分计算，但是由于定义了一个数组，需要额外存储空间；
  • 采用动态规划，计算并存储部分最优方案，极大优化了存储空间的占用；

6.3.3 用枚举思想解题

//橱窗插花，用枚举思想解题
#include <iostream>
using namespace std;

const int V = 5, F = 3;
//把一个数num表示为二进制数组binary[]
void ToBinary(int num, int binary[V])
{
	for(int i = 0; i < V; i++)
	{
		binary[i] = num & 1;	//按位与，取最低为 
		num = num >> 1; 		//右移一位 
	}
} 
//计算binary中1的个数
int count1(int binary[V])
{
	int count = 0;
	for (int i = 0; i < V; i++)
		count += binary[i];
	return count;
} 

int main()
{	
	int beauty[V][F] = {{7  , 5  , -21},
						{23 , 21 , 5  },
						{-5 , -4 , -4 },
						{-24, 10 , -20},
						{16 , 23 , 20 }};//定义美感数组
	int best_beauty = 0, best_put = 0;//定义最大美感得分，和插花方案
	
	//枚举，从0到（2^V-1）
	for (int i = 0; i < (1<<V); i++)
	{
		int binary[V] = {0};
		ToBinary(i, binary);//得到插花方案binary[] 
		if (count1(binary) != F)//花的数量不对，枚举下一个方案
			continue;
		//计算美感得分
		int sum_beauty = 0;
		for (int vase = 0, flower = 0; vase < V; vase++)
			if (binary[vase] == 1)//该花瓶中插的有花
			{
				sum_beauty += beauty[vase][flower];
				flower++; 
			} 
		//保存最大美感和插花方案
		if (sum_beauty > best_beauty)
		{
			best_beauty = sum_beauty;
			best_put = i;
		} 
	} 

	//输出答案
	cout << "最大美感得分：" << best_beauty << endl;
	cout << "插花方案：";
	int best_binary[V] = {0};
	ToBinary(best_put, best_binary); 
	for (int vase = 0, flower = 1; vase < V; vase++)
	{
		if (best_binary[vase] == 1)
		{
			cout << flower;
			flower++;
		}
		else
			cout << 0;
	}
	return 0;
}

6.3.4 采用递归的优化算法

//橱窗插花，采用递归的优化算法 
#include <iostream>
using namespace std;

const int V = 5, F = 3;
//把一个数num表示为二进制数组binary[]
void ToBinary(int num, int binary[V])
{
	for(int i = 0; i < V; i++)
	{
		binary[i] = num & 1;	//按位与，取最低为 
		num = num >> 1; 		//右移一位 
	}
} 
//计算binary中1的个数
int count1(int binary[V], int &high)
{
	int count = 0;
	high = -1;
	for (int i = 0; i < V; i++)
		if (binary[i] == 1)
		{
			high = i;
			count++;
		}
	return count;
} 

int main()
{	
	int beauty[V][F] = {{7  , 5  , -21},
						{23 , 21 , 5  },
						{-5 , -4 , -4 },
						{-24, 10 , -20},
						{16 , 23 , 20 }};//定义美感数组
	int best_beauty = 0, best_put = 0;//定义最大美感得分，和插花方案
	
	int partial_sum[1<<V] = {0};
	//枚举，从0到（2^V-1）
	for (int i = 1; i < (1<<V); i++)
	{
		int binary[V] = {0};
		ToBinary(i, binary);
		int high;
		int flowers = count1(binary, high);
		if (flowers > F)//大于F非法方案，小于F局部方案，等于F完整插花方案 
			continue;
		partial_sum[i] = partial_sum[i-(1<<high)] + beauty[high][flowers-1];
		if (flowers == F && partial_sum[i] > best_beauty)
		{
			best_beauty = partial_sum[i];
			best_put = i;
		}	
	}

	//输出答案
	cout << "最大美感得分：" << best_beauty << endl;
	cout << "插花方案：";
	int best_binary[V] = {0};
	ToBinary(best_put, best_binary); 
	for (int vase = 0, flower = 1; vase < V; vase++)
	{
		if (best_binary[vase] == 1)
		{
			cout << flower;
			flower++;
		}
		else
			cout << 0;
	}
	return 0;
}

6.3.5.1 动态规划解题，输出方案1

//橱窗插花，动态规划，输出方案1 
#include <iostream>
using namespace std;

const int V = 5, F = 3;
//把一个数num表示为二进制数组binary[]
void ToBinary(int num, int binary[V])
{
	for(int i = 0; i < V; i++)
	{
		binary[i] = num & 1;	//按位与，取最低为 
		num = num >> 1; 		//右移一位 
	}
} 

int main()
{	
	int beauty[V][F] = {{7  , 5  , -21},
						{23 , 21 , 5  },
						{-5 , -4 , -4 },
						{-24, 10 , -20},
						{16 , 23 , 20 }};//定义美感数组
	
	int best_partial[V+1][F+1] = {{0}};
	int best_put[V+1][F+1] = {{0}};
	//m个花瓶插n朵花的局部最优解 
	for (int m = 1; m <= V; m++)
		for (int n = 1; n <= m && n <= F; n++)
		{
			best_partial[m][n] = best_partial[m-1][n-1] + beauty[m-1][n-1];
			best_put[m][n] = best_put[m-1][n-1] + (1<<(m-1));
			if (n < m && best_partial[m][n] < best_partial[m-1][n])
			{
				best_partial[m][n] = best_partial[m-1][n];
				best_put[m][n] = best_put[m-1][n];
			}
			cout << m << " "
				 << n << " "
				 << best_partial[m][n] << " "
				 << best_put[m][n] << endl;
		}
	

	//输出答案
	cout << "最大美感得分：" << best_partial[V][F] << endl;
	cout << "插花方案：";
	int best_binary[V] = {0};
	ToBinary(best_put[V][F], best_binary); 
	for (int vase = 0, flower = 1; vase < V; vase++)
	{
		if (best_binary[vase] == 1)
		{
			cout << flower;
			flower++;
		}
		else
			cout << 0;
	}
	return 0;
}

6.3.5.2 动态规划，输出方案2

  计算量和存储空间都得到优化，但输出为倒序

//橱窗插花，动态规划，输出方案2，回溯输出逆序 
#include <iostream>
using namespace std;

const int V = 5, F = 3;
//把一个数num表示为二进制数组binary[] 

int main()
{	
	int beauty[V][F] = {{7  , 5  , -21},
						{23 , 21 , 5  },
						{-5 , -4 , -4 },
						{-24, 10 , -20},
						{16 , 23 , 20 }};//定义美感数组
	
	int best_partial[V+1][F+1] = {{0}};
	bool best_put[V+1][F+1] = {{false}};
	//m个花瓶插n朵花的局部最优解 
	for (int m = 1; m <= V; m++)
		for (int n = 1; n <= m && n <= F; n++)
		{
			best_partial[m][n] = best_partial[m-1][n-1] + beauty[m-1][n-1];
			best_put[m][n] = true;
			if (n < m && best_partial[m][n] < best_partial[m-1][n])
			{
				best_partial[m][n] = best_partial[m-1][n];
				best_put[m][n] = false;
			}
			cout << m << " "
				 << n << " "
				 << best_partial[m][n] << " "
				 << best_put[m][n] << endl;
		}
	

	//输出答案
	cout << "最大美感得分：" << best_partial[V][F] << endl;
	cout << "插花方案：";
	for (int m = V, n = F; m > 0; )
	{
		if (best_put[m][n])
		{
			cout << n;
			m--;
			n--;
		}
		else
		{
			cout << '0';
			m--;
		}
	}
	return 0;
}

6.3.5.3 动态规划，输出方案2，正序输出

  思路是从第3朵花开始从第5个花瓶开始逆向插花：
  所有的循环和递归方式不变，只是计算时将美感数组beauty[][]转置；
  同样在输出时注意，逆序输出则第一个输出的是第1朵花；
学堂在线-程序设计基础-第六章

//橱窗插花，动态规划,方案2，正序输出 
#include <iostream>
using namespace std;

const int V = 5, F = 3;

int main()
{	
	int beauty[V][F] = {{7  , 5  , -21},
						{23 , 21 , 5  },
						{-5 , -4 , -4 },
						{-24, 10 , -20},
						{16 , 23 , 20 }};//定义美感数组
	
	int best_partial[V+1][F+1] = {{0}};
	bool best_put[V+1][F+1] = {{false}};
	//m个花瓶插n朵花的局部最优解 
	for (int m = 1; m <= V; m++)
		for (int n = 1; n <= m && n <= F; n++)
		{
			best_partial[m][n] = best_partial[m-1][n-1] + beauty[V-m][F-n];
			best_put[m][n] = true;
			if (n < m && best_partial[m][n] < best_partial[m-1][n])
			{
				best_partial[m][n] = best_partial[m-1][n];
				best_put[m][n] = false;
			}
			cout << m << " "
				 << n << " "
				 << best_partial[m][n] << " "
				 << best_put[m][n] << endl;
		}
	

	//输出答案
	cout << "最大美感得分：" << best_partial[V][F] << endl;
	cout << "插花方案：";
	for (int m = V, n = F; m >= 1; )
		if (best_put[m][n] == true)
		{
			cout << F-n+1;
			m--;
			n--;
		}
		else
		{
			cout << 0;
			m--;
		}
	return 0;
}

6.4 最长公共子序列问题

  递归初始值的确定，需要仔细分析，本节课中的做法非常巧妙；
  存放长度的数组，可以用来进行比较，作为递归方向的判据；
  存放方向的数组，作为递归方向的标志，可以作为输出时回溯的判定；

//最长公共子序列问题 
#include <iostream>
#include <cstring>
using namespace std;

const int M = 10, N = 10;

int main() 
{
	char A[9] = "abcbdacb";		//要比较的字符串A 
	char B[6] = "bdcab";		//要比较的字符串B 
	int m = strlen(A);			//字符串A的长度作为循环范围 
	int n = strlen(B);			//字符串B的长度作为循环范围 
	int lcs[M][N];				//存放公共子序列的长度值 
	int decision[M][N];			//存放公共子序列计算时的取舍方向 
	enum		//定义取舍方向的标志 
	{
		I_J,	//i和j相等，子序列长度加1，lcs[i][j]=1+lsc[i+1][j+1] 
		I_1,	//i和j不相等，i+1比j公共子序列长度大，lsc[i][j]=lcs[i+1][j]
		J_1		//i和j不相等，j+1比i公共子序列长度大，lsc[i][j]=lcs[i][j+1] 
	};
	
	for (int i = 0; i < m+1; i++)
		lcs[i][n] = 0;	//初始化递归初值
	for (int j = 0; j < n+1; j++)
		lcs[m][j] = 0;	//初始化递归初值
	for (int i = m-1; i >= 0; i--)	//递归运算
		for (int j = n-1; j >= 0; j--)
			if ( A[i] == B[j])
			{
				lcs[i][j] = 1 + lcs[i+1][j+1];
				decision[i][j] = I_J;
			}
			else if ( lcs[i+1][j] > lcs[i][j+1])
			{
				lcs[i][j] = lcs[i+1][j];
				decision[i][j] = I_1;
			}
			else
			{
				lcs[i][j] = lcs[i][j+1];
				decision[i][j] = J_1;
			}
	
	for (int i = 0, j = 0; i < m && j < n; )	//回溯输出
		switch (decision[i][j])
		{
		case I_J:
			cout << A[i];
			i++;
			j++;
			break;
		case I_1:
			i++;
			break;
		case J_1:
			j++;
			break;
		}
	
	return 0;
}

语法自测-试题答案

学堂在线-程序设计基础-第六章
学堂在线-程序设计基础-第六章

学堂在线-程序设计基础-第六章
学堂在线-程序设计基础-第六章

上一篇：android Realm 优化


下一篇：Realm数据库使用教程（二），android工程师面试题目