当前位置: 首页 > news >正文

网站每个月8g流量河南推广网站的公司

网站每个月8g流量,河南推广网站的公司,做ppt卖给网站,thinkphp企业网站本篇博客将聚焦于通过递归来实现两种经典的枚举方法:指数型枚举和排列型枚举。这两种枚举方式在计算机科学和算法竞赛中都有广泛应用,无论是在解题中,还是在实际工作中都极具价值。 目录 前言 斐波那契数列递归 递归实现指数型枚举 算法思…

本篇博客将聚焦于通过递归来实现两种经典的枚举方法:指数型枚举排列型枚举。这两种枚举方式在计算机科学和算法竞赛中都有广泛应用,无论是在解题中,还是在实际工作中都极具价值。

目录

前言

斐波那契数列递归

递归实现指数型枚举

算法思路 

代码如下

递归实现排列型枚举

算法思路 

 代码如下

 总结


前言

在编程的世界里,递归是一种优雅且强大的技术,它能让复杂问题变得更加简洁和易于理解。无论是数学中的公式推导,还是计算机科学中的算法设计,递归都扮演着不可或缺的角色。在数据结构与算法中,递归不仅能帮助我们高效地解决问题,还能展现出代码的简洁性和表达力。

本篇博客将聚焦于通过递归来实现两种经典的枚举方法:指数型枚举排列型枚举。这两种枚举方式在计算机科学和算法竞赛中都有广泛应用,无论是在解题中,还是在实际工作中都极具价值。


斐波那契数列递归

递归最经典的就是斐波那契数列,其中第1个数是1,第2个数是2,第3个数是前两个数字之和。 

f(n) = f(n - 1) + f(n - 2) n\geq 3 

java代码如下: 

package AcWingLanQiao;import java.util.*;public class 递归 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();System.out.println(f(n));}public static int f(int n){if(n==1){ return 1;}if(n==2){ return 2;}return f(n-1)+f(n-2);}
}

 

递归实现指数型枚举

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

输入格式

输入一个整数 n。

输出格式

每行输出一种方案。

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

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

数据范围

1≤n≤15

输入样例

3

输出样例


3
2
2 3
1
1 3
1 2
1 2 3

算法思路 

每一个位置都有两种情况,分别是选和不选。

当有n个数时,结果就有2^{n}中情况。

当n为对的时候,上述对应的是递归搜索树。从第一个位置开始分两种情况,选和不选,后续每个位置一次类推。

我们用一个数组flag,数组下标表示从1到n,flag[i]表示该值在每个位置的状态,0表示还未考虑,1表示选,2表示这个位置不选;通过dfs深度优先搜索,用u来表示当前在哪个位置,先思考递归的出口,当当前位置u要大于n时(即u > n),就说明n个位置每个位置的情况都处理好了,就说明最后flag[i] = 1对应的下标就是结果所需的序列。

当u <= n时,我们只需处理两种情况,一种是选,一种是不选。当选时,将flag[u] = 1,然后递归的处理下一个位置dfs(u+1),最后再恢复现场flag[u] = 0,即相当于是当前的位置都处理完了,将位置恢复为未处理,然后再走另一种情况;当不选时,将flag[u] = 2,后递归的处理下一个位置dfs(u+1),最后再恢复现场flag[u] = 0。

代码如下

package AcWingLanQiao;
import java.io.*;
import java.util.*;public class 递归实现指数型枚举 {static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static int N = 16;/*状态数据,记录每个位置的当前状态0表示还未考虑1表示选它2表示不选它*/static int[] flag = new int[N];static int n;public static void main(String[] args)throws Exception {n = nextInt();dfs(1);pw.flush();}public static void dfs(int u){if(u > n){for(int i = 1;i <= n;i++){if(flag[i] == 1){pw.print(i+" ");}}pw.println();pw.flush();return;}flag[u] = 2;dfs(u+1);  //第一个分支不选flag[u] = 0;//恢复现场flag[u] = 1;dfs(u+1); //第二个分支选flag[u] = 0;}public static int nextInt() throws Exception {st.nextToken();return (int)st.nval;}
}

递归实现排列型枚举

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

输入格式

一个整数 n。

输出格式

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

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

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

数据范围

1≤n≤9

输入样例

3

输出样例

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

注:字典序排序是一种按照字典中单词出现的顺序来排列元素的方法。在计算机科学中,它被用来比较两个字符串的大小关系,即比较它们从左到右第一个不同字符的ASCII值的大小关系。这种排序方式不仅适用于英文单词,也适用于任意字符串的比较。

算法思路 

 用整型数组arr来存储数列的结果,布尔类型数组flag,其中flag[i]若为true表示数字i已被使用,若为false表示数字i未被使用。使用深度优先搜索dfs来解决此问题。我们可以通过每个位置放置哪个数字来进行思考。

我们先来思考递归的出口,当当前位置u大于n时(即u > n),说明所有的位置上数字都以排好,所以此时只需打印arr数组,就可以得到结果。当n为3时,说明一个位置有3种情况,所以要有一个外层循环,然后来判断flag[i]是否被使用,未被使用则将当前位置复制为i即arr[u] = i,还需将该数字对应的flage数组设置为已使用即flag[i] = true,然后递归的处理下一个位置即dfs(u+1),最后再进行回溯操作flag[i] = false。如果flag[i]已经被使用,则接着进行下一次数字进行判断,n个数字都被使用,也可说明数列已被排完序。

算法时间复杂度为O(n*n!)

 代码如下

import java.io.*;public class Main {static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static int N = 10;static int[] arr = new int[N];static boolean[] flag = new boolean[N]; //true表示用过 false表示未被用过static int n;public static void main(String[] args) throws IOException {n = nextInt();dfs(1);pw.flush();}public static void dfs(int u) {if(u > n){ //边界for(int i = 1; i<= n;i++){pw.print(arr[i]+" ");}pw.println();return;}//枚举每个分支for(int i = 1; i<= n;i++){if(!flag[i]){arr[u] = i;flag[i] = true;dfs(u+1);//恢复现场flag[i] = false;}}}public static int nextInt() throws IOException {st.nextToken();return (int) st.nval;}
}

代码输入

4

代码输出结果

1 2 3 4 
1 2 4 3 
1 3 2 4 
1 3 4 2 
1 4 2 3 
1 4 3 2 
2 1 3 4 
2 1 4 3 
2 3 1 4 
2 3 4 1 
2 4 1 3 
2 4 3 1 
3 1 2 4 
3 1 4 2 
3 2 1 4 
3 2 4 1 
3 4 1 2 
3 4 2 1 
4 1 2 3 
4 1 3 2 
4 2 1 3 
4 2 3 1 
4 3 1 2 
4 3 2 1 

 总结

通过本篇博客的学习,我们可以看到递归作为一种经典的编程技巧,不仅能够简化问题的解决过程,还能提高代码的可读性和执行效率。递归在指数型枚举和排列型枚举中的应用,展示了它在不同场景中的灵活性与强大功能。

无论是初学者还是有一定编程经验的开发者,理解并掌握递归的精髓对于解决实际问题都有很大的帮助。希望通过这篇博客,能够带给大家一些启发,并鼓励大家在实际编程过程中善于运用递归,解锁更多的编程奥秘。

http://www.ritt.cn/news/13496.html

相关文章:

  • 沈阳网站建设方案推广网站建设山东聚搜网络
  • 做弹幕网站私域流量营销
  • 东莞网站推广优化百度下载
  • 江苏省建设工程上岗证查询网站外贸网站免费推广b2b
  • 辽宁省住房和建设厅网站优化深圳seo
  • 互联网营销宣传武汉关键词seo排名
  • 昆山哪里有人做网站如何做推广
  • 设计网站用户需求分析报告广告网站有哪些
  • 闲置服务器做网站网络黄页推广软件哪个好用
  • 做微信商城网站公司百度sem认证
  • 网站开发项目时序图建网站教学
  • 做学术论文的网站网站搜索优化排名
  • 做网站和做网页一样吗seo教程
  • 查收录网站百度百家号注册
  • .vip域名的网站排名百度seo关键词优化费用
  • 哪些网站可以做公司制度徐州seo建站
  • wordpress 黑糖破解郑州关键词seo
  • 古镇免费网站建设网络营销都有哪些方法
  • 网站建设分工优化推广
  • 网站代码需要注意什么问题吗班级优化大师电脑版
  • 甘肃省住房和城乡建设部网站汕头seo公司
  • wordpress 移动导航菜单seo排名推广
  • 公司做的网站入哪个会计科目google浏览器网页版
  • 做网站用什么格式的图片怎么推广自己的网站
  • 大连门户网站开发优化关键词怎么做
  • 深圳市建设混凝土投标网站域名查询注册信息查询
  • 药品行业做网站网站seo分析工具
  • 阿里云网站建设方案书是什么企业营销策划
  • b s网站开发标准关键词排名工具
  • 网站建设落地页永久免费国外域名注册