第5章 函数的递归调用

1、斐波那契数列？

算法分析：

表达式：f[i] = a * f[i - 1] + b * f[i - 2],为了让代码好些，直接从1到100都弄出来，直接输出f[n]

时间复杂度

Java代码

import java.util.Scanner;

public class Main{
    static int N = 110;
    static int n,a,b,p;
    static int[] f = new int[N];
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        a = scan.nextInt();
        b = scan.nextInt();
        p = scan.nextInt();
        f[1] = 1;
        f[2] = 1;
        for(int i = 3;i <= 100;i ++)
        {
            f[i] = (a * f[i - 1] + b * f[i - 2]) % p;
        }
        System.out.println(f[n]);
    }
}

2、递归函数3

算法分析：

通过递归的形式，直接按照表达式输出

时间复杂度

Java代码

import java.util.Scanner;

public class Main{
    static int N = 110;
    static int n;
    static int[] f = new int[N];
    static int dfs(int x)
    {
        if(x <= 0) return 0;
        if(x == 1) return 1;
        if(x > 1 && x % 2 == 0) return 3 * dfs(x / 2) - 1;
        if(x > 1 && x % 2 == 1) return 3 * dfs((x + 1)/ 2) - 1;
        return 0;
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        System.out.println(dfs(n));
    }
}

3、阿克曼函数

算法分析：

通过递归的形式，直接按照表达式输出

Java代码

import java.util.Scanner;

public class Main{
    static int N = 110;
    static int n,m;
    static int[] f = new int[N];
    static int dfs(int m,int n)
    {
        if(m == 0) return n + 1;
        if(n == 0 && m > 0) return dfs(m - 1,1);
        if(m > 0 && n > 0) return dfs(m - 1,dfs(m,n - 1));
        return 0;
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        m = scan.nextInt();
        n = scan.nextInt();
        System.out.println(dfs(m,n));
    }
}

4、字符串弱等于

算法分析：

审题很重要，分为几点

• 1、a == b 返回true
• 2、若为偶数，将a和b中分，分成a1,a2,b1,b2
  dfs(a1,b1) && dfs(a2,b2)成立或者
  dfs(a1,b2) && dfs(a2,b1)成立则返回true
• 3、其余情况均返回false

时间复杂度

Java代码

import java.util.Scanner;

public class Main{
    static boolean dfs(String a,String b)
    {
        if(a.equals(b)) return true;
        if(a.length() == 1) return false;
        if(a.length() % 2 == 0 && a.length() == b.length())
        {
            int mid = a.length() / 2;
            String a1 = a.substring(0,mid); 
            String a2 = a.substring(mid); 
            String b1 = b.substring(0,mid); 
            String b2 = b.substring(mid); 
            if((dfs(a1,b1) && dfs(a2,b2)) || (dfs(a1,b2) && dfs(a2,b1))) return true;
            else return false;
        }
        return false;
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String a = scan.next();
        String b = scan.next();
        if(dfs(a,b)) System.out.println("YES");
        else System.out.println("NO");
    }
}