蓝桥杯AcWing学习笔记 1-1递归的学习（Java）

蓝桥杯

我的AcWing

题目及图片来自蓝桥杯C++ AB组辅导课

递归

利用递归+dfs枚举全排列

递归搜索树

每一个递归问题都可以画成递归搜索树求解。

例题

AcWing 92. 递归实现指数型枚举

高中数学集合问题

思想：考虑选不选这个数。

importjava.util.Scanner;publicclassMain{staticint n,N=16;staticint[] st =newint[N];// 状态，记录每个位置当前的状态：0表示还没考虑，1表示选它，2表示不选它publicstaticvoidmain(String[] args){Scanner sc =newScanner(System.in);
        n = sc.nextInt();dfs(1);}privatestaticvoiddfs(int u){if(u > n){for(int i =1; i <= n; i++){if(st[i]==1){System.out.print(i +" ");}}System.out.println();return;}

        st[u]=2;dfs(u +1);// 第一个分支：不选// 这两行恢复现场加不加都一样的 // 因为递归时会被下面的值给覆盖掉 所以不用手动恢复 这里加上是让代码看起来更加圆滑 更加还原算法本身
        st[u]=0;// 恢复现场

        st[u]=1;dfs(u +1);// 第二个分支：选
        st[u]=0;}}

Acwing 94. 递归实现排列型枚举

高中数学枚举

，输出n个数所有排列的次序。

题中说按字典序排列，但我们枚举后搜索树已经是按照字典序排列了。

思想：

1. 依次枚举每个数放到哪个位置
2. 依次枚举每个位置放那个数（本题代码）

importjava.util.Scanner;publicclassMain{staticint n,N=10;staticint[] state =newint[N];// 0表示还没放数，1~n表示放了哪个数staticboolean[] used =newboolean[N];// true表示用过，false表示还未用过publicstaticvoidmain(String[] args){Scanner sc =newScanner(System.in);
        n = sc.nextInt();dfs(1);}privatestaticvoiddfs(int u){if(u > n){// 边界for(int i =1; i <= n; i++){System.out.print(state[i]+" ");// 打印方案}System.out.println();return;}// 依次枚举每个分支，即当前位置可以填哪些数for(int i =1; i <= n; i++){if(!used[i]){
                state[u]= i;
                used[i]=true;dfs(u +1);// 恢复现场
                state[u]=0;
                used[i]=false;}}}}

AcWing 93. 递归实现组合型枚举

1~5选3个数，升序排列

思想：组合型枚举就是把指数型符合长度的结果挑出来。

优化：

剪枝

，优化dfs，假如第一个数是4，那么只有5可以选，凑不成3个数，第一个数是5也同理，所以第一个数不需要考虑4和5的分支。

importjava.util.Scanner;publicclassMain{staticint n, m,N=26;staticScanner sc =newScanner(System.in);staticint[] way =newint[N];publicstaticvoidmain(String[] args){
        n = sc.nextInt();
        m = sc.nextInt();dfs(1,1);}privatestaticvoiddfs(int u,int start){if(u + n - start < m)return;// 剪枝 优化dfs 如果把后面所有数全选上，都不够m个，当前分支就一定无解if(u == m +1){// 边界for(int i =1; i <= m; i++){System.out.print(way[i]+" ");// 打印方案}System.out.println();return;}for(int i = start; i <= n; i++){
            way[u]= i;dfs(u +1, i +1);
            way[u]=0;// 恢复现场}}}

第四届2013年蓝桥杯真题

AcWing 1209. 带分数

JavaB组第9题

同样暴力枚举

n = a + b / c

，两边同时乘c，

c·n = c·a + b

，n已知，枚举a，b，c即可求解。

importjava.util.Scanner;publicclassMain{staticfinalintN=10;staticint n;// 输入的目标数staticint cnt;// 最后的结果数staticint[] num =newint[N];// 保存全排列的结果staticboolean[] used =newboolean[N];// 标记数字状态 true表示已使用，false表示未使用staticScanner sc =newScanner(System.in);publicstaticvoidmain(String[] args){
        n = sc.nextInt();dfs(0);System.out.print(cnt);}privatestaticvoiddfs(int u){if(u ==9){// 两层循环将数组分成三段for(int i =0; i <7; i++){for(int j = i +1; j <8; j++){int a =calc(0, i);if(a >= n)return;// 优化：如果a比n还大 说明无解 直接returnint b =calc(i +1, j);int c =calc(j +1,8);if(a * c + b == c * n){// n = a + b / c 化为 c·n = c·a + b
                        cnt++;}}}return;}// 全排列模板for(int i =1; i <=9; i++){if(!used[i]){
                used[i]=true;
                num[u]= i;dfs(u +1);
                used[i]=false;// 恢复现场}}}// 在数组中计算某一区间的数privatestaticintcalc(int l,int r){int res =0;for(int i = l; i <= r; i++){
            res = res *10+ num[i];}return res;}}

y总的优化方案（很难）：其实我们不用枚举b了，当枚举完a和c后，利用公式变换得到

b = c·n - c·a

即得到b的值。

importjava.util.Scanner;importjava.util.Arrays;publicclassMain{staticfinalintN=10;staticint n;// 输入的目标数staticint ans;// 最后的结果数staticboolean[] st =newboolean[N];// 标记数字状态 true表示已使用，false表示未使用staticboolean[] backup =newboolean[N];// 判重数组，备份staticScanner sc =newScanner(System.in);publicstaticvoidmain(String[] args){
        n = sc.nextInt();dfs_a(0,0);System.out.print(ans);}privatestaticvoiddfs_a(int u,int a){if(a >= n)return;if(a !=0)dfs_c(u, a,0);for(int i =1; i <=9; i++){if(!st[i]){
                st[i]=true;dfs_a(u +1, a *10+ i);
                st[i]=false;// 恢复现场}}}privatestaticvoiddfs_c(int u,int a,int c){if(u >9)return;if(check(a, c)) ans++;for(int i =1; i <=9; i++){if(!st[i]){
                st[i]=true;dfs_c(u +1, a, c *10+ i);
                st[i]=false;// 恢复现场}}}privatestaticbooleancheck(int a,int c){long b = n *(long)c - a * c;// 这里要定义为long，要不然可能会溢出if(a ==0|| b ==0|| c ==0)returnfalse;// 不包含0，直接返回

        backup =Arrays.copyOf(st, st.length);// 将st数组的值copy到backup里，保持st原样，更改backup里面的值while(b !=0){int x =(int)(b %10);// 取个位
            b /=10;// 把个位删掉if(x ==0|| backup[x])returnfalse;
            backup[x]=true;}for(int i =1; i <=9; i++){if(!backup[i])returnfalse;}returntrue;}}

有对代码不理解的地方可以在下方评论。