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

网站优化 济南在线网站排名工具

网站优化 济南,在线网站排名工具,wordpress 插件商城,旅游找什么网站好本篇博客将聚焦于通过递归来实现两种经典的枚举方法:指数型枚举和排列型枚举。这两种枚举方式在计算机科学和算法竞赛中都有广泛应用,无论是在解题中,还是在实际工作中都极具价值。 目录 前言 斐波那契数列递归 递归实现指数型枚举 算法思…

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

目录

前言

斐波那契数列递归

递归实现指数型枚举

算法思路 

代码如下

递归实现排列型枚举

算法思路 

 代码如下

 总结


前言

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

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


斐波那契数列递归

递归最经典的就是斐波那契数列,其中第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.qdjiajiao.com/news/6083.html

相关文章:

  • 怎么把产品卖到国外去济南网站优化公司排名
  • 长葛哪里有做网站的时事热点新闻
  • 咨询服务类网站建设seo网站推广可以自己搞吗
  • 做led视频好的网站西地那非片能延时多久每次吃多少
  • 加速乐wordpress插件网络优化大师手机版
  • 细谈电商网站外链建设的策略济南最新消息
  • 门户网站建设制作哪里有整站优化
  • 学院网站建设规划全媒体广告代理加盟
  • 网站优化的重要性谷歌seo搜索引擎
  • .net 网站管理系统武汉seo哪家好
  • 网站方案范文如何引流推广产品
  • 无锡网站开发公司电话电子商务说白了就是干什么的
  • 网络调查问卷在哪个网站做网站seo哪家做的好
  • 怎么介绍自己做的静态网站seo优化网站的注意事项
  • 政府网站管理体系建设seo优化效果
  • 做彩票网站犯法不怎么做营销推广
  • 杭州网站设计公司哪家好长沙seo服务哪个公司好
  • 怎样免费建自己的网站免费建一个自己的网站
  • 网站分类有哪些网络推广计划书范文
  • 网站强制分享链接怎么做的中国万网域名注册服务内容
  • 网站开发硬件要求河南网站推广公司
  • 建设一个网站所需要注意的淘宝怎么设置关键词搜索
  • 汉服网页设计作品seo编辑是干什么的
  • 什么网站详情页做的好网络策划书范文
  • 给公司做门户网站网站推广途径和要点
  • 自己可以免费做网站吗网络推广seo怎么弄
  • 福建省建设厅网站seo关键词优化价格
  • 网站下载下来怎么做后台教育培训机构官网
  • 那个网站做搬家推广比较好昆明长尾词seo怎么优化
  • 最好看的免费网站源码免费网站的软件