【递归与递推】数的计算|数的划分|耐摔指数

 1.数的计算 - 蓝桥云课 (lanqiao.cn)

思路：

 1.dfs的变量=>每一次递归什么在变？

        （1）当前数的大小一直在变：sum

        （2）最高位的数：k

2.递归出口：最高位数字为1

3.注意：尽量使用全局变量 

public class Main {static int n = 0;static int count = 0;public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();dfs(n,n);System.out.println(count);}public static void dfs(int sum,int k) {//sum表示：当前数的大小;k代表最高位的数//递归出口count++;if (k==1) {return;}for (int i = 1; i <= k/2; i++) {dfs(sum*10+i,i);}}
}

---

1.数的划分 - 蓝桥云课 (lanqiao.cn)

 思路：

1.dfs的变量=>每一次递归什么在变？

（1）m：已经选了几个数了

（2)  last：已经遍历到哪一个数了（因为为了避免重复，排序都是从小到大）

（3）sum：当前选定的几个数的和

2.递归出口

（1）已经选定的数m   ==  k  （但是满足不一样就符合要求）

 （2）看当前选定的几个数的和sum  == n

3.注意：尽量使用全局变量 

//数的划分
public class Main {static int n;static int k;static int count=0;public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();k = sc.nextInt();dfs(0, 1,0);System.out.println(count);}public static void dfs(int m, int last,int sum) {
//m代表选取了m个数了;last表示遍历到哪个数了;sum代表目前已经累计多大的数了if (m == k) {//递归出口if (sum==n) count++;return;}for (int i = last; i <= n-sum; i++) {dfs(m+1,i,sum+i);}}
}

---

 1.耐摔指数 - 蓝桥云课 (lanqiao.cn)

思路： 

最佳策略就是第一次从中间，也就是m=n/2开始测，此时有两种情况：

1.第一部手机摔坏了。那么第二部手机只能从第一层慢慢的一层一层的向上测  此时b[i]=i-1+1=i  （1是第一部手机测的那一次，i-1是第二部手机测的那i-1次）

2.第一部手机没摔坏。那么还剩两部手机可以从下一层往上测i-1次   此时b[i]=b[i-1]

b[i]=b[i-1]+i;  //上一部手机没摔坏+上一部手机摔坏

3.第三部手机的分析跟第二部手机的分析一样，第三部手机相对于第二部手机来说是它的“第二部手机”  

c[i]=c[i-1]+b[i-1]+1;   //上一步手机没摔坏+上一部手机摔坏

public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] f2=new int[10010];//表示两步手机测i次的情况下能测的层数int[] f3=new int[10010];//表示三步手机测i次的情况下能测的层数int n = sc.nextInt();int i = 0;while(f3[i]<n) {i++;f2[i] = f2[i-1] + i;f3[i] = f3[i-1] + f2[i-1] + 1;}System.out.println(i);}
}