蓝桥杯算法特训第五课【博弈问题的思路】源代码

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


【课程中涉及的源代码】
1. 日期与星期
大数学家高斯有个好习惯:无论如何都要记日记。
他的日记有个与众不同的地方,他从不注明年月日,而是用一个整数代替,比如:4210

后来人们知道,那个整数就是日期,它表示那一天是高斯出生后的第几天。这或许也是个好习惯,它时时刻刻提醒着主人:日子又过去一天,还有多少时光可以用于浪费呢?

高斯出生于:1777年4月30日。
在高斯发现的一个重要定理的日记上标注着:5343,因此可算出那天是:1791年12月15日。

高斯获得博士学位的那天日记上标着:8113
请你算出高斯获得博士学位的年月日。

1949年的国庆节(10月1日)是星期六。
今年(2012)的国庆节是星期一。
那么,从建国到现在,有几次国庆节正好是星期日呢?

只要答案,不限手段!
可以用windows日历,windows计算器,Excel公式,。。。。。
当然,也可以编程!

【源代码】
【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
// 日期差问题
// 2015-3-2 距离 1979-12-15 多少天?
// 日期表示法?? 距离基点的天数

public class A
{
   
    static int day_dif(int year1,int month1,int day1,
                       int year2,int month2,int day2){
        return get_days(year2,month2,day2)
             - get_days(year1,month1,day1);
   
    }
   
    static boolean is_leap_year(int year){
        boolean tag = false;
        if(year%4==0) tag = true;
        if(year%100==0) tag = false;
        if(year%400==0) tag = true;
        return tag;
    }
   
    static int get_days(int year, int month, int day){
        int[] M = {0,31,28,31,30,31,30,31,31,30,31,30,31};
        if(is_leap_year(year)) M[2]++;
       
        int sum = 0;
        for(int i=1; i<year; i++){
            sum += 365;
            if(is_leap_year(i)) sum++;
        }
       
        for(int i=1; i<month; i++){
            sum += M[i];
        }
       
        sum += day;
        return sum;
    }
   
    public static void main(String[] args){
        System.out.println(day_dif(1979,12,15,2015,3,2));
    }
}

【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
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
// 日期差问题
// 2015-3-2 距离 1979-12-15 多少天?
// 日期表示法?? 距离基点的天数


int day_dif(int year1, int month1, int day1,int year2, int month2, int day2)
{
    return get_days(year2, month2, day2)- get_days(year1, month1, day1);

}

int is_leap_year(int year)
{
    int tag = 0;
    if (year % 4 == 0)
        tag = 1;
    if (year % 100 == 0)
        tag = 1;
    if (year % 400 == 0)
        tag = 1;
    return tag;
}

int get_days(int year, int month, int day)
{
    int M[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
    if (is_leap_year(year))
        M[2]++;

    int sum = 0;
    for (int i = 1; i < year; i++)
    {
        sum += 365;
        if (is_leap_year(i))
            sum++;
    }

    for (int i = 1; i < month; i++)
    {
        sum += M[i];
    }

    sum += day;
    return sum;
}
void main7()
{
    printf("%d\n", day_dif(1979, 12, 15, 2015, 3, 2));
}


2. excel地址
Excel单元格的地址表示很有趣,它使用字母来表示列号,比如:
A表示第1列,
B表示第2列,
Z表示第26列,
AA表示第27列,
AB表示第28列,
BA表示第53列,
….
当然Excel的最大列号是有限度的,所以转换起来不难。
如果我们想把这种表示法一般化,可以把很大的数字转换为很长的字母序列呢?

本题目既是要求对输入的数字, 输出其对应的Excel地址表示方式。

例如,
输入:
26
则程序应该输出:
Z

再例如,
输入:
2054
则程序应该输出:
BZZ

我们约定,输入的整数范围[1,2147483647]

【源代码】
【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
public class A
{
    // n 转换为excel列地址
    static String f(int n){
        for(int i=0; i<=26; i++)
        for(int j=(i==0)?0:1; j<=26; j++)
        for(int k=(j==0)?0:1; k<=26; k++){ int x = i*26*26 + j*26 + k; if(x==n){ String s =""; if(i>0) s += (char)(i-1+'A');
                if(j>0) s += (char)(j-1+'A');
                if(k>0) s += (char)(k-1+'A');              
                return s;
            }
        }
        return "";
    }
   
    public static void main(String[] args){
        for(int i=700; i<750; i++){
            System.out.println(i + ": " + f(i));
        }
    }
}

public class B
{
    // excel列地址转换为n
    static int f(String s){
        int n = 0;
        for(int i=0; i<s.length(); i++){
            n = n * 26 + (s.charAt(i)-'A' + 1);
        }
        return n;
    }
   
    public static void main(String[] args){
        System.out.println(f("AA"));
        System.out.println(f("BA"));
        System.out.println(f("ZZ"));
        System.out.println(f("AAA"));
    }
}

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

// n 转换为excel列地址
char * f(int n)
{
    for (int i = 0; i <= 26; i++)
        for (int j = (i == 0) ? 0 : 1; j <= 26; j++)
            for (int k = (j == 0) ? 0 : 1; k <= 26; k++)
            {
                int x = i * 26 * 26 + j * 26 + k;
                if (x == n)
                {


                    char *p = (char*)malloc(4);
                    memset(p, 0, 4);
                    int len = 0;
                    if (i)
                    {
                        p[len] = (char)(i + 'A' - 1);
                        len++;
                    }
                    if(j)
                    {
                        p[len] = (char)(j + 'A' - 1);
                        len++;
                    }
                    if (k)
                    {
                        p[len] = (char)(k + 'A' - 1);
                        len++;
                    }
                    return p;
                }
            }  

}

void main1()
{
    for (int i = 700; i < 750; i++){
        printf("%d :%s\n",i,f(i));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
   
// excel列地址转换为n
int ff(char *s,int len)
{
    int n = 0;
    for (int i = 0; i < len; i++)
    {
        n = n * 26 + (s[i] - 'A' + 1);
    }
    return n;
}

void main13()
{
    printf("%d\n", ff("AA", 2));
    printf("%d\n", ff("BA", 2));
    printf("%d\n", ff("ZZ", 2));
    printf("%d\n", ff("AAA", 3));
}

3. 取球博弈
今盒里有n个小球,A、B两人轮流从盒中取球。
每个人都可以看到另一个人取了多少个,也可以看到盒中还剩下多少个。
两人都很聪明,不会做出错误的判断。

每个人从盒子中取出的球的数目必须是:1,3,7或者8个。
轮到某一方取球时不能弃权!
A先取球,然后双方交替取球,直到取完。

被迫拿到最后一个球的一方为负方(输方)

编程确定出在双方都不判断失误的情况下,对于特定的初始球数,A是否能赢?
【源代码】
【JAVA:于航】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class A
{
    static boolean f(int n){
        if(n==0) return true;
       
        if(n>=1 && f(n-1)==false) return true;
        if(n>=3 && f(n-3)==false) return true;
        if(n>=7 && f(n-7)==false) return true;
        if(n>=8 && f(n-8)==false) return true;
       
        return false;
    }
   
    public static void main(String[] args){
        for(int i=1; i<=50; 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
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include<string.h>

int fff(int n)
{
    if (n == 0)
        return 1;

    if (n >= 1 && fff(n - 1) == 0)
        return 1;
    if (n >= 3 && fff(n - 3) == 0)
        return 1;
    if (n >= 7 && fff(n - 7) == 0)
        return 1;
    if (n >= 8 && fff(n - 8) == 0)
        return 1;

    return 0;
}

void main2()
{
    for (int i = 1; i <= 50; i++){
        printf("%d : %s\n", i, fff(i)?"true": "false");
    }
}


4. 填字母游戏
K大师在纸上画了一行n个格子,要小明和他交替往其中填入字母。
1. 轮到某人填的时候,只能在某个空格中填入L或O
2. 谁先让字母组成了“LOL”的字样,谁获胜。
3. 如果所有格子都填满了,仍无法组成LOL,则平局。

小明试验了几次都输了,他很惭愧,希望你能用计算机帮他解开这个谜。

本题的输入格式为:
第一行,数字n(n<10),表示下面有n个初始局面。
接下来,n行,每行一个串,表示开始的局面。
比如:“******”, 表示有6个空格。“L****”, 表示左边是一个字母L,它的右边是4个空格。

要求输出n个数字,表示对每个局面,如果小明先填,当K大师总是用最强着法的时候,小明的最好结果。
1 表示能赢
-1 表示必输
0 表示可以逼平

例如,
输入:
4
***
L**L
L**L***L
L*****L

则程序应该输出:
0
-1
1
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
import java.util.*;

public class A
{
    // -1: 必输,0: 平局, 1: 必赢
    static int f(char[] x)
    {
        String s = new String(x);      
        if(s.contains("LOL")) return -1;
        if(s.contains("*")==false) return 0;
       
        boolean ping = false;  // 假设无法平局
       
        for(int i=0; i<x.length; i++){
            if(x[i]=='*'){
                try{
                    x[i]='L';  //试着填L
                    switch(f(x)){
                        case -1: return 1;
                        case 0: ping = true;
                    }
                    x[i]='O';  //试着填O
                    switch(f(x)){
                        case -1: return 1;
                        case 0: ping = true;
                    }
                }
                finally{           
                    x[i]='*';
                }
            }
        }
       
        if(ping) return 0;
        return -1;
    }
   
    static int game(String s)
    {
        return f(s.toCharArray());
    }
   
    public static void main(String[] args)
    {  
        System.out.println(game("***"));
        System.out.println(game("L**L"));
        System.out.println(game("L**L***L"));
        System.out.println(game("L*****L"));
    }
}

import java.util.*;

public class LOL
{
    static Map<String, Integer> map = new HashMap<String, Integer>();
   
    // -1: 必输,0: 平局, 1: 必赢
    static int f(char[] x)
    {
        String s = new String(x);
        if(map.get(s) != null) return map.get(s);
       
        if(s.contains("LOL")) {
            map.put(s,-1);
            return -1;
        }
        if(s.contains("*")==false) {
            map.put(s,0);
            return 0;
        }
       
        boolean ping = false;
       
        for(int i=0; i<x.length; i++){
            if(x[i]=='*'){
                try{
                    x[i]='L';
                    {
                        int t = f(x);
                        if(t<0) {
                            map.put(s,1);
                            return 1;
                        }
                        if(t==0) ping = true;
                    }
                    x[i]='O';
                    {
                        int t = f(x);
                        if(t<0) {
                            map.put(s,1);
                            return 1;
                        }
                        if(t==0) ping = true;
                    }      
                }
                finally{           
                    x[i]='*';
                }
            }
        }
       
        if(ping){
            map.put(s,0);
            return 0;
        }
       
        map.put(s,-1);
        return -1;
    }
   
    static int game(String s)
    {
        map.clear();
        return f(s.toCharArray());
    }
   
    public static void main(String[] args)
    {  
        Scanner scan = new Scanner(System.in);
       
        int n = Integer.parseInt(scan.nextLine().trim());
        for(int i=0; i<n; i++){
            System.out.println(game(scan.nextLine().trim()));
        }
    }
}

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

// -1: 必输,0: 平局, 1: 必赢
int f3(char* x, int len)
{
    char *p = (char *)malloc(len);
    memset(p, 0, len);
    strcpy(p, x);

    if (strstr(p,"LOL"))
        return -1;
    if (!strstr(p,"*"))
        return 0;

    int  ping = 0;  // 假设无法平局

    for (int i = 0; i < len; i++)
    {
        if (p[i] == '*')
        {
           
                p[i] = 'L';  //试着填L
                switch (f3(p, len))
                {
                    case -1:
                        return 1;
                    case 0:
                        ping = 1;
                }
                p[i] = 'O';  //试着填O
                switch (f3(p, len))
                {
                    case -1:
                        return 1;
                    case 0:
                        ping = 1;
                }              
                p[i] = '*';
        }
    }
    if (ping)
        return 0;
    return -1;
}

int game(char * s)
{
    int len = strlen(s) + 1;
    int bool=f3(s, len);
    return bool;
}

void main31()
{
    printf("%d \n",game("***"));
    printf("%d \n", game("L**L"));
    printf("%d \n", game("L**L***L"));
    printf("%d \n", game("L*****L"));
}

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include<string.h>

typedef struct MyNode
{
    char*s1;
    int num;
    struct MyNode*pNext;
}MyNode;
MyNode *pHead = NULL;
MyNode *pTail = NULL;

void put(char*s,int x)
{
    MyNode*pNode = (MyNode*)malloc(sizeof(MyNode));
    pNode->num = x;
    int len = strlen(s);
    pNode->s1 = malloc(len);
    memset(pNode->s1, 0, len);
    strcpy(pNode->s1, s);
    pNode->pNext = NULL;

    if (pHead == NULL)
    {
        pHead = pNode;
        pTail = pNode;
    }
    else
    {
        pTail->pNext = pNode;
        pTail = pNode;
    }
}
struct flag
{
    int f;
    int num;
};

struct flag get(char *s)
{
    struct flag f1;
    f1.f = 0;

    MyNode * pTemp = pHead;
    while (pTemp)
    {
        if (!strcmp(pTemp->s1, s))
        {
            f1.f = 1;
            f1.num=pTemp->num;
        }
        pTemp = pTemp->pNext;
    }
    return f1;
}


// -1: 必输,0: 平局, 1: 必赢
int fn(char *x,int len)
{
    char *pc = (char*)malloc(len);
    memset(pc, 0, len);
    strcpy(pc, x);

    struct flag g = get(pc);
    if (g.f)
        return g.num;

    if (strstr(pc,"LOL"))
    {
        put(pc, -1);
        return -1;
    }


    if (!strstr(pc, "*"))
    {
        put(pc, 0);
        return 0;
    }

    int  ping = 0;
    for (int i = 0; i < len; i++)
    {
        if (x[i] == '*')
        {
                x[i] = 'L';
                {
                    int t = fn(x,len);
                    x[i] = '*';
                    if (t < 0)
                    {
                        put(pc, 1);
                        return 1;
                    }                      
                    if (t == 0)
                        ping = 1;
                }

                x[i] = 'O';
                {
                    int t = fn(x,len);
                    x[i] = '*';
                    if (t < 0)
                    {
                        put(pc, 1);
                        return 1;
                    }
                    if (t == 0)
                        ping = 1;
                }
        }
    }

    if (ping)
    {
        put(pc, 0);
        return 0;
    }

    put(pc, -1);
    return -1;
}

int myGame(char* s,int len)
{
    pHead = NULL;
    return fn(s,len);
}
void main()
{
    int n = 0;
    char arr[1024] = { 0 };
    scanf("%d",&n);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", arr);
        int len = strlen(arr);
        int x = myGame(arr, len);
        printf("%d \n", x);
    }
}


5. 高僧斗法
古时丧葬活动中经常请高僧做法事。
仪式结束后,有时会有“高僧斗法”的趣味节目,以舒缓压抑的气氛。

节目大略步骤为:先用粮食(一般是稻米)在地上“画”出若干级台阶(表示N级浮屠)。
又有若干小和尚随机地“站”在某个台阶上。
最高一级台阶必须站人,其它任意。(如图所示)

两位参加斗法的法师分别指挥某个小和尚向上走任意多级的台阶,但会被站在高级台阶上的小和尚阻挡,不能越过。
两个小和尚也不能站在同一台阶,也不能向低级台阶移动。

两法师轮流发出指令,最后所有小和尚必然会都挤在高段台阶,再也不能向上移动。
轮到哪个法师指挥时无法继续移动,则游戏结束,该法师认输。

对于已知的台阶数和小和尚的分布位置,请你计算先发指令的法师该如何决策才能保证胜出。

输入数据为一行用空格分开的N个整数,表示小和尚的位置。台阶序号从1算起,所以最后一个小和尚的位置即是台阶的总数。(N<100, 台阶总数<1000)

输出为一行用空格分开的两个整数: A B, 表示把A位置的小和尚移动到B位置。
若有多个解,输出A值较小的解,若无解则输出-1。

例如:
用户输入:
1 5 9
则程序输出:
1 4

再如:
用户输入:
1 5 8 10
则程序输出:
1 3

【源代码】
【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
// 组合博弈论....转化为尼姆堆
import java.util.*;
public class A
{
    static boolean f(int[] x)
    {
        int sum = 0;
        for(int i=0; i<x.length-1; i+=2){ sum ^= x[i+1] - x[i] - 1; // 两人一组间的空台阶数===>尼姆堆
        }
        return sum != 0;
    }
   
    static void solve(int[] x)
    {
        for(int i=0; i<x.length-1; i++){
            for(int k=x[i]+1; k<x[i+1]; k++){
                int old = x[i];  //试着走
                try{
                    x[i] = k;
                    if(f(x)==false) {
                        System.out.println(old + " " + k);
                        return;
                    }
                }
                finally{
                    x[i] = old; //回溯
                }
            }
        }
    }
   
    public static void main(String[] args)
    {  
        solve(new int[]{1,5,9});
        solve(new int[]{1,5,8,10});
        solve(new int[]{1,4,8,12,16,19,28,33,35,36,40,45,52,66,67,68,69,77
          ,85,99,102,134,155,211,214,216,355,376,400,412});
    }
}

【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
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
// 组合博弈论....转化为尼姆堆

int f4(int* x,int len)
{
    int sum = 0;
    for (int i = 0; i < len - 1; i += 2) { sum ^= x[i + 1] - x[i] - 1; // 两人一组间的空台阶数===>尼姆堆
    }
    return sum != 0;
}

void solve(int* x,int len)
{
    for (int i = 0; i < len - 1; i++)
    {
        for (int k = x[i] + 1; k < x[i + 1]; k++){
            int old = x[i];  //试着走
            {
                x[i] = k;
                if (!f4(x,len))
                {
                    printf("%d %d\n",old,k);
                    return;
                }
            }
           
            x[i] = old; //回溯
           
        }
    }
}

void main4()
{
    int x[] = { 1, 5, 9 };
    solve(x,3);
    int y[] = { 1, 5, 8, 10 };
    solve(y,4);
    int z[] = { 1, 4, 8, 12, 16, 19, 28, 33, 35, 36, 40, 45, 52, 66, 67, 68, 69, 77, 85, 99, 102, 134, 155, 211, 214, 216, 355, 376, 400, 412 };
    solve(z,30);
}


6. 古代赌局
俗话说:十赌九输。因为大多数赌局的背后都藏有阴谋。
不过也不尽然,有些赌局背后藏有的是:“阳谋”。

有一种赌局是这样的:桌子上放六个匣子,编号是1至6。
多位参与者(以下称玩家)可以把任意数量的钱押在某个编号的匣子上。
所有玩家都下注后,庄家同时掷出3个骰子(骰子上的数字都是1至6)。
输赢规则如下:

1.若只有1个骰子上的数字与玩家所押注的匣子号相同,则玩家拿回自己的押注,庄家按他押注的数目赔付(即1比1的赔率)。
2.若2个骰子上的数字与玩家所押注的匣子号相同,则玩家拿回自己的押注,庄家按他押注的数目的2倍赔付(即1比2的赔率)。
3.若3个骰子上的数字都与玩家押注的匣子号相同,则玩家拿回自己的押注,庄家按他押注的数目的10倍赔付(即1比10的赔率)。

乍一看起来,好像规则对玩家有利,庄家吃亏。但经过大量实战,会发现局面很难说,于是怀疑是否庄家做了手脚,庄家则十分爽快地说:可以由玩家提供骰子,甚至也可以由玩家来投掷骰子。

你的任务是:通过编程模拟该过程。模拟50万次,假定只有1个玩家,他每次的押注都是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
public class DuJu
{
    public static double f()
    {
        int a = (int)(Math.random() * 6) + 1;
        int b = (int)(Math.random() * 6) + 1;
        int c = (int)(Math.random() * 6) + 1;
       
        int w = (int)(Math.random() * 6) + 1;
       
        int n = 0;
        if(a==w) n++;
        if(b==w) n++;
        if(c==w) n++;
       
        if(n==3) return -10;
        if(n==2) return -2;
        if(n==1) return -1;
       
        return 1;
    }
   
    public static void main(String[] args)
    {
        int N = 500*1000;
       
        double sum = 0;
        for(int i=0; i<N; i++)
        {
            sum += f();
        }
       
        System.out.println(sum/N);
    }
}

【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
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
     double f5()
    {
         int a = (int)(rand() / (RAND_MAX + 0.0) * 6) + 1;
         int b = (int)(rand() / (RAND_MAX + 0.0) * 6) + 1;
         int c = (int)(rand() / (RAND_MAX + 0.0) * 6) + 1;

         int w = (int)(rand() / (RAND_MAX + 0.0) * 6) + 1;

        int n = 0;
        if (a == w) n++;
        if (b == w) n++;
        if (c == w) n++;

        if (n == 3) return -10;
        if (n == 2) return -2;
        if (n == 1) return -1;

        return 1;
    }

    void main5()
    {
        int N = 500 * 1000;

        double sum = 0;
        for (int i = 0; i < N; i++)
        {
            sum += f5();
        }

        printf("%f \n", sum / N);

    }


7. 火柴游戏
这是一个纵横火柴棒游戏。
如图1,在3×4的格子中,游戏的双方轮流放置火柴棒。
其规则是:
1. 不能放置在已经放置了火柴棒的地方(即只能在空格中放置)。
2. 火柴棒的方向只能是竖直或水平放置。
3. 火柴棒不能与其它格子中的火柴“连通”。
所谓连通是指两根火柴棒可以连成一条直线,且中间没有其它不同方向的火柴“阻拦”。
例如:
火柴游戏.jpg

图1

图1所示的局面下,可以在C2位置竖直放置(为了方便描述格子位置,图中左、下都添加了标记),但不能水平放置,因为会与A2连通。
同样道理,B2,B3,D2此时两种方向都不可以放置。
但如果C2竖直放置后,D2就可以水平放置了,因为不再会与A2连通(受到了C2的阻挡)。
4. 游戏双方轮流放置火柴,不可以弃权,也不可以放多根。

如某一方无法继续放置,则该方为负(输的一方)。

游戏开始时可能已经放置了多根火柴。
你的任务是:编写程序,读入初始状态,计算出对自己最有利的放置方法并输出放置后的局面。
图1的局面表示为:
00-1
-000
0100
即用“0”表示空闲位置,用“1”表示竖直放置,用“-”表示水平放置。

解法不唯一,找到任意解法即可。

例如,局面:
0111
-000
-000
的解:
-111
-000
-000

再例如,局面:
1111
—-
0010
的解:
1111
—-
0110

【源代码】
【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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.util.*;
public class A
{
    static void show(char[][] data){
        System.out.println();
        for(int i=0; i<data.length; i++){
            System.out.println(new String(data[i]));
        }
    }
   
    static boolean f(char[][] data){       
        for(int i=0; i<data.length; i++){
            String s = new String(data[i]).replaceAll("0","");
            if(s.contains("--")) return true;
        }
       
        for(int i=0; i<data[0].length; i++){
            String s = ("" + data[0][i] + data[1][i] + data[2][i]).replaceAll("0","");
            if(s.contains("11")) return true;
        }  
       
        for(int i=0; i<data.length; i++){
            for(int j=0; j<data[i].length; j++){
                if(data[i][j]=='0'){
                    try{
                        data[i][j] = '1';
                        if(f(data)==false) return true;
                        data[i][j] = '-';
                        if(f(data)==false) return true;
                    }
                    finally{
                        data[i][j] = '0';
                    }
                }
            }
        }
   
        return false;
    }
   
    static void solve(char[][] data){
        for(int i=0; i<data.length; i++){
            for(int j=0; j<data[i].length; j++){
                if(data[i][j]=='0'){
                    try{
                        data[i][j] = '1';
                        if(f(data)==false) {
                            show(data);
                            //return
                        }
                        data[i][j] = '-';
                        if(f(data)==false){
                            show(data);
                            //return;
                        }
                    }
                    finally{
                        data[i][j] = '0';
                    }
                }
            }
        }
    }
   
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
       
        char[][] data = new char[3][];
        data[0] = scan.nextLine().trim().toCharArray();
        data[1] = scan.nextLine().trim().toCharArray();
        data[2] = scan.nextLine().trim().toCharArray();
       
        solve(data);
        //System.out.println(f(data));
    }
}

【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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
void show(char* data[],int len1)
{
    printf("\n");
    for (int i = 0; i < len1; i++)
    {
        printf("%s\n", data[i]);
    }
}

int f6(char* data[], int len1)
{

    for (int i = 0; i < len1; i++)
    {
        int len2 = strlen(data[i]);
        char*p = (char*)malloc(len2 + 1);
        memset(p, 0, len2);

        int lenOfP = 0;
        for (int j = 0; j < len2;j++)
        {
            if (data[i][j]!='0')
            {
                p[lenOfP] = data[i][j];
                lenOfP++;
            }
        }
        if (strstr(p,"--"))
        {
            return 1;
        }
    }

    int lenth = strlen(data[0]);
    for (int i = 0; i < lenth; i++)
    {
        char*p = (char*)malloc(3);
        p[0] = data[0][i];
        p[1] = data[1][i];
        p[2] = data[2][i];


        int lenOfP = 0;
        for (int j = 0; j < 3; j++)
        {
            if (data[j][i] != '0')
            {
                p[lenOfP] = data[j][i];
                lenOfP++;
            }
        }
        if (strstr(p, "11"))
            return 1;
    }

    for (int i = 0; i < len1; i++)
    {

        int len2 = strlen(data[i]);
        for (int j = 0; j < len2; j++)
        {
            if (data[i][j] == '0')
            {
                {
                    data[i][j] = '1';
                    if (f6(data,len1) == 0)
                        return 1;
                    data[i][j] = '-';
                    if (f6(data,len1) == 0)
                        return 1;
                }
                {
                    data[i][j] = '0';
                }
            }
        }
    }

    return 0;
}

void solve6(char* data[],int len1)
{
    for (int i = 0; i < len1; i++)
    {
        int len2 = strlen(data[i]);
        for (int j = 0; j < len2; j++)
        {
            if (data[i][j] == '0'){
                {
                    data[i][j] = '1';
                    if (f6(data, len1) == 0)
                    {
                        show(data,len1);
                        //return
                    }
                    data[i][j] = '-';
                    if (f6(data, len1) == 0){
                        show(data, len1);
                        //return;
                    }
                }
                {
                    data[i][j] = '0';
                }
            }
        }
    }
}

void main6()
{
    char *data[3] = { NULL };
    for (int i = 0; i<3; i++)
    {
        data[i] = malloc(1024);
        memset(data[i], 0, 1024);

        scanf("%s", data[i]);
    }
           
    solve6(data,3);

    //System.out.println(f6(data));
}


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


Spread the word. Share this post!

Leave Comment

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