98 学年度第1 次考试(99.01.06) 2 题目一： 游乐园的摩天轮 题目说明：反覆游乐园是一家以摩天轮闻名的游乐园。乐园中有各式各样不同大小的摩天 轮， 可以让游客挑选。每个摩天轮的车厢都是以顺时针的方式来编号。反覆乐园与其他乐园最 大 的不同是每个乘客可以搭乘的时间都不一样。乐园老板每天给出两组不同的数字：右数与 左 数，当摩天轮开始运转时，会先让摩天轮被游客搭满，并且让1 号车厢在出口位置(下摩 天轮 的位置，也就是摩天轮与地面最接近的地方)；开始旋转时，会先逆时针转右数个有乘客 的车 厢，并且请转到出口位置的乘客下车，接下来再顺时针转左数个有乘客的车厢，并且请转 到 出口位置的乘客下车，接着再逆时针转右数个有乘客的车厢，依这个规则左右来回转动， 直 到摩天轮中都没有乘客，才会让下一批的乘客搭乘。小明的女朋友听说有这个反覆游乐园 以 後，非常的想要去玩，所以小明决定明天带着女朋友去反覆游乐园，但是小明是个穷学生 ， 而乐园中每次搭乘摩天轮的价格都非常昂贵，所以小明希望自己选择的车厢可以搭乘的最 久，可是他不知道该怎麽选择，所以请嘉义大学资工系的同学们帮帮忙，让他和女朋友的 约 会可以顺利进行。请写一个程式，自输入档中读入左数、右数以及摩天轮的车厢数量，计 算 小明应该选择几号车厢才会是最後一个下摩天轮的乘客，并输出车厢号码。例如：左数是 2， 右数是1，车厢总数量是4，如下图所示。因首先逆时针转1 个有乘客的车厢，也就是2 号 必 须下摩天轮；接着顺时针转2 个有乘客的车厢，也就是4 号必须下摩天轮；接着逆时针转 1 个有乘客的车厢，也就是1 号必须下摩天轮；此时只剩下3 号车厢有乘客，因此输出3， 即 小明选择3 号车厢可以搭乘最久。 输入档说明：输入档中第一行为一个正整数N，代表共有几组测试资料。之後接下来有N 行， 每行中有3 个正整数 L、R 和C，分别代表左数、右数(1￡ L,R ￡100) 及车厢总数量 (2 ￡ C ￡100)，每个数字中间有一个空格。 输出说明：每组测试资料输出结果於一行。 Sample Run: Input file: 3 2 1 4 5 3 6 4 6 8 Output: 3 3 1 3 4 1 2 3 4 1 1 3 3 游戏开始 2 下车 4 下车 1 下车 转2 只剩3 转 1 转1 98 学年度第1 次考试(99.01.06) 3 题目二：办公室中员工人数的极大值 题目说明：某单位总共有n 位员工，依照员工到达与离去的打卡时间，可得知第i 位员工 是 在xi 时到达，并在yi 时离开。因此第i 位员工待在办公室中的时间是[xi, yi)，亦即 xi ￡ t < yi 中所有可能的t。请读取xi 和yi，1 ￡ i ￡ n，找出同一时刻内，最多会有多少位员工 在办公 室中。 输入档说明：每个案例的第一行应包含一个正整数N，表示该案例中，该单位总共有几位 员 工。每个案例的第二行起接着的N 行，每行均包含两个不小於1 的正整数(该行第一个整 数应 该小於该行第二个整数)，代表每位员工的到达与离去时间。案例之间紧连，无空行。若 在案 例的第一行输入0，则表示结束输入，程式停止执行。 输出说明：当输入完每个案例後，应输出同一时刻内办公室中员工人数的极大值。 Sample Run: Input file: 3 6 10 5 7 7 15 6 20 50 15 23 3 12 8 44 40 48 30 32 0 Output: Max = 2 Max = 3 98 学年度第1 次考试(99.01.06) 4 题目三：兔子繁殖问题（rabbit population） 题目说明：假设： 第零个月，只有一对兔子。(多出0 对兔子) 第一个月，这对兔子生出一对兔子。(多出1 对兔子) 第二个月，两对兔子都各生出一对兔子，且第一对兔子死亡。(多出1 对兔子) 第三个月，三对兔子都各生出一对兔子，且第二对兔子死亡。(多出2 对兔子) 规则是每对兔子在它生命中会产下两对兔子。问第n 个月时多出的兔子数量。 令第n 个月时多出的兔子数量为F(n)，即F(0)=0，F(1)=1，F(2)=1，F(3)=2，… 以此类 推。 请撰写一个程式，可以从资料档中读入月份数n，求出Ｆ(n)。 输入档说明： 输入档第一行为一个正整数N 代表测试资料笔数，第二行起接下来有N 行 ， 每行为一个正整数或0 代表月份数n。 输出说明： 输出为Ｆ(n)，每组测试资料输出结果於一行。 Sample Run: Input file: 2 10 20 Output: 55 6765 98 学年度第1 次考试(99.01.06) 5 题目四：变形汉诺塔问题 题目说明：盘子依大小编号，最小为1 号，盘子分散在A、B、C 柱子上，假设各柱子上的 盘 子皆依大小顺序放置。因已经依大小顺序放置，且要将盘子由A 柱子搬至C 柱子上，所以 最 大编号的盘子在C 柱子上，就没有意义了，因此假设最大编号的盘子在A 或B 柱子上。输 入 资料只要知道在A 与B 柱子上的盘子，其余盘子在C 柱子。须将A 与B 柱子上的盘子以某 一资料结构储存，假设每个柱子上不超过10 个盘子。 举例说明做法： 例 1： A: 4 B: 3 C: 2 1 例 2： A: 4 B: 5 3 C: 2 1 较有效率做法：(此段落可以不读) 假设目前A 柱子上只有一个编号4 的盘子，B 柱子只有一个编号3 的盘子，只要将C 柱子 上 的1 及2 号盘子搬移至B 柱子，即可将编号4 的盘子搬移至C 柱子，再将B 柱子的盘子搬 移 至C 柱子即可完成。但是若B 柱子上有5 及3 号盘子，其最佳解为将3 号盘子搬移至A 柱 子， C 柱子上的1 及2 号盘子也搬移至A 柱子，即可顺利搬移5 号盘子至C 柱子。但是要这麽 做 考虑的条件较多，有一简单但较无效率的方法。 较方便写程式的做法： 假设目前A 与B 柱子上最小编号的盘子是h 号盘子，且假设此盘子在A 柱子上(若是B 柱 子， 则将以下之B 改成A)，欲将此h 号盘子搬移至C 柱子，此时，1 至h-1 号的盘子在C 柱子 上， 先以递回方式将C 柱子上的盘子搬移至B 柱子，将此h 号盘子搬移至C 柱子後，再以递回 方 式将B 柱子上的盘子搬移至C 柱子。如此，依次将A 与B 柱子上最小编号的盘子搬至C 柱 子。 请以此较方便写程式的做法完成程式设计。 输入档说明： 第一行 执行次数，此例共4 次。 第二行 第一次执行之A 柱子上的盘子，可能空的，有多个盘子时，由大至小编号，并以 一 98 学年度第1 次考试(99.01.06) 6 个空格分开。此例而言，A 柱子上有3 号盘子。 第三行 第一次执行之B 柱子上的盘子，可能空的，不考虑A、B 两柱子同时是空的。此例 而言，B 柱子上有4 号盘子，其余在C 柱子上，亦即C 柱子上有2 号及1 号盘子。 第四行 第二次执行之A 柱子上的盘子。A 柱子上有3 号盘子。 第五行 第二次执行之B 柱子上的盘子。B 柱子上有2 号及1 号盘子，C 柱子上没有盘子 。 第六行 第三次执行之A 柱子上的盘子。此行为空行，A 柱子上没有盘子。 第七行 第三次执行之B 柱子上的盘子。B 柱子上有4 号及3 号盘子，C 柱子上有2 号及1 号盘子。 第八行 第四次执行之A 柱子上的盘子。A 柱子上有5 号盘子。 第九行 第四次执行之B 柱子上的盘子。B 柱子上有3 号盘子，C 柱子上有4 号、2 号及1 号盘子。 输出说明：每次搬动盘子时，输出将几号盘子搬至哪个柱子，盘子编号与柱子代号以空格 分 开，以逗号分开每次的搬移。 Sample Run: Input file: 4 3 4 3 2 1 4 3 5 3 Output: 1 A,2 B,1 B,3 C,1 A,2 C,1 C,1 A,2 B,1 B,3 A,1 C,2 A,1 A,4 C,1 C,2 B,1 B,3 C,1 A,2 C,1 C, 1 C,1 A,2 C,1 C,1 A,2 B,1 B,3 C,1 A,2 C,1 C, 1 B,2 A,1 A,3 C,1 B,2 C,1 C,1 A,2 B,1 B,3 A,1 C,2 A,1 A,4 C,1 C,2 B,1 B,3 C,1 A,2 C,1 C, 1 B,2 A,1 A,3 C,1 B,2 C,1 C,1 A,2 B,1 B,3 A,1 C,2 A,1 A,4 B,1 B,2 C,1 C,3 B,1 A,2 B,1 B,5 C,1 A,2 C,1 C,3 A,1 B,2 A,1 A,4 C,1 C,2 B,1 B,3 C,1 A,2 C,1 C, 98 学年度第1 次考试(99.01.06) 7 题目 --

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