###### tags: `資訊科技概論` # 程式設計(使用C++、ZeroJudge) [銜接課程題單](https://hackmd.io/@cube/Hk1YqttAL) ## 零、評量方式 1. 上課基本練習 50% - 補交期限:上機考、期末作業解題報告前。 2. 作業解題數(ZJ共通過(AC)題數)&期中上機考 30% - 注意事項 * 作業可從每單元下方「淺黃色區塊」裏選,或任選其它題目都可。 * 不會的可以去參考網路上的程式碼、解法。 * 同學也可以互相討論,而且是鼓勵的。 * 不論如何,都要在了解解法後,不看別人的程式碼,自己親自寫一遍。 * 不要為了分數直接複製貼上別人的程式碼,那是無意義的行為,上機考你就會現出原形。 * 上機考時網路會斷線,沒有任何參考資料,請每個單元至少完成 3 題作業,熟練基本語法。 - 題數登記時間 * 四、迴圈教完後一週。(一~四單元作業累積共45題) - 成績計算方式 * 作業不批改,以上機考(教完後一週)檢核作業是否抄襲。 * **上機考不算分**,只是檢核抄襲用,並計算打折後作業成績。 * 上機考難度會低於作業,只要作業自已做,滿分是輕而易舉。 不做作業、複製貼上、投機取巧、不求甚解,零分是理所當然。 ```c 原始作業成績=min(題數*4,120) // 上限120 if(原始作業成績>=100) 作業成績=原始作業成績*(上機考成績/100) // 認真的同學可以有一點失誤的空間 // 原始作業120分,上機考100分,實得120分。 // 原始作業120分,上機考 80分,實得 96分。 else if(上機考成績>=原始作業成績) 作業成績=原始作業成績 // 老師承認你的作業是自己做的 // 原始作業 80分,上機考100分,實得 80分。 else if(上機考成績<原始作業成績) 作業成績=上機考成績 // 老師不承認你的作業是自己做的 // 原始作業 80分,上機考 40分,實得 40分。 // 原始作業 80分,上機考 0分,實得 0分。 ``` 3. 期末作業解題報告 20% - 上機考考差的同學請保握最後的機會。 - 10~12題。 * 每寫一題10分,上限120分(12題)。 * 期中考之前的舊範圍(四、迴圈之前),最多只能放3題。 * 其餘的必須是新範圍(五、陣列之後)新寫的題目,每個單元至多可放3題(不可以都寫同一單元的題目)。 - 每題的子標題為 (1) 單元、題號 (2) 解題動態、評分結果截圖 (3) 原始的解題思路(遇到的錯誤) (4) 錯誤程式碼 (5) 正確的解題思路(修正的地方) (6) 正確程式碼 - 檢核方式 * 請儘量放一開始有錯,然後修正的題目。如果你每一題都是一次AC,那你應該是骨骼清奇、萬中無一的練武奇才,應該不用怕老師的檢核吧。 * 如果老師懷疑你的程式是網路複製貼上,會請你當場重寫一次當做檢核,寫不出來作業直接作廢0分,所以作業請務必自己思考完成。 - 可放到學習歷程檔案。 4. 作業佔50%(AC題數+解題報告),不寫作業一定被當。 - 你可以這樣想像,如果上機考滿分,作業做1題就是總成績1分。請自我要求每週至少寫 2~3 題作業才是比較保險的做法。 - 不要考前才寫,初學程式會有很多錯誤,要花時間除錯。 - 中午電腦教室除考前1週外都開放,沒電腦、沒網路做作業的同學請善加利用。 - 如果對寫程式有興趣並要參加APCS檢定,下學期多元選修可以選修APCS(大學程式設計先修檢測)程式實作,挑選標準主要為ZJ的解題數(請寫在多元選修意向書裏)。 5. 學習歷程檔案之課程學習成果(Bonus) - [大學選才與高中育才輔助系統](https://collego.ceec.edu.tw/) - 最後一週上課結束前如果認證完成,學期總成績加分。 - 上傳的PDF大小限制為2MB,圖片如果太大,可用小畫家將解析度調小。 - HackMD筆記可下載成HTML(選單/下載 / HTML),再以[PDF24 Tools](https://tools.pdf24.org/zh/)轉成PDF。如果要將PDF插入到Word中,可用同一網站將PDF轉圖像再插入。 - [教授觀點](https://drive.google.com/file/d/1jdixJ5WfXijHrPptBT2WxKcMvLQIxcFU/view?usp=sharing) 6. [TOI線上練習賽](https://toi-reg.csie.ntnu.edu.tw/)(Bonus:分數/100直接加在總成績) - 上學期10、11、12月,下學期3、4、5月,最後一週。 - 星期一08:00 ~ 星期五20:00。 - 90分鐘。 - 教師代碼:12 - [證書](https://drive.google.com/open?id=1DcgDKn1R33kOPc_HazdIyQDgyYxSCPlZ)。 7. 基礎教學網站 - [基礎程式設計 - C與C++簡報、影片](http://www.18dice.tw/diceweb/teacherstudy/CandC++.html) 8. [SoloLearn C++ Tutorial](https://www.sololearn.com/) - 每一課*2,最高92分。 * Basic Concepts(1~11) * Conditionals and Loops(1~10) * Data Types, Arrays, Pointers(1~14) * Functions(1~11) - 此單元完成得8分。 * Classes and Objects(1~8) - 全部學完可拿到[證書](https://i.imgur.com/0yAAPlB.jpg)(額外加分)。 ## 一、基本使用 ### 1. 軟體 + [Code::Blocks](http://cs.cysh.cy.edu.tw/software/software_download.html) + [Dev-C++](http://cs.cysh.cy.edu.tw/software/software_download.html) + [VSCode](https://hackmd.io/@liaojason2/vscodecppwindows )([無法debug處理](https://stackoverflow.com/questions/37405975/c-for-vs-code-unable-to-start-debugging-program-path-is-missing-or-invalid?fbclid=IwAR1QQOzXkI6LQc2n0L3q0Sywp_Fx92igG83ngDbhLJrMdZXvaFEqtOW04hM)) + [GDB online Debugger | Compiler - Code, Compile, Run, Debug online C, C++](https://www.onlinegdb.com/) + [The collaborative browser based IDE - Replit](https://replit.com/) ### 2. 基本輸出與輸入 :::info EX_1_1:[d483: hello, world](https://zerojudge.tw/ShowProblem?problemid=d483) + 快速鍵:Ctrl+滾輪,F9,Ctrl+a,Ctrl+c,Ctrl+v,F2,F5 + 只能上傳一次,要重新上傳,請在檔名後加版本編號。 ::: :::info EX_1_2:[a001: 哈囉](https://zerojudge.tw/ShowProblem?problemid=a001) ``` c int main() { // 變數宣告 while(cin >> ...) //不需要加「;」 { cout << ... } return 0; } ``` + 所有程式都要寫在main裏,班級-座號-題號.cpp 只是要交的檔案,不要在裏面寫程式。 + 快速鍵:Shift+↑、↓、←、→、Home、End,Ctrl+x + 執行完的測試視窗要關閉,才能再次執行。 ::: ### 2. 變數型態 | 常用型態 | 意義 | 範圍 | |:-------|:---------- |:-------| | int | 整數 |-2147483648~2147483647|| | long long int | 長整數 |-2^63^ ~ 2^63^-1|| | float | 單精度浮點數(小數) |±1.5x10^−45^ ~ ±3.4x10^38^| | double | 雙精度浮點數(小數) |±5.0×10^−324^ ~ ±1.7×10^308^| | char | 字元 | 'A'| | string | 字串 | "Hello"| | bool | 布林 | true、false| ### 3. 變數宣告 ``` c int math=80; // 資料型態 變數名稱; double pi=3.14159265359; // 資料型態 變數名稱=初值; int sum,ave,rank; // 資料型態 變數名稱1,變數名稱2,變數名稱3...; ``` :::info EX_1_3:[a002: 簡易加法](https://zerojudge.tw/ShowProblem?problemid=a002) + cin >> a,b; 是錯誤的語法。 + 再開一個專案(homework)寫作業。 ::: :::info EX_1_4:[d489: 伏林的三角地](https://zerojudge.tw/ShowProblem?problemid=d489) + 以[海龍公式](http://www2.chsh.chc.edu.tw/bee/1050206/heron%20formula.pdf)求三角形面積。 + 「*」不可省略。 + 先乘除後加減,可用小括號改變運算順序。 + // 註解 + 需除錯時,可將變數印出來看。 ::: :::warning [d049: 中華民國萬歲!](https://zerojudge.tw/ShowProblem?problemid=d049) ::: :::warning [a861: 1. Secure the Perimeter](https://zerojudge.tw/ShowProblem?problemid=a861) ::: :::warning [c379: 成為出題者](https://zerojudge.tw/ShowProblem?problemid=c379) ::: :::warning [d461: 班際籃球賽](https://zerojudge.tw/ShowProblem?problemid=d461) ::: :::warning [d053: 10970 - Big Chocolate](https://zerojudge.tw/ShowProblem?problemid=d053) ::: ## 二、運算式與運算子 ### 1. 算數運算子 | 算數運算子 | 意義 | 備註| |:-------- |:------ |:-------| | + | 加 | | | - | 減 | | | * | 乘 | | | / | 除 | | | % | 取餘數 | | | ++ | 遞增 | i++ 即 i=i+1| | \-\- | 遞減 | i\-\- 即 i=i-1| :::info EX_2_1:[d050: 妳那裡現在幾點了?](https://zerojudge.tw/ShowProblem?problemid=d050) + % ::: :::info EX_2_2:[d485: 我愛偶數](https://zerojudge.tw/ShowProblem?problemid=d485) + 複合指定運算子(a=a+5 → a+=5) ::: :::info EX_2_3:[d051: 糟糕,我發燒了!](https://zerojudge.tw/ShowProblem?problemid=d051) + (f-32)*5/9 + 整數除法、浮點數除法:5/2、5.0/2。 + 型態轉換(double)。 + C++小數點位數控制。 ``` c #include <iomanip> cout << fixed << setprecision(3); // setprecision(n) 會將輸出的數值控制為 n 位數,如果加上 fixed 表示只控制小數點以下的位數。 ``` ::: :::warning [d073: 分組報告](https://zerojudge.tw/ShowProblem?problemid=d073) + / 整數除法 ::: :::warning [d827: 買鉛筆](https://zerojudge.tw/ShowProblem?problemid=d827) + % ::: :::warning [b757: 頸美椰子樹](https://zerojudge.tw/ShowProblem?problemid=b757) + double + / ::: :::warning [a862: 2. My Dear Friend VIR](https://zerojudge.tw/ShowProblem?problemid=a862) + double + / + C++小數點位數控制。 ::: :::warning [f651: 開關燈](https://zerojudge.tw/ShowProblem?problemid=f651) + / 整數除法 + 觀察n=1~10,找規律。類似d073。 ::: ### 2. 關係運算子 | 關係運算子 | 意義 | 備註| |:-------- |:------ |:-------| | == | 等於 | =是指派,==是判斷是否相等 | | != | 不等於 | | > | 大於 | | >= | 大於等於 | | < | 小於 | | <= | 小於等於 | :mega: a > b > c 要寫成 a > b && b > c ### 3. 邏輯運算子 | 邏輯運算子 | 意義 | 備註| |:-------- |:------ |:-------| | && | and | | \|\| | or | | ! | not | :::info EX_2_4:[d063: 0 與 1](https://zerojudge.tw/ShowProblem?problemid=d063) + ! ::: :::info EX_2_5:[e343: BMI 計算](https://zerojudge.tw/ShowProblem?problemid=e343) + 運算式中沒有中、大括號,通通都用小括號。 + 型態轉換。 + C++小數點位數控制。 + 需除錯時,可將變數印出來看。 ::: ## 三、條件式 ### 1. if 條件式語法 ``` c if(條件) { 條件「成立」時的程式碼 } ``` :mega: if()後不能加「;」 :::info EX_3_1:[a012: 10055 - Hashmat the Brave Warrior](https://zerojudge.tw/ShowProblem?problemid=a012) + long long ::: :::warning [a799: 正值國](https://zerojudge.tw/ShowProblem?problemid=a799) ::: :::warning [d068: 該減肥了!](https://zerojudge.tw/ShowProblem?problemid=d068) ::: :::warning [b682: 2. 同學早安](https://zerojudge.tw/ShowProblem?problemid=b682) + [提示](https://zerojudge.tw/ShowThread?postid=16450&reply=0) + 將時間全部轉成分鐘會比較好做,分鐘的時間差以/、%轉回小時、分。 + 因為校長最久只會站23小時59分,所以如果開始時間大於結束時間,表示站隔夜,結束時間要多加1440。 ::: ### 2. if~else 語法: ``` c if(條件) { 條件「成立」時的程式碼 } else { 條件「不成立」時的程式碼 } ``` :mega: 養成縮排的好習慣:大括號 { } 內的程式碼以Tab鍵向右縮排,可以增加程式碼的可讀性,並方便除錯。 :::info EX_3_2:[d064: ㄑㄧˊ 數?](https://zerojudge.tw/ShowProblem?problemid=d064) ::: :mega: 如果測資的第一行有一個整數t,代表測試的筆數,要用以下的寫法。 ```cpp= cin >> t; while(t>0) { .... t--; } 或 cin >> t; while(t--) { .... } ``` :mega: [常用運算子的優先順序](https://magicjackting.pixnet.net/blog/post/70902861) :::info EX_3_3:[d066: 上學去吧!](https://zerojudge.tw/ShowProblem?problemid=d066) + 7點半以後寫 h>=7 && m>=30,幾點會造成錯誤? + 8<=h<17 → h>=8 && h<17 + &&、|| ::: :::warning [b877: 我是電視迷](https://zerojudge.tw/ShowProblem?problemid=b877) ::: :::warning [f373: 週年慶 Anniversary](https://zerojudge.tw/ShowProblem?problemid=f373) + 題目簡述 - 天天百貨(編號0)消費滿2000折200,琪琪百貨(編號1)消費滿1000折100。 - 輸入一正整數 N (0 ≦ N ≦ 10000),代表預計花費的金額,請問去那個百貨可以得到最好的優惠(如果優惠後的價格一樣,預設去天天百貨)。 - 輸出折扣後的金額以及百貨的編號。 + 分別計算兩百貨折扣後的金額,比較大小輸出。 ::: :::warning [e948: 1. 基礎代謝率 (BMR Calculation)](https://zerojudge.tw/ShowProblem?problemid=e948) + 輸入的第一行有一個整數n,代表測試筆數。while(n--) // 兩個減號,[寫法參考](https://yuihuang.com/zj-e948/) + C++小數點位數控制。 ``` c #include <iomanip> cout << fixed << setprecision(2); ``` ::: :::warning [f043: 1. 小豪的回家作業 (Homework)](https://zerojudge.tw/ShowProblem?problemid=f043) + 給定兩整數R、A,求出A+B=R的B值後輸出。 + 如果R=A,則先將A-3再求B。 + A、B小的寫在算式的前面。 ::: ### 3. 巢狀 if 語法 ``` c if(條件1) { if(條件2) { 條件1「成立」,且條件2「成立」時的程式碼 } else { 條件1「成立」,且條件2「不成立」時的程式碼 } } else { 條件1「不成立」時程式碼 } ``` :mega: if或else的大括號{ }內,都可再增加條件式。 :::info EX_3_4:[d058: BASIC 的 SGN 函數](https://zerojudge.tw/ShowProblem?problemid=d058) + if(n>0) vs. if(n>=0) ::: :::info EX_3_5:[a006: 一元二次方程式](https://zerojudge.tw/ShowProblem?problemid=a006) + 開根號用sqrt(),需含入 cmath 標頭檔。 + d=0時,x1還是要計算過程。執行時,不會去執行不符合條件的程式碼。 + F8除錯示範。 + Q:x1、x2放在d後面計算可以嗎? ::: :::warning [a003: 兩光法師占卜術](https://zerojudge.tw/ShowProblem?problemid=a003) ::: :::warning [d065: 三人行必有我師](https://zerojudge.tw/ShowProblem?problemid=d065) ::: :::warning [b899: 2. 物品探測](https://zerojudge.tw/ShowProblem?problemid=b899) + 分別計算三點間的距離,最長的為正方形的對角線。 + 正方形四點 A、B、C、D,假設 A、C 為對角,則 D = A + C - B。 ::: ### 4. 多重選擇 if~else if~else 語法 ``` c if(條件1) { 條件1「成立」時程式碼區塊 } else if(條件2) { 條件1「不成立」,且條件2「成立」時的程式碼 } else if(條件3) { 條件1、2「不成立」,且條件3「成立」時的程式碼 } .... else { 上述條件都「不成立」時的程式碼 } ``` :mega: else if()可視需要增加。 :::info EX_3_6:[d460: 山六九之旅](https://zerojudge.tw/ShowProblem?problemid=d460) ::: :::warning [f337: 同樂會 (Party)](https://zerojudge.tw/ShowProblem?problemid=f337) ::: :::warning [c382: 加減乘除](https://zerojudge.tw/ShowProblem?problemid=c382) + 要宣告一個字元變數(char)讀「+ - * /」,比較時,字元前後要有單引號。 ::: :::warning [b676: 63萬勞工苦輪班不像人像機器](https://zerojudge.tw/ShowProblem?problemid=b676) ::: :::warning [a053: Sagit's 計分程式](https://zerojudge.tw/ShowProblem?problemid=a053) ::: :::warning [a244: 新手訓練 ~ for + if](https://zerojudge.tw/ShowProblem?problemid=a244) + long long + while(n--) ::: :::warning [e972: 1. 貨幣轉換 (Currency)](https://zerojudge.tw/ShowProblem?problemid=e972) + 先將預算轉成目的地的幣值。 + 依「預算<花費」,「預算-花費<0.05」(0.00以字串列印->"0.00"),「預算>花費」,分則輸出。 + C++小數點位數控制。 ``` c #include <iomanip> cout << fixed << setprecision(2) << money-m; ``` ::: ## 四、迴圈 ### 1. for 迴圈語法 ``` c for(變數初值;條件判斷;改變量) { 程式碼 } ``` :mega: 除錯練習 (1) Build and run (F9)後發現錯誤 (2) 設中斷點 (3) Debug (F8) (4) Debugging windows/Watches (5) Next line (F7) (6) Stop debugger :::info EX_4_1:[d498: 我不說髒話](https://zerojudge.tw/ShowProblem?problemid=d498) Q1:如果改變量寫i+1,會發生什麼事,練習除錯(F8)。 + i=i+1 或 i+=1 或 i++ + i+1不會改到i Q2:n輸入10,以除錯(F8)看流程,當n=10時,下一行會往上或往下執行?i 最後的值為? Q3:n=10時,i+=3(i=i+3),會印出幾次字串, i 最後的值為? ::: :::info EX_4_2:[d490: 我也愛偶數](https://zerojudge.tw/ShowProblem?problemid=d490) Q1:先完成a+...+b,但答案會錯誤? + 先將 i、sum 印出來看,或除錯(F8)。 + 初值歸零 Q2:初值歸零後,第2次答案會錯誤? + 變數範圍:int sum=0; // 宣告在while迴圈內 + 區塊變數:for(int i=a;) ::: :::warning [b970: 我不說髒話 (續)](https://zerojudge.tw/ShowProblem?problemid=b970) ::: :::warning [d046: 文文採西瓜](https://zerojudge.tw/ShowProblem?problemid=d046) ::: :::warning [d786: 三、平均值](https://zerojudge.tw/ShowProblem?problemid=d786) + 每筆測資sum要歸零。 ::: :::warning [c005: 10300 - Ecological Premium ](https://zerojudge.tw/ShowProblem?problemid=c005) + long long + 運算式可先化簡避免除法誤差。 ::: :::warning [f708: 蟲蟲危機 (Insect)](https://zerojudge.tw/ShowProblem?problemid=f708) + 題目簡述 - 第一行有整數 M 和 N (1 ≤ M ≤ 2000, 1 ≤ N ≤ 2000) 代表螞蟻和蚱蜢的總數 - 第二行有 M 個數字表示螞蟻的身高 Ai (1 ≤ Ai ≤ 1000, 1 ≤ i ≤M) - 第三行有 N 個數字表示蚱蜢的身高 Gi (1 ≤ Gi ≤ 1000, 1 ≤ i ≤ N) - 若螞蟻的數量比蚱蜢多且螞蟻的總身高比蚱蜢高,螞蟻們才敢決定跟蚱蜢打一架爭,輸出 Yes,否則輸出 No。 ::: :::warning [f338: 后羿射日(Archer)](https://zerojudge.tw/ShowProblem?problemid=f338) ::: :::warning [f312: 1.人力分配](https://zerojudge.tw/ShowProblem?problemid=f312) + 以for迴圈窮舉所有可能的工人分配方法。 + 求最大值可用max函式或if。 ::: :::warning [f605: 1. 購買力](https://zerojudge.tw/ShowProblem?problemid=f605) + 找出3物品最大值和最小值,可使用if或max、min函式。 + max 若要傳入三個以上的參數,須用大括號包住,並含入 algorithm 標頭檔。 ::: :::warning [c299: 1. 連號或不連號](https://zerojudge.tw/ShowProblem?problemid=c299) + 輸入數列時,找出其最大值和最小值,可使用if或max、min函式。 + 最大-最小+1==n,表示這個數列是連續的。 ::: :::warning [d660: 11764 - Jumping Mario](https://zerojudge.tw/ShowProblem?problemid=d660) + prev=now ::: ### 2. 巢狀迴圈語法 ``` c for(變數1初值;條件1判斷;改變量) { for(變數2初值;條件2判斷;改變量) { 程式碼 } } Q:在日常生活中,有什麼事像巢狀迴圈的概念? ``` :::info EX_4_3:[c418: Bert的三角形 (1)](https://zerojudge.tw/ShowProblem?problemid=c418) ::: :::info EX_4_4:[c419: Bert的三角形 (2)](https://zerojudge.tw/ShowProblem?problemid=c419) + 除錯練習:內圈若寫j--會如何? ::: :::warning [c420: Bert的三角形 (3)](https://zerojudge.tw/ShowProblem?problemid=c420) ::: :::warning [f063: The Strongest Chain](https://zerojudge.tw/ShowProblem?problemid=f063) + 巢狀迴圈。 + 求每條鏈子最小值中,找出最大值。 ::: :::warning [c013: 00488-Triangle Wave](https://zerojudge.tw/ShowProblem?problemid=c013) + 巢狀迴圈。 + 下半部 for(k=A-1;k>0;k\-\-) ::: ### 3. while 迴圈語法 ``` c while(條件判斷) // 條件為「真」的時候繼續執行 { 程式碼 } ``` ``` c= for(int i=1;i<=5;i++) { cout << "hello "; } cout << endl; int i=1; while(i<=5) { cout << "hello "; i++; } ``` :::info EX_4_5:[d189: 11150 - Cola](https://zerojudge.tw/ShowProblem?problemid=d189) + 請用while模擬換瓶過程,不可以直接套公式。 + 以除錯(F8)看換瓶過程。 + 先借瓶?或最後剩2空瓶才借瓶? ::: :::info EX_4_6:[a038: 數字翻轉](https://zerojudge.tw/ShowProblem?problemid=a038) + 前面有 0 的話應消除。如50200 不是輸出 00205,而是205。 + 0要輸出0。為何會TLE?除錯(F8)練習。 + 迴圈中斷 - break:強制跳出「整個」迴圈。 - continue:強制跳出「此次」 迴圈,繼續進入下一次圈。 ``` c== for(int i=1;i<=10;i++) { if(i==5) { break; // continue; } cout << i << " "; } ``` ::: :::warning [c079: 10346 - Peter's Smokes](https://zerojudge.tw/ShowProblem?problemid=c079) ::: :::warning [d570: 神龍見首不見尾](https://zerojudge.tw/ShowProblem?problemid=d570) ::: :::warning [f070: 1. 韓信點兵 (HanXin)](https://zerojudge.tw/ShowProblem?problemid=f070) + 因為答案很小,暴力解即可。 + while(true),從1開始測,輸出符合條件的值。 ::: :::warning [c350: “綠白黃” 四校聯課](https://zerojudge.tw/ShowProblem?problemid=c350) + ans+=(n/k)*w; // 每次新換的電話號碼 + n-=(n/k)*(k-w); // 因為 k > w,所以可以看成每一次的交換(k換w),新號碼會減少 (k-w) 個。 ::: ### 4. do..while 迴圈語法 ``` c do { 程式碼 }while(條件判斷); // 條件為「真」的時候繼續執行 ``` :mega: do while()後要加分號! :::info EX_4_7:[d356: NOIP2002 1.级数求和](https://zerojudge.tw/ShowProblem?problemid=d356) + 型別轉換。 + 浮點數誤差(float->double)。 + cout << --i << endl; ``` c int a=1,b; b=a++; b=++a; cout << a << " " << b << endl; ``` ::: :::info EX_4_8:[a149: 乘乘樂](https://zerojudge.tw/ShowProblem?problemid=a149) + mul*=n%10 vs. mul=mul*n%10 (錯誤) + [常用運算子的優先順序](https://magicjackting.pixnet.net/blog/post/70902861) + 以while迴圈改寫會發生什麼錯誤? ::: :::warning [a215: 明明愛數數](https://zerojudge.tw/ShowProblem?problemid=a215) ::: :::warning [c561: Bert 愛搗蛋](https://zerojudge.tw/ShowProblem?problemid=c561) + 將數字反轉,記錄最大值。 + 將數值反轉的方法,假設 a為原數值,rvs為反轉後的數值(預設值為 0) rvs=rvs*10+(a%10); a/=10; // 讓個位數消失 ::: :::warning [f374: 分組 Grouping](https://zerojudge.tw/ShowProblem?problemid=f374) ::: ## 五、陣列 ### 1. 陣列宣告 ``` c int a[5]; // 宣告一個大小為5的int陣列 a[0]=80; // 陣列的索引值由0開始 a[5]=90; // 錯誤,索引值0~4 int a[5]={1,3,5,7,9}; // 宣告陣列時設定初值 int a[5]={1}; // a[0]初值1,其餘預設為0 for(int i=0;i<5;i++) // 以 for 迴圈來控制陣列的 index cin >> a[i]; int a2d[4][2]; // 宣告二維陣列(多維陣列) int a2d[4][2]={{1,2},{3,4},{5,6},{7,8}}; Q:如何建立可以儲存班上期中考成績的2維陣列? // a2d[r][c]表示第 r 列,第 c 欄的值(類似英文書寫習慣) ``` :::info EX_5_1:[b127: 會議中心(Room)](https://zerojudge.tw/ShowProblem?problemid=b127) + [費式數列](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97) + 44->1134903170 + 45->1836311903 + int f[?]={0,1} vs. int f[?]={1,1} ::: :::info EX_5_2:[a693: 吞食天地](https://zerojudge.tw/ShowProblem?problemid=a693) + 每次都重算會TLE。 + [時間複雜度](https://jason-chen-1992.weebly.com/home/time-space-complexity) + [前綴和](https://www.youtube.com/watch?v=VfL7dzFkW30) + i=0時,food[i]=food[i-1]+t 會錯誤,所以改從index 1 開始放前綴和。 + [陣列宣告時,大小請直接指定為題目給的最大範圍,避免用變數。](https://openhome.cc/Gossip/CGossip/OneDimArray.html) ``` c int n; cin>>n; int food[n]; // 避免使用,編譯器不一定支援。 int food[100005]; ``` ::: :::info EX_5_3:[c067: 00591 - Box of Bricks](https://zerojudge.tw/ShowProblem?problemid=c067) + t=1要宣告在while迴圈外。 + for迴圈的計數變數來控制陣列存取的位置。 ``` c for(int i=0;i<n;i++) cin >> a[n]; // 錯誤 ``` ::: :::warning [f345: 新手練習題—陣列](https://zerojudge.tw/ShowProblem?problemid=f345) ::: :::warning [b138: NOIP2005 1.陶陶摘苹果](https://zerojudge.tw/ShowProblem?problemid=b138) ::: :::warning [f818: 物競天擇 (Survival)](https://zerojudge.tw/ShowProblem?problemid=f818) + 設一個變數存身高*體重的最小值,初值為1000005。 ::: :::warning [e339: 前綴和練習](https://zerojudge.tw/ShowProblem?problemid=e339) + 累加的數值會超過 int 上限。 + 若使用陣列記錄,小心不要出現b[-1]的狀況。 ::: :::warning [b558: 求數列第 n 項](https://zerojudge.tw/ShowProblem?problemid=b558) ::: :::warning [f442: 老鷹抓小雞 Eagle](https://zerojudge.tw/ShowProblem?problemid=f442) + 題目簡述 - 「老鷹抓小雞」的遊戲玩法為有一人是老鷹、一人是母雞、剩下的人為小雞(老鷹要抓小雞,母雞則要保護身後的小雞)。小雞被抓後會變成老鷹,老鷹則變成小雞(取代被抓小雞的位置)。 - 第一列有一正整數 N,代表有 N 隻小雞。 - 第二列有 N 個正整數,代表小雞的編號。 - 第三列有一正整數 E,代表老鷹的編號。 - 第四列有一正整數 Q,代表玩了 Q 回合。 - 第五列有 Q 個正整數,代表每回合被抓到小雞的編號。 - 輸出經過 Q 回合後,隊伍中小雞的編號。 ::: :::warning [b139: NOIP2005 2.校门外的树](https://zerojudge.tw/ShowProblem?problemid=b139) + 可以宣告一個整數陣列tree(預設為0),陣列的索引值代表位置,陣列值0、1表示有沒有樹。 ::: :::warning [a253: 王老先生的磨菇田](https://zerojudge.tw/ShowProblem?problemid=a253) + 因為蘑菇編號只介於0~100間,因此可以開一個大小為101的陣列(初始值皆為0),陣列的索引值代表蘑菇編號,儲存對應編號的蘑菇數量。 ::: :::warning [b374: [福州19中]众数](https://zerojudge.tw/ShowProblem?problemid=b374) + [想法參考](https://zerojudge.tw/ShowThread?postid=16300&reply=0) ::: :::warning [c199: 爬山去(Hiking)-TOI練習賽y7m5-1](https://zerojudge.tw/ShowProblem?problemid=c199) + 輸入時可先將重覆的數字去掉。 ::: ### 2. 二維陣列 :::info EX_5_4:[a694: 吞食天地二](https://zerojudge.tw/ShowProblem?problemid=a694) + [如何以a693的方式加速?](https://sites.google.com/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/a694-tun-shi-tian-de-er) |[0][0] |[0][1]|[0][2] |[0][3] |[0][4]|[0][5] | |:----: |:----:|:----: |:----: |:----:|:----: | |**[1][0]**| | | | | | |**[2][0]**| |[r1-1][c1-1]| | |[r1-1][c2]| |**[3][0]**| | |[r1][c1]| | | |**[4][0]**| | | | | | |**[5][0]**| |[r2][c1-1] | | |[r2][c2] | + 陣列初值設為0 ``` c #include <cstring> memset(a,0,sizeof(a)); ``` + [C++ IO加速](http://chino.taipei/note-2016-0311C-的輸出入cin-cout和scanf-printf誰比較快?/) ``` c ios::sync_with_stdio(false); cin.tie(0); ``` ::: :::info EX_5_5:[e798: p5. 卷積神經網路](https://zerojudge.tw/ShowProblem?problemid=e798) + 求最大值可用max函式或if。 + max 若要傳入三個以上的參數,須用大括號包住([initializer_list](https://blog.csdn.net/ko_tin/article/details/68190364)),並含入 algorithm 標頭檔。 ::: :::warning [b367: 翻轉世界](https://zerojudge.tw/ShowProblem?problemid=b367) + 假設 a180 為 a 轉 180 度後的陣列,a[i][j] 轉180度後會放在 a180[r-i-1][c-j-1]; ::: :::warning [f513: 舉旗遊戲 (Flag)](https://zerojudge.tw/ShowProblem?problemid=f513) + 題目簡述 - 第一列有兩正整數 R、C(3 ≦ R、C ≦ 100),表示有 R×C 個人排成 R 列 C 行。 - 接著輸入 R 列,每列有 C 個正整數(1或2),代表每個人旗子的編號。 - 如果某人周遭的八個人,旗子的編號跟他都不一樣,則該人就被淘汰。請問有多少人會被淘汰? + 陣列行、列可多開一個空間,index 0不要用,以免有些點的相鄰點會超出陣列。 + 如果自己的顏色和相鄰 8 點都不同,則淘汰人數+1。 ``` c if(a[i][j]!=a[i-1][j-1] && a[i][j]!=a[i-1][j] && a[i][j]!=a[i-1][j+1] && a[i][j]!=a[i][j-1] && ...) // 左上、上、右上、左 cnt++; ``` ::: :::warning [e911: 108 p5. 收入分析](https://zerojudge.tw/ShowProblem?problemid=e911) + 請注意x,y的定義和a694不同。 ::: :::warning [f162: 4. 獵人與斯芬克斯](https://zerojudge.tw/ShowProblem?problemid=f162) + 同 a694 的方法,計算(i,j)前的每個點(r,c)到(i,j)的重量和,判斷是否<=k,如果是,取最大值。 + 不需 while(cin >> K) ::: :::warning [f737: 農地 (Farmland)](https://zerojudge.tw/ShowProblem?problemid=f737) + 類似 a694 的方法,以前綴和的方式計算(1,1)到每個點的總成本,-1不能開墾,可以將其值設為比開墾總預算大的值。 + 針對每個點,窮舉計算所有邊長的正方形農地的成本和。 + 因為只要知道最大的開墾面積,所以每次計算可從目前最大邊長+1開始即可。如果點座標+邊長超出邊界,或成本和 > 總預算,則之後的邊長都不用再檢查。 + C++ IO加速。 + [解題參考](https://toi-reg.csie.ntnu.edu.tw/wp-content/uploads/question/202103/Farmland.odp) ::: :::warning [a867: 7. Minelayer](https://zerojudge.tw/ShowProblem?problemid=a867) + 可以從index 1 開始放,想像盤面最外圍包了一圈0,例如3x5的盤面: 0000000 0●●\*●\*0 0\*\*●●●0 0●\*\*●●0 0000000 + 宣告2維的字元陣列 char mine[17][32]={0}; int cnt[16][31]={0}; + 不需最外層的while() ::: :::warning [f148: 2. 定向越野 (Orienteering)](https://zerojudge.tw/ShowProblem?problemid=f148) + 可以宣告一個 arr[26][3] 的2維陣列,初值均為 0。 - 26 表示有 26 個字母,a 對應到index 0、b 對應到index 1 … - arr[ ][0]存字母是否存在,arr[ ][1]存列座標,arr[ ][2]存欄座標。 - 例如讀到 'a' 位於(0,2) arr[c-'a'][0]=1; arr[c-'a'][1]=0; arr[c-'a'][2]=2; + 當讀取的地圖字元不是'0' 時,標記此字元存在,記錄其座標,並累計目標數量。 + 如果目標數量<N,輸出"Mission fail."。否則從陣列 0 開始判斷該位子對應的字元是否存在,如果存在則輸出座標,直到滿 N 個目標。 ::: ## 六、字串 ### 1. 字串宣告 ``` c int a[3]={1,2,3}; cout << a; // 陣列名稱為陣列開始的位址 char c='x'; // 宣告字元 cout << c; cout << (int)c; // ASCII char s1[4]={'a','b','c','\0'}; // 字元陣列,宣告長度為3的字串要多一個空間用來儲存空字元'\0'作為結束符號 cout << s1; string s2="abc"; // 宣告string類別的字串 cout << s2; cout << s2[1]; ``` ### 2. 字串相關操作 [演算法筆記](https://archive.is/u1lQL) :::info EX_6_1:[b428: 凱薩加密](https://zerojudge.tw/ShowProblem?problemid=b428) Q:可以寫b[1]-a[1]嗎? ::: :::info EX_6_2:[d235: Q10929:You can say 11](https://zerojudge.tw/ShowProblem?problemid=d235) + 11的倍數判別法:奇數位數字和與偶數位數字和相差為11的倍數。 + 字串長度:n.size() 或 n.length() + 取絕對值函式:abs() + [1~13的倍數判別法](https://leestar2013.pixnet.net/blog/post/45638266) ::: :::info EX_6_3:[c276: 沒有手機的下課時間](https://zerojudge.tw/ShowProblem?problemid=c276) ::: :::warning [a009: 解碼器](https://zerojudge.tw/ShowProblem?problemid=a009) ::: :::warning [a065: 提款卡密碼](https://zerojudge.tw/ShowProblem?problemid=a065) ::: :::warning [d124: 3的倍数](https://zerojudge.tw/ShowProblem?problemid=d124) + 3的倍數判別法:各個數字和為3的倍數。 ::: :::warning [a882: B. 我灰灰的橡皮鴨是個恐怖的危機](https://zerojudge.tw/ShowProblem?problemid=a882) ::: :::warning [b516: 凱撒密碼-商競103](https://zerojudge.tw/ShowProblem?problemid=b516) ::: :::warning [e505: 12602 - Nice Licence Plates](https://zerojudge.tw/ShowProblem?problemid=e505) + 取絕對值函式:abs() ::: :::warning [f514: 拼字遊戲 (Spelling)](https://zerojudge.tw/ShowProblem?problemid=f514) + 找到後將S中的字元換成空白,避免下次被找到。 ::: ## 七、函式 ### 1. 自定函式宣告語法 ``` c 回傳值的型態 函式名稱(變數型態 參數1,變數型態 參數2,...) { 程式碼 return 回傳值或運算式; } ``` :::info EX_7_1:[a623: 3. Combination](https://zerojudge.tw/ShowProblem?problemid=a623) + 將n!寫成函式,在主程式呼叫3次。 + $C(n,k)=\frac{n!}{(n-k)! * k!}$,例如C(4,2)=6。 ::: :::info EX_7_2:[d237: 質數合](https://zerojudge.tw/ShowProblem?problemid=d237) + 以質數函式測試是否需加此數。 + TLE如何解決 - long long sum=2; for(int i=3;i<=2000000;i+=2) - 如果一個數是合數,它的最小質因數會小於等於它的平方根。 - 因為成對出現的因數中,一個會≦√n,而另一個會≧√n。因此只要檢查≦√n中是否有n的因數即可。 - 開根號用sqrt(),需含入 cmath 標頭檔。 + 不可直接輸出142913828922(超過int)。 ::: :::warning [a121: 質數又來囉](https://zerojudge.tw/ShowProblem?problemid=a121) + 1不是質數。 ::: :::warning [ZeroJudge b112: 5. 高中運動會](https://zerojudge.tw/ShowProblem?problemid=b112)。 + 寫一函式求兩數的最大公因數(輾轉相除法)。 ::: ### 2. 傳值(call by value)、傳參考(call by reference) :::info EX_7_3:[d491: 我也愛偶數 (swap 版)](https://zerojudge.tw/ShowProblem?problemid=d491) + 將兩數交換寫成函式。 + [等差數列](https://zh.wikipedia.org/wiki/%E7%AD%89%E5%B7%AE%E6%95%B0%E5%88%97) + ((b-a)/2+1)/2*(a+b) 會錯誤,分子可能是奇數。 ::: ``` c= void swap(int ....a, int ....b) // void 表示沒有回傳值 { int t; ........ ........ ........ cout << "函式內:"<< a << " " << b << endl; } int main() { int a=1,b=2; cout << "交換前:" << a << " " << b << endl; swap(a,b); cout << "交換後:" << a << " " << b << endl; return 0; } ``` ### 3. 遞迴 :mega: 問題的答案,可從同類的子問題(規模更小)得到。 :mega: 在函式之中呼叫函式自己本身,要有終止條件,不然會無窮遞迴下去。 :::info EX_7_4:[95數學學測填充題G](http://cs.cysh.cy.edu.tw/computer_concept_108/高中數學遞迴.pdf) 用黑、白兩種顏色的正方形地磚依照如下的規律拼成若干圖形: ![](https://i.imgur.com/PrDcedl.jpg) 拼第95個圖需用到幾塊白色地磚。(478) ::: ``` c= int f(int n) { if ........ // if後只有一行,可省略{} ........ else return ........ } int main() { int n; while(cin >> n) cout << f(n) << endl; // 5->28 return 0; } ``` :::info EX_7_5:[a044: 空間切割](https://zerojudge.tw/ShowProblem?problemid=a044) + [直線分割平面](https://www.youtube.com/watch?v=wcvpvWxf-Kw)([音量加大](https://drive.google.com/file/d/1Q9SVLISto12WSs2IDO1QmR8H2jXkbZJm/view?usp=sharing)) - b~n~=b~n-1~+n,b~1~=2 + [平面分割空間](https://www.youtube.com/watch?v=Fjd6Oz_cgYY)([音量加大](https://drive.google.com/file/d/1OO7cEC107YjZHytpb-OiBIJNibs7TzTU/view?usp=sharing)) - c~n~=c~n-1~+b~n-1~,c~1~=2 ::: :::warning [e357: 遞迴函數練習](https://zerojudge.tw/ShowProblem?problemid=e357) ::: :::warning [c002: 10696 - f91](https://zerojudge.tw/ShowProblem?problemid=c002) ::: ## 八、其它 ### 1. [結構(struct)](https://kopu.chat/2017/05/30/c-%E8%AA%9E%E8%A8%80%EF%BC%9A%E7%B5%90%E6%A7%8B%EF%BC%88struct%EF%BC%89%E8%87%AA%E8%A8%82%E4%B8%8D%E5%90%8C%E8%B3%87%E6%96%99%E5%9E%8B%E6%85%8B%E7%B6%81%E4%B8%80%E8%B5%B7/) ``` c // 自訂的資料型別 struct 結構名稱 { 資料型別 變數1; 資料型別 變數2; ... }; ``` :mega: struct 定義的最後面要加分號! :::info EX_8_1:[c316: 最遠點對!前傳](https://zerojudge.tw/ShowProblem?problemid=c316) ::: :::warning [a130: 12015 - Google is Feeling Lucky](https://zerojudge.tw/ShowProblem?problemid=a130) ::: :::warning [d809: 黑暗土地](https://zerojudge.tw/ShowProblem?problemid=d809) + [以行列式算三角形面積](http://euler.tn.edu.tw/area.pdf),避免浮點數誤差。 + 取絕對值函式:abs() + 要印出面積時再/2.0。 :::