题目一：加密解密 题目说明：有一台简易的二位元加密解密机，其功能如下：选择加密或是解密功能。机 器会将你输入的数字转换成二进位数值，之後依照你所设定的位移码将此段二进位数值 向右位移，并把超过的位数再从尾端放入，如此一来便形成一项新的二进位数值码，最 後再将此段二进位数值转换成十进位数字，得到一个新的数字，则加密完成。同样地， 当选择解密时，也是先将数字转换成二进位之後，依照输入的位移量，向左位移，并把 超出的位数由前端补入，最後将此一新的二进位数值转为十进位後，解码完成。请写一 个程式，完成此加密解密的功能。 输入档说明：输入档中第一行为一个正整数N，代表共有N 测试资料。每组资料有两行， 第一行有两个数字，第一个数字为0 代表是加密，1 代表是解密，第二个数字 K( 0 昼 K 昼100000 )，代表位移几位。第二行为一连串以空格格开的数字，每个数字介 於 0 到255 之间。 输出说明：将每组测试资料结果输出於一行，共N 行。 Sample Run: Input file: Output: 2 1 1 12 15 17 0 3 50 18 19 255 24 30 34 70 66 98 255 解题方法说明：这是一个非常简单的题目，首先，我们读入总共有的资料数量N，表示 接下来有N 笔资料要处理，所以用一个回圈跑N 次。 接下来，读入资料a 和b，a 表示加密或解密，b 则表示加解密时轮转的位数。 知道a 和b 之後，我们开始一个一个的读入数字。 把数字读进来以後，用一个阵列把这些数字转换成2 进位，方法就是一直对这数字除二 取余数。 做完以後我们可以得到八个数字，分别表示八个bit。 在有了这八个数字以後，我们只要依照先前读进来的a 和b，就可以知道我们该从哪个 bit 当作新的数字的第一个bit，之後只要把数字还原回十进位，本题就可以轻松解决。 需要注意的是，因为没有告诉你每组资料有几笔数字，所以你必须要会判断是否读到换 行，否则万事休矣。 祝你考试顺利。 3 题目二：求最大公因数 题目说明：以辗转相除法，求两正整数之最大公因数。例如，60 与96 的最大公因数为 12，其计算过程如下： 96=60×1 + 36 60=36×1 + 24 36=24×1 + 12 24=12×2 + 0 总共经过4 次运算，得到最後结果。 输入档说明：输入档中第一行为一个正整数N，代表共有N 测试资料。每组资料有两个 正整数，自行判断前後哪个数字较大。 输出说明：将每组测试资料所需之运算次数及最大公因数输出於一行，以空格分隔，共 N 行。 Sample Run: Input file: Output: 4 60 96 12 15 50 18 36 36 4 12 2 3 4 2 1 36 4 题目三：将资料逐一加入max heap 题目说明：Max heap 是一个complete binary tree 且其中任一节点的键值都不小於其子 节 点的键值。将一笔资料加入一个现有的max heap 时，先加入一个节点在树的最後面（保 持complete binary tree 的特性），然後采用bubbling up 的方式调整键值。如果节点 的键 值大於其父节点的键值，就将两个键值交换，直到无法往上交换为止。以图1 为例，若 要加入一笔键值为9 的资料，第一步就是将新节点加在原来heap 的最後面，如图2 所 示。接着就是将新的键值逐步调整到适当的位置，如图3 及图4 所示。本题需要将输入 档内的键值资料以一次一笔的方式加入一个max heap，完成後将max heap 中的所有键 值以breadth-first search 的顺序全部列出。 输入档说明：输入档内有一行N 个正整数（N <= 100）代表要逐一加入的键值资料，各 个数字中间有一个空格隔开，最後还有一个0 代表结束。 输出说明：输出一行结果，依breadth-first search 的顺序显示max heap 中的所有键值 ， 各个键值间以一个空格隔开。 11 6 7 4 5 5 6 2 图1 11 6 7 4 5 5 6 2 9 图2 11 6 7 9 5 5 6 2 4 图3 11 9 7 6 5 5 6 2 4 图4 5 Sample Run: Input file: Output: 6 4 5 11 5 7 6 2 9 0 11 9 7 6 5 5 6 2 4 6 题目四： Pachinko 题目说明：假设Pachinko 钢珠往下跑，碰到钉柱时，往左与往右跑的机率不一定相同， 又假 设钉柱的排列最高处只有一个，每往下一排增加一个钉柱。若共有N 排钉柱，则最底下一 排 有N 个钉柱，最底下则有N+1 个口袋。以下图为例，各有2 排钉柱，假设钢珠碰到每个钉 柱 时，往左与往右跑的机率比例依序(由上而下、由左至右)为 1:2、2:3、3:1，则钢珠进到 每个 口袋的机率依序为2/15(=1/3*2/5)、7/10(=1/3*3/5+2/3*3/4)、1/6(=2/3*1/4)。 输入档说明：输入档内第一行为一个正整数N (N <= 10)，代表共有N 排的钉柱，之後各 行为 依由上而下、由左至右之钉柱顺序，钢珠往左与往右跑的机率比例。 输出说明：依由左至右顺序，输出钢珠落到每一口袋的机率(至小数点以下2 位)，各个机 率 值间以一个空格隔开。 解题方法说明：把原来的图转一下，一排一排考虑，当读取一钉柱的左右机率後，往左的 机 率乘上碰到这根钉柱的机率，加给下一排同一位置的钉柱(或口袋)；往右的机率乘上碰到 这 根钉柱的机率，加给下一排下一个位置的钉柱(或口袋)。 储存钢珠碰到钉柱(及口袋)机率的资料结构，可以用一个二维矩阵，或用两个一维阵列。 记得要初始化为零，但碰到最高处那个钉柱的机率是1。 2/3 * 1/4 2/3 * 3/4 1/3 * 3/5 1 1/3 2/3 1/3 * 2/5 1 1/3 2/3 7 Sample Run: Input file: Output: 3 1 3 2 1 3 5 2 5 6 5 3 4 0.05 0.32 0.37 0.27 8 题目五：算术运算式计算 题目说明：有数笔资料，每笔资料有n 个栏位，栏位值为1 至99 间之整数，栏位编号0 至 n-1，n 小於10。欲对每笔资料做算术运算，假设算术运算只有加(+)、减(-)、乘(*)等三 种， 又假设算术运算式不考虑运算子之优先顺序，例如：某算术运算式 1 + 3 * 0 表示 (栏 位1 + 栏位3) * 栏位0，若某一笔资料各栏位值依序为 2, 5, 1, 6, 3，则依此算术运算式针对 此笔资 料之计算结果为 (5 + 6) * 2 = 22。请依各算术运算式计算所有资料之计算结果总合。 算术运算式中不会出现不存在之栏位编号，但是栏位编号在算术运算式中可以重复出 现，算术运算式之运算元个数不超过10 个，计算结果可能为负数，也可能是较大整数， 须使 用long int。 输入档说明：输入档第一行为两个整数M N，表示共有M 笔资料，每笔资料有N 个栏位， 数据间以空格隔开。第二行起为每笔资料。资料之後一行是一个整数K，表示有K 个算术 运 算式。每一算术运算式最後以q 表示该算术运算式结束。 输出说明：每一算术运算式输出一个结果。 Sample Run: Input file: Output: 6 5 9 8 4 7 2 6 8 5 3 3 6 6 3 3 2 15 8 4 7 2 11 5 1 7 2 8 6 5 5 3 3 1 + 3 * 0 q 2 * 2 - 1 + 3 q 4 - 2 * 0 + 0 - 1 - 3 * 2 q --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.130.189.43