第五周 进位制.ppt

第五讲 进位制问题 ACM算法与程序设计 2 30 自动取款机 ByteLand上的每位居民都有一个自已的银行帐号 帐号上记录了居民的存款金额 以硬币为单位 他们可以用自己的帐号在30台自动取款机上进行取款或付款的操作 这100台自动取款机的编号从0到30 每台取款机都有自己的运行特点 当你在编号为i的取款机上进行操作时 若i是偶数 你将从取款机中获得2 i个硬币 若i是奇数 你将付给该取款机2 i个硬币 假设你要从银行取14枚硬币 那么你可以在第4号取款机上操作 获得16枚硬币 接着在第1号取款机上操作 付出2枚硬币 最终就得到了14枚硬币 3 30 假设你要付给银行7枚硬币 那么你可以在第3号取款机上操作 先付给8枚硬币 接着在第0号取款机上操作 取回1枚硬币 最终你付给银行7枚硬币 注意 由于银行系统的保险措施 每台取款机最多只能被操作一次 现在 L先生将要向银行支取或交纳一定数额的硬币 你能设计出一个方案 对某些取款机进行操作 从面恰好完成L先生的要求 输入要求 输入由多行组成 每行表示要取款或付款的数目 正数表示取款 负数表示付款 输出要求 每行输入对应一行输出 按降序输出需要操作的自动取款机号码 问题叙述 4 30 输入输出样例 问题叙述 5 30 问题分析 如果i是偶数 则从第i号取款机中获得2 i个硬币 如果i是奇数 则将付给第i号取款机2 i个硬币 所以顾客一共支付的费用为 6 30 问题分析 这个式子与整数的二进制表示法非常相似 所不同的只是把2换成了 2 下面是两个例子 7 30 问题分析 观察上面的规律 得出商的符号呈交错变化 在程序中可作如下处理 用flag表示当前数的正负 每次除法后改变它的正负 用n记录当前数的绝对值 且当前数变化规律为 当n为正偶数时 直接除以2 当n为正奇数时 减1后除以2 当n为负偶数时 其绝对值直接除以2 当n为负奇数时 其绝对值加1再除以2 8 30 源程序 includeintmain void intk n flag a 31 while scanf d n为正整数结束 9 30 源程序 else n为负整数 if n 2 0 n 2 a k 0 else n n 1 2 a k 1 n为负整数结束flag flag for k k 1 k 0 k if a k 1 printf d k printf n return0 10 30 确定进制 6 9 42对于十进制来说是错误的 但是对于十三进制来说是正确的 即6 13 9 13 42 13 而42 13 4 13 1 2 13 0 54 10 你的任务是写一段程序读入三个整数p q和r 然后确定一个进制B 2 B 16 使得p q r 如果B有很多选择 输出最小的一个 例如 p 11 q 11 r 121 则有11 3 11 3 121 3 因为11 3 1 3 1 1 3 0 4 10 和121 3 1 3 2 2 3 1 1 3 0 16 10 对于进制10 有11 10 11 10 121 10 这种情况下 应该输出3 如果没有合适的进制 则输出0 11 30 输入要求 输入有T组测试样例 T在第一行给出 每一组测试样例占一行 包含三个整数p q r p q r的所有位都是数字 并且1 p q r 1 000 000 输出要求 对于每个测试样例输出一行 该行包含一个整数 即使得p q r成立的最小的B 如果没有合适的B 则输出0 问题叙述 12 30 解题思路 此问题很简单 选择一个进制B 按照该进制将被乘数 乘数 乘积分别转换成十进制 然后判断等式是否成立 使得等式成立的最小B就是所求的结果 分别用一个字符型数组存储p q r的各位数字符号 先以字符串的方式读入p q r 然后按不同的进制将它们转换成成十进制数 判断是否相等 13 30 源程序 include includeinttoten char x intb 按b进制转换为10进制 inti ret 0 intlen strlen x for i 0 i b return 1 ret b ret x i 0 returnret 14 30 源程序 intmain void charp 8 q 8 r 8 intn pt qt rt scanf d 15 30 skew数 当一个数以10进制表示的时候 它从右向左数的第k位数字表示它与10 k的乘积 比如 81307 10 8 10 4 1 10 3 3 10 2 0 10 1 7 10 0 80000 1000 300 0 7 81307而在Skewbinary表示中 第k位的值xk表示xk 2 k 1 1 每个位上的可能数字是0或1 最后面一个非零位可以是2 例如 10120 skew 1 2 5 1 0 2 4 1 1 2 3 1 2 2 2 1 0 2 1 1 31 0 7 6 0 44 前十个skew数是0 1 2 10 11 12 20 100 101 以及102 16 30 输入格式 输入包含一行或多行 每行包含一个整数n 如果n 0表示输入结束 否则n是一个skew数 输出格式 对于每一个输入 输出它的十进制表示 转换成十进制后 n不超过2 31 1 2147483647 问题叙述 17 30 解题思路 skew数的相邻位上 基数之间没有等比关系 计算每一位的基数后 再把一个skew数转换成十进制表示就很简单 对于长度为k的skew数 最后一位数字的基数为2 k 1 由于转换成十进制后 n不超过2 31 1 因此输入skew数的最大长度不超过31 用一个整型数组base 31 依次存储skew数最末位 倒数第2位 第31位的基数值 使用这个数组 把每个skew数转换成对应的十进制数 base 0 1base k 2 k 1 1 2 2 k 1 1 2 base k 1 1 18 30 源程序 include includeintmain void inti k base 31 sum charskew 32 base 0 1 for i 1 i 31 i base i 2 base i 1 1 while 1 scanf s skew if strcmp skew 0 0 break sum 0 k strlen skew for i 0 i strlen skew i k sum skew i 0 base k printf d n sum return0 19 30 数制转换 有一种数制的基数是3 权值可以取 1 0 1 并分别用符号 0 1表示 如这种数制的101表示十进制数的10 即1 3 2 0 3 1 1 3 0 10 又如这种数制的 0表示十进制数的 3 即 1 3 1 0 3 0 3 编程要求给定的有符号整数转换为新数制的数 该数的前面不能有多余的0 如10的数制表示为101 则不要输出成0101 20 30 输入格式 输入有一行或多行 每行有一个整数N 2147483647 N 2147483647 整数内不会有其他分隔符 输出格式 每行输入对应一行输出 该行是输入行的整数的新数制表示 不能有多余空行 每行之前不能有前导空格 问题叙述 21 30 解题思路 用数学归纳法证明其存在性 注意稍稍修改一下 即可得到求数制转换的算法 1 整数0的新数制表示为0 整数1的新数制表示为1 整数2的新数制表示为1 整数 1的新数制表示为 整数 2的新数制表示为 1 以上说明当 X 2 X k的所有X命题成立 以下证k 1和 k 1的新数制表示是存在的 22 30 解题思路 a kmod3 0 则由归纳假设k 3存在新数制A1A2 An 则k 1存在新数制表示A1A2 An1 即 k 1 mod3 1 k 1 1 k b kmod3 1 则由归纳假设 k 2 3存在新数制表示A1A2 An 则k 1存在新数制表示A1A2 An 即 k 1 mod3 2 k 1 1 k 2 c kmod3 2 则由归纳假设 k 1 3存在新数制表示A1A2 An 则k 1存在新数制表示A1A2 An0 即 k 1 mod3 0 k 1 k 1 23 30 解题思路 d kmod3 0 由归纳假设 k 3存在新数制表示A1A2 An 则 k 1存在新数制表示A1A2 An 即 k 1 mod3 2 k 1 1 k e kmod3 1 由归纳假设 k 1 3存在新数制表示A1A2 An 则 k 1存在新数制表示A1A2 An0 即 k 1 mod3 0 k 1 k 1 f kmod3 2 由归纳假设 k 2 3存在新数制表示A1A2 An 则 k 1存在新数制表示A1A2 An1 即 k 1 mod3 1 k 1 1 k 2 综上 由归纳原理得知对任意整数存在新数制表示 唯一性的证明比较简单 留给大家思考 24 30 算法 1 读入X 2 若X为0则输出0并结束 否则下一步 3 置结果串S为空 4 若X为0则输出S并结束 否则下一步 5 若X 0转 9 否则下一步 6 若Xmod3 0 X X 3 S 0 S 转 5 7 若Xmod3 1 X X 1 3 S 1 S 转 5 8 若Xmod3 2 X X 1 3 S S 转 5 9 若 Xmod3 0 X X 3 S 0 S 转 5 10 若 Xmod3 1 X X 1 3 S 1 S 转 5 11 若 Xmod3 2 X X 1 3 S S 转 5 25 30 源程序 includeintmain void chars 40 0 inti k n while scanf d 26 30 源程序 while n 0 if n 0 switch n 3 case0 n 3 s k 0 break case1 n n 1 3 s k 1 break default n n 1 3 s k break n 0结束 27 30 源程序 else switch n 3 case0 n 3 s k 0 break case 2 相当于1n n 1 3 s k 1 break default 相当于2n n 1 3 s k break n 0结束 转换结束 28 30 源程序 for i k 1 i 0 i printf c s i printf n return0 29 30 练习题 30 30 练习题 1 十进制到八进制 ai2734 把一个十进制正整数转化成八进制2 八进制到十进制 ai2735