(非官方整理題目) APCS 實作題 10901 第1題「猜拳模擬」參考解法

若您覺得文章寫得不錯,請點選網誌上的廣告,來支持小編,謝謝。


======底下文字取自 https://hackmd.io/@joylintp/APCS20200105 ======

pA 猜拳

有一個機器人跟真人玩 N 次猜拳,
真人在第i輪出的拳為 yi
機器人第一次會出的拳為 F,接下來出拳的方式如下:
如果前兩輪真人出的拳皆相同,則電腦這輪會出可以打敗前兩輪的拳;
否則,電腦會出與前一輪真人一樣的拳。
請輸出第 k 輪時會分出勝負,或 N 輪雙方都平手。

$\輸入格式:



y1 y2 ... yN

輸出格式:

c1 c2 ... ck : Drew at round N/Won at round k/Lost at round k

範圍:

F,yi,ci{0,2,5} (0指石頭,2指剪刀,5指布)
N10

範例測資:

Input 1:
0
4
2 5 0 2
Output 1:
0 : Won at round 1
Input 2:
2
2
2 0
Output 2:
2 2 : Lost at round 2
Input 3:
5
4
5 5 0 0
Output 3:
5 5 2 : Lost at round 3
Input 4:
5
6
5 5 2 2 0 0
Output 4:
5 5 2 2 0 0 : Drew at round 6

子題:

  1. (20%) N=1
  2. (20%) N=2,y1y2
  3. (60%) 無特別限制
======以上文字取自 https://hackmd.io/@joylintp/APCS20200105 ======

解法一:直接解題
用 pre 變數紀錄真人上一次是出什麼拳,此變數一開始設為 -1 ,代表真人尚未出拳。
g 變數紀錄遊戲結果,-1為程式輸,0為平手,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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>

using namespace std;

int main()
{
    // 0 指石頭,2 指剪刀,5 指布
    int n, f, y[10];
    while(cin >> f >> n)
    {
        // pre 紀錄真人上一次出什麼拳
        int pre = -1;

        // g 紀錄遊戲結果,-1為程式輸,0為平手,1為程式贏
        int g = 0;

        int i;
        for(i = 0; i < n; i++)
            cin >> y[i];

        for(i = 0; i < n; i++)
        {
            int h = y[i];
            cout << f << " ";

            if( (f == 0 && h == 2) || (f == 2 && h == 5) || (f == 5 && h == 0) )
            { g = 1;break; } // 程式贏
            else if( (f == 5 && h == 2) || (f == 0 && h == 5) || (f == 2 && h == 0) )
            { g = -1;break; } // 程式輸

            //前兩輪真人出的拳皆相同,電腦這輪會出可以打敗前兩輪的拳
            if(pre == h)
            {
                if(h == 0)
                    f = 5;
                else if(h == 2)
                    f = 0;
                else if(h == 5)
                    f = 2;
            }
            pre = h;
        }

        cout << ": ";
        switch(g)
        {
            case -1:
                cout << "Lost";
                break;
            case 0:
                cout << "Drew";
                i--;    // 平手時,i 會等於 n,減去 1,會讓回合數的數值正確
                break;
            case 1:
                cout << "Won";
                break;
            default:
            break;
        }
        cout << " at round " << i + 1 << endl;
    }

    return 0;
}


Python 程式碼:
 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
while True:
    try:
        # 0 指石頭,2 指剪刀,5 指布
        f = int(input())
        n = int(input())

        y = input()
        y = list(map(int, y.split()))

        # pre 紀錄真人上一次出什麼拳
        pre = -1

        # 紀錄遊戲結果,-1為程式輸,0為平手,1為程式贏
        g = 0

        for i in range(n):
            h = y[i]
            print(f, end=' ')

            # 程式贏
            if( (f == 0 and h == 2) or (f == 2 and h == 5) or (f == 5 and h == 0) ):
                print(': Won at round', i + 1)
                g = 1
                break
            # 程式輸
            elif( (f == 5 and h == 2) or (f == 0 and h == 5) or (f == 2 and h == 0) ):
                print(': Lost at round', i + 1)
                g = -1
                break

            # 前兩輪真人出的拳皆相同,電腦這輪會出可以打敗前兩輪的拳
            if pre == h:
                if h == 0:
                    f = 5
                elif h == 2:
                    f = 0
                elif h == 5:
                    f = 2
            pre = h

        if g == 0:
            print(': Drew at round', n)
    except EOFError:
        break

解法二:數學分析

不想在 if 內寫那麼多的條件時,就可以用此方法(見上圖)。
因為(0指石頭,2指剪刀,5指布),那將這三個數值分別除以2求商會得到(0指石頭,1指剪刀,2指布)。左邊是程式(變數 c ),右邊是真人(變數 h),那程式贏的情況如下:
(石頭) 0 贏 1 (剪刀)
(剪刀) 1 贏 2 (布)
(布)     2 贏 0 (石頭)
可推出當 (c + 1) % 3 == h 時,程式贏。

那程式輸的情況如下:
(石頭) 0 輸 2 (布)
(剪刀) 1 輸 0 (石頭)
(布)     2 輸 1 (剪刀)
可推出當 (c + 2) % 3 == h 時,程式輸。

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
#include <iostream>

using namespace std;

int main()
{
    int n, f, y[10];
    while(cin >> f >> n)
    {
        // pre 紀錄真人上一次出什麼拳
        int pre = -1;

        // g 紀錄遊戲結果,-1為程式輸,0為平手,1為程式贏
        int g = 0;

        int i;
        for(i = 0; i < n; i++)
            cin >> y[i];

        for(i = 0; i < n; i++)
        {
            cout << f << " ";
            int c = f / 2;
            int h = y[i] / 2;

            if( (c + 1) % 3 == h )
            { g = 1;break; } // 程式贏
            else if( (c + 2) % 3 == h)
            { g = -1;break; } // 程式輸

            //前兩輪真人出的拳皆相同,電腦這輪會出可以打敗前兩輪的拳
            if(pre == h)
            {
                // f: 0 指石頭,2 指剪刀,5 指布
                // h: 0 指石頭,1 指剪刀,2 指布
                int t[] = {5, 0, 2};
                f = t[h];
            }
            // 紀錄真人上一次的出拳
            pre = h;
        }

        cout << ": ";
        switch(g)
        {
            case -1:
                cout << "Lost";
                break;
            case 0:
                cout << "Drew";
                i--;    // 平手時,i 會等於 n,減去 1,會讓回合數的數值正確
                break;
            case 1:
                cout << "Won";
                break;
            default:
            break;
        }
        cout << " at round " << i + 1 << endl;
    }

    return 0;
}


解法三:查表法

不想在 if 內寫那麼多的條件時,就可以用此方法(見上圖)。
因為 0 指石頭,2 指剪刀,5 指布,可以用兩張表紀錄輸贏的情況:
        # w (win): 電腦贏的狀況
        w = {0:2, 2:5, 5:0}
        # l (lost): 電腦輸的狀況
        l = {2:0, 5:2, 0:5}

Python 程式碼:
 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
while True:
    try:
        # 0 指石頭,2 指剪刀,5 指布
        # 用字典來記錄輸贏的情況
        # w (win): 電腦贏的狀況
        w = {0:2, 2:5, 5:0}
        # l (lost): 電腦輸的狀況
        l = {2:0, 5:2, 0:5}
        c = int(input())
        n = int(input())

        y = input()
        y = list(map(int, y.split()))

        # pre 紀錄真人上一次出什麼拳
        pre = -1

        # 紀錄遊戲結果,-1為程式輸,0為平手,1為程式贏
        g = 0

        for i in range(n):
            h = y[i]
            print(c, end=' ')

            # 程式贏
            if( h == w[c] ):
                print(': Won at round', i + 1)
                g = 1
                break
            # 程式輸
            elif( h == l[c] ):
                print(': Lost at round', i + 1)
                g = -1
                break

            # 前兩輪真人出的拳皆相同,電腦這輪會出可以打敗前兩輪的拳
            # 因為要讓對方輸,所以從 lost 字典找值 
            if pre == h:
                c = l[h]

            pre = h

        if g == 0:
            print(': Drew at round', n)
    except EOFError:
        break