習題課(4)簡單計算.pdf

習題課 4 簡單計算 模擬 陳翀 cc net 12 04 2007 2 計算機解決問題的基本思想和方法 POJ 練習題分類 blem list htm 基本技能 基本輸入輸出 算術(shù)邏輯運算 循環(huán) 數(shù)組 指針 函數(shù) 基本應用 進制轉(zhuǎn)換 字符串處理 時間和日期處理 高精度計算 數(shù)據(jù)結(jié)構(gòu) 鏈表 二叉樹 基本算法 簡單計算題 排序 枚舉 遞歸 計算機模擬 動態(tài)規(guī)劃 3 概述 簡單計算題 棋盤走子步數(shù) 模擬 猴子選大王 約瑟夫問題 可模型化的問題 攔截導彈計數(shù) 基本技能 4 簡單計算題 基本過程包括 將一個用自然語言描述的實際問題抽象成一個計 算問題 給出計算過程 并編程實現(xiàn) 將計算結(jié)果還原成對原來問題的解答 關(guān)鍵是讀懂問題 搞清輸入和輸出數(shù)據(jù)的含義及給出的格式 通過輸入輸出樣例驗證自己的理解是否正確 5 POJ 1657 Distance on Chessboard 國際象棋的棋盤是黑白相 間的8 8的方格 棋子放 在格子中間 如圖所示 王 后 車 象的走子規(guī) 則如下 王王 橫 直 斜都可以走 但每步限走一格 后后 橫 直 斜都可以走 每步格數(shù)不受限制 車車 橫 豎均可以走 不能 斜走 格數(shù)不限 象象 只能斜走 格數(shù)不限 6 POJ 1657 Distance on Chessboard cont 寫一個程序 給定起始位置和目標位置 計算王 后 車 象從起始位置走到目標位置所需的最少步數(shù) 寫一個程序 給定起始位置和目標位置 計算王 后 車 象從起始位置走到目標位置所需的最少步數(shù) Input 第一行是測試數(shù)據(jù)的組數(shù)第一行是測試數(shù)據(jù)的組數(shù)t 0 t 20 以下每行是 一組測試數(shù)據(jù) 每組包括棋盤上的兩個位置 第一個是起 始位置 第二個是目標位置 位置用 以下每行是 一組測試數(shù)據(jù) 每組包括棋盤上的兩個位置 第一個是起 始位置 第二個是目標位置 位置用 字母字母 數(shù)字數(shù)字 的形式表 示 字母從 的形式表 示 字母從 a 到到 h 數(shù)字從 數(shù)字從 1 到到 8 Output 對輸入的每組測試數(shù)據(jù) 輸出王 后 車 象所需的最少 步數(shù) 如果無法到達 對輸入的每組測試數(shù)據(jù) 輸出王 后 車 象所需的最少 步數(shù) 如果無法到達 就輸出就輸出 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 本題心得 計算棋盤走子的步數(shù) 棋盤的性質(zhì) 子的規(guī) 則 兩種獲取參數(shù)的方法 第一種方法看起來簡 短 第二種方法輸入和處理的功能非常明確 11 POJ 2746 約瑟夫問題 Description 約瑟夫問題 有 只猴子 按順時針方向圍成一圈選大王 編號從 到 從第 號開始報數(shù) 一直數(shù)到 數(shù)到 的猴子退出圈外 剩下的猴 子再接著從 約瑟夫問題 有 只猴子 按順時針方向圍成一圈選大王 編號從 到 從第 號開始報數(shù) 一直數(shù)到 數(shù)到 的猴子退出圈外 剩下的猴 子再接著從1開始報數(shù) 就這樣 直到圈內(nèi)只剩下一只猴子時 這個猴子就是 猴王 編程求輸入 后 輸出最后猴王的編號 開始報數(shù) 就這樣 直到圈內(nèi)只剩下一只猴子時 這個猴子就是 猴王 編程求輸入 后 輸出最后猴王的編號 Input 每行是用空格分開的兩個整數(shù) 第一個是每行是用空格分開的兩個整數(shù) 第一個是 n 第二個是第二個是 m 0 m n 300 最后一行是 最后一行是 0 0 Output 對于每行輸入數(shù)據(jù) 最后一行除外對于每行輸入數(shù)據(jù) 最后一行除外 輸出數(shù)據(jù)也是一行 即最后猴王的編號 輸出數(shù)據(jù)也是一行 即最后猴王的編號 Sample Input 6 2 12 4 8 3 0 0 Sample Output 5 1 7 12 模擬題 現(xiàn)實中的有些問題 難以找到公式或規(guī)律 來進行解決 只能按照一定步驟 不停地 做下去 最后才能得到答案 這樣的問題 用計算機來解決十分合適 只要讓計算機模擬人在解決問題的行為即 可 13 解題思路 N個元素 每數(shù)夠m個淘汰一個 之后還從1 開始重查 最終只留下1個 有循環(huán) 往復計數(shù)1到m 重復做上面的事 直到n為1 被淘汰的留著位置 標記值 指到這里就跳過不計 終止條件 只剩一個元素 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個元素個元素 15 POJ 2945 攔截導彈 某 國為了防御敵國的導彈襲擊 開發(fā)出一種導彈攔截系統(tǒng) 但是這種導彈攔 截系統(tǒng)有一個缺陷 雖然它的第一發(fā)炮彈能夠到達任意的高度 但是以后每 一發(fā)炮彈都不能 高于前一發(fā)的高度 某天 雷達捕捉到敵國的導彈來襲 并 觀測到導彈依次飛來的高度 請計算這套系統(tǒng)最多能攔截多少導彈 攔截來 襲導彈時 必須按來襲導彈襲 擊的時間順序 不允許先攔截后面的導彈 再 攔截前面的導彈 某 國為了防御敵國的導彈襲擊 開發(fā)出一種導彈攔截系統(tǒng) 但是這種導彈攔 截系統(tǒng)有一個缺陷 雖然它的第一發(fā)炮彈能夠到達任意的高度 但是以后每 一發(fā)炮彈都不能 高于前一發(fā)的高度 某天 雷達捕捉到敵國的導彈來襲 并 觀測到導彈依次飛來的高度 請計算這套系統(tǒng)最多能攔截多少導彈 攔截來 襲導彈時 必須按來襲導彈襲 擊的時間順序 不允許先攔截后面的導彈 再 攔截前面的導彈 Input 輸入有兩行 第一行 輸入雷達捕捉到的敵國導彈的數(shù)量 輸入有兩行 第一行 輸入雷達捕捉到的敵國導彈的數(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 找到每個找到每個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 概述 簡單計算題 模擬 導彈問題 其他基本技能提要 兩種不同的getline用法 簡便實現(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 句中最長的單詞 輸入一個英文句子 長度不超過 句中最長的單詞 輸入一個英文句子 長度不超過40個字符 編寫程序 輸 出句子中最長的一個單詞 個字符 編寫程序 輸 出句子中最長的一個單詞 Input 長度不超過 長度不超過40的字符串的字符串 Output 句中最長的單詞 句中最長的單詞 Sample Input This is a test sentence Sample Output sentence 1 輸入只有一個句子 不需使用輸入只有一個句子 不需使用while 2 若句尾有標點 則標點和最后一個單詞可看成是一個單 詞 可以不用作額外判斷 若句尾有標點 則標點和最后一個單詞可看成是一個單 詞 可以不用作額外判斷 3 假設(shè)句中最長的單詞只有一個假設(shè)句中最長的單詞只有一個 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