LeetCode OJ: 58. Length of Last Word

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

原文題目連結：https://leetcode.com/problems/length-of-last-word/。此題要在含有大小寫字母以及空白字元的字串裡，找出最後一個英文字的字母長度。如果不存在此英文字就輸出 0。

範例一輸入："Good morning "
輸出：7 

範例二輸入："What a wonderful day"
輸出：3

演算法步驟如下：

• Step 1. 用一個變數 foundLen 紀錄目前找到的英文字長度，初值為0。
• Step 2. 從字串最右邊開始找，一直找到不是空白字元為止。
• Step 3. 當步驟 Step 2 找到不是空白字元時，foundLen = foundLen + 1。
• Step 4. 當步驟 Step 3 找到是空白字元時，回傳 foundLen 。

程式碼如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public: int lengthOfLastWord(string s) { if(s.length() == 0) return 0; int foundLen = 0; for(int i = s.length() - 1; i >= 0; i--) { if(s[i] == ' ') { if(foundLen > 0) return foundLen; continue; } else { foundLen++; } } return foundLen; } };

台中女中程式解題系統(Green Judge)基礎題庫解題說明

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

本篇筆者會從台中女中程式解題系統(Green Judge)基礎題庫(網址：http://www.tcgs.tc.edu.tw:1218/Problems?tab=tab00)中挑選題目出來說明。所挑選的題目如下：

• a014：貨比三家 (*) -- 多重/巢狀if
• a017：成績等第 (*) -- 多重/巢狀if
• a024：所有位數和 -- while 迴圈
• a025：數字倒轉 -- while 迴圈
• a032：小小綠的數學習題 (*) -- char
• a033：故障的計算機 -- 格式化輸出
• a034：距離 -- 數學函數-sqrt
• a035：位數 -- 數學函數-log10
• a041：收集冰棒棍 (**) -- 迴圈應用
• a042：13的次方 (**) -- 迴圈應用
• a043：最大公因數 -- 迴圈應用
• a044：盈數、虧數和完全數 -- 迴圈應用
• a045：質數判斷 -- 迴圈應用
• a048：數字金字塔 -- 多重迴圈
• a049：斜紋地硨 -- 多重迴圈
• a050：九九乘法表 -- 多重迴圈

底下逐一說明以上幾題筆者的解題思路。

a014：貨比三家 (*) -- 多重/巢狀if

這題可用一個變數min來表示最小值，可寫成如下程式碼：

而這樣子的寫法也可以改成迴圈版本：

a017：成績等第 (*) -- 多重/巢狀if

這題很多人會使用巢狀if來解題，但也可以用迴圈方式來解：

a024：所有位數和 -- while 迴圈

這題常見的解法會類似如下：

也可以用字串來解：

a025：數字倒轉 -- while 迴圈

這題常見的解法會類似如下：


也可以用字串來解：

a033：故障的計算機 -- 格式化輸出

這題用到 setfill 與 setw 格式化輸出函數。須注意什麼時候要補 '0'，什麼時候要補 '_'。

a034：距離 -- 數學函數-sqrt
這題用到 setprecision 與 fixed 格式化輸出函數以及 sqrt 數學函數。

a035：位數 -- 數學函數-log10
這題用到 log10 數學函數。須注意如何使用 log10 來算出 a 的 b 次方之位數，因為 a 的 b 次方可能會很大。

a041：收集冰棒棍 (**) -- 迴圈應用

此題用一個變數記錄目前吃了幾支冰棒(sum)，一個變數紀錄目前可換的冰棒數(q)，以及一個變數紀錄不換的冰棒有幾根(r)，接著看q + r 是否可以繼續換冰棒，一直重複到不能換冰棒為止。

a042：13的次方 (**) -- 迴圈應用
此題要求出13 的 N 次方的十位數，這題即使使用 long long int 也會造成 overflow。那保留13的N-1次方之十位數與個位數，就可以算出十位數數字是多少了。程式碼如下：

a043：最大公因數 -- 迴圈應用
此題使用迴圈來做輾轉相除法，即可算出最大公因數，變數 a 即為最大公因數。

a044：盈數、虧數和完全數 -- 迴圈應用

此題用迴圈從判斷1到 N/2 是否為 N 的因數，若是則加總(s)。接著比較加總結果與 N的大小關係來輸出對應的訊息。(那有沒有更好的演算法呢？)

a045：質數判斷 -- 迴圈應用

除了 2 以外，其餘偶數皆不是質數。若N是奇數，則判斷小於或等於 sqrt(N) 的所有奇數是不是N的因數，只要有一個是因數，N就不是質數。

a048：數字金字塔 -- 多重迴圈
a049：斜紋地硨 -- 多重迴圈

這兩題題與a046、a047可用2D座標(Cartesian coordinate system)的方式來解題。這樣的解法也可以畫出如下的圖形(可參考：Python 金字塔圖案、Python 巴斯卡三角形)：

a050：九九乘法表 -- 多重迴圈
常見的九九乘法表練習，須注意輸出的格式即可。

參考解答下載處：台中女中解題系統_基礎題庫.zip
此參考答案是筆者自己花時間撰寫出來的，若有疑問，歡迎透過底下方式來討論：

• 雲林SONG粉絲團 https://www.facebook.com/yunlinsong/
• APCS 大學程式設計先修檢測討論社群 https://www.facebook.com/groups/taiwan.apcs/
• 個人臉書 https://www.facebook.com/liaopinglun

祝各位解題愉快！

台中女中程式解題系統(Green Judge)校內初賽參考答案

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

台中女中程式解題系統(Green Judge)校內初賽網址：http://www.tcgs.tc.edu.tw:1218/Problems?tab=tab02

參考解答下載處：台中女中解題系統_校內初賽.zip
此份參考答案是筆者花時間做出來的，若有疑問，歡迎透過底下方式來討論：

• 雲林SONG粉絲團 https://www.facebook.com/yunlinsong/
• APCS 大學程式設計先修檢測討論社群 https://www.facebook.com/groups/taiwan.apcs/
• 個人臉書 https://www.facebook.com/liaopinglun

祝各位解題愉快！

程式練習題庫與學習資源

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

中文題庫
高中生程式解題系統 https://zerojudge.tw/

台中女中程式解題系統 http://www.tcgs.tc.edu.tw:1218/

新北市立林口高中ZeroJudge線上程式設計解題系統 http://course.lksh.ntpc.edu.tw/

一中電腦資訊研究社 Online Judge https://judge.tcirc.tw/

TOI 歷屆試題 https://toi-reg.csie.ntnu.edu.tw/tasks.php 

高中資訊學科能力競賽歷屆試題 https://hackmd.io/@cube/HyxueFBi4 

建中資訊TIOJ https://tioj.ck.tp.edu.tw/ 

網際網路程式設計全國大賽歷年比賽題目 https://contest.cc.ntu.edu.tw/npsc2019/problem.html

Lucky貓的 UVA（ACM）園地 http://luckycat.kshs.kh.edu.tw/ 

教育部程式自學平台 & ITSA線上程式設計競賽 https://e-tutor.itsa.org.tw/e-Tutor/

英文題庫
北京大學PKU JudgeOnline http://poj.org/
LeetCode https://leetcode.com/
Online Judge https://onlinejudge.org/
Kattis https://open.kattis.com/
Codeforces http://codeforces.com/
USA Computing Olympiad http://www.usaco.org/index.php
HackerRank https://www.hackerrank.com/
HackerEarth https://www.hackerearth.com/
Codewars https://www.codewars.com/

學習資源
演算法 algorithm https://hiskio.com/courses/127
大學 AP 程式設計 https://ic.sean.cat/apcp
C++ 從 Zero 開始 https://ic.sean.cat/cppzero/
2018 板中校內資訊培訓講義 https://ic.sean.cat/zi-xun-pei-xun
NCKU ACM Training Courses https://nckuacm.github.io/
資訊之芽算法班 https://www.csie.ntu.edu.tw/~sprout/algo2019/

Python 完全數(Perfect Number)

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

筆者有用C++來解高中生解題系統上的 高中生程式解題系統：c032: 00382 - Perfection
(題目連結：https://zerojudge.tw/ShowProblem?problemid=c032) 一題。而筆者在解台中女中程式解題系統(Green Judge)中的「a044：盈數、虧數和完全數 -- 迴圈應用」一題，是用迴圈從判斷1到 N/2 是否為 N 的因數，若是則加總(s)。接著比較加總結果與 N的大小關係來輸出對應的訊息。(那有沒有更好的演算法呢？)

此次換用 Python 程式語言來解，演算法如下：

找出此數的所有因數。
將所有因數加總。
判斷加總與此數之間的大小關係。

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

import sys msg = {0:"PERFECT", 1:"ABUNDANT", -1:"DEFICIENT"} def checkPerfection(n): sum = 0 for i in range(1, (n // 2) + 1, 1): if( n % i == 0 ): sum += i if( n == sum ): return 0 elif( n > sum ): return -1 elif( n < sum ): return 1 num = [] n = 1 for s in sys.stdin: tn = list(map(int,s.split())) for n in tn: if n == 0: break num.append(n) if n == 0: break print('PERFECTION OUTPUT') for n in num: ret = checkPerfection(n) print("%5d %s" % (n, msg[ret])) print('END OF OUTPUT')

Scratch 3 遊戲：人工智慧篇

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

在讀者閱讀此篇文章之前，請花個時間閱讀用十分鐘快速瞭解 《人工智慧的過去、現在與未來》，了解一下人工智慧是什麼玩意兒。而此篇文章要介紹如何用Scratch來製作有人工智慧的遊戲。雖然筆者在Scratch簡易人工智慧：有智慧的蟑螂與蟲蟲一文裡，修改了兩個Scratch遊戲，分別為 Scratch 遊戲：水中踩蟑螂 與 Scratch 遊戲：蟲蟲危機，讓遊戲的蟑螂與蟲蟲看起來有智慧(還請AI大師們用力鞭策在下)，修改的想法為三種：隨機移動、沿著X軸移動、沿著Y軸移動，而這三種方式用來當成遊戲中人工智慧的入門範例似乎可行(！？)。總之，這要看讀者們對人工智慧的理解是什麼，以及對人工智慧一詞的定義是什麼，才能自己做判斷(茶)。

此外有聽過深度學習的讀者們，可能會覺得人工智慧不是要讓電腦自己來學習嗎？以這兩個Scratch遊戲來說，根本就不能算人工智慧(笑)。恩，好了，這閒聊的話題就到此為止，開始進入主題囉！

在Scratch官網的專案分享上有個由SenatorPenguin所分享的Tic-Tac-Toe: Human vs. Computer專案，請讀者玩玩看這個遊戲。

有沒有感覺很像在與真人對戰呢？

那這遊戲是怎麼做出來的？有興趣的讀者可以到Tic-Tac-Toe: Human vs. Computer專案按下切換到程式頁面按鈕，就可以看到程式積木了。此外還有Scratcher網友分享聊天機器人：https://scratch.mit.edu/projects/229484236/、https://scratch.mit.edu/projects/105644873/；西洋棋：https://scratch.mit.edu/projects/148769358/；五子棋：https://scratch.mit.edu/projects/246218177/、https://scratch.mit.edu/projects/250789603/等可以讓玩家(人)與電腦對戰。一樣要請讀者試玩這幾個遊戲，看看有沒有覺得電腦很厲害？

遊戲所使用的人工智慧通常會分成底下幾種(當然不只有這樣子的分法)：漫遊型AI、行為型AI、策略型AI。漫遊型AI是指遊戲中的角色會根據固定的模式來行動，例如左右移動、上下移動、追著主角跑、或是一直跳等單一的動作，在Scratch簡易人工智慧：有智慧的蟑螂與蟲蟲一文中，所使用人工智慧可屬漫遊型AI。行為型AI則是組合多種漫遊型AI來產生具有一些行為的角色，來調整遊戲的難易度，例如攻擊型的角色會用比較多的時間來追逐主角，並攻擊主角；而保守型的角色，則會用比較多的時間來防守自己的寶物等，例如常見的史萊姆通常很弱、魔王通常很聰明又很強。策略型AI使用一些定義好的遊戲規則來開發程式，最常見於棋類遊戲、撲克牌等電腦遊戲，但現在有些會使用深度學習(Deep Learning)的方式來進行開發策略型AI，例如會玩圍棋的AlphaGo。那要怎麼入門遊戲人工智慧呢？請參考這一篇文章：The Total Beginner's Guide to Game AI。

台中女中程式解題系統(Green Judge)初級題庫參考答案

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

台中女中程式解題系統(Green Judge)初級題庫網址：http://www.tcgs.tc.edu.tw:1218/Problems?tab=tab01

參考解答下載處：台中女中解題系統_初級題庫.zip
此份參考答案是筆者花時間做出來的，若有疑問，歡迎透過底下方式來討論：

• 雲林SONG粉絲團 https://www.facebook.com/yunlinsong/
• APCS 大學程式設計先修檢測討論社群 https://www.facebook.com/groups/taiwan.apcs/
• 個人臉書 https://www.facebook.com/liaopinglun

祝各位解題愉快！

台中女中程式解題系統：b025: 棋盤格城市

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

題目連結 http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b025。

分析完題目後，會得到這是 combination 問題：
C(n, k) = C(n-1, k-1) + C(n-1, k)
C(n, 0) = C(n, n) = 1

程式碼：

1. #include <iostream>  
2.   
3. using namespace std;  
4.   
5. long long int combi(int n, int k)  
6. {  
7.     long long int C[n + 1][k + 1];  
8.     int i, j;  
9.   
10.     for (i = 0; i <= n; i++)  
11.     {  
12.         for (j = 0; j <= min(i, k); j++)  
13.         {  
14.             if (j == 0 || j == i) // C(n, 0) = C(n, n) = 1  
15.                 C[i][j] = 1;  
16.             else // C(n, k) = C(n-1, k-1) + C(n-1, k)  
17.                 C[i][j] = C[i - 1][j - 1] + C[i - 1][j];  
18.         }  
19.     }  
20.   
21.     return C[n][k];  
22. }  
23.   
24. int main()  
25. {  
26.     int x, y;  
27.     cin >> x >> y;  
28.     cout << combi(x+y, x) << endl;  
29.   
30.     return 0;  
31. }  

台中女中程式解題系統：b024: 指南宮的階梯

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

題目連結 http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b024。

分析爬樓梯問題後，會得到
3 階是 fib(4)
4 階是 fib(5)
5 階是 fib(6)
... etc

這樣的結果其實是 Fibonacci number。

程式碼：

1. #include <iostream>  
2.   
3. using namespace std;  
4.   
5. long long int combi(int n, int k)  
6. {  
7.     long long int C[n + 1][k + 1];  
8.     int i, j;  
9.   
10.     for (i = 0; i <= n; i++)  
11.     {  
12.         for (j = 0; j <= min(i, k); j++)  
13.         {  
14.             if (j == 0 || j == i) // C(n, 0) = C(n, n) = 1  
15.                 C[i][j] = 1;  
16.             else // C(n, k) = C(n-1, k-1) + C(n-1, k)  
17.                 C[i][j] = C[i - 1][j - 1] + C[i - 1][j];  
18.         }  
19.     }  
20.   
21.     return C[n][k];  
22. }  
23.   
24. int main()  
25. {  
26.     int x, y;  
27.     cin >> x >> y;  
28.     cout << combi(x+y, x) << endl;  
29.   
30.     return 0;  
31. }