第八课.暴力递归

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了第八课.暴力递归，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含9260字，纯文字阅读大概需要14分钟。

内容图文

1.汉诺塔：打印n层汉诺塔从最左边移动到最右边的全部过程

	public static void hanoi(int n) {
		if (n > 0) {
			func(n, "左", "中", "右");
		}
	}
	//1-i圆盘，目标是from->to,other是另外一个
	public static void func(int i, String start, String end, String other) {
		if (i == 1) {
			System.out.println("move 1 from " + start + " to " + end);
		} else {
			func(i - 1, start, other, end);
			System.out.println("move" + i + "from " + start + " to " + end);
			func(i- 1, other, end, start);
		}
	}

	public static void main(String[] args) {
		int n = 3;
		hanoi(n);
	}

2.打印一个字符串的全部字序列，包括空字符串
法一：

	public static void function(String str) {
		char[] chars = str.toCharArray();
		process(chars,0,new ArrayList<Character>());
	}
	//当前来到i位置，要和不要，走两条路
	//res之前的选择，所形成的路
	public static void process(char[] chs, int i, List<Character> res) {
		if(i==chs.length){
			printList(res);
			return;
		}
		List<Character> characters1 = copyList(res);
		process(chs,i+1,characters1);//要当前字符
		List<Character> characters2 = copyList(res);
		characters2.add(chs[i]);
		process(chs,i+1,characters2);//不要当前字符

	}

	public static void printList(List<Character> res) {
		for (Character re : res) {
			System.out.print(re);
		}
		System.out.println("\n");
	}

	public static List<Character> copyList(List<Character> list){
		List<Character> listA=new ArrayList<>();
		for (Character character : list) {
			listA.add(character);
		}
		return listA;
	}


	public static void main(String[] args) {
		String test = "abc";
		function(test);
	}

法二：

	public static void printAllSubsquence(String str) {
		char[] chars = str.toCharArray();
		process(chars,0);
	}
	//之前的选择，所形成的的结果，是str
	public static void process(char[] chs, int i) {
		if(i==chs.length){
			System.out.println(String.valueOf(chs));
			return;
		}
		process(chs,i+1);
		char temp=chs[i];//要当前字符的路
		chs[i]=0;
		process(chs,i+1);//不要当前字符的路
		chs[i]=temp;
	}
		public static void main(String[] args) {
		String test = "abc";
		printAllSubsquence(test);
	}

3.打印一个字符串的全排列，要求不出现重复的排列

	public static ArrayList<String> Permutation(String str) {
		if(str==null||str.length()==0){
			return null;
		}
		char[] chars = str.toCharArray();
		ArrayList<String> res=new ArrayList<>();
		process(chars,0,res);
		return res;
	}
	//str[i..]范围上，所有的字符，都可以在i位置上，后续都去尝试
	//str[0..i-1]范围上，是之前做的选择
	//把所有的字符串所形成的全排列，加入到res里去
	public static void process(char[] chs, int i, ArrayList<String> res) {
		if(i==chs.length){
			res.add(String.valueOf(chs));
			return;
		}
		boolean visit[]= new boolean[26];
		for(int j=i;j<chs.length;j++){
			if(!visit[chs[j]-'a']){
				visit[chs[j]-'a']=true;
				swap(chs,i,j);
				process(chs,j+1,res);
				swap(chs,i,j);
			}

		}
	}

	public static void swap(char[] chs, int i, int j) {
		char tmp = chs[i];
		chs[i] = chs[j];
		chs[j] = tmp;
	}

	public static void main(String[] args) {
		String abc="abc";
		ArrayList<String> permutation = Permutation(abc);
		for (String s : permutation) {
			System.out.println(s);
		}
	}

4.给你一个栈，请逆序这个栈，不能申请额外的数据结构，只能使用递归函数

	public static void reverse(Stack<Integer> stack) {
		if(stack.isEmpty()){
			return;
		}
		int result=getAndRemoveLastElement(stack);
		reverse(stack);
		stack.add(result);
	}

	public static int getAndRemoveLastElement(Stack<Integer> stack) {
		int result=stack.pop();
		if(!stack.isEmpty()){
			int last = getAndRemoveLastElement(stack);
			stack.push(result);
			return last;
		}else{
			return result;
		}
	}

	public static void main(String[] args) {
		Stack<Integer> test = new Stack<Integer>();
		test.push(1);
		test.push(2);
		test.push(3);
		test.push(4);
		test.push(5);
		reverse(test);
		while (!test.isEmpty()) {
			System.out.println(test.pop());
		}
	}

5.规定1和A对应，2和B对应，3和C对应
一个数字字符比如‘111’，就可以转化为“AAA”，“KA”和“AK”。
给定一个只有数字字符组成的字符串str，返回有多少种转化的结果

	public static int number(String str) {
		if(str==null||str.length()==0){
			return 0;
		}
		return process(str.toCharArray(),0);
	}
	//i之前的位置，如何转化已经做过决定了
	//i...有多少种转化的结果
	public static int process(char[] chs, int i) {
		if(i==chs.length){
			return 1;
		}
		if(chs[i]=='0'){
			return 0;
		}
		if(chs[i]=='1'){//i自己作为单独的部分，后续有多少种方法
			int res =process(chs,i+1);
			if(i+1<chs.length){
				res+=process(chs,i+2);//（i和i+1）作为单独的部分，后续有多少种方法
			}
			return res;
		}
		if(chs[i]=='2'){
			int res=process(chs,i+1);//i自己作为单独的部分，后续有多少种方法
			if (i + 1 < chs.length && chs[i+1]<='6'&&chs[i+1]>='0') {
				res+=process(chs,i+2);//（i和i+1）作为单独的部分并且没有超过26，后续有多少种方法
			}
			return res;
		}
		return process(chs,i+1);
	}

6.给定两个数组w和v，两个数组长度相等，w[i]表示第i件商品的重量，v[i]表示第i件商品的价值。再给定一个数组bag，要求你挑选商品的重量一定不能超过bag，返回满足这个条件下，你能获得的最大价值。
法一：有alreadyValue

	public static int maxValue1(int[] weights, int[] values, int bag) {
		return process2(weights, values, 0, 0, 0,bag);
	}
		public static int process2(int[] weights, int[] values, int i, int alreadyweight, int alreadyValue, int bag) {
		if(alreadyweight>bag){
			return 0;
		}
		if(i==weights.length){
			return alreadyValue;
		}
		return 	Math.max(process2(weights,values,i+1,alreadyweight+weights[i],alreadyValue+values[i],bag),process2(weights,values,i+1,alreadyweight,alreadyValue,bag));
	}

法二：没有alreadyValue

	public static int maxValue1(int[] weights, int[] values, int bag) {

		return process1(weights, values, 0, 0, bag);

	}
	//i..的货物自由选择，形成的最大价值返回
	//重量永远不要超过bag
	//之前做的决定，所达到的重量，alreadyweight
	public static int process1(int[] weights, int[] values, int i, int alreadyweight, int bag) {
		if (alreadyweight > bag) {
			return 0;
		}
		if (i == weights.length) {
			return 0;
		}
		return Math.max(

				process1(weights, values, i + 1, alreadyweight, bag),

				values[i] + process1(weights, values, i + 1, alreadyweight + weights[i], bag));
	}

测试代码：

	public static int maxValue2(int[] c, int[] p, int bag) {
		int[][] dp = new int[c.length + 1][bag + 1];
		for (int i = c.length - 1; i >= 0; i--) {
			for (int j = bag; j >= 0; j--) {
				dp[i][j] = dp[i + 1][j];
				if (j + c[i] <= bag) {
					dp[i][j] = Math.max(dp[i][j], p[i] + dp[i + 1][j + c[i]]);
				}
			}
		}
		return dp[0][0];
	}
	public static void main(String[] args) {
		int[] weights = { 3, 2, 4, 7 };
		int[] values = { 5, 6, 3, 19 };
		int bag = 11;
		System.out.println(maxValue1(weights, values, bag));
		System.out.println(maxValue2(weights, values, bag));
	}

7.给定一个整型数组arr，代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿。但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。

	public static int win1(int[] arr) {
		if(arr==null||arr.length==0){
			return 0;
		}
		return Math.max(f(arr,0,arr.length-1),s(arr,0,arr.length-1)); 
	}
	//先手
	public static int f(int[] arr, int i, int j) {
		if(i==j){
			return arr[i];
		}
		return Math.max(arr[i]+s(arr,i+1,j),arr[j]+s(arr,i,j-1));//注意调用的是s
	}
	//后手
	public static int s(int[] arr, int i, int j) {
		if(i==j){
			return 0;
		}
		return Math.min(f(arr,i+1,j),f(arr,i,j-1));//注意调用的是f，并且没有arr[i]+
	}

测试：

	public static int win2(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int[][] f = new int[arr.length][arr.length];
		int[][] s = new int[arr.length][arr.length];
		for (int j = 0; j < arr.length; j++) {
			f[j][j] = arr[j];
			for (int i = j - 1; i >= 0; i--) {
				f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
				s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
			}
		}
		return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
	}

	public static void main(String[] args) {
		int[] arr = { 1, 9, 1 };
		System.out.println(win1(arr));
		System.out.println(win2(arr));
	}

8.N皇后问题：
法一：正规解法

public static int num1(int n) {//n个皇后
		if (n < 1) {
			return 0;
		}
		int[] record = new int[n];//record[i] -->i行的皇后，放在了第几列
		return process1(0, record, n);
	}
	//潜台词：record[0..i-1]的皇后，任何两个皇后一定不共行、不共列、不共斜线
	//目前来到第i行
	//record[0..i-1]表示之前的行，放了皇后的位置
	//n代表整体一共有多少行
	//返回值，摆完所有的皇后，所有合理的摆法有多少种
	public static int process1(int i, int[] record, int n) {
		if (i == n) {//终止行
			return 1;
		}
		int res = 0;
		for (int j = 0; j < n; j++) {//当前行在i行，尝试i行所有的列->j
			//当前i行的皇后，放在j列，会不会和之前（0..i-1）的皇后，共行共列或共斜线
			//如果是，认为无效
			//如果不是，认为无效
			if (isValid(record, i, j)) {
				record[i] = j;
				res += process1(i + 1, record, n);
			}
		}
		return res;
	}
	//record[0..i-1]需要看，record[i...]不需要看
	//返回i行皇后，放在j列，是否有效
	public static boolean isValid(int[] record, int i, int j) {
		for (int k = 0; k < i; k++) {//之前的某k行皇后
			if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {//注意条件是||
				return false;
			}
		}
		return true;
	}

法二：位运算优化（没有掌握）

public static int num2(int n) {
		if (n < 1 || n > 32) {
			return 0;
		}
		int upperLim = n == 32 ? -1 : (1 << n) - 1;
		return process2(upperLim, 0, 0, 0);
	}

	public static int process2(int upperLim, int colLim, int leftDiaLim,
			int rightDiaLim) {
		if (colLim == upperLim) {
			return 1;
		}
		int pos = 0;
		int mostRightOne = 0;
		pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
		int res = 0;
		while (pos != 0) {
			mostRightOne = pos & (~pos + 1);
			pos = pos - mostRightOne;
			res += process2(upperLim, colLim | mostRightOne,
					(leftDiaLim | mostRightOne) << 1,
					(rightDiaLim | mostRightOne) >>> 1);
		}
		return res;
	}

测试：

public static void main(String[] args) {
		int n = 14;

		long start = System.currentTimeMillis();
		System.out.println(num2(n));
		long end = System.currentTimeMillis();
		System.out.println("cost time: " + (end - start) + "ms");

		start = System.currentTimeMillis();
		System.out.println(num1(n));
		end = System.currentTimeMillis();
		System.out.println("cost time: " + (end - start) + "ms");

	}

内容总结

以上是互联网集市为您收集整理的第八课.暴力递归全部内容，希望文章能够帮你解决第八课.暴力递归所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1028695.html

来源：【匿名】

【上一篇】前端下载文件流形式的文件【下一篇】关于IE的RegExp.exec的问题

更多 ►

【第八课.暴力递归】教程文章相关的互联网学习教程文章

归并排序：归并排序是建立在归并操作上的一种有效的排序算法,该算法是採用分治法（Divideand Conquer）的一个很典型的应用。将已有序的子序列合并，得到全然有序的序列。即先使每一个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。数据结构的学习过程中。我们常常会遇到排序算法，当中归并排序是一种高效而且算法复杂度比較简单的一种。在课本的介绍中，大部分都会介绍归并排序算法。可是...

编程将字符串s倒序输出，要求利用函数递归实现【代码】

编程将字符串s倒序输出，要求利用函数递归实现。 **输入格式要求："%s" 提示信息："input your string:\n" **输出格式要求："%c" 程序运行的输入输出样例：屏幕先输出提示信息： input your string: 然后用户键盘输入： abcdefg 最后屏幕输出： gfedcba 1 #include <stdio.h>2 void reverse(char s[])3 { 4 int len;5 len = strlen(s);6 7 if (len == 1)8 { ...

第八课.暴力递归【代码】

1.汉诺塔：打印n层汉诺塔从最左边移动到最右边的全部过程public static void hanoi(int n) {if (n > 0) {func(n, "左", "中", "右");}}//1-i圆盘，目标是from->to,other是另外一个public static void func(int i, String start, String end, String other) {if (i == 1) {System.out.println("move 1 from " + start + " to " + end);} else {func(i - 1, start, other, end);System.out.println("move" + i + "from " + start + "...

可变参数与递归

可变参数 (1) jDK1.5开始，java支持传递同类型的可变参数给一个方法 (2) 在方法声明中，在指定参数类型后加一个省略号(...) (3) 一个方法中只能指定一个可变参数，他必须是方法的最后一个参数，任何普通的参数必须在他之前声明递归（面试常考） (1) A方法调用B方法，我们很容易理解 (2) 递归就是：A方法调用A方法，就是自己调用自己 (3) 利用递归可以用简单的程序来解决一些复杂的问题，它通常把一个大型复杂的问题层层转化为一个...

是什么是递归？-[all]-[编程理论]

递归是所有编程语言中，都会讨论到的一个问题。递归的通俗认识编程是现实的抽象，这是能被应用到所有的编程概念的。递归也是如此，其实递归，就是重复，循环，我们大概上幼儿园的时候，其实就有过递归的概念。 ![](https://www.icode9.com/i/l/?n=18&i=blog/1735896/201912/1735896-20191220175944636-2005062005.png)

leetcode24 Swap Nodes in Pairs（递归）【代码】

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。示例: 给定 1->2->3->4, 你应该返回 2->1->4->3. class Solution {public ListNode swapPairs(ListNode head) {if(head==null||head.next==null) return head;ListNode next=head.next;head.next=swapPairs(next.next);next.next=head;return next;} }/*** Definition for singly-linked list.* publ...

逻辑数据库设计 - 单纯的树(递归关系数据)【代码】【图】

。这个需求并不简单，相互回复会导致无限多的分支，无限多的祖先-后代关系。这是一种典型的递归关系数据。对于这个问题，以下给出几个解决方案，各位客观可斟酌后选择。一、邻接表:依赖父节点邻接表的方案如下(仅仅说明问题)：CREATE TABLE Comments(CommentId　　int　　PK,ParentId　　 int,　　　　--记录父节点ArticleId　　int,CommentBody nvarchar(500),FOREIGN KEY (ParentId) REFERENCES Comments(CommentId) 　　--自连...

闭包、递归、回调【图】

闭包、递归、回调什么是闭包闭包指有权访问另一个函数作用域中变量的函数。js简单理解，一个作用域可以访问另外一个函数内部的局部变量，闭包即函数。闭包主要作用：延伸了变量的作用范围（函数在执行完后，局部变量销毁，但是闭包函数只有在内部函数都结束才会销毁）（函数内调用函数，被调函数访问该函数的变量（函数里面的函数存在访问外面函数里的变量就有闭包），该函数称作闭包函数）闭包经典面试题什么是递归函数...

SQL语句中使用 with 递归实现表中数据树状显示【图】

dept as(select DeptId,DeptUpId from DeptInfo union all select dept.DeptId,DeptInfo.DeptUpId from dept inner join DeptInfoon dept.DeptUpId=DeptInfo.DeptId) select * from DeptInfo　　执行后结果如下：　　小结一下：使用递归时查阅资料后还要注意以下几点：1. 递归 CTE 定义至少必须包含两个 CTE 查询定义，一个定位点成员和一个递归成员。可以定义多个定位点成员和递归成员；但必须将所有定位点成员查询定义置于第一个...

sql – 如何递归查找子项的所有ID？【代码】

我想从只有MySQL的树中获取孩子们的所有ID. 我有这样一张桌子：ID parent_id name 1 0 cat1 2 1 subcat1 3 2 sub-subcat1 4 2 sub-subcat2 5 0 cat2现在我试图以递归方式获取cat1(2,3,4)的所有子ID.有什么办法可以实现吗？解决方法:执行此操作有两种基本方法：邻接列表和嵌套列表.看看Managing Hierarchical Data in MySQL. 你有什么是邻接名单.没有办法用一个SQL语句递归抓取所有后...

SQL实现递归及存储过程中In()参数传递解决方案详解

1.SQL递归在SQL Server中，我们可以利用表表达式来实现递归算法，一般用于阻止机构的加载及相关性处理。 -->实现：假设OrganiseUnit（组织机构表）中主要的三个字段为OrganiseUnitID（组织机构主键ID）、ParentOrganiseUnitID（组织机构父ID）、OrganiseName（组织机构名称）代码如下:with organise as(select * from OrganiseUnit where OrganiseUnit.OrganiseUnitID = @OrganiseUnitID union all select OrganiseUnit.* from ...

第45课递归的思想与应用（下）【代码】【图】

1. 函数调用栈的回顾（1）用于保存函数中的实参、局部变量、临时变量等。（2）从起始地址开始往一个方向增长（如：高地址→低地址）（3）有一个专用“指针”标识当前已使用内存的“顶部”（4）当函数调用结束时，栈会恢复到被调用前的状态。可以利用这个时机进行一些的回溯算法的设计。【实例分析】函数调用栈分析：逆序打印单链表中的偶数结点（void r_print_even(Node* list)），见本课后面的源码2. 回溯求解八皇后问题（1）回溯...

第三章栈作业题2-栈及其应用-计算机17级 6-2 递归程序设计方法练习--递归输出单链表（10 分）

6-2 递归程序设计方法练习--递归输出单链表（10 分）本题要求用递归方法编写递归函数实现无头结点单链表的输出操作函数。L是一个不带头结点的单链表，函数void ListPrint_L_Rec(LinkList L)要求用递归的方法输出无头结点之单链表中各个元素的值，每个元素的前面都有一个空格（包括首元素）。递归思想可借鉴下述代码中链表创建的递归函数。函数接口定义：void ListPrint_L_Rec(LinkList L);其中 L 是一个不带头结点的单链表。裁...

游标和递归sql 的一些代码

DECLARE @UserID INT; --推广员帐号DECLARE @ProxyID INT; --代理帐号DECLARE @Score INT=1000; --分数SELECT @UserID = [SpreaderID]FROM [QPAccountsDB].[dbo].[AccountsInfo]WHERE UserID = 5055;SELECT --查出推广员的代理帐号 @ProxyID = ProxyIDFROM [QPAccountsDB].[dbo].[AccountsInfo] LEFT JOIN [QPProxyDB].[dbo].[BS_ProxyInfo] ON BS_ProxyInfo.account = AccountsInfo....

搜索递归具体运行流程【代码】

** 一般初学者在看搜索的时候，很可能被递归给扰乱，不知道每个数都是怎么变化的，怎么算出来的，以下就是最简单的题的所有计算流程，手算不易求支持 ** ** 题目描述 ** 排列与组合是常用的数学方法。先给一个正整数 ( 1 < = n < = 10 ) 例如n＝3，所有组合,并且按字典序输出： 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 输入输入一个整数n( 1<=n<=10) 输出输出所有全排列每个全排列一行，相邻两个数用空格隔开（最后一个数后面没有...

首页 / 更多教程 / 第八课.暴力递归

第八课.暴力递归

内容导读

内容图文

内容总结

内容备注

内容手机端

【第八课.暴力递归】教程文章相关的互联网学习教程文章

怎样使用递归实现归并排序【图】

编程将字符串s倒序输出，要求利用函数递归实现【代码】

第八课.暴力递归【代码】

可变参数与递归

是什么是递归？-[all]-[编程理论]

leetcode24 Swap Nodes in Pairs（递归）【代码】

逻辑数据库设计 - 单纯的树(递归关系数据)【代码】【图】

闭包、递归、回调【图】

SQL语句中使用 with 递归实现表中数据树状显示【图】

sql – 如何递归查找子项的所有ID？【代码】

SQL实现递归及存储过程中In()参数传递解决方案详解

第45课递归的思想与应用（下）【代码】【图】

第三章栈作业题2-栈及其应用-计算机17级 6-2 递归程序设计方法练习--递归输出单链表（10 分）

游标和递归sql 的一些代码

搜索递归具体运行流程【代码】

更多教程 - 最新教程

更多教程 - 最热教程