精华内容
下载资源
问答
  • 蓝桥杯递归习题.doc

    2021-07-05 18:07:21
    蓝桥杯递归习题.doc
  • 最近几天在刷蓝桥杯往年的真题, 发现数据结构方面的考察较少, 许多问题可以通过递归解决. 还有两套往年试题没有刷, 先就已经刷的题目总结一下. 几种常见的递归题目 1. 类型一 2. 类型二 3. 类型三 4. 类型四 5. 其他...

    最近几天在刷蓝桥杯往年的真题, 发现数据结构方面的考察较少, 许多问题可以通过递归解决. 还有两套往年试题没有刷, 先就已经刷的题目总结一下.

    几种常见的递归题目

    1. 类型一
    2. 类型二
    3. 类型三
    4. 类型四
    5. 其他类型


    类型一

    描述: 这类递归题目的原型是让一个字符串全排列, 比如说现在有字符串"abc", 它还可以有"acb", "bac", "bca", "cab", "cba"等排列方式. 通过全排列的方式可以得到全部可能的结果, 然后再从可能的结果中选出符合要求的结果.

    这种题目一般有两个考察重点, 一个是全排列怎么写,(这个代码套路是固定的)
    另外一个就是判断某个排列是否符合要求, 在判断这一步能考很多细节

    例题: 带分数
    • 100 可以表示为带分数的形式:100 = 3 + 69258 / 714
    • 还可以表示为:100 = 82 + 3546 / 197
    • 注意特征带分数中,数字1~9分别出现且只出现一次(不包含0)。
    • 类似这样的带分数,100 有 11 种表示法。
    题目要求:
    从标准输入读入一个正整数N (N<1000*1000)
    程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
    注意:不要求输出每个表示,只统计有多少表示法!
    
    例如:
    用户输入:
    100
    程序输出:
    11
    
    再例如:
    用户输入:
    105
    程序输出:
    6
    题目分析:
    • 这是一道典型非常典型的题目. 1~9个数字每个自能出现一次, 为了求出所有结果, 我们必须先求出所有的数字组合, 然后再判断每个数字组合是否能凑出这样的带分数.
    public class DaiFenShu {
        
        public static int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        public static int n;
        public static int res = 0;//记录结果
        
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            n = sc.nextInt();
            process(0);//全排列
            System.out.println(res);
        }
        
        public static void process(int index){
            if(index == arr.length){
                check();//得出一种排列, 判断排列是否符合要求.
                return;
            }
            for(int i = index; i < arr.length; i++){
                swap(i, index);
                process(index + 1);
                swap(i, index);
            }
        }
        
        public static void check(){
            for(int i = 0; i < arr.length - 3; i++){
                for(int j = i + 1; j < arr.length - 2; j++){
                    int jiaShu = getNum(0, i);//带分数种的加数
                    int fenZi = getNum(i + 1, j);//分子
                    int fenMu = getNum(j + 1, arr.length - 1);//分母
                    if(fenZi % fenMu == 0 && jiaShu + fenZi / fenMu == n){//分子要能整除分母(也可以用float保存3种数, 就不用判断整除)
                        res++;
                    }
                }
            }
        }
        
        public static int getNum(int i, int j){
            int num = 0;
            int system = 1;//用于算10的次方的基数, 如果用系统Math.pow()算10次方的话会慢很多.
            for(int n = j; n >= i; n--){
                num += arr[j--] * system;
                system *= 10;
            }
            return num;
        }
        
        public static void swap(int i, int j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

     


    类型二

    描述: 我曾经在学习汉诺塔问题的时候, 被那简单的几行代码惊艳到. 这种类型的递归我擅自给他命名为状态转移型递归. 类似这种套路的递归在很多问题中也能用到, 比如下面的例题, 两人博弈, 大家的操作都是一样的, 就是状态发生了变化.

    例题: 取球博弈

    • 两个人玩取球的游戏。
    • 一共有N个球,每人轮流取球,每次可取集合{n1,n2,n3}中的任何一个数目。
    • 如果无法继续取球,则游戏结束。
    • 此时,持有奇数个球的一方获胜。
    • 如果两人都是奇数,则为平局。
    • 假设双方都采用最聪明的取法,
    • 第一个取球的人一定能赢吗?
    • 试编程解决这个问题。
    • 输入格式:
    • 第一行3个正整数n1 n2 n3,空格分开,表示每次可取的数目 (0<n1,n2,n3<100)
    • 第二行5个正整数x1 x2 ... x5,空格分开,表示5局的初始球数(0<xi<1000)
    • 输出格式:
    • 一行5个字符,空格分开。分别表示每局先取球的人能否获胜。
    • 能获胜则输出+,
    • 次之,如有办法逼平对手,输出0,
    • 无论如何都会输,则输出-
    例如,输入:
    1 2 3
    1 2 3 4 5
    
    程序应该输出:
    + 0 + 0 -
    
    再例如,输入:
    1 4 5
    10 11 12 13 15
    
    程序应该输出:
    0 - 0 + +
    
    再例如,输入:
    2 3 5
    7 8 9 10 11
    
    程序应该输出:
    + 0 0 0 0
    
    资源约定:
    峰值内存消耗(含虚拟机) < 256M
    CPU消耗  < 3000ms

    思路

    • 首先要明确每一局的情况, 假设一局有x个球, 取球情况的数组为n.
    32520
    • 在每一局中, 某一方取球都会根据取球情况数组进行试探, 如上图.
    • 在每次递归中, 需要的参数有当前剩下的球, 我摸的球数, 对手摸的球数.
    • 如何才能判断一局的胜负? 在所有情况中, 只要对手输过, 结果就是赢; 如果对手没输过, 但是平过, 结果就是平; 否则, 结果就是输. (因为题目条件: 双方都采取最聪明的办法)
    • 最大的难点在于在于递归的过程中, 不是每次都是我摸, 而是我摸一次, 对手摸一次, 这里恰好就是这种类型递归的魅力所在.
    • 具体落实到代码中
    public class QuQiuBoYi {
        
        public static int[] n = new int[3];
        public static int[] m = new int[5];
        
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            for(int i = 0; i < 3; i++){
                n[i] = sc.nextInt();
            }
            Arrays.sort(n);
            for(int i = 0; i < 5; i++){
                m[i] = sc.nextInt();
                char res = process(m[i], 0, 0);//每输入一局的球数, 就计算一局
                System.out.print(res + " ");
            }
        }
        
        public static char process(int num, int me, int you){
            if(num < n[0]){//没球可摸,进行结算
                if((me & 1) != 0 && (you & 1) == 0){//我奇数, 对手偶数, 赢
                    return '+';
                }else if((me & 1) == 0 && (you & 1) != 0){//我偶数, 对手奇数, 输
                    return '-';
                }else{
                    return '0';//平
                }
            }
            boolean draw = false;
            for(int i = 0; i < 3; i++){
                if(num >= n[i]){
                    //重点!假设当前这轮是我摸球, 在我摸完球me+n[i]后, 就到对手摸, me和you的位置转换, 设定中间的参数是摸球的一方
                    char res = process(num - n[i], you, me + n[i]);
                    if(res == '-'){//由于下一轮是对手摸球, 如果他输了
                        return '+';//我就赢了
                    }else if(res == '0'){//如果有平局, 要记录下来
                        draw = true;
                    }
                }
            }
            return draw ? '0' : '-';
        }
    }

    优化

    • 作为编程大题, 如果不优化是过不了极端的数据样本的.
    • 这题可以用数组记录重复出现的情况, 进行记忆型递归, 用空间换时间.
    • 问题来了: me和you是不断交换的, 怎样才算是一种情况?
    • 在base case中, 最后决定输赢的, 不是你我手上有多少个球, 而是你我的球数的奇偶情况, 所以我们把每一种情况记录为: 剩余的球数和双方球数的奇偶情况.
    public class Nine {
        
        public static int[] n = new int[3];
        public static int[] m = new int[5];
        public static char[][][] cache = new char[1000][2][2];
        
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            for(int i = 0; i < 3; i++){
                n[i] = sc.nextInt();
            }
            Arrays.sort(n);
            for(int i = 0; i < 5; i++){
                m[i] = sc.nextInt();
                char res = process(m[i], 0, 0);
                System.out.print(res + " ");
            }
        }
        
        public static char process(int num, int me, int you){
            if(num < n[0]){
                if((me & 1) != 0 && (you & 1) == 0){
                    return '+';
                }else if((me & 1) == 0 && (you & 1) != 0){
                    return '-';
                }else{
                    return '0';//平
                }
            }
            if(cache[num][me][you] != '\0'){
                return cache[num][me][you]; 
            }
            boolean draw = false;
            for(int i = 0; i < 3; i++){
                if(num >= n[i]){
                    char res = process(num - n[i], you, ((me + n[i]) & 1) == 0 ? 0 : 1);//只记录奇偶情况
                    if(res == '-'){
                        cache[num][me][you] = '+';
                        return '+';
                    }else if(res == '0'){
                        draw = true;
                    }
                }
            }
            if(draw){
                cache[num][me][you] = '0';
                return '0';
            }else{
                cache[num][me][you] = '-';
                return '-';
            }
        }
    }

     


    类型三

    描述: 第二种递归, 这种题目一般都和走矩阵和走格子有关, 每一层递归里面都要进行操作, 每次递归都会影响到最后的结果. 每一次递归, 根据参数可以确定为一种状态, 如果固定的状态对应固定的结果, 称之为无后效性递归, 这样的递归就可以通过画表格, 填表格的方式改成动态规划. 如果不改成动态规划的话, 可以用数组记录下每个状态对应的结果, 如果再次来到这种状态, 可以直接查表得出结果, 进行记忆型递归.

    例题: 地宫寻宝

    • X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。
    • 地宫的入口在左上角,出口在右下角。
    • 小明被带到地宫的入口,国王要求他只能向右或向下行走。
    • 走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。
    • 当小明走到出口时,如果他手中的宝贝恰好是k件,则这些宝贝就可以送给小明。
    • 请你帮小明算一算,在给定的局面下,他有多少种不同的行动方案能获得这k件宝贝。
    输入一行3个整数,用空格分开:n m k (1<=n,m<=50, 1<=k<=12)
    
    接下来有 n 行数据,每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值
    
    要求输出一个整数,表示正好取k个宝贝的行动方案数。该数字可能很大,输出它对 1000000007 取模的结果。
    
    例如,输入:
    2 2 2
    1 2
    2 1
    程序应该输出:
    2
    
    再例如,输入:
    2 3 2
    1 2 3
    2 1 5
    程序应该输出:
    14
    
    资源约定:
    峰值内存消耗(含虚拟机) < 256M
    CPU消耗  < 2000ms
    解题思路:
    • 每来到一个格子, 先判断能不能拿起宝贝. 如果能不能拿起来, 就有两种选择, 往右或下走; 如果能拿起来, 就有4种选择, 往右或下走, 并选择是否拿起宝贝. 所以在递归的过程中除了传递位置的参数, 还要维护一个当前宝贝的最大值, 和一个已经拿了多少个宝贝的变量. 为了能达到时间和空间的要求, 必须使用记忆数组优化.
    public class DiGongXunBao {
        
        public static int n;
        public static int m;
        public static int k;
        public static int mod = 1000000007;
        public static int[][] arr = new int[50][50];
        public static int[][][][] dp = new int[50][50][15][15];
        
        public static void main(String[] args) {
            initDp();
            Scanner sc = new Scanner(System.in);
            n = sc.nextInt();
            m = sc.nextInt();
            k = sc.nextInt();
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    arr[i][j] = sc.nextInt();
                }
            }
            System.out.println(process(0, 0, -1, 0));
        }
        
        public static int process(int x, int y, int max, int cur){
            if(dp[x][y][max + 1][cur] != -1){
                return dp[x][y][max + 1][cur];
            }
            if(x == n - 1 && y == m - 1){
                if(cur == k || (arr[x][y] > max && cur == k - 1)){
                    return 1;
                }
            }
            if(x >= n || y >= m || cur > k){
                return 0;
            }
            int value = arr[x][y];
            int res = 0;
            if(value > max){
                res += process(x + 1, y, value, cur + 1);
                res %= mod;
                res += process(x, y + 1, value, cur + 1);
                res %= mod;
            }
            res += process(x + 1, y, max, cur);
            res %= mod;
            res += process(x, y + 1, max, cur);
            res %= mod;
            dp[x][y][max + 1][cur] = res;
            return dp[x][y][max + 1][cur];
        }
        
        public static void initDp(){
            for(int a = 0; a < 50; a++){
                for(int b = 0; b < 50; b++){
                    for(int c = 0; c < 15; c++){
                        for(int d = 0; d < 15; d++){
                            dp[a][b][c][d] = -1;
                        }
                    }
                }
            }
        }
    }

     


    类型四

    描述: 每次递归时的操作受到之前递归的限制. 典型的是八皇后问题. 每次递归填的数会限制到下一次递归填的数. 这种问题要注意一个关键的因素是要进行回溯. 因为如果不回溯的话下一步的递归就不能遍历所有可能性. 看具体例子.

    例题: 方格填数
    • 如下的10个格子
       +--+--+--+
       |  |  |  |
    +--+--+--+--+
    |  |  |  |  |
    +--+--+--+--+
    |  |  |  |
    +--+--+--+
    • 填入0~9的数字。要求:连续的两个数字不能相邻。
      (左右、上下、对角都算相邻)
    • 一共有多少种可能的填数方案?
    • 请填写表示方案数目的整数。
    解题思路:
    • 每次递归填一个数要考虑连续的数不能相邻, 也就是要考虑一个数周围的8个格子的数都不能与其相邻. 如果直接在原图的不规则矩阵中操作会非常不方便, 可以通过扩充矩阵, 让每个格子周围都有8个格子.
    扩充成5*6的矩阵
    +--+--+--+--+--+--+
    |xx|xx|xx|xx|xx|xx|
    +--+--+--+--+--+--+
    |xx|xx|  |  |  |xx|
    +--+--+--+--+--+--+
    |xx|  |  |  |  |xx|
    +--+--+--+--+--+--+
    |xx|  |  |  |xx|xx|
    +--+--+--+--+--+--+
    |xx|xx|xx|xx|xx|xx|
    +--+--+--+--+--+--+
    public class FangGeTianShu {
        
        public static int res = 0;
        public static int[] a = new int[10];
        public static int[][] p = new int[5][6];
        
        public static void main(String[] args) {
            initP();
            process(1, 2);
            System.out.println(res);
        }
        
        public static void process(int x, int y){
            if(x == 3 && y == 4){
                res++;
                return;
            }
            for(int i = 0; i <= 9; i++){
                if(canFill(i, x, y) && a[i] == 0){
                    p[x][y] = i;
                    a[i] = 1;
                    if(y == 4){
                        process(x + 1, 1);
                    }else{
                        process(x, y + 1);
                    }
                    a[i] = 0;
                    p[x][y] = -10;
                }
            }
        }
        
        public static boolean canFill(int num, int x, int y){
            for(int i = -1; i <= 1; i++){
                for(int j = -1; j <= 1; j++){
                    if(i == 0 && j == 0) continue;
                    if(Math.abs(p[x + i][y + j] - num) <= 1){
                        return false;
                    }
                }
            }
            return true;
        }
        
        public static void initP(){
            for(int i = 0; i < 5; i++){
                for(int j = 0; j < 6; j++){
                    p[i][j] = -10;
                }
            }
        }
    }
    

     


    其他类型

    描述: 其他类型递归这里暂且只描述一种, 它令我印象深刻. 在一个大问题中要拆分成许多个小问题, 大问题的答案要通过小问题的答案生成. 对应在递归就是父递归要得出结果必须先通过子递归得出结果.

    例题: 生命之树

    • 在X森林里,上帝创建了生命之树。
    • 他给每棵树的每个节点(叶子也称为一个节点)上,都标了一个整数,代表这个点的和谐值。
      上帝要在这棵树内选出一个非空节点集S,使得对于S中的任意两个点a,b,都存在一个点列 {a, v1, v2, ..., vk, b} 使得这个点列中的每个点都是S里面的元素,且序列中相邻两个点间有一条边相连。
    • 在这个前提下,上帝要使得S中的点所对应的整数的和尽量大。
      这个最大的和就是上帝给生命之树的评分。
    • 经过atm的努力,他已经知道了上帝给每棵树上每个节点上的整数。但是由于 atm 不擅长计算,他不知道怎样有效的求评分。他需要你为他写一个程序来计算一棵树的分数。
    「输入格式」
    第一行一个整数 n 表示这棵树有 n 个节点。
    第二行 n 个整数,依次表示每个节点的评分。
    接下来 n-1 行,每行 2 个整数 u, v,表示存在一条 u 到 v 的边。由于这是一棵树,所以是不存在环的。
    
    「输出格式」
    输出一行一个数,表示上帝给这棵树的分数。
    
    「样例输入」
    5
    1 -2 -3 4 5
    4 2
    3 1
    1 2
    2 5
    
    「样例输出」
    8
    
    「数据范围」
    对于 30% 的数据,n <= 10
    对于 100% 的数据,0 < n <= 10^5, 每个节点的评分的绝对值不超过 10^6 。
    
    资源约定:
    峰值内存消耗(含虚拟机) < 256M
    CPU消耗  < 3000ms

    思路

    • 题目的意思是有一颗连通的树, 任意连通的点都可以构成一个点集, 现在的问题是如何求得一个和最大的点集.
    • 先根据样例输入画图, 画成一棵树的样子以便分析.
    o_%e7%94%9f%e5%91%bd%e4%b9%8b%e6%a0%91.png
    • 画树的时候选取根结点是任意的.
    • 我们以一棵树分析如何求最大和点集, 假设对结点2进行分析.
    • 以结点2为源头, 向子结点方向扩充子集的范围, 最开始子集里只有结点2, 也就是-2.
    • 遍历到左孩子4, 如果以该节点为源的子集的值大于0, 那么子集就加上这个结点, 因为这样会使子集的和增大. 于是子集的和变成-2 + 4 = 2.
    • 然后继续遍历孩子结点, 把结点5也加入进来, 最终子集的和变成2 + 5 = 7.
    • 这样便确认了以2为起点的点集的最大和.
    • 通过这一逻辑, 可以推出递归函数.
    public class ShengMingZhiShu {
        
        public static List<Integer>[] rel;
        public static int[] arr;
        
        public static void main(String[] args) {
            //处理输入
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            arr = new int[n + 1];
            rel = new ArrayList[n + 1];
            initRelArr();
            for(int i = 1; i < arr.length; i++){
                arr[i] = sc.nextInt();
            }
            for(int i = 0; i < n - 1; i++){
                int a = sc.nextInt();
                int b = sc.nextInt();
                rel[a].add(b);
                rel[b].add(a);
            }
            
            process(1, 0);
            int max = Integer.MIN_VALUE;
            for(int i = 1; i < arr.length; i++){
                max = Math.max(max, arr[i]);
            }
            System.out.println(max);
        }
        
        public static void process(int cur, int father){
            int max = arr[cur];//拿到当前结点的值作为初始值. 
            for(int i = 0; i < rel[cur].size(); i++){//遍历孩子点集
                int son = rel[cur].get(i);
                if(son == father) continue;//防止孩子点集中包含当前结点
                process(son, cur);//计算孩子点集的最大和
                if(arr[son] > 0){
                    max += arr[son];
                }
            }
            arr[cur] = max;//计算完以当前结点为源的点集的最大和, 保存进数组.
        }
        
        public static void initRelArr(){
            for(int i = 0; i < rel.length; i++){
                rel[i] = new ArrayList<Integer>();
            }
        }
    }

     


    总结

    • 蓝桥杯题目中很多题目能用递归解决, 在递归题目中相当一部分题目是有规律的, 在规律之下, 不同的题目又有不同的细节需要处理, 挺锻炼人的. 当然也有的递归题目不能用常规套路, 需要对具体题目具体分析. 希望自己能在比赛中做出更多题目.

    转载于:https://www.cnblogs.com/tanshaoshenghao/p/10542853.html

    展开全文
  • 蓝桥杯真题 递归

    2018-03-08 23:27:45
    思考 真题 39级台阶 小明刚刚看完电影《第39级台阶》。离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级! 站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶。先迈左脚,然后...
    • 真题 出栈顺序

    X星球特别讲究秩序,所有道路都是单行线。
    一个甲壳虫车队,共16辆车,按照编号先后发车,夹在其它车流中,缓缓前行。

    路边有个死胡同,只能容一辆车通过,是临时的检查站,如图所示。
    X星球太死板,要求每辆路过的车必须进入检查站,也可能不检查就放行,也可能仔细检查。
    如果车辆进入检查站和离开的次序可以任意交错。那么,该车队再次上路后,可能的次序有多少种?

    为了方便起见,假设检查站可容纳任意数量的汽车。
    显然,如果车队只有1辆车,可能次序1种;2辆车可能次序2种;3辆车可能次序5种。

    这里写图片描述

    解题代码不是没看懂

    这里写图片描述

    • 真题 趣味算式填符号
      这里写图片描述

    解题答案

    这里写图片描述

    • 思考题 真题 39级台阶

    小明刚刚看完电影《第39级台阶》。离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级!
    站在台阶前,他突然又想着一个问题:
    如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,也就是说一共要走偶数步。那么,上完39级台阶,有多少种不同的上法呢?
    请你利用计算机的优势,帮助小明寻找答案。

    • 作业

    公园票价为5角。假设每位游客只持有两种币值的货币:5角、1元。
    再假设持有5角的有m人,持有1元的有n人。
    由于特殊情况,开始的时候,售票员没有零钱可找。
    我们想知道这m+n名游客以什么样的顺序购票则可以顺利完成购票过程。
    显然,m < n的时候,无论如何都不能完成;
    m>=n的时候,有些情况也不行。比如,第一个购票的乘客就持有1元。
    请计算出这m+n名游客所有可能顺利完成购票的不同情况的组合数目。
    注意:只关心5角和1元交替出现的次序的不同排列,持有同样币值的两名游客交换位置并不算做一种新的情况来计数。

    要求给出两种解法

    展开全文
  • 样例输入 3 2 样例输出 5 思路:本采用递归的方法求解,假设我们现在m借鞋n还鞋,我们想办法拆分它,找出向下的一个表达式,并确定终止情况 首先我们定义函数的目的:我们的函数fun(m,n)是表示当m人还鞋n人借鞋的...

    这里写目录标题

    算法训练 未名湖边的烦恼

    资源限制
    时间限制:1.0s 内存限制:256.0MB
    问题描述
      每年冬天,北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋,可是人太多了,每天下午收工后,常常一双冰鞋都不剩。
      每天早上,租鞋窗口都会排起长龙,假设有还鞋的m个,有需要租鞋的n个。现在的问题是,这些人有多少种排法,可以避免出现体育组没有冰鞋可租的尴尬场面。(两个同样需求的人(比如都是租鞋或都是还鞋)交换位置是同一种排法)
    输入格式
      两个整数,表示m和n
    输出格式
      一个整数,表示队伍的排法的方案数。
    样例输入
    3 2
    样例输出
    5

    思路:本题采用递归的方法求解,假设我们现在m借鞋n还鞋,我们想办法拆分它,找出向下的一个表达式,并确定终止情况

    1. 首先我们定义函数的目的:我们的函数fun(m,n)是表示当m人还鞋n人借鞋的时、总的排序情况。
    2. 我们找到递归终止的条件:当m<n即 还鞋的人<借鞋的人 的时候,我们找不出排序的情况,返回0, 当n==0 即没有人借鞋的时候,我们返回1.
    3. 我们找到递归的关系式: m人还鞋n人借鞋的所有情况是怎样来的?(思考向下递归的过程), 只可能是m人还鞋n-1人借鞋的时候又有人借了一双以及m人-1还鞋n人借鞋时候又还了一双。所以fun(m,n)=fun(m-1,n)+fun(m,n-1)
      思考过程完毕,现在献上代码
    
    import java.util.Scanner;
    
    //未名湖畔 还鞋。
    public class Main {
       public static void main(String [] args){
           Scanner in =new Scanner(System.in);
           int m=in.nextInt();
           int n=in.nextInt();
           System.out.println(fun(m,n));
       }
    
       //fun()表示当前m人还鞋,n人组鞋 共有 fun(m,n)种排序。
       public static int fun(int m,int n){
       //递归终止条件,如果借的人多于还的人 则怎样都无法保证, 如果没有借的人,则只有一种排序方式。
       if (m<n)
        {
            return 0;//当借出数量<归还数量时
        }
       if (n==0)
        {
            return 1;
        }
           // 找到等价关系式。
           // 前面的fun(m-1,n)意思是还鞋子的一个人站在最前面,之后剩下的那些人再接着排序,fun(m,n-1) 意思是借鞋子的人站在最后面,剩下的再接着排序。
        return fun(m-1,n)+fun(m,n-1); //fun(m-1,n)和fun(m,n-1)表示下一次借鞋子和还鞋子的数量
       }
    }
    
    
    展开全文
  • 蓝桥杯递归练习2.docx
  • 蓝桥杯递归类型

    千次阅读 2017-04-09 09:51:45
    递归用在那些拐弯抹角的地方,用的是堆栈,存在效率问题,所以多用递推别用递归 递归的过程:回溯 - 结束递归条件 - 递推结果 (因为递归占内存:所以是慎选的方法) 答案为 18 public static int...
    1.计算年龄
    5个人坐在一起,问第5个人多少岁,他说比第4个人大2岁。问第4个人多少岁,他说比第3个人大2岁。问第3个人多少岁,他说比第2个人大2岁。问第2个人多少岁,他说比第1个人大2岁。问第1个人多少岁,他说是10岁。请问第5个人多大?
    -------------------------------------------------------------------------------------------------------------
    题目分析:
    递归用在那些拐弯抹角的地方,用的是堆栈,存在效率问题,所以多用递推别用递归
    递归的过程:回溯-结束递归条件-递推结果
    (因为递归占内存:所以是慎选的方法)
    答案为18
    public static int getYear(int num) {
         if(num<=1){
              return 10;
         }else{
              return getYear(num-1)+2;
         }
    }

    2.组合数
    从4个人中选2个人参加活动,一共有6种选法。
    从n个人中选m个人参加活动,一共有多少种选法?下面的函数实现了这个功能。
    请仔细分析代码,填写缺少的部分(下划线部分)。
    int f(int n, int m)
    {
    if(m>n) return 0;
         if(m==0) _______________;
    return f(n-1,m-1) + _____________;
    }
    --------------------------------------------------------------------------------------------------------------
    题目分析:
    1.当要选的人数多于总人数的时候,有0种情况
    2.当要选的人数为0的时候,只有一种情况,全部给你
    3.而递归的真正意义在于把4个人选2个人根据选不选这个人分割成:
         a.当我选这个人,剩下的情况就是n-1个人中选m-1个人。
         b.当我不选这个人的时候,剩下的就是n-1个人中选m个人。
    (这个递归就是将一个算式分割成两个残缺的算式,从而利用他们的差别获取答案)

    public static int f(int n, int m) {
         if(m>n){
              return 0;
         }
         if(m==0){
              return 1;
         }
         return f(n-1,m-1) + f(n-1,m);
    }
    程序的结点有两个:1.当取得人数多于总人数的时候     2.当要取的人数为0的时候,只有1种情况
    程序的公式采用的是将取人的过程分成两种情况:1.取了指定一个人  2.没有取这个人  两种情况的总和就是取人的所有可能
    结果:当输入4个取2个,结果为6


    3.Fibonacci数列

    Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1。

    当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少。
    输入格式
    输入包含一个整数n。
    输出格式
    输出一行,包含一个整数,表示Fn除以10007的余数。

    说明:在本题中,答案是要求Fn除以10007的余数,因此我们只要能算出这个余数即可,而不需要先计算出Fn的准确值,再将计算的结果除以10007取余数,直接计算余数往往比先算出原数再取余简单。
    样例输入
    10
    样例输出
    55
    样例输入
    22
    样例输出
    7704
    数据规模与约定
    1 <= n <= 1,000,000。
    --------------------------------------------------------------------------------------------------------------
    题目分析:
    1.我选用简单的递归方式来获取结果:
    public static int get(int num) {
         if(num==1||num==2){
              return 1;
         }
         return get(num-1)+get(num-2);
    }
    虽然部分结果出来了,但是运行严重超时,没有用到 直接计算余数往往比先算出原数再取余简 这个知识点。
    2.所以抛弃递归,采用递推正推的方式,不是知道1,2脚标的值么,一直加下去。(过程可以mod10007,切掉开头,对于要求的结果不会什么影响)
        ...
         al.add(0);
         al.add(1); //1
         al.add(1);  //2

         for (int i = 1; i <= n; i++) {
              al.add((al.get(i)+al.get(i+1))%10007);   //3开始
         }
         System.out.println(al.get(n));
    这里用0补上0脚标的位置,1,2脚标的位置用1补上,然后根据前面的元素做循环将后面的元素补上,最后输出所要求的脚标元素
    4.未名湖边的烦恼
    问题描述
      每年冬天,北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋,可是人太多了,每天下午收工后,常常一双冰鞋都不剩。
      每天早上,租鞋窗口都会排起长龙,假设有还鞋的m个,有需要租鞋的n个。现在的问题是,这些人有多少种排法,可以避免出现体育组没有冰鞋可租的尴尬场面。(两个同样需求的人(比如都是租鞋或都是还鞋)交换位置是同一种排法)
    输入格式
      两个整数,表示m和n
    输出格式
      一个整数,表示队伍的排法的方案数。
    样例输入
    3 2
    样例输出
    5
    数据规模和约定
      m,n∈[0,18]
    -------------------------------------------------------------------------------------------------------------
    题目分析:
    1.m人还鞋,n人借,结点就在于0人借的时候,排序有一种
    2. m人还,n人借可以分割:a.当少了一个人还  b.当少了一个人借(递归的情况就是两个式子的总和还是完整的。和选人的区别是,选人是选中+不选中。而鞋子是缺这+缺那)
    public static int shoeSort(int m, int n) {
         if(n>m){   //不符合的情况
              return 0;
         }
         if(n==0){     //取得人数为0,一种情况
              return 1;
         }
         return shoeSort(m-1, n)+shoeSort(m, n-1);   //少一个存的+少一个取=刚好平衡
    }


    5.斐波那契数列
    0,1,1,2,3,5,8,13,21,34,55...称为斐波那契数列。
    数列的第0项是0,第1项和第2项是1,第10项是55,它的第100项是多少?
    --------------------------------------------------------------------------------------------------------------------
    题目分析:
    1.要在不用递推的情况下用速度比较快的递归,所以要减少递归调用的次数。
    ...
    public static long f(int num,long[] arr) {
         if(arr[num]!=0){
              return arr[num];
         }
         if(num==1||num==2){
              return arr[num]=1;
         }
         return arr[num]=f(num-1,arr)+f(num-2,arr);
    }
    注意要点:这一题定义一个数组,然后传过来存储已经算出的信息。(其脚标对应没关系,能提取就行)
    答案是3736710778780434371


    6.搭积木
    小明最近喜欢搭数字积木,
    一共有10块积木,每个积木上有一个数字,0~9。
    搭积木规则:
    每个积木放到其它两个积木的上面,并且一定比下面的两个积木数字小。
    最后搭成4层的金字塔形,必须用完所有的积木。
    下面是两种合格的搭法:

       0
      1 2
     3 4 5
    6 7 8 9

       0
      3 1
     7 5 2
    9 8 6 4   

    请你计算这样的搭法一共有多少种?
    请填表示总数目的数字。

    题目分析:
    1.首先要获取的数量,所以定义一个计数器
    2.要存储数字,新建一个数字数组。但是有一些数字用过的就不要再用,所以在定义一个标识数组
    3.执行方法,用对数组的一项赋值,因为有很多值要尝试,所以用for循环。为了防止赋值重复,需要进行判断标识,当前这个数有没有用过。
    4.没有用的话使用这个数,标识使用过了,然后递归执行获取下一个数。但是当结束这条路要回溯标识。

    注意事项:
    1.排列的问题在节点处进行判断,将每一项进行比较筛选

     ... if(num==10){
              if(check()){   //判断是否符合情况
                  count++;
              }
              return;
         }

         for (int i = 0; i < 10; i++) {
              arr[num]=i;
              if(!isExist[arr[num]]){
                  isExist[arr[num]]=true;
                  f(num+1);
                  isExist[arr[num]]=false;
              }
         }...

    答案是: 768(完成时间:8min)
    要点注意:当要做多个数的全排列的时候,使用回溯:设置路线的判断,不行就回溯(可以解决重复数字的问题)
    7. 第39级台阶
        小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级!
        站在台阶前,他突然又想着一个问题:
        如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,也就是说一共要走偶数步。那么,上完39级台阶,有多少种不同的上法呢?
        请你利用计算机的优势,帮助小明寻找答案。

    题目分析:
    1.多种情况使用递归的方式
    2.解决减过多的问题,设置结点:当小于0,直接return上一层
    3.最后的结点,当阶梯走完,验证偶数步才++,否者还是需要return上一层
    4.两种情况交融配合的方式,将一阶和二阶写在一起
    ...
    public static void walk(int sta, int step) {
         if(sta<0){   //走过头
              return;
         }
         if(sta==0){
              if(step%2==0){
                  count++;
              }
              return;
         }
         walk(sta-1,step+1);
         walk(sta-2,step+1);
    }

    注意事项:
    1.阶梯结束不代表走的是偶数步,所以需要添加计步器,最后判断步数是不是偶数步进行筛选
    答案是: 51167078   (6min26完成)

    8.奇怪的比赛
    某电视台举办了低碳生活大奖赛。题目的计分规则相当奇怪:
    (1)每位选手需要回答10个问题(其编号为1到10),越后面越有难度。答对的,当前分数翻倍;答错了则扣掉与题号相同的分数(选手必须回答问题,不回答按错误处理)。
     (2)每位选手都有一个起步的分数为10分。 某获胜选手最终得分刚好是100分,如果不让你看比赛过程,你能推断出他(她)哪个题目答对了,哪个题目答错了吗?
     (3)如果把答对的记为1,答错的记为0,则10个题目的回答情况可以用仅含有1和0的串来表示。例如:0010110011 就是可能的情况。
     (4) 你的任务是算出所有可能情况。每个答案占一行。

    题目分析:
    1.这里用递归解,每一层变化的数据有:a.题目数 b.分数 c.对错情况   (注意分数减的是下一题:+1)
    2.递归的结点是n==10
         public static void main(String[] args) {
              f(0,10,"");   //从0到10
         }

         public static void f(int num,int fen,String st) {
              if(num==10){      //0执行第1题
                  if(fen==100){
                       System.out.println(st);
                  }
                  return;
              }else{

                  f(num+1, fen*2, st+"1");
                  f(num+1, fen-num-1, st+"0");   //题号和num错开一位,所以应该减去下一题的题号
              }
         }

    题目要点:从第0道题的循环就分数变化,所以第10道题不用分数变化,而是用成数据返回
    答案是:
    1011010000
    0111010000
    0010110011
    要点注意:其实0解决的是第一题,所以减去题号要减去脚标下一位的题号

    9.全排列
    题目n个数字进行排列

    题目分析:
    1.全排列要求的就是把所有可能的情况展现出来
    2.结点:当cur指标指到最后一个n的时候,输出数组所有文字
    3.递归式,for循环往里面填入一个数字,至于数字是什么,通过判断数字有没有出现过,没有的话填入数据,并且将指针移向下一位继续执行。
         if(cur==num){
              for (int i = 0; i < arr.length; i++) {
                  System.out.print(arr[i]);
              }
              System.out.println();
         }else{
              for (int i = 1; i <=num; i++) {
                  arr[cur]=i;
                  boolean flag=false;
                  for (int j = 0; j < cur; j++) {
                       if(arr[j]==i){
                            flag=true;
                       }
                  }
                  if(!flag){
                       isExist[arr[cur]]=true;
                       f(cur+1);
                       isExist[arr[cur]]=false;
                  }
              }
         }
    注意事项:排序的数字由1到当前这个数,而cur指针是从0开始,当它等于这个数的时候其实就是超出的位置,做节点判断即可。
    ... for (int i = 1; i <= A.length; i++) {
            boolean isExist=false;
            for (int j = 0; j < cur; j++) {
                if(A[j]==i){
                    isExist=true;
                }
            }
            if(!isExist){
                A[cur]=i;
                prirnt(n, A, cur+1);
            }
        }...
    注意事项:cur限制查看存在的枚举范围
    这里有两个注意要点:
         a.用普通数组,因为普通数组容易随意替换该位置的数
         b.因为递归的return后继续运行机制,所以判断数字是否重复不能用数组的长度,而是用根据层数变化的cur(和回溯的区别就是,这里将每个数放进去之前进行筛选,其每种情况都需要大量筛选,占内存比较大)
    当输入6个数:结果为
    1 2 3       1 3 2       2 1 3       2 3 1       3 1 2       3 2 1

    10.李白打酒
        话说大诗人李白,一生好饮。幸好他从不开车。
        一天,他提着酒壶,从家里出来,酒壶中有酒2斗。他边走边唱:
        无事街上走,提壶去打酒。
        逢店加一倍,遇花喝一斗。

        这一路上,他一共遇到店5次,遇到花10次,已知最后一次遇到的是花,他正好把酒喝光了。

        请你计算李白遇到店和花的次序,可以把遇店记为a,遇花记为b。则:babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢?请你计算出所有可能方案的个数(包含题目给出的)。

    题目分析:
    1.用递归推出所有情况,进行筛选
    public static void f(int d, int h,int all,int type,int j) {    //type店0花1
         if(all>=15){
              if(d==5&&h==10&&type==1&&j==0){
                  count++;
              }
              return;
         }else{
              f(d+1, h, all+1, 0, j*2);
              f(d, h+1, all+1, 1, j-1);
         }
    }
    为了简化参数,其实可以设定第10个是花,所以限制到第九,剩下如果是1就说明成立。注意传进来的酒是2斗!!!
    public static void dfs(int d, int h,int j) {    //type店0花1
         if(d>5||h>9){return;}
         if(d==5&&h==9){
              if(j==1){
                  count++;
              }
              return;
         }
         dfs(d+1, h, j*2);
         dfs(d, h+1, j-1);
    }



    展开全文
  • 蓝桥杯——递归问题

    2019-03-14 21:38:45
    递归问题 深搜dfs 在有条件的情况下试探各种情况 找出口 递归的终止条件 递归函数参数边界值的界定 汉诺塔问题Hanoi /*思想 1.src上的n-1个盘子移到medium 2.src剩下的一个最大的盘子移到dest 3.medium上的n-...
  • 蓝桥杯-经典的递归问题(一)

    千次阅读 2016-09-02 22:46:51
    珍惜作者劳动成果 转载请注明出处致谢蓝桥杯取球问题 问题描述: 在n个球中, 任意取出m个(不放回), 求有多少种不同的取法. 求解思路: 从题目上看, 这个问题对于递归来说似乎没有突破口, 找不到合适的相似性? 这就要...
  • 试题 算法提高 求最大公约数 资源限制 时间限制:1.0s 内存限制:512.0MB 编写一函数gcd,求两个正整数的最大公约数。 样例输入: 5 15 样例输出: 5 样例输入: 7 2 样例输出: 1 """ ...import ma...
  • 蓝桥杯递归解法)

    2021-04-16 09:32:14
    题目 1004: [递归]母牛的故事 时间限制: 1Sec 内存限制: 128MB 提交: 70090 解决: 21616 题目描述 有一头母牛,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。请编程实现在第n年的...
  • 牌型种数 小明被劫持到X赌城,被迫与其他3人玩牌。 一副扑克牌(去掉大小王牌,共52张),均匀发给4个人,每个人13张。 这时,小明脑子里突然...对于这一来说,我刚开始想的是暴力破解(应该还是挺多同学也是吧)...
  • 文章目录蓝桥杯 快速排序????题目描述分析 蓝桥杯 快速排序???? 题目描述 排序在各种场合经常被用到。 快速排序是十分常用的高效率的算法。 其思想是:先选一个“标尺”, 用它把整个队列过一遍筛子, 以保证:其...
  • 蓝桥杯练习——递归

    2021-02-23 19:30:22
    蓝桥杯练习——递归(1) 循环与递归 循环与递归有一定的相似性,这是将循环改为递归的关键,就是发现逻辑的相似性 递归最重要的一点,就是找到递归的出口,及返回的条件 构造相似性 有时候相似性并不会太明显,需要去...
  • 可以使用暴力破解判断所有组合,然而比赛时需要节省时间,所以使用递归(本参考蓝桥学苑2016届B组试题,个人检查无误,本地运行有误)。 算法展示 #include using namespace std; int a[10000],N,i,ans = 0; void...
  • 试题 算法提高 递归输出                              &...
  • 趣味算式 蓝桥杯 110 递归

    千次阅读 2014-03-11 19:22:07
    匪警请拨110,即使手机欠费也可拨通!  为了保障社会秩序,保护人民群众生命财产安全,警察叔叔需要与罪犯斗智斗勇,因而需要经常性地进行体力训练和智力训练!  某批警察叔叔正在进行智力训练: ...
  • 递归算法在程序中不断反复调用自身的方法调用方式。此处的重点是调用自身递归满足两个条件1.有反复执行的过程(调用自身)2.有跳出反复执行过程的条件(递归出口)递归算法在软件竞赛中,考察的非常多我的qq:...
  • 蓝桥杯递归问题

    2019-04-05 09:16:33
    2,找到递归公式或者**等价转换** 都是父问题转化为求解子问题 二:找变化的量 变化的量要作为参数 三:找到出口 根据参数变化的趋势,对边界进行控制,适时终止递归 斐波那契数列问题 等价于两...
  • 试题 历届试题 斐波那契 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述  斐波那契数列大家都非常熟悉。它的定义是: f(x) = 1 … (x=1,2)  f(x) = f(x-1) + f(x-2) … (x>2) 对于给定的整数 n 和 m,我们...
  • 写一个递归程序,输入一个整数,按从高位到低位的顺序输出其所有数字,每两个数字中间用空格格开。例如,输入整数12345,输出1 2 3 4 5。请进一步思考如何修改程序,才能输出数字取反后的整数,即在上例中输出整数...
  • 试题 算法训练 递归输出数字 ...注意这里的进一步思考仅供个人练习,不要提交到作业程序中,即最后的结果不要输出54321,否则自动判程序会出错 输入格式  输入一个整数n(1<=n<=100000) 输
  •  输出一个与样例类似的n行的数字三角形,同一行每两个数之间用一个空格隔开即可(图中只是为防止面格式化而用’_'代替空格) 样例输入 4 样例输出 ___1 __2_3 _4_5_6 7_8_9_10 数据规模和约定  n<=20 非递归...
  • 蓝桥杯(一):递归

    2021-10-01 14:25:13
    递归:自己调用自己 2^15 = 32768 2^16 = 65536 字典序:从小到大枚举,能放就放 92. 递归实现指数型枚举 思路一:状态压缩写法 #include <iostream> #include <cstring> #include <algorithm> ...
  • java 蓝桥杯 递归 阶乘

    2021-05-12 21:58:55
    1,试着用递归的思想来做这道 代码演示 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner
  • 很简单,跟着设要求的思路走,如果k=0或者n,返回1,否则递归下去,当然,如果没有设的描述,这道的思路就没有那么清晰了。 代码如下: #include<bits/stdc++.h> using namespace std; int ...
  • } } 分析: 递归函数参数的含义 参数变化的方向 public class 字母组串 { // a个A,b个B,c个C 字母,能组成多少个不同的长度为n的串。 static int f(int a, int b, int c, int n) { if (a || b || c ) ...
  • if(wait==0) //递归出口 全部车入栈完毕,为一种方案 return 1; else if(check==0)//没有车可以出了 只能入 return(push(wait-1,1)); else{ //可进可出 //System.out.println(wait+" "+check); ...
  • 一个串的子串是指该串的一个连续的局部。如果不要求连续,则可称为它的子序列。 比如对串: "abcdefg" 而言,"ab","abd","bdef" 等都是它的子序列。 ...特别地,一个串本身,以及空串也是它的子序列。...
  • 蓝桥杯 | 递归 2/24

    2021-02-24 14:27:39
    时间:2021/2/24 测试练习 递归实现组合型枚举(AcWing) 视频学习 蓝桥杯训练营(C++) 1

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,178
精华内容 2,071
关键字:

蓝桥杯递归题

友情链接: ClearText.rar