▼

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
這題可用一個變數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
此參考答案是筆者自己花時間撰寫出來的，若有疑問，歡迎透過底下方式來討論：

祝各位解題愉快！
沒有留言:

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

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

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

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



祝各位解題愉快！
沒有留言:

程式練習題庫與學習資源

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

中文題庫
高中生程式解題系統 https://zerojudge.tw/
台中女中程式解題系統 http://www.tcgs.tc.edu.tw:1218/
新北市立林口高中ZeroJudge線上程式設計解題系統 http://course.lksh.ntpc.edu.tw/
一中電腦資訊研究社 Online Judge https://judge.tcirc.tw/
高中資訊學科能力競賽歷屆試題 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
此份參考答案是筆者花時間做出來的，若有疑問，歡迎透過底下方式來討論：


祝各位解題愉快！
沒有留言:

台中女中程式解題系統：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. }
沒有留言: