簡易 Python 問答機器人(Simple Python QA Robot)

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

本篇文章會以一個簡易問答機器人來了解底下的 Python 相關知識：變數、字串、函數、字典、if/if else/if elif else 判斷式、for 迴圈。


聊天機器人程式架構
儲存問題與答案的 quiz 串列。
兩個主要函數：sendMsg 函數、readMsg 函數。

變數(Variables)
底下用非很精準的解釋，畢竟變數和容器還是不一樣的觀念
變數可看成容器，而容器有很多種，例如罐子、紙箱、寶特瓶、水桶、背包、鉛筆盒等。

但若是有30個人都帶著一模一樣的罐子容器時，那要怎麼辨別這個罐子是誰的啊？！
所以就給這些罐子一個獨一無二的名稱！開始來命名囉！

「豬頭罐子」、「空罐子」、「軟罐子」、「硬罐子」、「無敵罐子」、「我的罐子」、「你的罐子」、「不說話罐子」、「機器人罐子」、「腳罐子」、「黑罐子」、「紅罐子」

可以亂命名嗎？！好像不給個規則會產生一些怪怪的名稱。在程式語言裡，變數是有命名規則的，大多的程式語言通常會有底下兩個規則：
  • 第一個字必須是英文字母(大小寫字母皆可)或是底線字元「_」，不可以是數字或其他符號。
  • 第一個字之後的其他字必須是英文字母(大小寫字母皆可)、底線字元「_」或是數字，不可以使用其他符號。

而 Python 提供的容器(Data Types)有底下幾種：
  • 文字容器(Text Type)：字串(string)。
  • 數字容器(Numeric Types)：整數(int)、浮點數(float)、複數(complex)。
  • 序列容器(Sequence Types)：串列(list)、元組(tuple)、range(小編不知道要如何翻成中文)。
  • 映射容器(Mapping Type)：字典(dict)。
  • 集合容器(Set Types)：可變集合(set)、不可變集合(frozenset)。
  • 布林容器(Boolean Type)：布林(bool)。
  • 二元容器(Binary Types)：位元組(bytes)、位元組陣列(bytearray)、memoryview(小編不知道要如何翻成中文)。。
Python 變數的使用方式如下：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
# 宣告一個變數 n ，並將 n 設成整數 3
n = 3

# 宣告一個變數 f ，並將 f 設成浮點數 3.3
f = 3.3

# 宣告一個變數 c ，並將 c 設成複數 1 + 2j
c = 1 + 2j

print(n)  # 印出變數 n 的值
print(f)  # 印出變數 f 的值
print(c)  # 印出變數 c 的值


函式(Functions) 此部分可參考 Python 函數(Functions) 一文
在解釋函式是什麼之前，先來看看Scratch程式設計裡的一些積木：
在Scratch裡，每一個積木都是一個函式，而且都已被分類了，例如上圖中的動作、外觀、音效等積木。讀者也可以在 code.org 玩玩Artist https://studio.code.org/s/course3/stage/5/puzzle/1 與 Bee https://studio.code.org/s/course3/stage/6/puzzle/1，幫助了解什麼是函式。Python 函式的樣子如下：
1
2
3
4
5
# 函式的框架
def yourFunction(para1, para2):
    '''
        your function code is here
    '''

1
2
3
4
def 函數名稱( 參數列 ):
   "函數說明"
   程式碼
   return [運算式(Expression)]

例子：
1
2
3
4
5
6
7
8
9
# 兩數的加法
def sumWith(a, b):
    return (a+b)

# 宣告變數 a ，並將呼叫 sumWith(3, 4) 的結果 (3 + 4) 指定給變數 a。
a = sumWith(3, 4)

# print 也是函式，印出變數 a 的內容
print(a)

字串(String)
Python 的字串是以單引號 (single quotation marks) 或是雙引號 (double quotation marks)，所包圍的文字。

而多行字串可用三個雙引號來表示，底下皆為 Python 的字串範例：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
'這是單引號字串'
"這是雙引號字串"
s = "How are you?"
a = 'Fine, and you?'

"""
這是
多行
字串
"""


字典(Dictionary)
下圖為 Dictionareis 的示意圖：


Python 字典範例：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
# 建立英漢字典對照表
d = {
    'python': '蟒蛇',
    'ruby': '紅寶石',
    'dictionary': '字典',
    'English': '英文',
    'Chinese': '中文',
    'apple': '蘋果',
    'dog': '狗',
    'cat': '貓',
    'sun': '太陽'
    }

if/if else/ if elif else 判斷式
判斷式 if 的語法。
if 語法
1
2
if 判斷條件:
  程式碼...

if/else 語法
1
2
3
4
if 判斷條件:
  程式碼...
else:
  程式碼...

if/elif/else 語法
1
2
3
4
5
6
if 判斷條件1:
  程式碼...
elif 判斷條件2:
  程式碼...
else:
  程式碼...

Python判斷式範例：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# 考試成績結果判斷
holanScore = 59
if holanScore < 60:
  print("版主考試不及格啦！")

holanScore = 60
if holanScore >= 60:
  print("版主考試及格了！")
else:
  print("版主考試不及格啦！")

holanScore = 61
if holanScore >= 90:
  print("版主不就好棒棒！！！")
elif holanScore >= 70:
  print("版主考試及格啦！")
else:
  print("版主考試有通過嗎？")

串列(List)  此部分可參考 Python 串列(或陣列？)結構 一文。
先來認識什麼是串列。下圖為 Lists 的示意圖：

  

這是什麼意思呢？請繼續看下圖
請把串列先想成有很多格子的容器，每個格子都有自己的編號(又稱索引值)，但此容器有個限制條件：每一個格子只能放一樣東西。所以上圖中，第 0 格放了什麼？第 3 格放了什麼？第 9 格放了什麼？OK，了解此概念後，來看一下 Python串列的語法：[expression, ... ]。先這樣子解讀「把東西放在中括號[]內，用 , 逗號(是英文的逗號)來區隔每一個東西。」所以上圖就可以寫成：
myTreasure = ['dog', 'cat', 'penguin', 'sun', 'mouse', 'tree', 'rose', 'diamond', 'snake', 'chair']


串列的每一格當成是哆啦A夢的百寶袋，因為 Python 串列的每一格就像百寶袋一樣，雖然一格只能放一樣東西，但此東西是可以是已經裝好東西的一個容器。



for迴圈(for loop) 此部分可參考 Python 重複式迴圈語法一文
for loop 語法如下：
1
2
3
4
5
for 變數 in 序列:
    程式碼第1行
    程式碼第2行
    ...etc
    程式碼第n行

for loop範例：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
import string
# 列出小寫英文字母
for lowCase in string.ascii_lowercase:
    print(lowCase, end=',')

print()

# 列出大寫英文字母
for upCase in string.ascii_uppercase:
    print(upCase, end=',')

計分功能(Scoring)
在這個程式裡，使用了 cnt 變數來記錄玩家答對了幾題。

範例程式：
 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
def sendMsg(msg):
    print(msg)

def readMsg():
  return input()

welcome = "嗨！您好！接下來會問您幾個腦筋急轉彎的問題。 " \
          "相信您一定可以表現很好。"
sendMsg(welcome)

quiz = [
    {
  "question": "台灣現任總統是誰？",
  "answer": "蔡英文"
 },
 {
  "question": "什麼地方的路最窄",
  "answer": "冤家路窄"
 },
 {
  "question": "書店買不到什麼書？",
  "answer": "遺書"
 },
 {
  "question": "借什麼可以不還？",
  "answer": "借過"
 },
 {
  "question": "右手永遠抓不到什麼？",
  "answer": "右手"
 },
 {
  "question": "什麼樣的河人們永遠也渡不過去？",
  "answer": "銀河"
 },
 {
  "question": "什麼東西越擦越小？",
  "answer": "橡皮擦"
 },
 {
  "question": "一加一等於多少？",
  "answer": "不三不四"
 },
 {
  "question": "一口咬掉牛尾巴，是什麼字？",
  "answer": "告"
 },
 {
  "question": "上海的南京路，來往最多的是什麼人？",
  "answer": "中國人"
 }

]


cnt = 0    # 答對題數
for q in quiz:
    sendMsg(q["question"])
    response = readMsg()
    if response == q["answer"]:
        sendMsg("答對了！")
        cnt += 1
    else:
        sendMsg("答錯了！正確答案是 %s" % 
                      q["answer"])
      
sendMsg("您答對了 %d 題。" % cnt)

if cnt < 2:
    sendMsg("請加油！")
# Add elif and else
elif cnt < 4:
    sendMsg("不錯喔！")
else:
    sendMsg("真厲害！")


程式執行結果：


思考與程式練習：如何增加這個問答機器人在判斷玩家的回答的改善機制(人工智慧)？例如在回答「借什麼可以不還？」時，「借過」與「借光」是同義詞，這兩個詞都要算對。
Labels: ,

APCS 實作題 10610 第2題交錯字串參考解法

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

此題在高中生程式解題系統的題號為：c462: apcs 交錯字串 (Alternating Strings)。

============底下文字取自官方的試題文件============
問題描述 
一個字串如果全由大寫英文字母組成，我們稱為大寫字串；如果全由小寫字母組成則稱為小寫字串。字串的長度是它所包含字母的個數，在本題中，字串均由大小寫英文字母組成。假設 k 是一個自然數，一個字串被稱為「k-交錯字串｣，如果它是由長度為 k 的大寫字串與長度為 k 的小寫字串交錯串接組成。

舉例來說，「StRiNg｣是一個 1-交錯字串，因為它是一個大寫一個小寫交替出現；而「heLLow｣是一個 2-交錯字串，因為它是兩個小寫接兩個大寫再接兩個小寫。但不管 k 是多少，「aBBaaa｣、「BaBaBB｣、「aaaAAbbCCCC｣都不是 k-交錯字串。

本題的目標是對於給定 k 值，在一個輸入字串找出最長一段連續子字串滿足 k-交錯字串的要求。例如 k=2 且輸入「aBBaaa｣，最長的 k-交錯字串是「BBaa｣，長度為 4。又如 k=1 且輸入「BaBaBB｣，最長的 k-交錯字串是「BaBaB｣，長度為 5。
============以上文字取自官方的試題文件============

解法如下：
變數 cg 記錄目前交錯字串長度。
變數 g 紀錄最大交錯字串長度。
變數 ck 紀錄目前字母case累積次數。
變數 preL 紀錄上一個字母的case是大寫u、小寫 l、未知n。
變數 curL 紀錄目前字母的case是大寫u、小寫 l、未知n。

將題目輸入的 k 值分成兩種情況來處理，這是因為筆者的解法在處理 k = 1 與 k > 1 這兩種情況時，剛好是相反的。

k = 1 時，當發生大小寫轉換(preL != curL)時，cg 就加 1；否則  cg 設為 1。 g 設為 max(g, cg)。


k > 1 時，請參考底下圖片：
當發生大小寫轉換(preL != curL)時，目前字母case累積次數 ck 會有三種情況：
ck < k，將 cg = 0。
ck == k，將 cg + k，cg = max(g, cg)。
ck > k，cg = k。

請注意到上圖右邊是個？號，這是因為在字串到尾端時，若沒有發生大小寫轉換，會少考慮到右邊的？號中ck次數的情況。

所以改為當沒發生大小寫轉換(preL == curL) 時，判斷底下兩件事：
ck == k，將 cg + k，cg = max(g, cg)。
ck > k，cg = k。
而在發生大小寫轉換(preL != curL)時，將 cg = 0，ck = 1。 

以 k = 2 為例，g, cg, ck 值的變化如下表：
最大交錯字串長度(g)的改變會發生在紅色或橘色字母上。
目前交錯字串長度(cg)的改變會發生在橘色字母上。

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
#include <stdio.h>
#include <string.h>
#include <ctype.h>

// 回傳兩個整數的最大值
int max(int x,int y) {
    return (x >= y? x: y);
}

// 取得字母大小寫
char letterCase(char c)
{
    if(islower(c)) return 'l';
    if(isupper(c)) return 'u';
    return 'n';
}

int main(void) {
    int k;
    char str[100000];

    while(scanf("%d", &k) == 1)
    {
        int g = 0;      // 交錯字串最大長度
        int cg = 0;     // 目前交錯字串長度
        scanf("%s", str);
        int len = strlen(str);

        char preL = 'n';    // 上一個字母是大寫u、小寫 l、未知n。
        char curL;          // 目前字母是大寫u、小寫 l、未知n。
        int ck = 0;         // 目前字母case累積次數

        //  k 為 1 時要另外處理
        if(k == 1)
        {
            for(int i = 0; i < len; i++)
            {
                curL = letterCase(str[i]);      // 取得字母大小寫
                if(preL != curL)    // 轉換大小寫時
                    cg++;
                else                // 沒轉換大小寫時
                    cg = 1;

                g = max(cg, g);     // g 和 cg 誰是最大交錯字串長度
                preL = curL;        // 上一個字母case為目前字母case
            }
        }
        else
        {
            for(int i = 0; i < len; i++)
            {
                curL = letterCase(str[i]);

                if(preL == curL)
                {
                    ck++;
                    if(ck == k)             // 累積到 k 次
                    {
                        cg += k;            // 加到目前交錯字串長度
                        g = max(cg, g);     // g 和 cg 誰是最大交錯字串長度
                    }

                    if(ck > k)              // 目前case次數超過 k 次
                        cg = k;             // 目前交錯字串長度也只能等於 k
                }
                else if(preL != curL)       // 轉換大小寫時
                {
                    if(ck < k) cg = 0;      // 目前case次數小於 k 次，目前交錯字串長度歸零
                    ck = 1;                 // case次數從 1 開始
                }
                preL = curL;                // 上一個字母case為目前字母case
            }
        }

        printf("%d\n", g);
    }
    return 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <string>

using namespace std;

// 取得字母大小寫
char letterCase(char c)
{
    if(islower(c)) return 'l';
    if(isupper(c)) return 'u';
    return 'n';
}

int main(void) {
    int k;
    string str;

    while(cin >> k)
    {
        int g = 0;      // 交錯字串最大長度
        int cg = 0;     // 目前交錯字串長度
        cin >> str;
        int len = str.length();

        char preL = 'n';    // 上一個字母是大寫u、小寫 l、未知n。
        char curL;          // 目前字母是大寫u、小寫 l、未知n。
        int ck = 0;         // 目前字母case累積次數

        //  k 為 1 時要另外處理
        if(k == 1)
        {
            for(int i = 0; i < len; i++)
            {
                curL = letterCase(str[i]);      // 取得字母大小寫
                if(preL != curL)    // 轉換大小寫時
                    cg++;
                else                // 沒轉換大小寫時
                    cg = 1;
                
                g = max(cg, g);     // g 和 cg 誰是最大交錯字串長度
                preL = curL;        // 上一個字母case為目前字母case
            }
        }
        else
        {
            for(int i = 0; i < len; i++)
            {
                curL = letterCase(str[i]);

                if(preL == curL)
                {
                    ck++;
                    if(ck == k)             // 累積到 k 次
                    {
                        cg += k;            // 加到目前交錯字串長度
                        g = max(cg, g);     // g 和 cg 誰是最大交錯字串長度
                    }

                    if(ck > k)              // 目前case次數超過 k 次
                        cg = k;             // 目前交錯字串長度也只能等於 k
                }
                else if(preL != curL)       // 轉換大小寫時
                {
                    if(ck < k) cg = 0;      // 目前case次數小於 k 次，目前交錯字串長度歸零
                    ck = 1;                 // case次數從 1 開始
                }
                preL = curL;                // 上一個字母case為目前字母case
            }
        }

        cout << g << 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
45
46
47
48
49
50
def letterCase(c):
    if c.isupper():
        return 'u'
    if c.islower():
        return 'l'
    return 'n'

while True:
    try:
        k = int(input())
        g = 0      # 交錯字串最大長度
        cg = 0     # 目前交錯字串長度
        s = input()
        l = len(s)

        preL = 'n'    # 上一個字母是大寫u、小寫 l、未知n。
        curL = 'n'     # 目前字母是大寫u、小寫 l、未知n。
        ck = 0         # 目前字母case累積次數

        #  k 為 1 時要另外處理
        if(k == 1):
            for i in range(l):
                curL = letterCase(s[i])      # 取得字母大小寫
                if(preL != curL):    # 轉換大小寫時
                    cg = cg + 1
                else:                # 沒轉換大小寫時    
                    cg = 1
                g = max(cg, g)     # g 和 cg 誰是最大交錯字串長度
                preL = curL        # 上一個字母case為目前字母case
        else:
            for i in range(l):
                curL = letterCase(s[i])
                if preL == curL:
                    ck = ck + 1
                    if(ck == k):             # 累積到 k 次    
                        cg += k            # 加到目前交錯字串長度
                        g = max(cg, g)     # g 和 cg 誰是最大交錯字串長度

                    if(ck > k):              # 目前case次數超過 k 次
                            cg = k             # 目前交錯字串長度也只能等於 k
                    
                elif preL != curL:       # 轉換大小寫時
                    if ck < k:
                        cg = 0      # 目前case次數小於 k 次，目前交錯字串長度歸零
                    ck = 1                 # case次數從 1 開始
                preL = curL                # 上一個字母case為目前字母case

        print(g)
    except EOFError:
        break
Labels: , , ,

APCS 實作題 10603 第2題小群體參考解法

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

此題在高中生程式解題系統的題號為：c291: APCS 2017-0304-2小群體。

題目簡短說明如下：
好友的關係會形成一些小群體。例如 N=10，好友編號如下，
0 的好友是 4，4 的好友是 6，6 的好友是 8，8 的好友是 5，5 的好友是 0，所以 0、4、6、8、和 5 就形成了一個小群體。另外，1 的好友是 7 而且 7 的好友是 1，所以 1 和7 形成另一個小群體，同理，3 和 9 是一個小群體，而 2 的好友是自己，因此他自己是一個小群體。總而言之，在這個例子裡有 4 個小群體：{0,4,6,8,5}、{1,7}、{3,9}、{2}。

延伸：輸出各小群體內每個人的編號，例如上述例子為{0,4,6,8,5}、{1,7}、{2}、{3,9}。

解法一：用陣列
用兩個陣列，一個(f [50000])用來記錄自己的好友是誰，一個(g[50000])用來記錄有沒有加入到群體裡。

尚未組成群體：

群體編號為 1：

群體編號為 2：

群體編號為 3：

群體編號為 4：


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

int main(void) {
    int n;

    while(scanf("%d", &n) == 1)
    {
        int f[50000];   // 自己的好友是誰
        char g[50000] = {0};  // 有無加入群體

        for(int i = 0; i < n; i++)
            scanf("%d", &f[i]);

        int grpCnt = 0;     // 紀錄有幾個群體
        int nxt = 0;        // 自己的好友是誰
        for(int i = 0; i < n; i++)
        {
            if(g[i] == 0) // 尚未加入群體
            {
                nxt = i;              // 目前尚未加入群體的人
                do
                {
                    g[nxt] = grpCnt + 1;    // 已加入此群體
                    nxt = f[nxt];       // 換下一位好友
                }while(g[nxt] == 0);
                grpCnt++;               // 已找完群體的人數，所以將群體數加一
            }
        }

        printf("%d\n", grpCnt);

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

using namespace std;

int main(void) {
    int n;

    while(cin >> n)
    {
        int f[50000];   // 自己的好友是誰
        char g[50000] = {0};  // 有無加入群體

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

        int grpCnt = 0;     // 紀錄有幾個群體
        int nxt = 0;        // 自己的好友是誰
        for(int i = 0; i < n; i++)
        {
            if(g[i] == 0) // 尚未加入群體
            {
                nxt = i;              // 目前尚未加入群體的人
                do
                {
                    g[nxt] = grpCnt + 1;   // 已加入此群體
                    nxt = f[nxt];       // 換下一位好友
                }while(g[nxt] == 0);
                grpCnt++;               // 已找完群體的人數，所以將群體數加一
            }
        }

        cout << grpCnt << 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
while True:
    try:
        n = int(input())
        f = input()
        # 紀錄自己的好友是誰
        f = list(map(int, f.split()))

        # 有無加入群體
        g = []

        # 群體編號為 0 代表尚未分群到
        for i in range(n):
            g.append(0)

        # 紀錄有幾個群體
        grpCnt = 0

        # 從 0 號開始找起
        for i in range(n):
            if g[i] == 0:
                nxt = i  # 目前尚未加入群體的人

                while True:
                    g[nxt] = grpCnt + 1  # 已加入此群體
                    nxt = f[nxt]         # 換自己好友的編號
                    if g[nxt] != 0:      # 自己好友已有加入群體
                        break
                grpCnt = grpCnt + 1      # 已找完群體的人數，所以將群體數加一

        print(grpCnt)
                
    except EOFError:
        break

註：解法一的程式碼是可以輸出各小群體內每個人的編號，如{0,4,6,8,5}、{1,7}、{2}、{3,9}的結果，只是程式碼沒有做輸出。

解法二：用 (key, value) 的資料結構
C語言本身沒有提供 (key, value) 這種資料結構，要自己做一個，有興趣的讀者可以試試。而C++可以使用 map 這個 container；Python 則是用 Dictionary。程式的資料結構就會變成如下：

每次都從尚未分到群體的最小編號者開始找起，整個流程如下。

首先從編號 0 開始找起

會找出群體為{0,4,6,8,5} 。

從編號  1 找起
會找出群體為{1,7} 。

從編號 2 找起
會找出群體為{2} 。

從編號 3 找起
會找出群體為{3,9} 。


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

using namespace std;

int main(void) {
    int n;

    while(cin >> n)
    {
        map<int, int> m;
        for(int i = 0; i < n; i++)
        {
            int v;
            cin >> v;
            m[i] = v;
        }

        int grpCnt = 0;     // 紀錄有幾個群體

        while(!m.empty())
        {
            // 每群都從未分到群體的最小編號開始
            int f = m.begin()->first;       // 自己的編號
            int nxtF = m.begin()->second;   // 自己好友的編號

            //cout << "{";
            while(true)
            {
                //cout << f << ",";
                m.erase(f);                     // 已加入群體，所以從表中刪除
                f = nxtF;                       // 換成自己好友編號
                if(m.find(nxtF) == m.end())     // 找自己好友的好友編號
                    break;                      // 若找不到，代表此群體已建立好
                nxtF = m.find(nxtF)->second;    // 換成自己好友的好友編號
            }
            //cout << "}" << endl;
            grpCnt++;
        }

        cout << grpCnt << 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
while True:
    try:
        n = int(input())
        f = input()
        # 紀錄自己的好友是誰
        f = list(map(int, f.split()))

        m = {}
        for i in range(n):
            m[i] = f[i]
       
        # 紀錄有幾個群體
        grpCnt = 0

        while len(m) > 0:
            # 每群都從未分到群體的最小編號開始
            f = list(m.keys())[0]         # 自己的編號
            nxtF = list(m.values())[0]    # 自己好友的編號

            # print('{', end='')
            while True:
                del m[f]    # 已加入群體，所以從表中刪除
                #print(f,',', end='')
                f = nxtF    # 換成自己好友編號
                if not f in m.keys():   # 找自己好友的好友編號
                    break               # 若找不到，代表此群體已建立好
                nxtF = m[nxtF]          # 換成自己好友的好友編號

            # print('}')
            grpCnt = grpCnt + 1      # 已找完群體的人數，所以將群體數加一

        print(grpCnt)
                
    except EOFError:
        break

註：解法二的程式碼是可以輸出各小群體內每個人的編號，如{0,4,6,8,5}、{1,7}、{2}、{3,9}的結果，而該部分的程式碼被註解掉。

Labels: , , ,

(非官方整理題目) 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指布）
N≤10

範例測資：

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,y1≠y2
  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


Labels: , ,
訂閱： 文章 (Atom)