蓝桥杯算法特训第四课【数学知识的运用】源代码

【内容简介】
本文章内容为【2018蓝桥杯大赛算法特训(软件)系列课程】第四课【数学知识的运用】中涉及到的课上例题的代码实现,加入赛前算法特训获取全部课程内容请联系【小蓝】。


【课程中涉及的源代码】
1. 奇怪的捐赠
地产大亨Q先生临终的遗愿是:拿出100万元给X社区的居民抽奖,以稍慰藉心中愧疚。
麻烦的是,他有个很奇怪的要求:

  1. 100万元必须被正好分成若干份(不能剩余)。每份必须是7的若干次方元。比如:1元, 7元,49元,343元,…
  2. 相同金额的份数不能超过5份。
  3. 在满足上述要求的情况下,分成的份数越多越好!

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class A
{
    public static void main(String[] args){
        // 直接求一个数字的7进制表示
        // 如果没有函数,可以自己用长除法取余数的方式
        String s = Integer.toString(1000*1000,7);
        int sum=0;
        for(int i=0; i<s.length(); i++){
            sum += s.charAt(i)-'0';
        }
        System.out.println(s);
        System.out.println("result=" + sum);
    }
}

【C:志愿者】


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

void main1()
{
    // 直接求一个数字的7进制表示
    // 如果没有函数,可以自己用长除法取余数的方式
    char arr[1024] = { 0 };
    _itoa(1000 * 1000, arr, 7);
    int sum = 0;

    for (int i = 0; i < strlen(arr); i++)
    {
        sum += arr[i] - '0';
    }
    printf("%s\n", arr);
    printf("result=%d", sum);
}


2. 天平称重
【问题描述】
用天平称重时,我们希望用尽可能少的砝码组合称出尽可能多的重量。
如果只有5个砝码,重量分别是1,3,9,27,81
则它们可以组合称出1到121之间任意整数重量(砝码允许放在左右两个盘中)。

本题目要求编程实现:对用户给定的重量,给出砝码组合方案。
例如:
用户输入:
5
程序输出:
9-3-1
用户输入:
19
程序输出:
27-9+1

要求程序输出的组合总是大数在前小数在后。
可以假设用户的输入的数字符合范围1~121。

【源代码】
【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
38
39
40
41
42
43
44
// 天平称重,递归解法
public class A
{
    // 把s中的符号取反(+变-,-变+)
    static String reve(String s){
        s = s.replace('-','#');
        s = s.replace('+','-');
        s = s.replace('#','+');
        return "-" + s;
    }
   
    static String f(int x){
        int a = 1;
        while(a<x) a *= 3;
       
        if(a==x) return "" + a;
       
        if(x<=a/2) return a/3 + "+" + f(x-a/3);
       
        return a + reve(f(a-x));
    }
   
    public static void main(String[] args){
        for(int i=1; i<100; i++){ System.out.println(i + ": " + f(i)); } } } // 天平称重,进制解法 public class B { static String f(int n){ String s = ""; int q = 1; //位权重 while(n>0){
            int sh = n/3; //商
            if(n%3 == 1) s = "+" + q + s;
            if(n%3 == 2){
                sh++;
                s = "-" + q + s;
            }
           
            n = sh;
            q *= 3;
        }  
       
        return s.substring(1);
    }
       
    public static void main(String[] args){
        for(int i=1; i<100; 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include <string.h>

// 天平称重,递归解法

// 把s中的符号取反(+变-,-变+)
    char* reve(char *s)
    {
        int n = strlen(s);
        for (int i = 0; i < n;i++)
        {
            if (s[i]=='-')
            {
                s[i] = '+';
            }
            else if (s[i]=='+')
            {
                s[i] = '-';
            }
        }

        char *p = (char *)malloc(n + 2);
        memset(p, 0, n + 2);
        p[0] = '-';
        strcat(p, s);

        return p;
    }

    char* f(int x)
    {
        char *p = (char *)malloc(1024);
        memset(p, 0, 1024);

        int a = 1;
        while (a < x)
            a *= 3;

        if (a == x)
        {
            _itoa(a, p, 10);
            return p;
        }
           
        if (x <= a / 2)
        {
            int m = x - a / 3;
            char *p1 = f(m);
            _itoa(a/3, p, 10);
            strcat(p, "+");
            return strcat(p, p1);
        }
        char *h = reve(f(a - x));
        _itoa(a, p, 10);
        strcat(p, h);
        return p;
    }

    void main21(){
        for (int i = 1; i < 100; i++)
        {
            char*p=f(i);
            printf("%d : %s\n", i, p);
        }
    }

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
51
52
53
54
55
56
57
58
59
60
61
#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
// 天平称重,进制解法
   
char * f2(int n){
    char*p = (char*)malloc(1024);
    memset(p, 0, 1024);


    int q = 1; //位权重
    while (n > 0){
        int sh = n / 3; //商
        if (n % 3 == 1)
        {

            char arr[1024] = { 0 };
            strcpy(arr, p);
            memset(p, 0, 1024);

            strcat(p, "+");

            char arr1[1024] = { 0 };
            _itoa(q, arr1, 10);
            strcat(p, arr1);

            strcat(p, arr);
        }

        if (n % 3 == 2)
        {
            sh++;

            char arr[1024] = { 0 };
            strcpy(arr, p);
            memset(p, 0, 1024);

            strcat(p, "-");

            char arr1[1024] = { 0 };
            _itoa(q, arr1, 10);
            strcat(p, arr1);

            strcat(p, arr);
        }

        n = sh;
        q *= 3;
    }

    return p+1;
}

void main22(){
    for (int i = 1; i < 100; i++)
    {
        char*p = f2(i);
        printf("%d : %s\n", i, p);
    }
}


3. 尼姆堆
【问题描述】
有3堆硬币,分别是3,4,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
29
30
31
32
// 尼姆堆的模2加(异或)解法
/*
    10
   101
  1100
  1110
--------
  0101  
*/

public class A
{
    static void f(int[] a){
        int sum = 0;
        for(int i=0; i<a.length; i++){
            sum ^= a[i];
        }
        if(sum==0){
            System.out.println("输了");
            return;
        }
       
        for(int i=0; i<a.length; i++){
            int x = sum ^ a[i];
            if(x<a[i]) System.out.println(a[i] + " --> " + x);
        }
    }
   
    public static void main(String[] args){
        int[] a = {2,5,12,14};
        f(a);
    }
}

【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
#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include <string.h>

// 尼姆堆的模2加(异或)解法
/*
10
101
1100
1110
--------
0101
*/


    void f3(int* a,int len)
    {
        int sum = 0;
        for (int i = 0; i<len; i++)
        {
            sum ^= a[i];
        }
        if (sum == 0)
        {
            printf("输了\n");
            return;
        }

        for (int i = 0; i<len; i++)
        {
            int x = sum ^ a[i];
            if (x < a[i]) printf("%d --> %d\n", a[i], x);
        }
    }

    void main3()
    {
        int a[] = { 2, 5, 12, 14 };
        f3(a,4);
    }


4. 公约公倍
【问题描述】
如果两个数很大,怎样求最大公约数,最小公倍数?
如果是n个数呢?比如1000个数的最小公倍数

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
   辗转相除法
   欧几里得定理 gcd(A,B) = gcd(B,A%B)
   算数基本定理:质因数分解的唯一性
     n = p1^n1 * p2^n2 * ...
*/


public class A
{
    static int gcd(int a, int b){
        if(b==0) return a;
        return gcd(b, a%b);
    }
   
    static int lcm(int a, int b){
        return a * b / gcd(a,b);
    }
   
    public static void main(String[] args){
        System.out.println(gcd(42,60));
        System.out.println(lcm(42,60));
    }
}

【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
#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
/*
辗转相除法
欧几里得定理 gcd(A,B) = gcd(B,A%B)
算数基本定理:质因数分解的唯一性
n = p1^n1 * p2^n2 * ...
*/

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a%b);
}

int lcm(int a, int b)
{
    return a * b / gcd(a, b);
}

void main4()
{
    printf("%d\n", gcd(42, 60));
    printf("%d\n", lcm(42, 60));

}


5. 一步之遥
【问题描述】
从昏迷中醒来,小明发现自己被关在X星球的废矿车里。
矿车停在平直的废弃的轨道上。
他的面前是两个按钮,分别写着“F”和“B”。

小明突然记起来,这两个按钮可以控制矿车在轨道上前进和后退。
按F,会前进97米。按B会后退127米。
透过昏暗的灯光,小明看到自己前方1米远正好有个监控探头。
他必须设法使得矿车正好停在摄像头的下方,才有机会争取同伴的援助。
或许,通过多次操作F和B可以办到。

矿车上的动力已经不太足,黄色的警示灯在默默闪烁…
每次进行 F 或 B 操作都会消耗一定的能量。
小明飞快地计算,至少要多少次操作,才能把矿车准确地停在前方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
38
39
40
41
42
43
44
45
46
47
/*
  解不定方程
  97x + 127y = 1
 
  欧几里得定理 ---- 辗转相除法  gcd
  扩展欧几里得定理
  Ax + By = gcd(A,B)
  理论基础: gcd(A,B) == gcd(B,A%B)
 
  求出特解后,通解很好表示
 
  Ax + By = gcd(A,B)
  Ax + By = gcd(B,A%B)
  B(A/B x + y) + (A%B)x = gcd(B,A%B)
  对比:
  A/B x + y = 新x
  x = 新y
*/


public class A
{
    // 返回最大公约数
    // xy: 顺便解出的xy
    static int e_gcd(int A, int B, int[] xy)
    {
        if(B==0){
            xy[0] = 1;
            xy[1] = 0;
            return A;
        }
       
        int ans = e_gcd(B, A%B, xy);
        int t = xy[0];
        xy[0] = xy[1];
        xy[1] = t - A/B * xy[0];
        return ans;
    }
   
    public static void main(String[] args)
    {
        int[] xy = new int[2];
        int a = e_gcd(97,127,xy);
       
        System.out.println(a);
        System.out.println(xy[0] + " " + xy[1]);   
    }
}

【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
#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
/*
解不定方程
97x + 127y = 1

欧几里得定理 ---- 辗转相除法  gcd
扩展欧几里得定理
Ax + By = gcd(A,B)
理论基础: gcd(A,B) == gcd(B,A%B)

求出特解后,通解很好表示

Ax + By = gcd(A,B)
Ax + By = gcd(B,A%B)
B(A/B x + y) + (A%B)x = gcd(B,A%B)
对比:
A/B x + y = 新x
x = 新y
*/


// 返回最大公约数
// xy: 顺便解出的xy
int e_gcd(int A, int B, int* xy,int len)
{
    if (B == 0)
    {
        xy[0] = 1;
        xy[1] = 0;
        return A;
    }

    int ans = e_gcd(B, A%B, xy,len);
    int t = xy[0];
    xy[0] = xy[1];
    xy[1] = t - A / B * xy[0];
    return ans;
}

void main5()
{
    int* xy =(int *) malloc(sizeof(int)*2);
    int a = e_gcd(97, 127, xy,2);
    printf("%d \n", a);
    printf("%d " " %d \n", xy[0], xy[1]);
}


6. 有理数
【问题描述】
如果求 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + …. + 1/100 = ?
要求绝对精确,不能有误差。

【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
public class A
{
    public static void main(String[] args){
        Rati x = new Rati(1,3).add(new Rati(1,6));
        System.out.println(x);
    }
}

【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
51
52
53
54
55
56
57
58
59
#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Rati
{
    long zi;
    long mu;
}Rati;

long gcd1(long a, long b)
{
    if (b==0)
        return a;
    return gcd1(b, a%b);
}

Rati* add(Rati it1, Rati it2)
{
    Rati*p = (Rati*)malloc(sizeof(Rati));
    p->zi = it1.zi*it2.mu + it2.zi*it1.mu;
    p->mu = it1.mu*it2.mu;
    return p;

}

Rati* mul(Rati it1, Rati it2)
{
    Rati*p = (Rati*)malloc(sizeof(Rati));
    p->zi  = it1.zi*it2.zi;
    p->mu = it1.mu*it2.mu;
    return p;
}

//最大公约数
long gcd2(long a, long b)
{
    if (b == 0)
        return a;
    return gcd2(b, a%b);
}

void main()
{
    Rati*sum=(Rati*)malloc(sizeof(Rati));
    sum->zi = 0;
    sum->mu = 1;

    for (int i = 1; i <= 10; i++) { Rati*p = (Rati*)malloc(sizeof(Rati)); p->zi = 1;
        p->mu = i;
        sum = add(*sum,*p);
        long x = gcd2(sum->zi, sum->mu);
        sum->zi = sum->zi / x;
        sum->mu = sum->mu / x;
    }
    printf("1/2 + 1/3 + 1/4 + 1/5 + 1/6 +1/7 + 1/8 + 1/9 + 1/10 = ");
    printf("%d / %d ",sum->zi,sum->mu);
}


7. 素数
【问题描述】
第1个素数是2,第2个素数是3,…
求第100002(十万零二)个素数

【源代码】
【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
38
39
40
41
42
/*
筛到第x个素数,需要数组准备多大?
素数分布定理:不大于n的素数的个数为:n / ln(n)
    double t = 100;
    while(t / Math.log(t) < x) t *= 1.1;
    System.out.println(t);
   
   
*/


public class SuShu
{
    public static void main(String[] args)
    {
        int N = 1500 * 1000;
        int x = 100002;
       
        byte[] a = new byte[N];
       
        for(int i=2; i<N/2; i++)
        {
            if(a[i]==1) continue; //越过已经找到的合数
            for(int k=2; k<=N/i; k++)
            {
                if(i*k<N) a[i*k] = 1;
            }
        }
       
       
        int m = 0;
        for(int i=2; i<N; i++)
        {
            if(a[i]==0)
            {
                m++;
                if(m==x) System.out.print(i + " ");
            }
        }
       
        System.out.println("m=" + m);
    }
}

【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
#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include <string.h>

/*
筛到第x个素数,需要数组准备多大?
素数分布定理:不大于n的素数的个数为:n / ln(n)
double t = 100;
while(t / Math.log(t) < x) t *= 1.1;
System.out.println(t);
*/


void main()
{
    int N = 1500 * 1000;
    int x = 100002;

    int* a = (int *)malloc(N*sizeof(int)); 
    memset(a, 0, N*sizeof(int));
    for (int i = 2; i<N / 2; i++)
    {
        if (a[i] == 1)
            continue; //越过已经找到的合数
        for (int k = 2; k <= N / i; k++)
        {
            if (i*k<N)
                a[i*k] = 1;
        }
    }

    int m = 0;
    for (int i = 2; i<N; i++)
    {
        if (a[i] == 0)
        {
            m++;
            if (m == x)
                printf("%d \n",i);
        }
    }


    printf("m= %d" , m);
}


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

Spread the word. Share this post!

Leave Comment

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