習(xí)題課(4)簡單計(jì)算.pdf

習(xí)題課 4 簡單計(jì)算 模擬 陳翀 cc net 12 04 2007 2 計(jì)算機(jī)解決問題的基本思想和方法 POJ 練習(xí)題分類 blem list htm 基本技能 基本輸入輸出 算術(shù)邏輯運(yùn)算 循環(huán) 數(shù)組 指針 函數(shù) 基本應(yīng)用 進(jìn)制轉(zhuǎn)換 字符串處理 時(shí)間和日期處理 高精度計(jì)算 數(shù)據(jù)結(jié)構(gòu) 鏈表 二叉樹 基本算法 簡單計(jì)算題 排序 枚舉 遞歸 計(jì)算機(jī)模擬 動(dòng)態(tài)規(guī)劃 3 概述 簡單計(jì)算題 棋盤走子步數(shù) 模擬 猴子選大王 約瑟夫問題 可模型化的問題 攔截導(dǎo)彈計(jì)數(shù) 基本技能 4 簡單計(jì)算題 基本過程包括 將一個(gè)用自然語言描述的實(shí)際問題抽象成一個(gè)計(jì) 算問題 給出計(jì)算過程 并編程實(shí)現(xiàn) 將計(jì)算結(jié)果還原成對原來問題的解答 關(guān)鍵是讀懂問題 搞清輸入和輸出數(shù)據(jù)的含義及給出的格式 通過輸入輸出樣例驗(yàn)證自己的理解是否正確 5 POJ 1657 Distance on Chessboard 國際象棋的棋盤是黑白相 間的8 8的方格 棋子放 在格子中間 如圖所示 王 后 車 象的走子規(guī) 則如下 王王 橫 直 斜都可以走 但每步限走一格 后后 橫 直 斜都可以走 每步格數(shù)不受限制 車車 橫 豎均可以走 不能 斜走 格數(shù)不限 象象 只能斜走 格數(shù)不限 6 POJ 1657 Distance on Chessboard cont 寫一個(gè)程序 給定起始位置和目標(biāo)位置 計(jì)算王 后 車 象從起始位置走到目標(biāo)位置所需的最少步數(shù) 寫一個(gè)程序 給定起始位置和目標(biāo)位置 計(jì)算王 后 車 象從起始位置走到目標(biāo)位置所需的最少步數(shù) Input 第一行是測試數(shù)據(jù)的組數(shù)第一行是測試數(shù)據(jù)的組數(shù)t 0 t 20 以下每行是 一組測試數(shù)據(jù) 每組包括棋盤上的兩個(gè)位置 第一個(gè)是起 始位置 第二個(gè)是目標(biāo)位置 位置用 以下每行是 一組測試數(shù)據(jù) 每組包括棋盤上的兩個(gè)位置 第一個(gè)是起 始位置 第二個(gè)是目標(biāo)位置 位置用 字母字母 數(shù)字?jǐn)?shù)字 的形式表 示 字母從 的形式表 示 字母從 a 到到 h 數(shù)字從 數(shù)字從 1 到到 8 Output 對輸入的每組測試數(shù)據(jù) 輸出王 后 車 象所需的最少 步數(shù) 如果無法到達(dá) 對輸入的每組測試數(shù)據(jù) 輸出王 后 車 象所需的最少 步數(shù) 如果無法到達(dá) 就輸出就輸出 Inf Sample Input 2 a1 c3 f5 f8 Sample Output 2 1 2 1 3 1 1 Inf 7 規(guī)則的解釋 王 后 車 象 y x y x 1 y x 2 y x 3 2 x y 0 31 x y 8 include include include using namespace std int main int n cin n string begin new string n end new string n for int i 0 i begin i end i for int i 0 i n i int x int y x abs begin i 0 end i 0 y abs begin i 1 end i 1 delete begin delete end POJ 1657 if x 0 else if x y cout y else cout x if x y x 0 y 0 cout 1 else cout 2 if x 0 y 0 cout 1 else cout 2 if abs x y 2 0 cout Inf endl else if x y cout 1 endl else cout 2 endl 9 include include include using namespace std int main int n cin n string begin end while n cin begin end int x int y x abs begin 0 end 0 y abs begin 1 end 1 POJ 1657 if x 0 else if x y cout y else cout x if x y x 0 y 0 cout 1 else cout 2 if x 0 y 0 cout 1 else cout 2 if abs x y 2 0 cout Inf endl else if x y cout 1 endl else cout 2 endl 10 本題心得 計(jì)算棋盤走子的步數(shù) 棋盤的性質(zhì) 子的規(guī) 則 兩種獲取參數(shù)的方法 第一種方法看起來簡 短 第二種方法輸入和處理的功能非常明確 11 POJ 2746 約瑟夫問題 Description 約瑟夫問題 有 只猴子 按順時(shí)針方向圍成一圈選大王 編號(hào)從 到 從第 號(hào)開始報(bào)數(shù) 一直數(shù)到 數(shù)到 的猴子退出圈外 剩下的猴 子再接著從 約瑟夫問題 有 只猴子 按順時(shí)針方向圍成一圈選大王 編號(hào)從 到 從第 號(hào)開始報(bào)數(shù) 一直數(shù)到 數(shù)到 的猴子退出圈外 剩下的猴 子再接著從1開始報(bào)數(shù) 就這樣 直到圈內(nèi)只剩下一只猴子時(shí) 這個(gè)猴子就是 猴王 編程求輸入 后 輸出最后猴王的編號(hào) 開始報(bào)數(shù) 就這樣 直到圈內(nèi)只剩下一只猴子時(shí) 這個(gè)猴子就是 猴王 編程求輸入 后 輸出最后猴王的編號(hào) Input 每行是用空格分開的兩個(gè)整數(shù) 第一個(gè)是每行是用空格分開的兩個(gè)整數(shù) 第一個(gè)是 n 第二個(gè)是第二個(gè)是 m 0 m n 300 最后一行是 最后一行是 0 0 Output 對于每行輸入數(shù)據(jù) 最后一行除外對于每行輸入數(shù)據(jù) 最后一行除外 輸出數(shù)據(jù)也是一行 即最后猴王的編號(hào) 輸出數(shù)據(jù)也是一行 即最后猴王的編號(hào) Sample Input 6 2 12 4 8 3 0 0 Sample Output 5 1 7 12 模擬題 現(xiàn)實(shí)中的有些問題 難以找到公式或規(guī)律 來進(jìn)行解決 只能按照一定步驟 不停地 做下去 最后才能得到答案 這樣的問題 用計(jì)算機(jī)來解決十分合適 只要讓計(jì)算機(jī)模擬人在解決問題的行為即 可 13 解題思路 N個(gè)元素 每數(shù)夠m個(gè)淘汰一個(gè) 之后還從1 開始重查 最終只留下1個(gè) 有循環(huán) 往復(fù)計(jì)數(shù)1到m 重復(fù)做上面的事 直到n為1 被淘汰的留著位置 標(biāo)記值 指到這里就跳過不計(jì) 終止條件 只剩一個(gè)元素 n Ptr 14 include using namespace std const int MAX NUM 300 int anLoop MAX NUM 10 int main int n m while 1 cin n m if n 0 break for int i 0 i for int i 0 i n i int nCounted 0 while nCounted m while anLoop nPtr 0 nPtr nPtr 1 n nCounted nPtr nPtr 1 n nPtr if nPtr 0 nPtr n 1 if i n 1 cout anLoop nPtr endl anLoop nPtr 0 指過無效元素指過無效元素 指過有效元素指過有效元素 查夠查夠m個(gè)元素個(gè)元素 15 POJ 2945 攔截導(dǎo)彈 某 國為了防御敵國的導(dǎo)彈襲擊 開發(fā)出一種導(dǎo)彈攔截系統(tǒng) 但是這種導(dǎo)彈攔 截系統(tǒng)有一個(gè)缺陷 雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度 但是以后每 一發(fā)炮彈都不能 高于前一發(fā)的高度 某天 雷達(dá)捕捉到敵國的導(dǎo)彈來襲 并 觀測到導(dǎo)彈依次飛來的高度 請計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈 攔截來 襲導(dǎo)彈時(shí) 必須按來襲導(dǎo)彈襲 擊的時(shí)間順序 不允許先攔截后面的導(dǎo)彈 再 攔截前面的導(dǎo)彈 某 國為了防御敵國的導(dǎo)彈襲擊 開發(fā)出一種導(dǎo)彈攔截系統(tǒng) 但是這種導(dǎo)彈攔 截系統(tǒng)有一個(gè)缺陷 雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度 但是以后每 一發(fā)炮彈都不能 高于前一發(fā)的高度 某天 雷達(dá)捕捉到敵國的導(dǎo)彈來襲 并 觀測到導(dǎo)彈依次飛來的高度 請計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈 攔截來 襲導(dǎo)彈時(shí) 必須按來襲導(dǎo)彈襲 擊的時(shí)間順序 不允許先攔截后面的導(dǎo)彈 再 攔截前面的導(dǎo)彈 Input 輸入有兩行 第一行 輸入雷達(dá)捕捉到的敵國導(dǎo)彈的數(shù)量 輸入有兩行 第一行 輸入雷達(dá)捕捉到的敵國導(dǎo)彈的數(shù)量k k a i 0 t a i 0 t 207 所以 所以b 1 b 0 1 2 a 2 155 207 155 所以 所以 b 2 max b 1 1 b 0 1 b 1 1 3 a 3 300 300 300 所以 所以b 3 b 0 1 2 a 4 299 300 299 所以 所以b 4 b 3 1 3 a 5 170 299 170 所以 所以b 5 b 4 1 4 a 6 158 170 158 所以 所以b 6 b 5 1 5 19 include using namespace std int main int k cin k int array array new int k for int i 0 i array i int b b new int k for int i 0 i k i b i 1 cout max endl delete array delete b 找到每個(gè)找到每個(gè)b i 的值的值 for int i 1 i k i for int t 0 t array i 選擇最大選擇最大 int max b 0 for int i 1 i max max b i 20 概述 簡單計(jì)算題 模擬 導(dǎo)彈問題 其他基本技能提要 兩種不同的getline用法 簡便實(shí)現(xiàn)itoa 的靈丹 stringstream 數(shù)組名和指針的區(qū)別 21 C Library Reference C Library Input Output Stream Library Strings Library Standard Template Library STL STL Containers STL Algorithms 22 1 getline兩種用法 getline 讀入字符串 stream類 讀入字符串 string類 23 istream getline include istream istream read a line of characters int MAX LENGTH 100 char line MAX LENGTH cin getline line MAX LENGTH 24 string class defines the global function getline include istream read data from an I O stream into a string string s getline cin s cout You entered s str string str getline cin str 26 Loop variable names 循環(huán)變量生命周期問題 新C 規(guī)范 出了for之外 局部變量i失效 for int i 0 i 4 i cin getline c i 80 for int i 0 i 4 i for int j 0 j 80 j 27 2 Do not use itoa C style code std stringstream ss std string str num ss str num include int main std stringstream ss std string s int i 21 ss s s 21 s 132 ss i i 132 C style code char buffer 255 sprintf buffer d 100 28 C String Streams Three main classes are available in stringstream allows input and output istringstream allows input only ostringstream allows output only 29 回憶講過的POJ 2880 page 21 of 句中最長的單詞 輸入一個(gè)英文句子 長度不超過 句中最長的單詞 輸入一個(gè)英文句子 長度不超過40個(gè)字符 編寫程序 輸 出句子中最長的一個(gè)單詞 個(gè)字符 編寫程序 輸 出句子中最長的一個(gè)單詞 Input 長度不超過 長度不超過40的字符串的字符串 Output 句中最長的單詞 句中最長的單詞 Sample Input This is a test sentence Sample Output sentence 1 輸入只有一個(gè)句子 不需使用輸入只有一個(gè)句子 不需使用while 2 若句尾有標(biāo)點(diǎn) 則標(biāo)點(diǎn)和最后一個(gè)單詞可看成是一個(gè)單 詞 可以不用作額外判斷 若句尾有標(biāo)點(diǎn) 則標(biāo)點(diǎn)和最后一個(gè)單詞可看成是一個(gè)單 詞 可以不用作額外判斷 3 假設(shè)句中最長的單詞只有一個(gè)假設(shè)句中最長的單詞只有一個(gè) 30 include include include using namespace std int main string s w re int big 0 getline cin s string類的類的getline用法 從流中讀到用法 從流中讀到s istringstream stream s istringstream型變量初始化用型變量初始化用string while stream w istringstream型變量可輸出到型變量可輸出到string if w size big 注意不是全部輸出 而是被空格分開注意不是全部輸出 而是被空格分開 big w size re w cout re endl POJ 2880 31 3 Array int main int ar