★递归递推★_C

---------------------------------------------------------------------------------------------------------------------------------

①递归

92-递归实现指数型枚举

94-递归实现组合型枚举

1209-带分数

②递推

717- 简单斐波那契

1208-翻硬币

95-费解的开关

①递归 92-递归实现指数型枚举

题目：

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式：

输入一个整数 n。

输出格式：

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 11 个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围：

1≤n≤15

输入样例：

输出样例：

分析：

DFS求解

第一步：画递归树，对于小于等于n的数，每一个数只有两种选择：选或不选，运用深搜先全部选或不选，再逐级返回输出答案

递归树：

第二步：思路转化成代码

递归的临界条件是什么？数组下标从1开始，u>n输出

需要的变量：开一个状态bool数组，来表示该数有没有被选

本题要求：只是要求同行内升序，不同行之间不做要求

代码：

#include
using namespace std;

const int N=20;
bool state[N];
int num[N];
int n;

void dfs(int u)
{
	if(u>n)
	{
		for(int i=1;i<=n;i++)
			if(state[i]==1)
				cout<>n;
	
	dfs(1);
	
	
	return 0;
}

---------------------------------------------------------------------------------------------------------------------------------

94-递归实现组合型枚举

题目详情：

从 1∼n这 n 个整数中随机选出 m 个，输出所有可能的选择方案。

输入格式

两个整数 n,m 在同一行用空格隔开。

输出格式

按照从小到大的顺序输出所有方案，每行 1个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。

数据范围

n>0 ,
0≤m≤n ,
n+(n−m)≤25

输入样例：
5 3
输出样例：
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 
思考题：如果要求使用非递归方法，该怎么做呢？

分析：

题目要求：n最大值能取到24，所以N开得要比24大；同行升序，不同行按对应下标升序

第一步：画递归树：

第二步：转换成代码

1、题目要求同行升序，那么我们需要设置一个状态数，记录当前枚举到哪了，再次进入递归时从记录的状态数开始枚举，可以保证同行和不同行内都为升序

2、dfs(int u,int state):一个记录下标，一个记录已经枚举到的数

3、一次递归结束条件：u>m

代码

//4.4重做 
#include
using namespace std;

const int N=20;
int num[N];
int n,m;
int flag;

void dfs(int u,int state)
{
	if(u>m)
	{
		for(int i=1;i<=m;i++)
			cout<>n>>m;
	
	dfs(1,1);
	
	return 0;
}

另一种解法代码（不设置状态数）：

分析

1、传入的参数即为当前枚举到哪了

2、设置一个flag，用来表示现在已经枚举了几个数了

3、一次递归结束条件变为：flag==m

#include
#include
#include
#include
#include
using namespace std;

const int N=110;
int n,m;
int flag=0;
int p[N];

void dfs(int u)
{
	//边界条件-当存储的数为m时
	if(flag==m)
	{
		for(int j=1;j<=flag;j++)
			cout<

 
--------------------------------------------------------------------------------------------------------------------------------- 
 
1209-带分数 
题目详情： 
 
 
 数据范围 
 1≤N<10^6 
 
分析： 
 
 1、将除法转换成除法：n=a+b/c  -->  n*c=a*c+b ;a为输入 
 2、暴搜，先用递归求出0~9的全排列，然后将求出的数通过循环分为三段分别为a,b,c; 
         如果满足n*c=a*c+b，则为答案 
 
 代码： 
#include
#include 
using namespace std;

const int N=1e6+10;
int n;			    //需要求的目标数
int num[10];        //存放全排列的结果
bool st[10];        //全排列记录数是否被用过
int res=0;          //最终结果

int arr(int l,int r)
{
	int ans=0;//划分好的答案
	for(int i=l;i<=r;i++)
	{
		ans=ans*10+num[i];
	} 
	return ans;
	
} 

void dfs(int u)
{
	if(u>9)
	{
        //暴力将每个数划分为三段
		for(int i=1;i<=7;i++)
			for(int j=i+1;j<=8;j++)
			{
				int a=arr(1,i);
				int b=arr(i+1,j);
				int c=arr(j+1,9);
				
			    //满足题设条件
				if(n*c==a*c+b)
				{
					res++;
				}
			}
			
			return ;
	}
	
	//对数进行全排列 
	for(int i=1;i<=9;i++)
	{
		if(!st[i])
		{
			st[i]=true;
			num[u]=i;
			dfs(u+1);
			st[i]=false;
		}
	}
}

int main()
{
	cin>>n;
	
	dfs(1);
	
	cout<
 
另一种解法： 
 
 利用函数：next_permutation(num+1,num+9)； 
  
 对于next_permutation函数，其函数原型为： 
      #include  
      bool next_permutation(iterator start,iterator end) 
  
 对本题中的num[1]~num[9]进行升序排序，但注意，只能从原数组现有的序列开始升序排序，所以原数组必须初始化为num[10]={0,1,2,3,4,5,6,7,8,9}（假如下标从1开始的话） 
 假如传的为next_permutation(num+1,num+4)，只会对1,2,3,4进行升序排序，5~9顺序不变 
 如图： 
  
  
 
 
next_permutation用法链接https://www.cnblogs.com/kingwz/p/15187020.html 
代码：  
//函数全排列
#include
#include
using namespace std;

int n;
int num[10];
int ans=0;

int calt(int l,int r)
{
	int res=0;
	for(int i=l;i<=r;i++)
	{
		res=res*10+num[i];
	}
	
	return res;
}

int main()
{
	cin>>n;
	for(int i=1;i<=9;i++)	num[i]=i;
	do{
		for(int i=1;i<8;i++)
			for(int j=i+1;j<9;j++)
			{
				int a=calt(1,i);
				int b=calt(i+1,j);
				int c=calt(j+1,9);
				
				if(a*n==b*a+c) ans++;
			}
	}while(next_permutation(num+1,num+10));
	
	cout<
 
--------------------------------------------------------------------------------------------------------------------------------- 

②递推 
 
递推介绍:递推是按照一定的规律来计算序列中的每个项，通常是通过计算前面的一些项来得出序列中的指定项的值。

其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。

 
 
717- 简单斐波那契 
题目详情: 
 
 代码: 
#include
using namespace std;

const int N=1e6+10;
int f[N]; 

int main()
{
	int n;
	cin>>n;
	f[0]=0;
	f[1]=1;
	
	//递推求f[i]
	for(int i=2;i
 

 
1208-翻硬币 
题目详情:  
 
 分析: 
 
 题目要求:翻动两个相邻的硬币为一步 *** 作 
         其实本题很简单,每一个硬币最多进行一步 *** 作,如果进行两步 *** 作相当于没动,要想达到最终结果,我们只需逐一比较 
 
代码:  
#include 
#include
using namespace std;

int cnt=0;
int main()
{
	string a,b;
	cin>>a>>b;
	
	for(int i=0;i
 

95-费解的开关 
题目详情 
 
 你玩过“拉灯”游戏吗？ 
 25 盏灯排成一个 5×5 的方形。

 
 每一个灯都有一个开关，游戏者可以改变它的状态。

 
 每一步，游戏者可以改变某一个灯的状态。

 
 游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

 
 我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。

 
 下面这种状态 
 10111
01101
10111
10000
11011
 
 在改变了最左上角的灯的状态后将变成： 
 01111
11101
10111
10000
11011
 
 再改变它正中间的灯后状态将变成： 
 01111
11001
11001
10100
11011
 
 给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。

 
 输入格式 
 第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。

 
 以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。

 
 每组数据描述了一个游戏的初始状态。

 
 各组数据间用一个空行分隔。

 
 输出格式 
 一共输出 n行数据，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

 
 对于某一个游戏初始状态，若 6 步以内无法使所有灯变亮，则输出 −1。

 
 数据范围 
 0 
 
输入样例： 
 3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111
 
 输出样例： 
 3
2
-1 
 
分析：  
 
     首先,我们需要明确的是,当第一行唯一确定时,那么按法便唯一确定
     为什么呢?我们肯定是一行一行的将灯泡变亮,第一行的灯泡只能由第二行来决定,因为一旦你动了第一行的开关,
 它相邻的灯泡一定会改变,如果相邻灯泡变暗且是改行最后一个灯光,那我们就必须再按相邻的这个灯泡开关,可原来点亮的灯泡又暗了, 
 这样十分麻烦且不好计算,所以我们用下一行的灯泡来决定上一行的灯泡.那么问题又来了,相同的灯泡最多按一次,因为按
 两次相当于没按,所以,当第一行确定时,整个开关的按法就确定了, 该行的灯泡必须由下一行相应的灯泡点亮
     所以,我们只要把第一行所有的情况求出来,再针对每一种情况求解即可
    总结:每一行开关的 *** 作完全被前一行灯泡的亮灭状态所决定  
 要解决的问题:
 1.如何枚举第一行的 *** 作 (一行5个灯光，一共有2^5-1个状态)
     位运算,定义op（op<=31）,判断op对应二进制的每个位置上是1还是0,如果是1,就对第一行该位置的灯泡进行 *** 作  (如3的二进制表示00011，那么对第4和5个灯光的开关进行 *** 作)
2.turn(x,y):灯光坐标,改变灯光及相邻灯光的状态
     定义偏移量:(-1,0),(1,0),(0,0),(0,-1),(0,1),分别表示上下左右的位置 
 3.时间复杂度:32*25*5*500 
 
 
memcpy函数用法https://www.runoob.com/cprogramming/c-function-memcpy.html 
 
代码 ： 
#include
#include
#include
using namespace std;


const int N=10;
char g[N][N],backup[N][N];
int dx[5]={-1,0,1,0,0},dy[5]={0,1,0,-1,0};	//偏移量，用来改变一个灯光周围灯光的状态


void turn(int x,int y)
{
	for(int i=0;i<5;i++)
	{
		int a=x+dx[i];
		int b=y+dy[i];
		
        //判断是否越界，越界就直接进行下一次循环
		if(a<0||a>=5||b<0||b>=5) continue;
		
		if(g[a][b]=='0') g[a][b]='1';
		else g[a][b]='0';
	}
} 

int main()
{
	int q;	//q组数据
	cin>>q;
	while(q--)
	{
		//输入一组的数据 
		for(int i=0;i<5;i++) cin>>g[i];
		
		
		
		int res=100; 
		for(int op=0;op<32;op++)
		{
			//对原始数据进行备份，因为要进行32次循环每次循环需要在原始数据上操作 
			memcpy(backup,g,sizeof g);
			
			int step=0;	//记录步数
			
			//对第一行的5个数据进行操作 
			for(int i=0;i<5;i++)
			{
				if(op>>i&1)	//如果op二进制的第5-i位为1，就对第一行的该灯光进行 *** 作 
				{
					step++;
					turn(0,4-i); 
				}
			} 
			
			//如果1~4行的灯光为灭，我们需要 *** 作一下
			//即按一下下一行j列的灯光开关 
			for(int i=0;i<4;i++)
				for(int j=0;j<5;j++)
				{
					if(g[i][j]=='0')
					{
						step++;
						turn(i+1,j);
					}
				}
		
			//对一组数据检测完后，检查是否灯全亮
			int dark=1;
			for(int i=0;i<5;i++)
				if(g[4][i]=='0') 
				{
					dark=0;
					break;
				}
			
			//如果灯光全亮，更新答案 
			if(dark==1) res=min(res,step); 
			
			//对数据进行恢复 
			memcpy(g,backup,sizeof g);	
		}
		
		//不可以将灯光的全亮检查放在这里
		//因为这只能判断一种情况，即当op=31时对灯光进行操作的情况 
		
		//进行输出	
		if(res>6)
			cout<<-1<
 
					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/langs/564786.html

★递归递推★

发表评论

评论列表（0条）