习题课(4)简单计算.pdf

习题课 4 简单计算 模拟 陈翀 cc net 12 04 2007 2 计算机解决问题的基本思想和方法 POJ 练习题分类 blem list htm 基本技能 基本输入输出 算术逻辑运算 循环 数组 指针 函数 基本应用 进制转换 字符串处理 时间和日期处理 高精度计算 数据结构 链表 二叉树 基本算法 简单计算题 排序 枚举 递归 计算机模拟 动态规划 3 概述 简单计算题 棋盘走子步数 模拟 猴子选大王 约瑟夫问题 可模型化的问题 拦截导弹计数 基本技能 4 简单计算题 基本过程包括 将一个用自然语言描述的实际问题抽象成一个计 算问题 给出计算过程 并编程实现 将计算结果还原成对原来问题的解答 关键是读懂问题 搞清输入和输出数据的含义及给出的格式 通过输入输出样例验证自己的理解是否正确 5 POJ 1657 Distance on Chessboard 国际象棋的棋盘是黑白相 间的8 8的方格 棋子放 在格子中间 如图所示 王 后 车 象的走子规 则如下 王王 横 直 斜都可以走 但每步限走一格 后后 横 直 斜都可以走 每步格数不受限制 车车 横 竖均可以走 不能 斜走 格数不限 象象 只能斜走 格数不限 6 POJ 1657 Distance on Chessboard cont 写一个程序 给定起始位置和目标位置 计算王 后 车 象从起始位置走到目标位置所需的最少步数 写一个程序 给定起始位置和目标位置 计算王 后 车 象从起始位置走到目标位置所需的最少步数 Input 第一行是测试数据的组数第一行是测试数据的组数t 0 t 20 以下每行是 一组测试数据 每组包括棋盘上的两个位置 第一个是起 始位置 第二个是目标位置 位置用 以下每行是 一组测试数据 每组包括棋盘上的两个位置 第一个是起 始位置 第二个是目标位置 位置用 字母字母 数字数字 的形式表 示 字母从 的形式表 示 字母从 a 到到 h 数字从 数字从 1 到到 8 Output 对输入的每组测试数据 输出王 后 车 象所需的最少 步数 如果无法到达 对输入的每组测试数据 输出王 后 车 象所需的最少 步数 如果无法到达 就输出就输出 Inf Sample Input 2 a1 c3 f5 f8 Sample Output 2 1 2 1 3 1 1 Inf 7 规则的解释 王 后 车 象 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 本题心得 计算棋盘走子的步数 棋盘的性质 子的规 则 两种获取参数的方法 第一种方法看起来简 短 第二种方法输入和处理的功能非常明确 11 POJ 2746 约瑟夫问题 Description 约瑟夫问题 有 只猴子 按顺时针方向围成一圈选大王 编号从 到 从第 号开始报数 一直数到 数到 的猴子退出圈外 剩下的猴 子再接着从 约瑟夫问题 有 只猴子 按顺时针方向围成一圈选大王 编号从 到 从第 号开始报数 一直数到 数到 的猴子退出圈外 剩下的猴 子再接着从1开始报数 就这样 直到圈内只剩下一只猴子时 这个猴子就是 猴王 编程求输入 后 输出最后猴王的编号 开始报数 就这样 直到圈内只剩下一只猴子时 这个猴子就是 猴王 编程求输入 后 输出最后猴王的编号 Input 每行是用空格分开的两个整数 第一个是每行是用空格分开的两个整数 第一个是 n 第二个是第二个是 m 0 m n 300 最后一行是 最后一行是 0 0 Output 对于每行输入数据 最后一行除外对于每行输入数据 最后一行除外 输出数据也是一行 即最后猴王的编号 输出数据也是一行 即最后猴王的编号 Sample Input 6 2 12 4 8 3 0 0 Sample Output 5 1 7 12 模拟题 现实中的有些问题 难以找到公式或规律 来进行解决 只能按照一定步骤 不停地 做下去 最后才能得到答案 这样的问题 用计算机来解决十分合适 只要让计算机模拟人在解决问题的行为即 可 13 解题思路 N个元素 每数够m个淘汰一个 之后还从1 开始重查 最终只留下1个 有循环 往复计数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 拦截导弹 某 国为了防御敌国的导弹袭击 开发出一种导弹拦截系统 但是这种导弹拦 截系统有一个缺陷 虽然它的第一发炮弹能够到达任意的高度 但是以后每 一发炮弹都不能 高于前一发的高度 某天 雷达捕捉到敌国的导弹来袭 并 观测到导弹依次飞来的高度 请计算这套系统最多能拦截多少导弹 拦截来 袭导弹时 必须按来袭导弹袭 击的时间顺序 不允许先拦截后面的导弹 再 拦截前面的导弹 某 国为了防御敌国的导弹袭击 开发出一种导弹拦截系统 但是这种导弹拦 截系统有一个缺陷 虽然它的第一发炮弹能够到达任意的高度 但是以后每 一发炮弹都不能 高于前一发的高度 某天 雷达捕捉到敌国的导弹来袭 并 观测到导弹依次飞来的高度 请计算这套系统最多能拦截多少导弹 拦截来 袭导弹时 必须按来袭导弹袭 击的时间顺序 不允许先拦截后面的导弹 再 拦截前面的导弹 Input 输入有两行 第一行 输入雷达捕捉到的敌国导弹的数量 输入有两行 第一行 输入雷达捕捉到的敌国导弹的数量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用法 简便实现itoa 的灵丹 stringstream 数组名和指针的区别 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 循环变量生命周期问题 新C 规范 出了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 假设句中最长的单词只有一个假设句中最长的单词只有一个 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