雲林SONG

程式設計可以改變您的未來(Programming can change your future)。雲林SONG 全名為雲林軟體工程(SOftware eNGineering)，目標致力於軟體人才的培養並推廣開源軟體落實於資訊教育。程式設計的觀念是軟體產品的基礎，程式碼就像沙子一樣，要紮實，所建立出來的高塔才會穩固。本站也提供資訊教育相關的教學資源。 YunlinSONG stands for Yunlin SOftware eNGineering, offering tutorial for computer programming and promoting open-source software. Teaching resources in information technology education are provided here.

電腦遊戲設計入門

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

本部落格的幾篇文章：

說明了一些開發環境的建立，也介紹了一些小遊戲的做法。但，設計電腦遊戲一定要學程式設計嗎？例如開源跨平台遊戲開發工具介紹：GDevelop 文中提到的 GDevelop 以及遊戲程式開發工具與網站 ( Tools and their website for game programming ) 所提到的 Clickteam Fusion、RPG Maker，這三款軟體皆可不需撰寫程式碼，就可以設計遊戲囉。

除了這三款軟體之外，還有沒有其他的工具呢？當然有(不然要這篇文章做什麼呢！？)。此類軟體有免費與付費的，底下就分為這兩類來介紹。

須付費電腦遊戲設計軟體：

Game Maker https://www.yoyogames.com/gamemaker
Game Maker 最初推出的時候，有免費的版本，現在有30天試用的版本。提供拖拉(drag and drop)功能，讓使用者只要熟悉幾個指令就可以開發遊戲。除了拖拉方式外，也提供腳本語言GameMaker Language給開發者撰寫程式碼。

Construct 3 https://www.construct.net/en
除了有 Construct2 的功能外，增加了底下功能：支援Mac 和 Linux系統、多國語言、第三方工具的擴充。Construct3的使用方式可參考此連結：Construct3教學文章。

GameSalad https://gamesalad.com/
GameSalad這套軟體一樣有視覺式的編輯畫面，操作方式像Flash與Dreamweaver，開發者只需要把遊戲物件放到當位置，並設定相關的物理原則，即可設計出簡單的2D遊戲囉。

免費電腦遊戲設計軟體：

Stencyl http://www.stencyl.com/
Stencyl官網標榜「Create Amazing Games Without Code」，不會寫程式也可製作出HTML5與Flash遊戲。也是透過拖拉的方式來進行遊戲的製作。

Construct 2 https://www.scirra.com/construct2以HTML5為城市語言的2D遊戲開發工具，透過視覺化的界面與拖拉動作，即可讓沒有程式設計基礎的人來完成一個遊戲。Construct2的使用方式可參考此連結：Construct2教學文章。

題外話：免費的遊戲設計軟體還是會有一些功能限制，例如無法將開發好的遊戲發布到App商店上去賣等。

高中生程式解題系統：a134: 00948 - Fibonaccimal Base

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

題目連結 https://zerojudge.tw/ShowProblem?problemid=a134。

此題和 c121: 00495 - Fibonacci Freeze 、LintCode: Fibonacci 費布那西數列很接近，都是與費波那契數列有關。

程式碼是先建立好Fibonacci數列，也知道N最大值為500，所以就建立前40項的Fibonacci數列。從小於N的最大Fibonacci數開始找起，就可以唯一的表示法。

程式碼：

import sys

fibs = list(range(40))
fibs[0] = 0
fibs[1] = 1

for i in range(2, 40):
    fibs[i] = fibs[i-1] + fibs[i-2]

#print(fibs)
    
n = int(input())

for x in range(n):
    d = int(input())
    print(str(d) + " = ", end="")

    isPut = False
    for i in range(39, 1, -1):
        if d >= fibs[i]:
            d = d - fibs[i]
            isPut = True
            print("1", end="")
        elif isPut == True:
            print("0", end="")

    print(" (fib)")

三角函數觀念與常見公式

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

本篇文章整理與三角函數有關的資訊。

三角函數的基本觀念
影片版

文字版：三角函數基本概念
定義整理(取自三角函數- 維基百科)：

\theta

的正弦是對邊與斜邊的比值：

\sin {\theta }={\frac {a}{h}}

\theta

的餘弦是鄰邊與斜邊的比值：

\cos {\theta }={\frac {b}{h}}

\theta

的正切是對邊與鄰邊的比值：

\tan {\theta }={\frac {a}{b}}

\theta

的餘切是鄰邊與對邊的比值：

\cot {\theta }={\frac {b}{a}}

\theta

的正割是斜邊與鄰邊的比值：

\sec {\theta }={\frac {h}{b}}

\theta

的餘割是斜邊與對邊的比值：

\csc {\theta }={\frac {h}{a}}

平方關係

定義整理(取自三角函數- 維基百科)：
由

\sin^2\! x + \cos^2\! x = 1.

可導出底下式子

\tan ^{2}\!x+1=\sec ^{2}\!x.

1+\cot ^{2}\!x=\csc ^{2}\!x.

和角與差角公式

定義整理
和角公式(取自三角函數- 維基百科)：

{\begin{aligned}\sin \left(x+y\right)&=\sin x\cos y+\cos x\sin y,\\\cos \left(x+y\right)&=\cos x\cos y-\sin x\sin y,\\\tan(x+y)&={\frac {\tan x+\tan y}{1-\tan x\tan y}}.\end{aligned}}

差角公式(取自三角函數- 維基百科)：
${\begin{aligned}\sin \left(x-y\right)&=\sin x\cos y-\cos x\sin y,\\\cos \left(x-y\right)&=\cos x\cos y+\sin x\sin y,\\\tan(x-y)&={\frac {\tan x-\tan y}{1+\tan x\tan y}}.\end{aligned}}$

二倍角公式(取自三角函數- 維基百科)：
${\begin{aligned}\sin 2x&=2\sin x\cos x={\frac {2\tan x}{1+\tan ^{2}x}},\\\cos 2x&=\cos ^{2}x-\sin ^{2}x=2\cos ^{2}x-1=1-2\sin ^{2}x={\frac {1-\tan ^{2}x}{1+\tan ^{2}x}},\\\tan 2x&={\frac {2\tan x}{1-\tan ^{2}x}}.\end{aligned}}$

積化和差(取自三角函數- 維基百科)：

$2\cos \theta \cos \varphi ={\cos(\theta -\varphi )+\cos(\theta +\varphi )}$
$2\sin \theta \sin \varphi ={\cos(\theta -\varphi )-\cos(\theta +\varphi )}$
$2\sin \theta \cos \varphi ={\sin(\theta +\varphi )+\sin(\theta -\varphi )}$
$2\cos \theta \sin \varphi ={\sin(\theta +\varphi )-\sin(\theta -\varphi )}$
$\tan \theta \tan \varphi ={\frac {\cos(\theta -\varphi )-\cos(\theta +\varphi )}{\cos(\theta -\varphi )+\cos(\theta +\varphi )}}$
${\begin{aligned}\prod _{k=1}^{n}\cos \theta _{k}&={\frac {1}{2^{n}}}\sum _{e\in S}\cos(e_{1}\theta _{1}+\cdots +e_{n}\theta _{n})\\[6pt]&{\text{where }}S=\{1,-1\}^{n}\end{aligned}}$

和差化積(取自三角函數- 維基百科)：

$\sin \theta \pm \sin \varphi =2\sin \left({\frac {\theta \pm \varphi }{2}}\right)\cos \left({\frac {\theta \mp \varphi }{2}}\right)$
$\cos \theta +\cos \varphi =2\cos \left({\frac {\theta +\varphi }{2}}\right)\cos \left({\frac {\theta -\varphi }{2}}\right)$
$\cos \theta -\cos \varphi =-2\sin \left({\frac {\theta +\varphi }{2}}\right)\sin \left({\frac {\theta -\varphi }{2}}\right)$

Python 函數(Functions)

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

程式語言所用的函數(Functions)和數學上的函數有著很相似的觀念，但程式語言的函數比較複雜一點，需要了解底下知識：函數宣告、函數定義、函數呼叫。然而不是所有的程式語言都會有這三種觀念，因此本文會分別以C語言和Python語言來說明這三種觀念(註：C語言也是有版本之分的，請參考 https://en.wikipedia.org/wiki/C_(programming_language)#History)。

函數宣告(Function declaration)
C語言語法如下：

1	回傳型態函數名稱( 參數列 );

C語言範例：

int sum(int a, int b);
int add(int, int);
int min(int x, int y);
int max(int, int);

因為 Python 目前沒有 Function declaration 的語法，請直接使用 Function definition。

函數定義(Function definition)
C語言語法如下：

1
2
3

回傳型態 函數名稱( 參數列 ) {
   函數主體
}

C語言範例：

int sum(int a, int b) {
    return a + b;
}

int add(int a, int b) {
    return a + b;
}

int min(int x, int y) {
    return x <= y ? x: y;
}

int max(int x, int y) {
    return x >= y ? x: y;
}

Python語言語法如下：

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

Python語言範例：

def sum(a, b):
    return a + b

def add(a, b):
    return a + b

def min(x, y):
    if x <= y:
        return x
    else:
        return y

def max(x, y):
    if x >= y:
        return x
    else:
        return y

函數呼叫(Function call)
C語言語法如下：

1	函數名稱( 參數列 );

C語言範例：

int sumInt = sum(4, 5);
int addInt = add(9, 11);
int minInt = min(0, 123);
int maxInt = max(123, 0);

Python語言語法如下：

1	函數名稱( 參數列 )

Python語言範例：

sumInt = sum(4, 5)
addInt = add(9, 11)
minInt = min(0, 123)
maxInt = max(123, 0)

自訂函數範例
瞭解上述的語法後，就可以自訂函數了，底下提供C語言與Python語言的自訂函數範例。

C 語言範例：

#include <stdio.h>

int sum(int a, int b);
int add(int, int);
int min(int x, int y);
int max(int, int);

int main(void) {
  int sumInt = sum(4, 5);
  int addInt = add(9, 11);
  int minInt = min(0, 123);
  int maxInt = max(123, 0);

  printf("Sum:%d add:%d min:%d max:%d\n", sumInt, addInt, minInt, maxInt);
  return 0;
}

int sum(int a, int b) {
    return a + b;
}

int add(int a, int b) {
    return a + b;
}

int min(int x, int y) {
    return x <= y ? x: y;
}

int max(int x, int y) {
    return x >= y ? x: y;
}

Python語言範例：

def sum(a, b):
    return a + b

def add(a, b):
    return a + b

def min(x, y):
    if x <= y:
        return x
    else:
        return y

def max(x, y):
    if x >= y:
        return x
    else:
        return y

sumInt = sum(4, 5)
addInt = add(9, 11)
minInt = min(0, 123)
maxInt = max(123, 0)

print("Sum:", sumInt, "add:", addInt, "min:", minInt, "max:", maxInt)

Python 排序(Sorting)

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

筆者有用C++來解高中生解題系統上的高中生程式解題系統：排序 Sorting

(題目連結：https://zerojudge.tw/ShowProblem?problemid=a104) 一題。

本篇換用 Python 程式語言來解。雖然本部落有介紹過一些常見的排序演算法：「Python 排序演算法範例 ( Sorting Algorithms in Python )」。但因為 Python 有內建的排序函數 list.sort與sorted 可用，排序部分就用內建函數了。於是針對此題的演算法會變成如下：

讀取正整數 n
讀取一行正整數數列 line
設定 numbers 為空串列
將數列 line 每一個正整數加到 numbers 中
對 numbers 排序並輸出結果

Python程式碼：

import sys

while True:
    line = sys.stdin.readline()
    if not line:
        break

    n = int(line)

    line = sys.stdin.readline()
    numbers = []
    for x in line.split():
        numbers.append(int(x))

    for x in sorted(numbers):
        print(x, end=" ")

    print()

Python 完全平方和

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

筆者有用C++來解高中生解題系統上的高中生程式解題系統：完全平方和
(題目連結：https://zerojudge.tw/ShowProblem?problemid=a059) 一題。

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

找出在範圍 [a, b]內大於或等於 a 的完全平方數(curSquare)，與 a 的平方根(minRoot)。
當 curSquare 小於或等於 b 時
{
將 curSquare 加到 squareSum 裡
minRoot += 1
curSquare = minRoot * minRoot
}

Python程式碼：

from math import sqrt
    
n = int(input())

for i in range(n):
    a = int(input())
    b = int(input())

    # Current Square Number
    curSquare = 0

    # Minimal square root
    minRoot = int(sqrt(a))
    if minRoot * minRoot == a:
        curSquare = a
    else:
        minRoot = minRoot + 1
        curSquare = minRoot * minRoot

    squareSum = 0
    while curSquare <= b:
        squareSum += curSquare
        minRoot += 1
        curSquare = minRoot * minRoot

    print("Case " + str(i + 1) + ":", squareSum)

Python 阿姆斯壯數

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

筆者有用C++來解高中生解題系統上的高中生程式解題系統：阿姆斯壯數 Armstrong number
(題目連結：https://zerojudge.tw/ShowProblem?problemid=a040) 一題。

本篇換用 Python 程式語言來解，而當時所寫的 C++ 為先建立好阿姆斯壯數的對應表，算有點偷吃步，這次用演算法來解囉。首先要知道數字是幾位數，可將數字轉成字串後，在呼叫計算字串長度函數 order = len(str(x)) ，接著就是將每位數的 order 次方加總(s)，並檢查是否與原來數字相等。

Python程式碼：

import sys
  
def isArm (x):
    order = len(str(x))
    temp = x 
    s = 0
    while (temp != 0): 
        r = temp % 10
        s = s + (r ** order)
        temp = temp // 10
  
    return (s == x) 
  
  
for s in sys.stdin:
    n, m = map(int, s.split())

    flag = False

    for i in range(n, m):
        if isArm(i):
            flag = True
            print(str(i), end = " ")

    if flag == False:
        print("none")
    else:
        print()

Python 數字翻轉

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

筆者有用C++來解高中生解題系統上的高中生程式解題系統：數字翻轉
(題目連結：https://zerojudge.tw/ShowProblem?problemid=a038) 一題。

本篇換用 Python 程式語言來解，短短幾行就解決了！這是因為 python 有Slicing語法可用。

Python程式碼：

import sys

for s in sys.stdin:
    print(int(s[::-1]))

Python 二進位制轉換

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

筆者有用C++來解高中生解題系統上的高中生程式解題系統：二進位制轉換 Binary to Decimal
(題目連結：https://zerojudge.tw/ShowProblem?problemid=a034) 一題。

本篇換用 Python 程式語言來解，短短幾行就解決了！這是因為 python 可以使用 bin 函數來進行轉換。

Python程式碼：

import sys

for s in sys.stdin:
    print(int(bin(int(s))[2:]))

Python 五則運算

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

筆者有用C++來解高中生解題系統上的 a017: 五則運算
(題目連結：https://zerojudge.tw/ShowProblem?problemid=a017) 一題。

本篇換用 Python 程式語言來解，短短幾行就解決了！這是因為 python 可以使用 eval 來進行數學運算，在 python 裡， // 為整數除法。

程式碼如下：

import sys

for s in sys.stdin:
    print(eval(s.replace("/", "//")))

Python 最大公因數(GCD)

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

筆者有用C++來解高中生解題系統上的 a024: 最大公因數(GCD)
(題目連結：https://zerojudge.tw/ShowProblem?problemid=a024) 一題。本篇只是換用 Python 程式語言來解，也是用輾轉相除法來解。

程式碼如下：

import sys

for s in sys.stdin:
    num = list(map(int,s.split()))
    a = num[0]
    b = num[1]
    while( a != 0):
            a = a % b;
            b = b - a;

    print(b)

除了這個解法外，還可以有什麼解法呢？

Python 費氏數列

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

筆者在高中生解題系統上選出一些關於費氏數列的題目：

a134: 00948 - Fibonaccimal Base：https://zerojudge.tw/ShowProblem?problemid=a134
b837: 104北二1費氏數列：https://zerojudge.tw/ShowProblem?problemid=b837
d486: Fibonacci 's computation process：https://zerojudge.tw/ShowProblem?problemid=d486

針對這幾個題目要如何解題呢？首先要了解什麼是費氏數列，我們可從Wikipedia費氏數列的說明知道(底下文字節錄自Wikipedia費氏數列)：

在數學上，費波那契數列是以遞迴的方法來定義：

$F_{0}=0$

$F_{1}=1$

$F_{n}=F_{{n-1}}+F_{{n-2}}$ （n≧2）

用文字來說，就是費波那契數列由0和1開始，之後的費波那契系數就是由之前的兩數相加而得出。首幾個費波那契系數是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……（OEIS中的數列A000045）
特別指出：0不是第一項，而是第零項。

根據此數學定義，所以我們可以寫出底下遞迴版本 Python 程式：

def fibon(n):
  # 檢查 n 是否為整數
  if(type(n) == int):
    if n < 2:
      return n
    else:
      return fibon(n-1) + fibon(n-2)

fibon(3.3) # 測試浮點數
for i in range(10):
  print(fibon(i), end=', ')

或是用動態規劃版本 Python 程式：

def dp_fib(n):
  if n < 2:
      return n  
  
  n0 = 0
  n1 = 1
  fib = 0
  for i in range(n-1):
    fib = n1 + n0
    n0 = n1
    n1 = fib
  return fib

# 輸出前 9 項
for i in range(10):
  print(dp_fib(i), end=', ')

註：上頭兩個程式在效能上還可以提升，那要怎麼做呢？

了解後，就可以開始試著解這三題了。

a134: 00948 - Fibonaccimal Base：https://zerojudge.tw/ShowProblem?problemid=a134
這一題筆者採取動態規劃的方式，因為第40項費氏數為102,334,155大於題目的最大值100,000,000，所以先求出前39項的費氏數列，再做輸出的運算就可以了。

Python解題程式碼：

import sys

fibs = list(range(40))
fibs[0] = 0
fibs[1] = 1

for i in range(2, 40):
    fibs[i] = fibs[i-1] + fibs[i-2]

#print(fibs)
    
n = int(input())

for x in range(n):
    d = int(input())
    print(str(d) + " = ", end="")

    isPut = False
    for i in range(39, 1, -1):
        if d >= fibs[i]:
            d = d - fibs[i]
            isPut = True
            print("1", end="")
        elif isPut == True:
            print("0", end="")

    print(" (fib)")

b837: 104北二1費氏數列：https://zerojudge.tw/ShowProblem?problemid=b837
這一題筆者採取動態規劃的方式，因為第31項費氏數為1,346,269大於題目的最大值1,000,000，所以先求出前30項的費氏數列，並使用bisect找出 lower and upper bounds的費氏數做輸出的運算就可以了。

Python解題程式碼：

from bisect import bisect_left
from bisect import bisect_right 

fibs = list(range(31))
fibs[0] = 0
fibs[1] = 1

for i in range(2, 31):
    fibs[i] = fibs[i-1] + fibs[i-2]

# print(fibs)
    
t = int(input())

for x in range(t):
    a, b = input().split()
    a = int(a)
    b = int(b)
    # b = int(input())

    low = 0
    high = 0
    if(a >= b):
        low = bisect_left(fibs, b)
        high = bisect_right(fibs, a)
    else:
        low = bisect_left(fibs, a)
        high = bisect_right(fibs, b)

#    print("Low = ", low, " High = ", high)
#    print("Starting = ", fibs[low], " Ending = ", fibs[high])
    count = high - low

    i = low
    while i < high:
        print(fibs[i])
        i = i + 1
    print(count)

    if x < t - 1:
        print("------")

d486: Fibonacci 's computation process：https://zerojudge.tw/ShowProblem?problemid=d486
和前兩題一樣，用動態規劃算出前15項的和，但是 f(0) 的值改為 1，接著將 n 當成串列 g，演算法如下：
當串列 g 的某一元素大於或等於 2 時
{
r 為空串列
若 g 的元素大於或等於2時
{
將此元素減 1，放到 r
將此元素減 2，放到 r
}
否則 { 將此元素放到 r }

g = r
輸出 r 的結果
}

Python解題程式碼：

fibs = list(range(16))
fibs[0] = 1
fibs[1] = 1

for i in range(2, 16):
    fibs[i] = fibs[i-1] + fibs[i-2]

n = int(input())

while n != 0:
    g = [n]
    print("f(" + str(n) + ") ")

    while any( i >= 2 for i in g):
        r = []

        for t in g:
            if t >= 2:
                r.append(t - 1)
                r.append(t - 2)
            else:
                r.append(t)
        g = r

        for t in r:
            print("f(" + str(t) + ") ", end="")

        print()

    print("f(" + str(n) + ") = " + str(fibs[n]))

    n = int(input())

訂閱：文章 (Atom)