信息学奥赛一本通T1208：递归算法 2的幂次方表示

【题目描述】任何一个正整数都可以用2的幂次方表示。例如：137=27+23+20同时约定方次用括号来表示，即ab可表示为a(b)。由此可知，137可表示为：2(7)+2(3)+2(0)进一步：7=22+2+20（21用2表示）3=2+20所以最后137可表示为：2(2(2)+2+2(0))+2(2+2(0))+2(0)又如：1315=210+28+25+2+1所以1315最后可表示为：2(2(2+

• 0
• 2
• 轩爸
• 发布于 2020-04-27 16:20
• 阅读 ( 1683 )

信息学奥赛一本通T1206：递归算法 放苹果

【题目描述】把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。【输入】第一行是测试数据的数目t（0≤t≤20）。以下每行均包含二个整数M和N，以空格分开。1≤M，N≤10。【输出】对输入的每组数据M和N，用一行输出相应的K。【输入样例】1【输出样例】8【源程序】

• 0
• 0
• 轩爸
• 发布于 2020-04-27 16:20
• 阅读 ( 1296 )

信息学奥赛一本通T1205：递归算法 汉诺塔问题

【题目描述】约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到中间的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。【输入】输入为一个整数(小于20）后面跟三个单字符字符串。整数为盘子的数目，后三个字符表示三个杆子的编号。【输出】输出每一步移动盘子的记录。一次移动一行。每次移动的

• 0
• 2
• 轩爸
• 发布于 2020-04-27 10:20
• 阅读 ( 1996 )

信息学奥赛一本通T1204：递归算法 爬楼梯

【题目描述】树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数。【输入】输入包含若干行，每行包含一个正整数N，代表楼梯级数，1≤N≤30。【输出】不同的走法数，每一行输入对应一行输出。【输入样例】​5【输出样例】​8【源程序】 

• 0
• 0
• 轩爸
• 发布于 2020-04-27 10:20
• 阅读 ( 1153 )

信息学奥赛一本通T1203：递归算法 扩号匹配问题

【题目描述】在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注。【输入】输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串

• 0
• 0
• 轩爸
• 发布于 2020-04-27 10:20
• 阅读 ( 979 )

信息学奥赛一本通T1202：递归算法 Pell数列

【题目描述】Pell数列a1,a2,a3,...的定义是这样的，a1=1,a2=2,...,an=2an−1+an−2(n>2)。【输入】第1行是测试数据的组数 n，后面跟着 n 行输入。每组测试数据占 1 行，包括一个正整数k(1≤k<1000000)。【输出】n 行，每行输出对应一个输入。输出应是一个非负整数。【输入样例】2【输出样例】1【源程序】 

• 0
• 2
• 轩爸
• 发布于 2020-04-27 10:20
• 阅读 ( 3789 )

信息学奥赛一本通T1201：递归算法 菲波那契数列

【题目描述】菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。【输入】第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1≤a≤20)。【输出】输出有n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数的大小。【输入样例】​4【输出样例】​5【源程序】

• 0
• 0
• 轩爸
• 发布于 2020-04-27 10:20
• 阅读 ( 1046 )

信息学奥赛一本通T1200：递归算法 分解因数

【题目描述】给出一个正整数aa，要求分解成若干个正整数的乘积，即a=a1×a2×a3×...×an，并且1<a1≤a2≤a3≤...≤an，问这样的分解的种数有多少。注意到a=a也是一种分解。【输入】第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1<a<32768)。【输出】n行，每行输出对应一个输入。输出应是一个正整数，指明满足要求的分解的种

• 0
• 1
• 轩爸
• 发布于 2020-04-26 16:20
• 阅读 ( 1812 )

信息学奥赛一本通T1199：递归算法 全排列

【题目描述】给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。【输入】只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在1到6之间。【输出】输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义：已知S=s1，s2...sk,T=t1，t2...tk，则S<T等价于，存在p(1≤p≤k)，使得s1=t1,s2=t2,...,sp

• 0
• 1
• 轩爸
• 发布于 2020-04-26 16:20
• 阅读 ( 1760 )

信息学奥赛一本通T1198：递归算法 逆波兰表达式

【题目描述】逆波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值，其中运算符包括+ - * /四个。【输入】输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。【输出】输出为一行，表

• 0
• 0
• 轩爸
• 发布于 2020-04-26 16:20
• 阅读 ( 1029 )

信息学奥赛一本通T1197：递推算法 山区建小学

【题目描述】政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为didi(为正整数)，其中，0<i<m。为了提高山区的文化素质，政府又决定从m个村中选择n个村建小学(设0<n≤m<500)。请根据给定的m、n以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离

• 0
• 0
• 轩爸
• 发布于 2020-04-26 16:20
• 阅读 ( 1414 )

信息学奥赛一本通T1196：递推算法 踩方格

【题目描述】有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：a、每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；b、走过的格子立即塌陷无法再走第二次；c、只能向北、东、西三个方向走；请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。【输入】允许在方格上行走的步数n(n≤20)。【输出】计算出的方案数量。【输入样例】2【输出样例】7

• 0
• 1
• 轩爸
• 发布于 2020-04-26 16:20
• 阅读 ( 1580 )

信息学奥赛一本通T1195：递推算法 判断整除

【题目描述】一个给定的正整数序列，在每个数之前都插入+号或-号后计算它们的和。比如序列：1、2、4共有8种可能的序列：    (+1) + (+2) + (+4) = 7    (+1) + (+2) + (-4) = -1    (+1) + (-2) + (+4) = 3    (+1) + (-2) + (-4) = -5    (-1) + (+2) + (+4) = 5    (-1)

• 0
• 1
• 轩爸
• 发布于 2020-04-26 10:20
• 阅读 ( 1501 )

信息学奥赛一本通T1194：递推算法 移动路线

【题目描述】X桌子上有一个m行n列的方格矩阵，将每个方格用坐标表示，行坐标从下到上依次递增，列坐标从左至右依次递增，左下角方格的坐标为(1,1)，则右上角方格的坐标为(m,n)。小明是个调皮的孩子，一天他捉来一只蚂蚁，不小心把蚂蚁的右脚弄伤了，于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中，蚂蚁从左下角的方格中移动到右上角的方格中，每步移动一个方格。蚂蚁始终在方格矩阵内移动，请计算出

• 0
• 2
• 轩爸
• 发布于 2020-04-26 10:20
• 阅读 ( 1852 )

信息学奥赛一本通T1192：递推算法 放苹果

【题目描述】把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。【输入】第一行是测试数据的数目t（0≤t≤20）。以下每行均包含二个整数M和N，以空格分开。1≤M，N≤10。【输出】对输入的每组数据M和N，用一行输出相应的K。【输入样例】1【输出样例】8【源程序】 

• 0
• 0
• 轩爸
• 发布于 2020-04-26 10:20
• 阅读 ( 1111 )

信息学奥赛一本通T1193：递推算法 吃糖果

【题目描述】名名的妈妈从外地出差回来，带了一盒好吃又精美的巧克力给名名(盒内共有 N 块巧克力，0<N<20)。妈妈告诉名名每天可以吃一块或者两块巧克力。假设名名每天都吃巧克力，问名名共有多少种不同的吃完巧克力的方案。例如：如果N=1，则名名第1天就吃掉它，共有1种方案；如果N=2，则名名可以第1天吃1块，第2天吃1块，也可以第1天吃2块，共有2种方案；如果N=3，则名名第1天可以吃1

• 0
• 0
• 轩爸
• 发布于 2020-04-26 10:20
• 阅读 ( 766 )

信息学奥赛一本通T1191：递推算法 流感传染

【题目描述】有一批易感人群住在网格状的宿舍区内，宿舍区为n*n的矩阵，每个格点为一个房间，房间里可能住人，也可能空着。在第一天，有些房间里的人得了流感，以后每天，得流感的人会使其邻居传染上流感，（已经得病的不变），空房间不会传染。请输出第m天得流感的人数。【输入】第一行一个数字n，n不超过100，表示有n*n的宿舍房间。【输出】输出第m天，得流感的人数。【输入样例】5【输出样例】16【源程序】 

• 0
• 0
• 轩爸
• 发布于 2020-04-26 10:20
• 阅读 ( 1666 )

信息学奥赛一本通T1190：递推算法 上台阶

【题目描述】楼梯有n(71>n>0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法。【输入】输入的每一行包括一组测试数据，即为台阶数n。最后一行为0，表示测试结束。【输出】每一行输出对应一行输入的结果，即为走法的数目。【输入样例】1【输出样例】1【源程序】 

• 0
• 1
• 轩爸
• 发布于 2020-04-25 16:20
• 阅读 ( 2410 )

信息学奥赛一本通T1189：递推算法 Pell数列

【题目描述】Pell数列a1,a2,a3,...的定义是这样的，a1=1,a2=2,...,an=2an−1+an−2(n>2).给出一个正整数k，要求Pell数列的第k项模上32767是多少。【输入】第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数k (1≤k<1000000)。【输出】n行，每行输出对应一个输入。输出应是一个非负整数。【输入样例】2【输

• 0
• 0
• 轩爸
• 发布于 2020-04-25 16:20
• 阅读 ( 1194 )

信息学奥赛一本通T1188：递推算法 菲波那契数列

【题目描述】菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。给出一个正整数a，要求菲波那契数列中第a个数对1000取模的结果是多少。【输入】第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1 ≤ a ≤ 1000000)。【输出】n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数对1000取模得到

• 0
• 0
• 轩爸
• 发布于 2020-04-25 16:20
• 阅读 ( 1258 )