递归之兔子问题

谁践踏了优雅 2022-06-06 05:49 246阅读 0赞

1.有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问第二十个月的兔子对数为多少？

(使用递归去解决)

分析：首先我们要明白题目的意思指的是每个月的兔子总对数；假设将兔子分为小中大三种，兔子从出生后三个月后每个月就会生出一对兔子，

那么我们假定第一个月的兔子为小兔子，第二个月为中兔子，第三个月之后就为大兔子，那么第一个月分别有1、0、0，第二个月分别为0、1、0，

第三个月分别为1、0、1，第四个月分别为,1、1、1，第五个月分别为2、1、2，第六个月分别为3、2、3，第七个月分别为5、3、5……

兔子总数分别为：1、1、2、3、5、8、13……

于是得出了一个规律，从第三个月起，后面的兔子总数都等于前面两个月的兔子总数之和，即为斐波那契数列。

package com.hui.test;
    /**
     * 有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，
     * 假如兔子都不死，问第二十个月的兔子对数为多少？(使用递归去解决)
     * 
     * */
    public class Homework1 {
    	public static void main(String[] args) {
    		int i = 20;
    		
    		System.out.println("兔子第"+i+"个月的总数为："+f(i));
    		
    	}
    	public static int f(int x) {
    		//第一月和第二月都是1对
    		if(x == 1 || x == 2) {
    			return 1;
    		}else {//第三个月开始是之前两个月的数量之和
    			return f(x-1)+f(x-2);
    		}
    		
    	}
    }

![Center][]

2:定义一个数组,比如:int\[\] arr = \{13,24,57,69,80\}使用二分查找查找这个数组中的24元素对应的索引

**二分法思想：**

假如有一组数为3，12，24，36，55，68，75，88要查给定的值24.可设三个变量front，mid，end分别指向数据的[上界][Link 1]，中间和下界，mid=（front+end）/2.

1.开始令front=0（指向3），end=7（指向88），则mid=3（指向36）。因为mid>x，故应在前半段中查找。

2.令新的end=mid-1=2，而front=0不变，则新的mid=1。此时x>mid，故确定应在后半段中查找。

3.令新的front=mid+1=2，而end=2不变，则新的mid=2，此时a\[mid\]=x，查找成功。

4.如果要查找的数不是数列中的数，例如x=25，当第三次判断时，x>a\[mid\]，按以上规律，令front=mid+1，即front=3，出现front>end的情况，表示查找不成功。

3:统计大串中小串出现的次数

举例：在字符串” woaijavawozhenaijavawozhendeaijavawozhendehenaijavaxinbuxinwoaijavagun”中java出

现了5次

package org.westos_10_作业;
    /**
     *需求 
     * 3:统计大串中小串出现的次数
            举例：在字符串” woaijavawozhenaijavawozhendeaijavawozhendehenaijavaxinbuxinwoaijavagun”中java出
            现了5次
    
     * */
    public class Homework3 {
    	public static void main(String[] args) {
    		//定义一个字符串
    		String str = "woaijavawozhenaijavawozhendeaijavawozhendehenaijavaxinbuxinwoaijavagun";
    		
    		int count = 0;
    		for(int i=0;i<str.length()-3;i++) {
    			//使用subString方法获得字符串的一部分并返回
    			String s = str.substring(i, i+4);
    			if("java".equals(s)) {
    				count++;
    			}
    		}
    		System.out.println("一共有"+count+"个java");
    	}
    }

[Center]: /images/20220606/a9f1c67c584d47dfad5a69ce0be1adf4.png
[Link 1]: https://baike.baidu.com/item/%E4%B8%8A%E7%95%8C