开发者社区> 朱培> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

递归算法案例分析

简介: 一、递归练习(斐波那契数列) 不死神兔 故事得从西元1202年说起,话说有一位意大利青年,名叫斐波那契。 在他的一部著作中提出了一个有趣的问题:假设一对刚出生的小兔一个月后就能长成大兔,再过一个月就能生下一对小兔,并且此后每个月都生一对小兔,一年内没有发生死亡, 问:一对刚出生的兔子,一年内繁殖成多少对兔子? 算法分析: 1 1 2 3 5 8 13
+关注继续查看

一、递归练习(斐波那契数列)

  • 不死神兔
  • 故事得从西元1202年说起,话说有一位意大利青年,名叫斐波那契。
  • 在他的一部著作中提出了一个有趣的问题:假设一对刚出生的小兔一个月后就能长成大兔,再过一个月就能生下一对小兔,并且此后每个月都生一对小兔,一年内没有发生死亡,
  • 问:一对刚出生的兔子,一年内繁殖成多少对兔子?
算法分析:
  • 1 1 2 3 5 8 13
  • 第一个月一对小兔子 1
  • 第二个月一对大兔子 1
  • 第三个月一对大兔子生了一对小兔子 2
  • 第四个月一对大兔子生了一对小兔子
  • 一对小兔子长成大兔子 3
  • 第五个月两对大兔子生两对小兔子
  • 一对小兔子长成大兔子 5

我们首先可以用非递归的方法来做这个题目
private static void demo1() {
		// 方法一
		// 用数组做不死神兔
		int[] arr = new int[12];
		arr[0] = 1;
		arr[1] = 1;
		// 遍历数组对其他元素赋值
		for (int i = 2; i < arr.length; i++) {
			arr[i] = arr[i - 2] + arr[i - 1];
		}
		// 如何获取最后一个数,
		System.out.println(arr[arr.length - 1]);
	}


然后我们可以用第递归来做,
	// 第2种方法:用递归求斐波那契数列
	/*
	 * 分析: 1=fun(1) 1=fun(2) 2=fun(1)+fun(2) 3=fun(2)+fun(3)
	 */
	public static int fun(int num) {
		if (num == 1 || num == 2) {
			return 1;
		} else {
			return fun(num - 2) + fun(num - 1);
		}
	}


二、集合练习(约瑟夫环)
  • 幸运数字
/*
	 * 返回值类型为int
	 * 
	 */
	public static int getLuckNum(int num){
		//创建集合1到num的对象
		ArrayList<Integer>  list=new ArrayList<>();
		for(int i=1;i<=num;i++){
			list.add(i);    //存储到集合中
		}
		int count=1;    //只要是3的倍数就remove掉
		for(int i=0;list.size()!=1;i++){  //只要集合中人数超过1,就要不断的杀
			if(i==list.size()){
				i=0;         //如果i增长到集合最大的索引+1时,就重新归0
			}
			if(count%3==0){
				list.remove(i--);
				
			}
			count++;
					
		}
		return list.get(0);
	}


三、
递归练习(1000的阶乘所有零和尾部零的个数)
当然,如果我们直接使用以下方法来做的话是不可行的
/*
		 * int result=1; //这里要从1开始,不能从0开始,因为任何数乘0都为0 
		 * for(int i=1;i<=1000;i++){
		 * 		result=result*i; 
		 * } 
		 * 	System.out.println(result);
		 * //此方法不能使用,因为这样计算的值(1000的阶乘)超出int的取值范围了
		 */

所以我们需要这样做,先去求出1000的阶乘,然后再去统计有多少个0.

// 求出1000的阶乘
		BigInteger bi1 = new BigInteger("1");
		for (int i = 1; i <= 1000; i++) {
			BigInteger bi2 = new BigInteger(i + "");// 转换为字符串类型的
			bi1 = bi1.multiply(bi2); // 将bi1与bi2相乘的结果赋值给bi1
		}

// 求出尾部所有的0
	private static void demo2(BigInteger bi1) {
		String str=bi1.toString();
		StringBuilder sb=new StringBuilder(str);
		str=sb.reverse().toString();  //链式编程
		int count=0;
		for(int i=0;i<str.length();i++){
			if('0'!=str.charAt(i)){
				break;
			}else{
				count++;
			}
		}
		System.out.println(count);
	}

	// 求出所有的0
	private static void demo1(BigInteger bi1) {
		String str = bi1.toString();// 获取字符串表现形式
		int count = 0;
		for (int i = 0; i < str.length(); i++) {
			if ('0' == str.charAt(i)) { // 如果字符串中出现了0则计数器加1
				count++;
			}
		}
		System.out.println(count);
	}

那么如果我们用递归来做的话,这个问题就会非常简单了,

//求出1000的阶乘所有零和尾部零的个数,用递归做
public class h {

	public static void main(String[] args) {
		System.out.println(fun(1000));

	}
	public static int fun(int num){
		
		if(num>0 && num<5){
			return 0;
		}else{
			return num/5 + fun(num/5);
		}
	}
}

File类递归练习(统计该文件夹大小)
需求:,从键盘接收一个文件夹路径,统计该文件夹大小

</pre><pre name="code" class="java">/*
	 * 从键盘接收一个文件夹路径
	 * 定义一个无限循环
	 * 将键盘录入的结果存储并封装成File对象
	 * 对File对象判断
	 * 将文件夹路径对象返回
	 * 
	 * 
	 * 统计该文件夹大小
	 * 1、定义一个求和变量
	 * 2、获取该文件夹下所有的文件和文件夹listFiles();
	 * 3、遍历数组
	 * 4、判断是文件就计算大小并累加
	 * 5、判断是文件夹就递归调用
	 * 
	 * 
	 */

	public static void main(String[] args){
		File dir=getDir();
		System.out.println(getFileLength(dir));
	}
	
	public static File getDir(){
		Scanner sc=new Scanner(System.in);
		System.out.println("请输入一个文件夹路径");
		while(true){
			String line=sc.nextLine();
			File dir=new File(line);
			if(!dir.exists()){
				System.out.println("目录不存在");
			}else if(dir.isFile()){
				System.out.println();
			}else{
				return dir;
			}	
		}
	
	}
	
	public static long getFileLength(File dir){
		long len=0;
		File[] files=dir.listFiles();
		for(File file :files){
			if(file.isFile()){
				len=len+file.length();
			}else{
				len=len+getFileLength(file);
			}
		}
		return len;
	}




File类递归练习(删除该文件夹)
需求:,从键盘接收一个文件夹路径,删除该文件夹

分析:

/*
	 * 1、获取该文件夹下的所有文件和文件夹
	 * 2、遍历数组
	 * 3、判断是文件直接删除
	 * 4、如果是文件夹,递归调用
	 * 5、循环结束后,把控文件夹删除
	 * 
	 */

	public static void main(String[] args) {
		File dir=a.getDir();
		deleteFile(dir);

	}
	public static void deleteFile(File dir){
		File[] subFiles=dir.listFiles();
		for(File file:subFiles){
			if(file.isFile()){
				file.delete();
			}else{
				deleteFile(file);
			}
		}
		//循环结束后把文件夹删除掉
		dir.delete();
	}




File类递归练习(拷贝)
需求,从键盘接收两个文件夹路径,把其中一个文件夹中(包含内容)拷贝到另一个文件夹中

/*
	 * 1、在目标文件夹中创建原文件夹
	 * 2、获取原文件夹中所有的文件和文件夹,存储在File数组中
	 * 3、遍历数组
	 * 4、如果是文件就用io流读写
	 * 5、如果是文件夹就递归调用
	 * 
	 */
	public static void main(String[] args) throws IOException {
		File src=a.getDir();
		File dest=a.getDir();
		if(src.equals(dest)){
			System.out.println("目录文件夹是源文件夹的子文件夹");
		}else{
			copy(src,dest);
		}
	}

	public static void copy(File src, File dest) throws IOException {
		File newDir=new File(dest,src.getName());
		newDir.mkdir();
		File[] subFiles=src.listFiles();
		for (File file : subFiles) {
			if(file.isFile()){
				BufferedInputStream bis=new BufferedInputStream(new FileInputStream(file));
				BufferedOutputStream bos=new BufferedOutputStream(new FileOutputStream(new File(newDir,file.getName())));
				int b;
				while((b=bis.read())!=-1){
					bos.write(b);
				}
				bis.close();
				bos.close();
			}else{
				//如果是文件夹就递归调用
				copy(file,newDir);
			}
		}
		
	}




File类递归练习(按层级打印)
* 要求:,从键盘接收一个文件夹路径,把文件夹中的所有文件以及文件夹的名字按层级打印,

/*
	 * 1、获取所有文件和文件夹,返回的File数组
	 * 2、遍历数组
	 * 3、无论是文件还是文件夹,都需要直接打印
	 * 4、如果是文件夹,递归调用
	 * 
	 */
	public static void main(String[] args) {
		File dir=a.getDir();
		printLev(dir,0);
		
	}

	public static void printLev(File dir,int level) {
		File[] subFiles=dir.listFiles();
		for (File file : subFiles) {
			for(int i=0;i<=level;i++){
				System.out.print("\t");
			}
			System.out.println(file);
			if(file.isDirectory()){
				printLev(file,level+1);
			}
		}
		
	}






版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
二分查找的思路分析|学习笔记
快速学习二分查找的思路分析
0 0
算法系统学习-最最简单递归算法分析和迭代法
系列是基于有一定语言基础(C,C++,Java等等)和基本的数据结构基础进行的算法学习专栏,如果觉得有点吃力 😥 ,建议先了解前提知识再学习喔!本个专栏会将用更容易理解的表达去学习算法,如果在一些表述上存在问题还请各位多多指点
0 0
详细实例说明+典型案例实现 对迭代法进行全面分析 | C++
上面我们对迭代算法进行了细致的举例和经典代码的讲解。使用该算法时,要注意体会我们所要求的东西它在程序代码中的更新迭代过程,理解核心思想从而去更好的运用这种常用的经典算法解决常规问题。
0 0
Leetcode第1题至第10题 思路分析及C++实现
笔者按照目录刷题,对于每一道题,力争使用效率最高(时间复杂度最低)的算法,并全部通过C++代码实现AC。(文中计算的复杂度都是最坏情况复杂度) 因为考虑到大部分读者已经在Leetcode浏览过题目了,所以每道题都按照 解题思路 -> 实现代码 -> 问题描述 的顺序进行讲解。
1273 0
递归方法小综合
使用递归可以简化我们的理解,便于阅读,但是当数据量大的时候会占用较大的内存,所以程序运行的速度会大打折扣。 使用递归需要满足以下条件: 1、有终止条件(记住:递归不是死循环) 2、有递归部分,通俗的就是说,函数直接或间接的调用自身 下面是不同语言下实现的递归程序: 1...
504 0
大白话理解递归本质,可视化递归过程
大白话理解递归本质,可视化递归过程
0 0
冒泡排序思路分析 | 学习笔记
简介:快速学习冒泡排序思路分析
0 0
1418.点菜展示表 手把手教你对场景模拟题型的分析与解题方法,轻松解题!
1418.点菜展示表 手把手教你对场景模拟题型的分析与解题方法,轻松解题!
0 0
+关注
朱培
CSDN博客专家,大数据与云计算领域,常年活跃于Github、CSDN、开源中国等开源社区。
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载