循环与递归

  • 递归调用仅仅是被调函数恰为主调函数
  • 注意每次调用的层次不同
  • 注意每次分配形参并非同一个变量
  • 注意返回的次序

Q:打印从0 - n

  1. 循环

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public class A {
    //打印从0到n
    public static void fun(int n){
    //循环
    for (int i = 0; i <= n; i++) {
    System.out.println(i);
    }
    public static void main(String[] args) {
    fun(9);
    }
    }
  2. 递归

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public class A {
    //打印从0到n
    public static void f(int n){
    //递归
    if (n>0) f(n-1);
    System.out.println(n);;
    }
    public static void main(String[] args) {
    f(9);
    }
    }

Q:打印begin - end(递归)

1
2
3
4
5
6
7
8
9
10
11
public class A {
public static void f(int begin, int end){
if (begin>end)
return;
System.out.println(begin);
f(begin+1,end);
}
public static void main(String[] args) {
f(0,9);
}
}

Q:计算数组begin到结束的所有元素之和(递归)

1
2
3
4
5
6
7
8
9
10
11
12
13
public class A {
public static int f(int[] a, int begin){
if (begin==a.length)
return 0;
int x = f(a, begin+1);
return x+a[begin];
}
public static void main(String[] args) {
int[] a = {2,5,3,6,7,6,9,4,5,9,7,8,5,1,2,3};
int sum = f(a,0); //a 从第0项开始的累加值
System.out.println(sum);
}
}

Q:比较两个字符串是否相同

  1. 调用Java现成工具包

    1
    2
    3
    4
    5
    6
    7
    8
    public class A {
    public static boolean isSameString(String s1, String s2){
    return s1.equals(s2);
    }
    public static void main(String[] args) {
    System.out.println(isSameString("abc","abcd"));
    }
    }
  2. 递归

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public class A {
    public static boolean f(String s1, String s2){
    if (s1.length() != s2.length())
    return false;
    if (s1.length()==0)
    return true;
    if (s1.charAt(0) != s2.charAt(0))
    return false;
    return f(s1.substring(1),s2.substring(1));

    }
    public static void main(String[] args) {
    System.out.println(f("abc","abcd"));
    }
    }

经典递归问题

Q:在n个球中,任意取m个(不放回),求有多少种不同的取法

1
2
3
4
5
6
7
8
9
10
11
public class A {
public static int f(int n, int m){
if (n<m) return 0;
if (n==m) return 1;
if (m==0) return 1;
return f(n-1,m-1) + f(n-1,m); //想象在n个球中有一个特殊的球x,取法划分:包不包含x
}
public static void main(String[] args) {
System.out.println(f(10,3));
}
}

Q:求n个元素的全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class A {
public static void f(char[] data, int k){
if (k==data.length){
for (int i = 0; i < data.length; i++) System.out.print(data[i]);
System.out.println();
}
for (int i = k; i < data.length; i++) { //k:当前的交换位置(关注点),与其后的元素交换
{char t = data[k];data[k] = data[i];data[i] = t;} //试探
f(data, k+1);
{char t = data[k];data[k] = data[i];data[i] = t;} //回溯
}
}
public static void main(String[] args) {
char[] data = "ABCDE".toCharArray();
f(data,0);
}
}

Q:求两个串的最大公共子序列的长度

最大公共子序列:两个串在不逆向原有字符顺序所能得到的相同字符数量最多的公共子串

1
2
3
4
5
6
7
8
9
10
11
12
13
public class A {
public static int f(String s1, String s2){
if (s1.length()==0 || s2.length()==0) return 0;
if (s1.charAt(0) == s2.charAt(0))
return f(s1.substring(1), s2.substring(1)) + 1;
else
return Math.max(f(s1.substring(1),s2),f(s1,s2.substring(1)));
}
public static void main(String[] args) {
int k = f("fabckd","xbacd");
System.out.println(k);
}
}

递归真题训练

构建递归的要诀:

  1.找到相似性

  2.定义出口

Q:反转串问题

  • 题目如图:

image-20210313235244637

  • 解决方法:
1
2
3
4
5
6
7
8
9
public class A {
public static String f(String s){
if (s.length()==1) return s;
return f(s.substring(1)) + s.charAt(0);
}
public static void main(String[] args) {
System.out.println(f("abcd"));
}
}

Q:杨辉三角形问题

  • 题目如图:

image-20210313235139050

  • 解决方法:
1
2
3
4
5
6
7
8
9
10
public class A {
public static int f(int m,int n){
if (m == 0) return 1;
if (n==0 || n==m) return 1;
return f(m-1,n-1) + f(m-1,n);
}
public static void main(String[] args) {
System.out.println(f(5,3));
}
}

Q:组合数学问题

  • 题目如图:

image-20210315213100172

  • 解决方法:
1
2
3
4
5
6
7
8
9
public class A {
public static int g(int m,int n){
if (m==0 || n==0) return 1;
return g(m-1,n) + g(m,n-1);
}
public static void main(String[] args) {
System.out.println(g(3,2));
}
}

Q:整数的分划问题

  • 题目如图:

image-20210315214540223

  • 解决方法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class A {
public static void f(int n, int[] a, int k){
//对n进行加法划分
//a:缓冲;k:当前的位置
if (n <= 0){
for (int i = 0; i < k; i++)
System.out.print(a[i] + " ");
System.out.println();
return;
}
for (int i=n; i>0; i--){
if (k>0 && i > a[k-1]) continue;
a[k] = i;
f(n-i, a, k+1);
}
}
public static void main(String[] args) {
int[] a = new int[1000];
f(6,a,0);
}
}
  • 运行结果:

    image-20210315225051155

浮点数的注意事项

  • 浮点数:足够接近|a-b|<seta。。。不能判断两个浮点数精确相等

    eg:System.out.println(0.2+0.1 == 0.3); 结果为:false

浮点数在比较时:

  1.千万不能用‘ == ’

  2.如上例子可如此比较:System.out.println(Math.abs(0.2+0.1-0.3)<1E-10);

上述例子也可将方程左右同时扩大10倍,化为整数运算,如此做更安全。

  • float a = 3.0/0;

    double a = 3.0/0;

    上述两式a的值都为Infinity

    double a = -3.0/0;

    上式a的值为-Infinity

    1/a = 0.0

    满足极限运算法则

    无穷与无穷运算结果为NaN,即Not a Number

例题:

image-20210327215623811

  • 解决方法:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public class A {
    public static void main(String[] args) {
    for (int a = 20; a >=1; a--) {
    for (int b = a-1; b >= 1; b--) {
    for (int c = b-1; c >= 1; c--) {
    for (int d = c-1; d >= 1; d--) {
    //if (1/a + 1/b + 1/c + 1/d == 1)
    //注意上式有两个错误:
    //1.整型/整型只能得到整型,所以每一项结果都是0
    //2.浮点型不能出现"=="的写法,这是雷区
    if(b*c*d + a*c*d + a*b*d + a*b*c == a*b*c*d)
    System.out.println(a + "," + b + "," + c + "," + d);
    }
    }
    }
    }
    }
    }

  • 运行结果:

    image-20210327215801918