蓝桥杯算法特训第二课【递归原理与构造技巧】源代码

【内容简介】
本文章内容为【2018蓝桥杯大赛算法特训(软件)系列课程】第二课【递归原理与构造技巧】中涉及到的课上例题的代码实现,加入赛前算法特训获取全部课程内容请联系【小蓝】。


【课程中涉及的源代码】
1. 串的翻转
【问题描述】
【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
public class A
{
    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("abcde"));
    }
}

【C:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char * f(char * s, int num)
{
    if (num <= 1)
    {
        return s;
    }
    else
    {
        char *p = (char *)malloc(num+1);
        memset(p, 0, num+1);
        strcpy(p, s+1);
        char *pp = f(p, num-1);        
        strcpy(p, pp);
        if (p!=pp)
            free(pp);
        strncpy(p+num-1,s,1);      
        return p;
    }
}

void main()
{
    char arr[100] = "abcde";
    printf("%s", f(arr, 5));

}


2. 循环改递归
【问题描述】
【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class A
{
    static void f(int a, int b){
        for(int i=a; i<=b; i++){
            System.out.println(i);
        }
    }
   
    static void g(int a, int b){
        if(a<b) g(a,b-1);
        System.out.println(b);
    }
   
    public static void main(String[] args){
        //f(1,10); 
        g(1,10);
    }
}

【C语言:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void f2(int a, int b)
{
    for (int i = a; i <= b; i++){
        printf("%d ",i);
    }
}

void g2(int a, int b)
{
    if (a < b)
        g2(a, b - 1);
    printf("%d   ",b);
}

void main()
{
    //f2(1,10);
    g2(1, 10);
}


3. 出栈次序
【问题描述】
X星球特别讲究秩序,所有道路都是单行线。
一个甲壳虫车队,共16辆车,按照编号先后发车,夹在其它车流中,缓缓前行。
路边有个死胡同,只能容一辆车通过,是临时的检查站,如图所示。
出栈次序.jpg
X星球太死板,要求每辆路过的车必须进入检查站,也可能不检查就放行,也可能仔细检查。
如果车辆进入检查站和离开的次序可以任意交错。那么,该车队再次上路后,可能的次序有多少种?
为了方便起见,假设检查站可容纳任意数量的汽车。
显然,如果车队只有1辆车,可能次序1种;2辆车可能次序2种;3辆车可能次序5种。
【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
  如果进栈次序为:1 2 3 4 5 。。。
  出栈次序有多少种情况?
 
*/


public class A
{
    // n 个等着进栈,栈中有m个
    static int f(int n, int m)
    {
        if(n==0) return 1;
        if(m==0) return f(n-1,1);
        return f(n,m-1) + f(n-1, m+1);
    }
   
    static int f(int n)
    {
        return f(n, 0);
    }
   
    public static void main(String[] args)
    {
        for(int i=1; i<17; i++){
            System.out.println(i + ": " + f(i));
        }
    }
}

【C语言:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
如果进栈次序为:1 2 3 4 5 。。。
出栈次序有多少种情况?

*/


    // n 个等着进栈,栈中有m个
    int f3(int n, int m)
    {
        if (n == 0)
            return 1;
        if (m == 0)
            return f3(n - 1, 1);
        return
            f3(n, m - 1) + f3(n - 1, m + 1);
    }

    int f5(int n)
    {
        return f3(n, 0);
    }

    void main()
    {
        for (int i = 1; i<17; i++)
        {
            printf("%d : %d \n", i, f5(i));
        }
    }


4. 第39级台阶
【问题描述】

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

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class A
{
    // 奇数步
    static long g(int n)
    {
        if(n==0) return 0;
        if(n==1) return 1;
        //if(n==2) return 1;
       
        return f(n-1) + f(n-2);
    }
   
    // 偶数步
    static long f(int n)
    {
        if(n==0) return 1;
        if(n==1) return 0;
        //if(n==2) return 1;
       
        return g(n-1) + g(n-2);
    }
   
    public static void main(String[] args)
    {
        System.out.println(f(5));
        System.out.println(f(39));
    }
}

【C语言:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long ff(int n);
    // 奇数步
long gg(int n)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    /*if(n==2)
        return 1;*/

    return ff(n - 1) + ff(n - 2);
}

    // 偶数步
long ff(int n)
{
    if (n == 0)
        return 1;
    if (n == 1)
        return 0;
    /*if(n==2)
        return 1;*/

    return gg(n - 1) + gg(n - 2);
}

void main()
{
        printf("%d \n",ff(5));
        printf("%d ", ff(39));
}

5. 算式填符号
【问题描述】

匪警请拨110,即使手机欠费也可拨通!
为了保障社会秩序,保护人民群众生命财产安全,警察叔叔需要与罪犯斗智斗勇,因而需要经常性地进行体力训练和智力训练!

某批警察叔叔正在进行智力训练:
1 2 3 4 5 6 7 8 9 = 110

请看上边的算式,为了使等式成立,需要在数字间填入加号或者减号(可以不填,但不能填入其它符号)。之间没有填入符号的数字组合成一个数,例如:12+34+56+7-8+9 就是一种合格的填法;123+4+5+67-89 是另一个可能的答案。

请你利用计算机的优势,帮助警察叔叔快速找到所有答案。
每个答案占一行。形如:
12+34+56+7-8+9
123+4+5+67-89
……

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class SuanShi
{
    //a: 参加计算的元素
    //k: 目前考虑的元素下标
    //so: 合成好的结果串
    //goal: 计算目标
    static void f(int[] a, int k, String so, int goal){
        if(k==0){
            if(a[0] == goal){
                System.out.println(a[0]+so);
            }
            return;
        }
       
        f(a,k-1,"+"+a[k]+so, goal-a[k]);
        f(a,k-1,"-"+a[k]+so, goal+a[k]);
        int old = a[k-1];
        a[k-1] = Integer.parseInt("" + a[k-1] + a[k]);
        f(a,k-1,so,goal);
        a[k-1] = old;
    }
   
    public static void main(String[] args){
        int[] a = {1,2,3,4,5,6,7,8,9};     
        f(a,8,"",110);
    }
}

【C语言:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

    //a: 参加计算的元素
    //k: 目前考虑的元素下标
    //so: 合成好的结果串
    //goal: char
    void fk(int *a, int k, char *s, int goal){
        if (k == 0){
            if (a[0] == goal){
                printf("%d%s\n",a[0],s);
            }
            return;
        }

        char * p = malloc(k * 2 + 1);
        memset(p, 0, k * 2 + 1);

        p[0] = '+';
        _itoa(a[k], p+1, 10);
        int x = strlen(p);
        strcat(p+x, s);    
        fk(a, k - 1, p, goal - a[k]);

        p[0] = '-';
        fk(a, k - 1, p, goal + a[k]);


        int old = a[k - 1];
        char ak[1024] = { 0 };
        char ak2[1024] = { 0 };
        _itoa(a[k - 1], ak, 10);
        _itoa(a[k], ak2, 10);
        strcat(ak, ak2);
        a[k - 1] = atoi(ak);
        memset(p, 0, k * 2 + 1);
        strcat(p, s);
        fk(a, k - 1, p, goal);
        a[k - 1] = old;
    }


   
    void main()
    {
        int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        fk(a, 8, "", 110);
    }


6. 找钱问题
【问题描述】

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

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//考虑最后一个人
public class ZhaoQian1
{
    //m: 持有5角的
    //n: 持有1元的
    static int f(int m, int n){
        if(m<n) return 0;
        if(m==1) return 1;
        if(n==0) return 1;
           
        return f(m-1,n) + f(m,n-1);
    }
   
    public static void main(String[] args){
        System.out.println(f(2,2));
        System.out.println(f(3,2));
        System.out.println(f(5,3));
    }
}

//考虑第一个人
public class ZhaoQian2
{
    //m: 持有5角的
    //n: 持有1元的
    //t: 售票员手里有多少个5角的
    static int f(int m, int n, int t){
        if(m+t<n) return 0; if(m==0) return 1; if(n==0) return 1; int r = f(m-1,n,t+1); if(t>0) r += f(m,n-1,t-1);
        return r;
    }
   
    public static void main(String[] args){
        System.out.println(f(2,2,0));
        System.out.println(f(3,2,0));
        System.out.println(f(5,3,0));
    }
}

【C语言:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//考虑最后一个人
//m: 持有5角的
//n: 持有1元的
int f6(int m, int n)
{
    if (m < n)
        return 0;
    if (m == 1)
        return 1;
    if (n == 0)
        return 1;

    return f6(m - 1, n) + f6(m, n - 1);
}

void main(){
    printf("%d \n",f6(2, 2));
    printf("%d \n",f6(3, 2));
    printf("%d \n",f6(5, 3));

}

//==========================================

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//考虑第一个人
//m: 持有5角的
//n: 持有1元的
//t: 售票员手里有多少个5角的
int fn(int m, int n, int t)
{
    if (m + t<n) return 0; if (m == 0) return 1; if (n == 0) return 1; int r = fn(m - 1, n, t + 1); if (t>0)
        r += fn(m, n - 1, t - 1);
    return r;
}

void main()
{
    printf("%d \n", fn(2, 2, 0));
    printf("%d \n", fn(3, 2, 0));
    printf("%d \n", fn(5, 3, 0));

}

7. 振兴中华
【问题描述】
小明参加了学校的趣味运动会,其中的一个项目是:跳格子。
地上画着一些格子,每个格子里写一个字,如下所示:(也可参见下图)

从我做起振
我做起振兴
做起振兴中
起振兴中华
振兴中华.jpg
比赛时,先站在左上角的写着“从”字的格子里,可以横向或纵向跳到相邻的格子里,但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。

要求跳过的路线刚好构成“从我做起振兴中华”这句话。
请你帮助小明算一算他一共有多少种可能的跳跃路线呢?

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class A
{
    static int f(int m, int n)
    {
        if(m==1 || n==1) return 1;
       
        return f(m-1,n) + f(m,n-1);
    }
   
    public static void main(String[] args)
    {
        System.out.println(f(5,4));
        //System.out.println(f(3,2));
    }

}

【C语言:志愿者】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int f7(int m, int n)
{
    if (m == 1 || n == 1)
        return 1;
    return f7(m - 1, n) + f7(m, n - 1);
}

void main7()
{
    printf("%d \n", f7(5, 4));
    //printf("%d \n", f7(3, 2));
}


如果您需要更多课程内容和讲解视频,请联系小蓝

Spread the word. Share this post!

Leave Comment

电子邮件地址不会被公开。 必填项已用*标注