devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

专题一：递推与递归

作者：你好赵伟 | 2024-08-01 22:51:39

赞

踩

专题一：递推与递归

递归

 例题

 递归实现指数型枚举

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

输入格式

输入一个整数 n。

输出格式

每行输出一种方案。

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

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

各行（不同方案）之间的顺序任意。

数据范围

1≤n≤15

输入样例：
3
输出样例：
  1.  
  2. 3
  3. 2
  4. 2 3
  5. 1
  6. 1 3
  7. 1 2
  8. 1 2 3

  1. import java.util.*;
  2. public class Main{
  3.     static int N=16;
  4.     static int n;
  5.     static int []st=new int[N];    //表状态，0表示未考虑，1表示选，2表示不选
  6.     static void df(int u){
  7.         if(u>n){    //递归出口，输出选择的数
  8.             for(int i=1;i<=n;i++){
  9.                 if(st[i]==1)
  10.                     System.out.print(i+" ");
  11.             }
  12.             System.out.println();
  13.             return ;
  14.         }
  15.         //也可不恢复现场
  16.         st[u] =2;   //未选择，递归第一个选的分支
  17.         df(u+1);
  18.         st[u] =0;   //恢复现场
  19.         
  20.         st[u]=1;//第二个分支，选了
  21.         df(u+1);
  22.         st[u]=0;//恢复现场
  23.     }
  24.     
  25.     public static void main(String[] args){
  26.         Scanner scan =new Scanner(System.in);
  27.         n=scan.nextInt(); 
  28.         df(1);
  29.         scan.close();
  30.     }
  31. }

 递归实现排列型枚举

把 1∼n 这 n个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式

一个整数 n。

输出格式

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

首先，同一行相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围

1≤n≤9

输入样例：
3
输出样例：
  1. 1 2 3
  2. 1 3 2
  3. 2 1 3
  4. 2 3 1
  5. 3 1 2
  6. 3 2 1

  1. import java.util.*;
  2. public class Main{
  3.     static int N=10;
  4.     static int[] st=new int[N];         //存放第u个位置放什么数
  5.     static boolean[] use=new boolean[N];//表示是否选用了i
  6.     static int n;
  7.     public static void dfs(int u){
  8.         if(u>n){                    //递归出口,表示u个位置都已存放数
  9.             for(int i=1;i<=n;i++){
  10.                 System.out.print(st[i]+" ");
  11.             }
  12.             System.out.println();
  13.             return ;
  14.         }
  15.         //枚举每个分支
  16.         for(int i=1;i<=n;i++){
  17.             if(!use[i]){    //如果数i没有用过
  18.                 st[u]=i;    //第u个位置放i
  19.                 use[i]=true;
  20.                 dfs(u+1);
  21.                 //恢复现场
  22.                 st[u]=0;    //第u个位置未选用i
  23.                 use[i]= false;
  24.             }
  25.         } 
  26.     }
  27.     
  28.     public static void main(String[] args){
  29.         Scanner scan=new Scanner(System.in);
  30.         n=scan.nextInt();
  31.         dfs(1);
  32.         scan.close();
  33.     }
  34. }

时间复杂度：n*(1+n+n(n-1)+......+n!)<n*3n!

递归实现组合型枚举

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

 
输入格式

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

输出格式

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

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

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

数据范围

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

输入样例：
5 3
输出样例：
  1. 1 2 3 
  2. 1 2 4 
  3. 1 2 5 
  4. 1 3 4 
  5. 1 3 5 
  6. 1 4 5 
  7. 2 3 4 
  8. 2 3 5 
  9. 2 4 5 
  10. 3 4 5 

  1. import java.util.*;
  2. public class Main{
  3.     static int N=30;
  4.     static int n,m;
  5.     static int[] st=new int[N]; //存放选择的数
  6.     public static void dfs(int u,int k){    //u表示位置。从k开始枚举
  7.         if(m>u+n-k) return ;                       //剪枝优化，当m-u+1>n-k+1时
  8.         if(u==m+1){                         //递归出口，u个位置都已有数
  9.             for(int i=1;i<=m;i++){
  10.                 System.out.print(st[i]+" ");
  11.             }
  12.             System.out.println();
  13.             return ;
  14.         }
  15.         for(int i=k;i<=n;i++){  //枚举
  16.             st[u]=i;        //第u个位置存放i
  17.             dfs(u+1,i+1);   //递归调用
  18.             st[u]=0;        //第u个位置不存放i，恢复现场
  19.         }
  20.     }
  21.     public static void main(String[] args){
  22.         Scanner scan=new Scanner(System.in);
  23.         n=scan.nextInt();
  24.         m=scan.nextInt();
  25.         dfs(1,1);
  26.         scan.close();
  27.     }
  28. }

带分数 

题目描述：


100 可以表示为带分数的形式：100=3+69258714
还可以表示为：100=82+3546197
注意特征：带分数中，数字 1∼9 分别出现且只出现一次（不包含 0）。
类似这样的带分数，100 有 11 种表示法。

输入格式

一个正数

输出格式


输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。

数据范围

1≤N<106
1

输出样例


输入样例1：

100
1
输出样例1：

11
1
输入样例2：

105
1
输出样例2：

6

 费解的开关

你玩过“拉灯”游戏吗？

25盏灯排成一个 5×5的方形。

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

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

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

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

下面这种状态

  1. 10111
  2. 01101
  3. 10111
  4. 10000
  5. 11011

在改变了最左上角的灯的状态后将变成：

  1. 01111
  2. 11101
  3. 10111
  4. 10000
  5. 11011

再改变它正中间的灯后状态将变成：

  1. 01111
  2. 11001
  3. 11001
  4. 10100
  5. 11011

给定一些游戏的初始状态，编写程序判断游戏者是否可能在 66 步以内使所有的灯都变亮。

输入格式

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

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

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

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

输出格式

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

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

数据范围

0<n≤500

输入样例：
  1. 3
  2. 00111
  3. 01011
  4. 10001
  5. 11010
  6. 11100
  7.  
  8. 11101
  9. 11101
  10. 11110
  11. 11111
  12. 11111
  13.  
  14. 01111
  15. 11111
  16. 11111
  17. 11111
  18. 11111

输出样例：

  1. 3
  2. 2
  3. -1
 思路：

1.第一行的操作确定，则整个操作确定，枚举对第一行共32种操作，对第一行的操作是解题的精髓，

2.对第2,3,4行的操作要根据其前一行的状态进行

3.检查最后一行是否符合状态

  1. import java.util.*;
  2. public class Main{
  3. 	static int[][] g=new int[5][5];
  4. 	static int[][] st=new int[5][5];
  5. 	static int ans=Integer.MAX_VALUE;
  6. 	static int[] dx= {0,0,1,0,-1},dy= {0,-1,0,1,0};	//原地，左下右上
  7. 	static void turn(int x,int y) {
  8. 		for(int i=0;i<5;i++) {
  9. 			int a=x+dx[i],b=y+dy[i];
  10. 			if(a>=0&&b>=0&&a<5&&b<5) {		//控制边界
  11. 				st[a][b] ^=1;
  12. 			}
  13. 		}
  14. 	}
  15. 	static int work() {
  16. 	    //对第一行一共有32次操作
  17. 		for(int l=0;l<32;l++) {		
  18. 		    int step=0;
  19. 			for(int i=0;i<5;i++) {
  20. 				st[i]=Arrays.copyOf(g[i], g[i].length);
  21. 			}
  22. 			
  23. 			//操作第一行
  24. 			for(int i=0;i<5;i++) {
  25. 				if((l >> i&1)==1) {	//如果l对应的二进制数为1,表明要对这个灯进行一次按灯操作,否则就是不操作，从而枚举32种情况
  26. 					turn(0,i);
  27. 					step++;
  28. 				}
  29. 			}
  30. 			//对2,3,4行进行操作
  31. 			for(int i=0;i<4;i++) {	
  32. 				for(int j=0;j<5;j++) {
  33. 					if(st[i][j]==0) {
  34. 						turn(i+1,j);
  35. 						step++;
  36. 					}
  37. 				}
  38. 			}
  39.             //判断最后一行			
  40. 			boolean succes=true;
  41. 			for(int i=0;i<5;i++) {
  42. 				if(st[4][i]==0) {	//最后一行若有不亮的，返回false
  43. 					succes=false;
  44. 					break;
  45. 				}
  46. 			}
  47. 			if(succes) {
  48. 				ans=Math.min(ans, step);
  49. 			}
  50. 		}
  51.     //操作完返回 		
  52. 		if(ans<=6) {
  53. 			return ans;
  54. 		}else {
  55. 			return -1;
  56. 		}
  57. 	}
  58.     public static void main(String[] args){
  59.         Scanner scan=new Scanner(System.in);
  60.         int n=scan.nextInt();
  61.         for(int i=0;i<n;i++) {
  62.             
  63.         	for(int j=0;j<5;j++) {
  64.         	    String s=scan.next();
  65.         		for(int k=0;k<5;k++)
  66.         			g[j][k]=s.charAt(k) - '0';
  67.         	}
  68.         	int a=work();
  69.         	System.out.println(a);
  70.         	ans=10;
  71.         }
  72.         scan.close();
  73.     }
  74. }

翻硬币

 

 解题思路：有解的话必有一种解

  1. import java.util.*;
  2. public class fanyingbi {
  3. 	static char[] a,b;
  4. 	public static void main(String[] args) {
  5. 		// TODO Auto-generated method stub
  6. 		Scanner scan=new Scanner(System.in);
  7. 		a=scan.nextLine().toCharArray();
  8. 		b=scan.nextLine().toCharArray();
  9. 		int step=0;
  10. 		for(int i=0;i<a.length-1;i++) {
  11. 			if(a[i]==b[i]) 
  12. 				continue;
  13. 			else {
  14. 				step++;
  15. 				if(a[i]=='o') {
  16. 					a[i]='*';
  17. 					if(a[i+1]=='o') {
  18. 						a[i+1]='*';
  19. 					}else {
  20. 						a[i+1]='o';
  21. 					}
  22. 				}else {
  23. 					a[i]='o';
  24. 					if(a[i+1]=='o') {
  25. 						a[i+1]='*';
  26. 					}else {
  27. 						a[i+1]='o';
  28. 					}
  29. 				}
  30. 				
  31. 			}
  32. 		}
  33. 		System.out.print(step);
  34. 		scan.close();
  35. 	}
  36.  
  37. }

飞行员兄弟

飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 16 个把手的冰箱。

已知每个把手可以处于以下两种状态之一：打开或关闭。

只有当所有把手都打开时，冰箱才会打开。

把手可以表示为一个 4×4的矩阵，您可以改变任何一个位置 [i,j] 上把手的状态。

但是，这也会使得第 i 行和第 j列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数最小值是多少。

输入格式

输入一共包含四行，每行包含四个把手的初始状态。

符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。

至少一个手柄的初始状态是关闭的。

输出格式

第一行输出一个整数 N，表示所需的最小切换把手次数。

接下来 N行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。

注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。

数据范围

1≤i,j≤4

输入样例：
  1. -+--
  2. ----
  3. ----
  4. -+--
输出样例：
  1. 6
  2. 1 1
  3. 1 3
  4. 1 4
  5. 4 1
  6. 4 3
  7. 4 4
  1. import java.util.*;
  2. public class Main{
  3. 	static char[][] map=new char[4][4];
  4. 	static char[][] backup=new char[4][4];
  5. 	static int ans=Integer.MAX_VALUE;
  6. 	static String end="";
  7. 	static int get(int x,int y) {
  8. 		return x*4+y;
  9. 		
  10. 	}
  11. 	static void turn_one(int x,int y) {
  12. 		if(map[x][y]=='+')
  13. 			map[x][y]='-';
  14. 		else {
  15. 			map[x][y]='+';
  16. 		}
  17. 	}
  18. 	static void turn_all(int x,int y) {
  19. 		for(int i=0;i<4;i++) {
  20. 			turn_one(x,i);
  21. 			turn_one(i,y);
  22. 		}
  23. 		turn_one(x,y);
  24. 	}
  25. 	public static void main(String[] args) {
  26. 		// TODO Auto-generated method stub
  27. 		Scanner scan=new Scanner(System.in);
  28. 		for(int i=0;i<4;i++) {
  29. 			map[i]=scan.nextLine().toCharArray();
  30. 		}
  31. 		//枚举2^16种情况
  32. 		for(int op=0;op<(1<<16);op++) {
  33. 			//备份
  34. 			for(int i=0;i<4;i++) {
  35. 				backup[i]=map[i].clone();
  36. 			}
  37. 			int step=0;
  38. 			String str="";
  39. 			//枚举每一个开关
  40. 			for(int i=0;i<4;i++) {
  41. 				for(int j=0;j<4;j++){
  42. 					if((op>>get(i,j)&1)==1) {
  43. 						step++;
  44. 						str+=(i+1);
  45. 						str+=(j+1);
  46. 						turn_all(i,j);
  47. 					}
  48. 				}
  49. 			}
  50. 			//判断是否全亮
  51. 			boolean has_closed=false;
  52. 			for(int i=0;i<4;i++) {
  53. 				for(int j=0;j<4;j++) {
  54. 					if(map[i][j]=='+') {
  55. 						has_closed=true;
  56. 						break;
  57. 					}
  58. 				}
  59. 			}
  60. 			if(!has_closed) {
  61. 				if(step<=ans) {
  62. 					ans=step;
  63. 					end=str;
  64. 				}
  65. 			}
  66. 			//还原
  67. 			for(int i=0;i<4;i++) {
  68. 				map[i]=backup[i].clone();
  69. 			}
  70. 		}
  71. 		System.out.println(ans);
  72. 		for(int op=0;op<end.length();op+=2) {
  73. 			System.out.println(end.charAt(op)+" "+end.charAt(op+1));
  74. 		}
  75. 	}
  76.  
  77. }

位运算

想看i的第k位是否是1，i>>k&1

op>>get(i,j)&1

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/916224
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号