师兄面试总结编程部分解答之五

最新推荐文章于 2021-06-29 10:43:34 发布

antter0510

最新推荐文章于 2021-06-29 10:43:34 发布

阅读量847

点赞数

分类专栏：工作文章标签： c++ 动态规划面试编程

本文链接：https://blog.csdn.net/antter0510/article/details/38875911

版权

工作专栏收录该内容

7 篇文章

订阅专栏

本文深入探讨了递归与动态规划算法的应用，通过青蛙跳楼梯问题和N×N棋盘走法实例，详细解析了如何使用递归和动态规划解决实际问题。包括字符全排列、八皇后问题等经典算法案例。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

五、递归

青蛙跳楼梯（每次跳1或2层，跳到N层有多少种跳法）

//青蛙跳楼梯（每次跳1或2层，跳到N层有多少种跳法）类似斐波那契数列
int frogJump(int level)
{
	int* select = new int[level];//表示到达第i层共有多少种跳法
	select[0] = 1;
	select[1] = 2;
	for(int i = 2; i < level; i++)
	{
		select[i] = select[i - 1] + select[i - 2]; 
	}
	printf("%d\n",select[level-1]);
	return select[level - 1];
}

3、N×N的棋盘，从一角走到另一角，只能走“日”字，即象棋中的马，问有多少种走法等

//N×N的棋盘，从一角走到另一角，只能走“日”字，即象棋中的马，问有多少种走法等
//形参N表示棋盘尺寸
int chessboard(int N)
{
	//所谓走“日”字，即为只能横向或纵向走一个单元格
	//grid(i, j) = grid(i - 1, j) + grid(i, j - 1)//动态规划
	int* grid = new int[N*N];
	//首先对左侧及上侧单元格进行初始化，初始化为1
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < N; j++)
		{
			if(i == 0 || j == 0)
				grid[i * N + j] = 1;
			else
			{
				grid[i * N + j] = grid[(i - 1) * N + j] + grid[i * N + j - 1];
			}
		}
	}
	return grid[ N*N - 1 ];
}

六、全排列

1、字符输出有多少种全排列（需递归调用二次）

//字符输出有多少种全排列,即输出字符所有组合可能，递归及非递归实现
//str为给定字符串
//递归形式
void swap(char* src,char* dest)
{
	char tmp = *src;
	*src = *dest;
	*dest = tmp;
}
void permutation_recu(char* str,char* begin)
{
	//遍历固定一个字符，将之后的片段继续遍历固定第一个字符，与剩余部分进行交换，
	if(*begin == '\0')
		printf("%s\n",str);
	//将所以字符依次放在第一个位置
	char* cur = begin;
	while(*cur != '\0')
	{
		swap(cur,begin);
		permutation_recu(str,begin + 1);
		swap(cur,begin);
		cur++;
	}
}

2、八皇后问题

/八皇后问题，得到最终可能的排列组合数
static int queue_count = 0;

bool judgeQueue(int queue[])
{
	for(int i = 1; i < 8; i++)
	{
		int row = i;
		int col = queue[i];

		for(int j = 0; j < i; j++)
		{
			int rowOld = j;
			int colOld = queue[j];

			if (colOld == col)
				return false;
			if (colOld - rowOld == col - row)
				return false;
			if(colOld + rowOld == row + col)
				return false;
		}
	}
	return true;
}
void eightQueue(int queue[],int begin)
{
	
	//每行中均含有一个皇后，之后的问题便是，如何在列方向进行八皇后的移动，
	//每个皇后同样共有八种移动可能，类似全排列思路，最复杂的解决方案，
	if(begin == 8) 
	{
		if(judgeQueue(queue))
			queue_count++;
		return;
	}
	for(int i = 0; i < 8; i++)
	{
		queue[begin] = i;
		eightQueue(queue,begin + 1);
	}
}
//解题太慢了，，，批评