2016年4月29日 星期五

給新手的C++教學 (上冊) - 3. 認識運算子 (Acquaintance to operators)

回到「給新手的C++教學 (上冊)」

上一章

利用先前學到的概念,我們已經有能力可以讓程式跟人互動了!
不過,這樣似乎還缺了甚麼?
我們的程式目前好像只能模仿我們的輸入

如果我們的程式除了記憶力之外,還可以擁有強大的運算能力,把計算結果輸出給我們,那該有多好啊~
這樣,就可以真正的利用程式來幫助我們計算了!

要讓我們的程式開竅,我們可以使用「運算子 (Operator)」

運算子是甚麼呢?
千萬別被它的名稱嚇到了,其實「運算子」就只是「加減乘除」而已XD
比較需要注意的是,「乘法」的符號是「*」,「除法」的符號是「/」
(WTF原來這麼簡單?!)

還記的你在寫數學題目時會用到的算式嗎?
舉個例子:1+2的答案是?
你一定知道答案是3
信不信,電腦在學會「C++」之後 (電腦學會C++?請見第一章),也知道答案是3!
不信嗎?我們來做個小測試:

#include<cstdio>
int main()
{
    int a=1,b=2;
    printf("%d\n",a+b);
    return 0;
}

不用說你也知道要做甚麼吧?
趕快在Dev-C++裡面把這份程式碼打出來,然後按下鍵盤上的「F11鍵」查看程式執行結果吧!

程式輸出3了!
(可能有細心的讀者發現,我把Dev-C++的背景改成黑色了,這只是個人習慣,因為我覺得黑色背景比較好看XD)

在打出這份程式碼的過程中,聰明的你可能會注意到
原本的寫法
int a,b;
變成了
int a=1,b=2;
意思就是,我們定義型別為int的兩個變數,a和b (不懂?複習一下第二章吧)
然後把a設定成1,b設定成2
這種「將剛被定義出來的變數設定數值」的動作
我們稱之為「初始化 (Initialization)」(這個看起來很難的字眼,其實真的就是這麼簡單XD)
如果你有使用過Windows XP作業系統,你可能在登入畫面看過這個字眼
沒錯,這時候「Windows XP」這個巨大的程式,正在設定它裡面每個變數的數值

這是Windows XP的登入畫面,有時候會顯示「正在初始化...」
回到正題
程式輸出3了!電腦果然厲害!
那麼該來考考電腦了
現在,請你問問看電腦
2+3
567+789
273*7122
91/13
87411-24005
105-324
分別是多少呢?

答案是
2+3=5
567+789=1356
273*7122=1944306
91/13=7
87411-24005=63406
105-324=-219
你的電腦答對了嗎?
現在,請你嘗試問電腦更難、更刁鑽的問題
甚麼情況下電腦會答錯呢?

電腦真的有可能會算錯喔
舉兩個例子:
100000*100000
5/3

如果你覺得驚訝,代表你是個正常人

100000*100000的答案是「10000000000」
但是電腦卻回答了「1410065408」
5/3的答案是「1.6666666666......」
但是電腦卻回答了「1」
Why?
我們來回顧一下程式碼:

#include<cstdio>
int main()
{
    int a=100000,b=100000;
    printf("%d\n",a*b);
    return 0;
}
 

以及

#include<cstdio>
int main()
{
    int a=5,b=3;
    printf("%d\n",a/b);
    return 0;
}
 

可以發現,我們的程式是用兩個int去進行計算的
數學上,整數的加減乘法具有封閉性
也就是兩個整數相加、相減、相乘後的結果還是一個整數
程式上也一樣,「int」的運算也具有封閉性,不過封閉性更強了,連「除法」也具有封閉性!
事實上,你對兩個int進行任何運算,結果一定還是一個int!

int無法處理小數,所以「1.6666666666......」就捨去小數部分,變成了「1」,合情合理
(如果結果是「-1.6666666666......」,以int的型別儲存後就會變成「-1」) (註10)

至於「1410065408」,這就揭露了int的另外一個秘密了

事實上,你電腦的記憶體再怎麼多,還是有限的,因此不可能儲存很大很大的數字
對於int這種類型的變數,電腦會撥出大小為「32個位元」的記憶體去儲存它 (註1)
甚麼是位元?
就是0或1,電腦中最基本的儲存和運算單位

也就是說,int其實就是一個「最多32位數的二進位數字」
哪有?我們看到的int怎麼看都是一個十進位數字啊
那是因為電腦學會了C++,所以知道要怎麼把這個二進位數字轉換成十進位數字,輸出給我們看
那「負數」怎麼辦呢?
電腦學會了C++,很聰明的解決了這個問題
方法就是把32個位元的其中一個位元拿掉,這個位元就不用來表示二進位數字的其中一個位數了
電腦拿這個位元來表示這個數字的正負號
如果這個位元是0,表示這個數字是正數
如果這個位元是1,表示這個數字是負數
很聰明吧!

所以,剩下的「31個位元」所能表示的數字範圍就是「$0\sim 2^{31}-1$」(表示正數時) 或「$-2^{31}\sim -1$」(表示負數時) 了 (每個位元有2種情況 (0或1),因此31個位元可以有$2^{31}$種組合,這牽涉到一點數學排列組合的知識)
也就是「$0\sim 2147483647$」或「$-2147483648\sim -1$」(註3)
因此,int的最小值是「-2147483648」,最大值是「2147483647」

也因此,如果int的計算結果超出了「-2147483648~2147483647」的範圍,電腦就會因為撥出來給int變數的記憶體不夠而算錯喔~
這種情況,我們稱作「溢位 (Overflow)」,這是我們寫程式的人需要注意的,因為它會導致錯誤的計算結果

上面我們有提到,int無法處理小數,因此5/3的答案是「1」
不知聰明的你有沒有想到
那我們乾脆就用可以處理小數的「float」來計算就好啦!

廢話不多說,馬上來試試看!

#include<cstdio>
int main()
{
    float a=5,b=3;
    printf("%f\n",a/b);
    return 0;
}
 

要注意的是,float也滿足加減乘除的封閉性,因此計算出來的東西也是一個float,要用「%f」來輸出,而不是int的「%d」

用「float」計算5/3的結果
耶!果然有小數了!
等等,為甚麼最後一位是7?
剛剛有提到,電腦的記憶體是有限的,因此不可能儲存很大很大的數字,當然也不可能儲存很多很多的小數
float是用「科學記號」的方式儲存的,換句話說,「24005」會被當作「$2.4005*10^{4}$」來看待 (事實上不是如此,請見「註2」)
其中,「2.4005」和「4」是分開儲存的,和int一樣會被轉成二進位數字,儲存在電腦撥出來給它的記憶體中 (事實上不是如此,請見「註2」)
這兩個數字當然也有其範圍極限

還記得第二章提到的誤差問題嗎?
就是這樣來的喔~

綜合起來
float的範圍約落在「$-10^{38}\sim -10^{-38}$」、「0」、「$10^{-38}\sim 10^{38}$」
誤差約「0.00001% (也就是$10^{-7}$)」
這裡看不懂沒關係,你只要知道float有誤差就好 ^_^ (float非主流,見註6)

最後,再跟大家報告一個好消息
數學上,我們習慣「先乘除,後加減」
因此「$5\times 6+9\div 3$」的答案是「$5\times 6+9\div 3=(5\times 6)+(9\div 3)=30+3=33$」
而不是「$5\times 6+9\div 3=30+9\div 3=39\div 3=13$」喔
程式上,「先乘除,後加減」的規則也是成立的!
而且,還可以使用括號喔!

以下提供兩個例子,讓你深入了解C++程式的奧妙!
「先乘除,後加減」

#include<cstdio>
int main()
{
    int a=5,b=6,c=9,d=3;
    printf("%d\n",a*b+c/d);
    return 0;
}
 
「先乘除,後加減」,因此程式輸出「33」

「有括號,要先算」

#include<cstdio>
int main()
{
    int a=5,b=6,c=9,d=3;
    printf("%d\n",a*(b+c)/d);
    return 0;
}
 
「有括號,要先算」,因此程式輸出「25」

現在,換你了!
你玩出了甚麼東西呢?

下一章

感謝:pr3pony、李旺陽學長、WillyPillow
(版權所有 All copyright reserved)

2016年4月28日 星期四

給新手的C++教學 (上冊) - 2. 變數 (Variable)

回到「給新手的C++教學 (上冊)」

上一章

利用上一章學到的東西,我們已經有能力可以在螢幕上顯示任何文字了!
但是,這樣的程式還無法和人互動

我們的程式要怎麼和人互動呢?
方法是人輸入一些文字然後按下鍵盤上的Enter鍵,把這些文字輸入給程式
然後程式就可以依照輸入的東西來作出對應的回應了 (這裡的「回應」指的是在螢幕上顯示東西)

這裡先來向大家解釋甚麼是「輸入 (Input)」和「輸出 (Output)」
它們可以當動詞也可以當名詞,在以後的文章看到時,可能需要自行判斷一下
當動詞時,「輸入」代表將一段文字傳給程式,「輸出」代表程式將一段文字顯示在螢幕上
當名詞時,「輸入」代表傳給程式的一段文字,「輸出」代表程式在螢幕上顯示的一段文字
懂了嗎?^_^
(p.s.其實輸入輸出的意義不僅僅是這樣,但在以後的教學中,它們就只會是這個意思)

不過,要做到「程式依照輸入的東西來作出對應的回應」,就代表
你的程式必須記住你輸入了甚麼東西

我們要怎麼實現讓程式擁有記憶呢?
方法就是把資訊以「變數 (Variable)」的形式儲存起來

變數要怎麼使用呢?
在C++裡面,變數有很多種類型,我們稱作「型別 (Type)」
有哪些型別呢?
我想想喔,有short、int、long long、bool、char、float、double、......,甚至在新版的C++ (C++11) 又新增了一些型別
不過,大部分都不會用到 (或很少用到)
事實上,你只要學好int、char、float這三種型別,就足夠應付所有功能了!
其他的型別就只是int、char、float這三種型別的「功能增強版」或「功能削弱版」(?)

「int」是「整數 (Integer)」,這種型別的變數是用來儲存「一個整數」的
「char」是「字元 (Charactor)」,這種型別的變數是用來儲存「一個字」的
「float」是「浮點數 (Floating-point number)」,別被它的名字嚇到,其實「float」做的事情就和「int」一樣,只是「float」可以允許「小數」的存在,缺點是你必須接受些微的計算誤差。現階段,這個誤差你可以不用考慮它

介紹完了,那要怎麼使用呢?
來看個範例
我們希望輸入一個整數,然後程式就會輸出一個跟你輸入的數值相同的整數 (例如:輸入「12」或「012」,會得到輸出「12」)
也就是『輸入一個「int」,輸出一個「int」』
程式碼在這裡:

2016年4月27日 星期三

給新手的C++教學 (上冊) - 1. 最簡單的程式 (The simplest program)

回到「給新手的C++教學 (上冊)」

上一章 (這是第一章)

我們口中的「寫程式」,到底是甚麼意思呢?
就是把程式碼寫出來

程式碼就像文章一樣 (這裡的例子是英文文章),都是由許多的英文字母、空白和標點符號組成的
每篇文章都有各自想表達的意義,每份程式碼也都有各自想表達的邏輯
作家利用文章來向大眾表達內心的想法,程式設計師則利用程式碼來向電腦表達邏輯

電腦要怎麼知道你想說甚麼?
我們必須學會「英文」這個語言,才能讀懂文章的意思
電腦當然也不例外
電腦必須學會「C++」這個語言,才能讀懂程式碼的意思

要怎麼讓電腦學會「C++」?
我們在學校接受教育,學會閱讀英文文章
電腦則是藉由安裝新功能,學會閱讀C++程式碼

簡單來說就是
開始寫程式之前,你的電腦最好先安裝好特定的軟體
不然你的電腦會看不懂你寫出來的程式碼
這類讓電腦看懂程式碼的軟體稱作「編譯器」
C++的編譯器就是GCC

作家在撰寫文章時需要好寫的筆、好用的橡皮擦、好寫的紙
程式設計師在撰寫程式碼時需要好用的編輯器
甚麼是編輯器?

給新手的C++教學 (上冊)

給新手的C++教學 (上冊)

誠摯歡迎任何讀者試讀!
若閱讀或理解遇到任何困難,請參考「B. 遇到困難了? (There are troubles?)」
此教學的目的在於讓沒寫過程式的人、不借助網路上其他資料,也能夠看懂這系列教學,所以如果有任何不了解之處,懇請在本風景區留言,或寄到電子信箱,告訴小莫,會以最快的速度作出滿意的修改!
電子信箱:fsps60312@yahoo.com.tw
如果看懂了,給個鼓勵小莫也會很開心呦 ^_^
目前進度:
2016/6/2完成!!!歡迎留言!!!
(最近一次的修正:2018/7/26 18:13)

0. 目錄 (Catagories)
1. 最簡單的程式 (The simplest program) ←←從這一章開始讀
2. 變數 (Variable)
3. 認識運算子 (Acquaintance to operators)
4. 條件判斷 (Decision making)
5. 迴圈 (Loop)
6. 陣列 (Array)
7. 讓程式碼看起來更簡單 (Simplify the code)
8. 字元 & 字串 (Charactor & String)
9. 函式 (Function)
10. 變數的作用範圍 (Scope)
11. 結構 (Structure)
12. 指標 (Pointer) ←← 互動式動畫
13. 額外語法 (Extra syntax)
A. 補充資料 (Additional materials)
B. 遇到困難了? (There are troubles?)

快訊:決定開源!--給新手的C++教學 - 開源公告

下載Dev-C++

前往「給新手的C++教學 (下冊)」(未完成)

感謝:李青育老師、陳柏叡學長
(版權所有 All copyright reserved)

---Motivation驅動力教學,Mobius扭帶公司發行---

2016年3月20日 星期日

[公告]code風景區暫緩更新 (本文將持續更新直到資奧結束)

【IOI2016結束,本文到此為止】
【「鑽礦遊戲Digging Game 3」請期待~XD】

2016/8/16
競賽結果:http://pcms.ioi2016.ru/
銀牌第二,有點噢但還算不錯www
感謝大家的鼓勵與支持~ ^_^

2016/8/12
比賽實況連結似乎還沒出來
擔心來不及所以先煩請大家多多關注IOI 2016的官網 (http://ioi2016.ru/)
知道實況連結後要記得互相通知哦~
再次提醒比賽時間為8/14和8/16的14:00~19:00(UTC+8台北 (台灣) 時間)
歡迎大家來幫TWN(台灣隊)加油!

2016/8/11
國際資訊奧林匹亞競賽將於俄羅斯的喀山舉行
分成兩天比賽
比賽時間轉成台灣時區後分別是8/14和8/16的14:00~19:00(UTC+8)
歡迎大家來幫TWN(台灣隊)加油!
比賽有實況哦~實況連結代補充

2016/4/27
官方國手名單公布!!!
http://toi.csie.ntnu.edu.tw/news_show.php?ID=92

2016/4/24
目前情況樂觀,感謝路上好友相伴與支持
每次模擬考都有進步,十分感動!
以第二名的成績結訓,十分滿意!
雖然官方國手名單還沒公佈,但應該不會有問題了

鑽礦遊戲Digging Game 3製作決定!
敬請期待~(學電影用語XD)
歡迎隨時關心遊戲開發進度
另外,歡迎提供遊戲背景音樂,不限檔案格式、不限風格
請寄到我的電子信箱(收到後會回信通知):fsps60312@yahoo.com.tw
並附上署名,將在遊戲結束畫面公開感謝您的大恩大德!
鑽礦遊戲Digging Game 2在這裡,請參考~

接下來的國手培訓
還在拿捏時間的分配
寫遊戲和題目的時間要分配多少呢?

名次曲線:6→4→3→2
分數曲線:319→326→473→330 (最後一次滿分400,其他500)


2016/4/17
第三次模擬考幾乎滿分!
名次上升到第三名,和第四名拉了109分的差距!
國手有望,繼續努力維持前四名!
名次曲線:六→四→三
分數曲線:319→326→473

2016/3/28
第二階段選訓營官方名單 (不按照名次排序)
入選了!繼續努力!


2016/3/20
現在正在準備資訊奧林匹亞競賽
將「暫時」降低文章發布頻率
若造成不便,敬請見諒

Surprise!!!

2016年3月12日 星期六

[CodeChef XORSACK]Hououin Kyouma and Xorsack

中文版

The problem source is not easy to find, so the problem link is provided.

Definitions:
"A number set" is a set of numbers, "Number sets" means a lot of sets of numbers
"$bit_{i}$" is the $i$-th $bit$ of a number or $\oplus($elements of a number set$)$ ($\oplus$ is the sign of $XOR$)
"$X_{i}$" is number $X$'s $bit_{i}$ ($X$'s $i$-th $bit$)

One $bit$ by one $bit$, we can try maintain the number sets satisfy current conditions.

But the number of number sets is too large ($2^N$)!
What can we do?
It doesn't matter, we can save these $N$ numbers. (call it $s$, $s$ can represent all $2^N$ number sets)
At least later we still can get all the number sets, by enumerate "to choose or not to choose"(call it "choosing state") of each elements of $s$.

The first step is maintain all the number sets, whose $bit_{1}=K_{1}$.

Suppose that $K_{1}=0$
We can know, whether we choose each number (in $s$), whose $bit_{1}=0$, does not matter.
The key point is, how to pick up all the number sets, which has even number of elements satisfy $bit_{1}=1$. ($bit_{1}$ of all the number sets would $=0$ only if we do this)
Consider all elements (in $s$), whose $bit_{1}=1$, $v_{1},v_{2},v_{3},...,v_{n}$
We can prove that $s'=\{v_{1}\oplus v_{2},v_{2}\oplus v_{3},v_{3}\oplus v_{4},...,v_{n-1}\oplus v_{n}\}$ can exactly represent all number sets that contain even number of elements, whose $bit_{1}=1$ (Why? Maybe you could figure out by yourself :))

So, what we should do is replace $s$ with $\{{elements\ (in\ original\ s),\ whose\ bit_{1}=0},s'\}$
Then, we can continue to maintain all the number sets, satisfy $(bit_{i}=K_{i},\forall 1\leq i\leq 2)$, $(bit_{i}=K_{i},\forall 1\leq i\leq 3)$..., and so on!

What if $K_{1}=1$?
We can know, whether we choose each number (in $s$), whose $bit_{1}=0$, does not matter.
The key point is, how to pick up all the number sets, which has odd number of elements satisfy $bit_{1}=1$. ($bit_{1}$ of all the number sets would $=1$ only if we do this)
Consider all elements (in $s$), whose $bit_{1}=1$, $v_{1},v_{2},v_{3},...,v_{n}$
We just know that $s'=\{v_{1}\oplus v_{2},v_{2}\oplus v_{3},v_{3}\oplus v_{4},...,v_{n-1}\oplus v_{n}\}$ can exactly represent all number sets that contain even number of elements, whose $bit_{1}=1$
Why not make each number sets, which originally doesn't contain $v_{1}$, contains $v_{1}$,
and make each number sets, which originally contains $v_{1}$, does not contains $v_{1}$?

Therefore, what should we do was just replace $s$ with $\{\{$elements (in original $s$), whose $bit_{1}=0\},s'$ after modify its $v_{1}$'s choosing state$\}$
Then, we can continue to maintain all the number sets, satisfy $(bit_{i}=K_{i},\forall 1\leq i\leq 2)$, $(bit_{i}=K_{i},\forall 1\leq i\leq 3)$..., and so on!

The problem is, how to modify all number sets' $v_{1}$'s choosing state in $s'$?
We can know that choosing the same number twice, has the effect equals to not to choose the number.
Therefore, we just force it to choose an extra number, $v_{1}$.
For implementation, just let $K\oplus v_{1}$! (But I use another variable, $now$, to represent the changes of $K$)

The answer is $No$ if $v_{1}$ does not exist when we need it.
Or there's nothing going wrong until the last $bit$ is considered (That means there are still number sets satisfy the conditions), the answer is $Yes$

Time complexity: $O(31N)$ (My code enumerates $31$ $bit$s)

code:

[CodeChef XORSACK]Hououin Kyouma and Xorsack

English version

這題目不好找,附上題目連結

說明:
$bit_{i}$為某數字或某數字集合$\oplus$起來的數字,它的第$i$個$bit$ ($\oplus$為$XOR$的符號)
$X_{i}$為數字$X$的$bit_{i}$

我們可以嘗試一個$bit$一個$bit$慢慢維護符合目前條件的數字集合們

可是數字集合的數量實在太多了 ($2^N$),該怎麼辦呢?
沒關係,我們先存下這$N$個數字 (稱$s$,$s$代表了這$2^N$種數字集合),這樣至少以後會知道枚舉$s$裡面每個數字的選或不選就可以得到每一種數字集合

第一步就是維護出所有會讓$bit_{1}=K_{1}$的數字集合

假設$K_{1}=0$
我們知道,$s$中$bit_{1}=0$的那些數字選或不選都沒有影響
重點是要怎麼挑出那些包含偶數個$bit_{1}=1$的數字的集合 (因為這樣它們的$bit_{1}$才會$=0$)
考慮$s$中$bit_{1}=1$的數字為$v_{1},v_{2},v_{3},...,v_{n}$
可以證明,$s'=\{v_{1}\oplus v_{2},v_{2}\oplus v_{3},v_{3}\oplus v_{4},...,v_{n-1}\oplus v_{n}\}$恰可以代表所有選擇偶數個$bit_{1}=1$的數字的集合!(想一想,為甚麼XD)

因此,我們只要將$s$取代成$\{{原本s裡面bit_{1}=0的數字},s'\}$,就可以繼續維護$(bit_{i}=K_{i},\forall 1\leq i\leq 2)$、$(bit_{i}=K_{i},\forall 1\leq i\leq 3)$...的數字集合!

如果$K_{1}=1$呢?
我們知道,$s$中$bit_{1}=0$的那些數字選或不選都沒有影響
重點是要怎麼挑出那些包含奇數個$bit_{1}=1$的數字的集合 (因為這樣它們的$bit_{1}$才會$=1$)
考慮$s$中$bit_{1}=1$的數字為$v_{1},v_{2},v_{3},...,v_{n}$
剛剛我們知道了,$s'=\{v_{1}\oplus v_{2},v_{2}\oplus v_{3},v_{3}\oplus v_{4},...,v_{n-1}\oplus v_{n}\}$恰可以代表所有選擇偶數個$bit_{1}=1$的數字的集合
那麼,把所有沒選到$v_{1}$的集合改成有選到$v_{1}$,選到$v_{1}$的集合改成沒選到$v_{1}$就好了!

因此,我們只要將$s$取代成$\{\{原本s裡面bit_{1}=0的數字\},修改v_{1}選擇狀態後的s'\}$,就可以繼續維護$(bit_{i}=K_{i},\forall 1\leq i\leq 2)$、$(bit_{i}=K_{i},\forall 1\leq i\leq 3)$...的數字集合!

問題來了,要怎麼修改$s'$中所有集合的$v_{1}$選擇狀態?
我們知道,同一個數字選兩次等於沒選
因此,我們就強迫多選一個數字$v_{1}$,實作上將$K\oplus v_{1}$就好了!(不過我是另外用一個變數$now$來儲存$K$的變化)

當發現需要$v_{1}$它卻不存在時,答案為$No$
否則如果算到最後一個$bit$仍然還沒出錯 (代表還是存在符合條件的數字選擇方案),答案為$Yes$

時間複雜度:$O(31N)$ (枚舉了$31$個$bit$)

code: