《问题解答专题》PPT课件.ppt

问题解答专题 基础题 2003p 1 现在市场上有一款汽车A很热销 售价是2万美元 汽车A每加仑汽油可以行驶20英里 普通汽车每年大约行驶12000英里 油价是每加仑1美元 不久我公司就要推出新款节油汽车B 汽车B每加仑汽油可以行驶30英里 现在我们要为B制定价格 它的价格略高于A 我们预计如果用户能够在两年内通过节省油钱把B高出A的价钱弥补回来 则他们就会购买B 否则就不会购买B 那么B的最高价格应为万美元 12000 2 24000 英里 24000 20 120024000 30 8001200 800 400 加仑 400 1 400 美元 2 04 2004p 1 一个家具公司生产桌子和椅子 现在有113个单位的木材 每张桌子要使用20个单位的木材 售价是30元 每张椅子要使用16个单位的木材 售价是20元 使用已有的木材生产桌椅 不一定要把木材用光 最多可以卖元钱 20 x 16y 113 0 30 7 20 1401 30 5 20 1302 30 4 20 1403 30 3 20 1504 30 2 20 1605 30 0 20 150 2004p 2 75名儿童到游乐场去玩 他们可以骑旋转木马 坐滑行铁道 乘宇宙飞船 已知其中20人这三种东西都玩过 55人至少玩过其中的两种 若每样乘坐一次的费用是5元 游乐场总共收入700 可知有名儿童没有玩过其中任何一种 20 15 300 35 10 350 10 5 50 75 55 10 10 2009t 2 某个国家的钱币面值有1 7 72 73共计四种 如果要用现金付清10015元的货物 假设买卖双方各种钱币的数量无限且允许找零 那么交易过程中至少需要流通张钱币 29 1 3 2 35 29 343 681 49 193 7 22 1 0 2009p 2 有如下的一段程序 1 a 1 2 b a 3 d a 4 e a d 5 c 2 d 6 f b e d 7 g a f c 现在要把这段程序分配到若干台 数量充足 用电缆连接的PC上做并行执行 每台PC执行其中的某几个语句 并可随时通过电缆与其他PC通讯 交换一些中间结果 假设每台PC每单位时间可以执行一个语句 且通讯花费的时间不计 则这段程序最快可以在单位时间内执行完毕 注意 任意中间结果只有在某台PC上已经得到 才可以被其他PC引用 例如若语句4和6被分别分配到两台PC上执行 则因为语句6需要引用语句4的计算结果 语句6必须在语句4之后执行 5 2001p 1 在a b c d e f六件物品中 按下面的条件能选出的物品是 1 a b两样至少有一样 2 a d不能同时取 3 a e f中必须有2样 4 b c要么都选 要么都不选 5 c d两样中选一样 6 若d不选 则e也不选 a b c f 假定取 根据 则 不取 根据 也不取 根据 取 根据 取 最后 矛盾 假定 都取 根据 则 不取 根据 也不取 根据 取 根据 取 最后 能做到 2004t 2 已知a b c d e f g七个人中 a会讲英语 b会讲英语和汉语 c会讲英语 意大利语和俄语 d会讲汉语和日语 e会讲意大利语和德语 f会讲俄语 日语和法语 g会讲德语和法语 能否将他们的座位安排在圆桌旁 使得每个人都能与他身边的人交谈 如果可以 请以 ab 开头写出你的安排方案 abdfgec 2005p 2 有3个课外小组 物理组 化学组和生物组 今有张 王 李 赵 陈 5名同学 已知张 王为物理组成员 张 李 赵为化学组成员 李 赵 陈为生物组成员 如果要在3个小组分别选出3位组长 一位同学最多只能担任一个小组的组长 共有 种选择方案 陈张王陈李王陈赵王 陈李张陈赵张 李赵王赵李王 李赵张赵李张 李张王赵张王 1998p 2 某班有50名学生 每位学生发一张调查卡 上写a b c三本书的书名 将读过的书打 结果统计数字如下 只读a者8人 只读b者4人 只读c者3人 全部读过的有2人 读过a b两本书的有4人 读过a c两本书的有2人 读过b c两本书的有3人 1 读过a的人数是 2 一本书也没有读过的人数是 8 4 2 2 12 8 4 3 4 2 2 3 2 2050 20 30 1995p 5 有红 黄 黑 白四色球各一个 放置在一个内存编号为1 2 3 4四个格子的盒中 每个格子放置一只球 它们的顺序不知 甲 乙 丙三人猜测放置顺序如下 甲 黑编号1 黄编号2 乙 黑编号2 白编号3 丙 红编号2 白编号4 结果证明甲乙丙三人各猜中了一半 写出四色球在盒子中放置情况及推理过程 假定 黑为1 黄为2 黑为2 白为3 红为2 白为4 黄为4 1995t 2 有标号为A B C D和1 2 3 4的8个球 每两个球装一盒 分装4盒 标号为字母的球与标号为数字的球有着某种一一对应的关系 称为匹配 并已知如下条件 1 匹配的两个球不能在一个盒子内 2 2号匹配的球与1号球在一个盒子里 3 A号和2号球在一个盒子里 4 B匹配的球和C号球在一个盒子里 5 3号匹配的球与A号匹配的球在一个盒子里 6 4号是A或B号球的匹配球 7 D号与1号或2号球匹配 请写出这四对球匹配的情况 4 D D 1998p 3 任给自然数n k 1 K 9 按如下计算步骤求序列XJXJ 1 X0的步骤 1 j 02 如果N K则转第3步 否则转第7步3 Xj NMODK4 N NDIVK5 j j 16 回第2步7 Xj N8 结束试求当 N 1998 K 3时 XJXJ 1 X0之值 2202000 三进制数 排序 2005p 1 将数组 32 74 25 53 28 43 86 47 中的元素按从小到大的顺序排列 每次可以交换任意两个元素 最少需要交换 次 5 用直接选择排序实现 25 74 32 53 28 43 86 4725 28 32 53 74 43 86 4725 28 32 53 74 43 86 4725 28 32 43 74 53 86 4725 28 32 43 47 53 86 7425 28 32 43 47 53 86 7425 28 32 43 47 53 74 86 基本思想 首先在所有数据中选最小的数据 把它与第一个数据交换 然后在其余的数据中再选出最小的数据与第二个数据交换 依次类推 直到全部排完 constn 10 vara array 1 n ofinteger k i j temp integer beginrandomize fori 1tondoa i random 100 fori dobegink i forj doifa j a k then if thenbegintemp a k a k a i a i temp end end fori 1tondowrite a i 3 writeln end 1ton 1 i 1ton k j ki 排列组合 2008p 1 书架上有四本不同的书A B C D 其中A和B是红皮的 C和D是黑皮的 把这四本书摆在书架上 满足所有黑皮的书都排在一起的摆法有 种 满足A必须比C靠左 所有红皮的书要摆放在一起 所有黑皮的书要摆放在一起 共有 种摆法 2009p 1 小陈现有2个任务A B要完成 每个任务分别有若干步骤如下 A a1 a2 a3 B b1 b2 b3 b4 b5 在任何时候 小陈只能专心做某个任务的一个步骤 但是如果愿意 他可以在做完手中任务的当前步骤后 切换至另一个任务 从上次此任务第一个未做的步骤继续 每个任务的步骤顺序不能打乱 例如 a2 b2 a3 b3 是合法的 而 a2 b3 a3 b2 是不合法的 小陈从B任务的b1步骤开始做 当恰做完某个任务的某个步骤后 就停工回家吃饭了 当他回来时 只记得自己已经完成了整个任务A 其他的都忘了 试计算小陈饭前已做的可能的任务步骤序列共有种 70 排列组合 加法原理 B任务中的b1一定做 而且肯定是第一个做的 除了b1外 第一类 完成A任务只有1种 第二类 完成A任务和b2有C 4 1 4种 第三类 完成A任务和b2 b3有C 5 2 10种 第四类 完成A任务和b2 b3 b4有C 6 3 20种 第五类 完成A任务和b2 b3 b4 b5有C 7 4 35种 加起来1 4 10 20 35 70 2002p 2 将N个红球和M个黄球排成一行 例如 N 2 M 3可得到10种排法 问题 当N 4 M 3时有种不同排法 7 4 3 35 2001p 2 平面上有三条平行直线 每条直线上分别有7 5 6个点 且不同直线上三个点都不在同一条直线上 问用这些点为顶点 能组成多少个不同三角形 C 7 2 5 6 C 5 2 7 6 C 6 2 7 5 7 6 5 21 11 10 13 15 12 210 231 130 180 210 751 2001t 平面上有三条平行直线 每条直线上分别有7 5 6个点 且不同直线上三个点都不在同一条直线上 问用这些点为顶点 能组成多少个不同四边形 21 10 21 15 21 5 6 10 15 10 6 7 15 5 7 2250 归纳 1999p 2 根据Nocomachns定理 任何一个正整数n的立方一定可以表示成n个连续的奇数的和 例如 13 123 3 533 7 9 1143 13 15 17 19在这里 若将每一个式中的最小奇数称为X 那么当给出n之后 请写出X与n之间的关系表达式 X N2 N 1 1995p 4 已知如下N N 1 2个数据 按行的顺序存入数组A 1 A 2 中 a11a21a22a31a32a33 an1an2an3 ann其中 第一个下标表示行 第二个下标表示列 若 aij i j j i 1 2 n 存贮在A k 中 试问 k和i j之间的关系如何表示 给定k值 k n n 1 2 后 写出能决定相应的i j值的算法 k i 1 i 2 j j k i 1 whilej idobeginj j i i i 1 end 2002t 2 n0 k 1 nk 1 设有一棵k叉树 其中只有度为0和k两种结点 设n0 nk 分别表示度为0和度为k的结点个数 试求出n0和nk之间的关系 n0 数学表达式 数学表达式仅含nk k和数字 n0 n2 1 n0 2 n3 1 n0 3 n4 1 1999t 将Ln定义为求在一个平面中用n条直线所能确定的最大区域数目 例如 当n 1时 L1 2 进一步考虑 用n条折成角的直线 角度任意 放在平面上 能确定的最大区域数目Zn是多少 例如 当n 1时 Z1 2 如下图所示 当给出n后 请写出以下的表达式 Ln Zn 1 2 Ln n n 1 2 1 n 0 Zn L2n 2n 2n2 n 1 2 1 14 1 1 27 1 1 2 311 1 1 2 3 4 Zn L2n 2n 2n2 n 1 2006t 2 将边长为n的正三角形每边n等分 过每个分点分别做另外两边的平行线 得到若干个正三角形 我们称为小三角形 正三角形的一条通路是一条连续的折线 起点是最上面的一个小三角形 终点是最下面一行位于中间的小三角形 在通路中 只允许由一个小三角形走到另一个与其有公共边的且位于同一行或下一行的小三角形 并且每个小三角形不能经过两次或两次以上 图中是n 5时一条通路的例子 设n 10 则该正三角形的不同的通路的总数为 n 5时 方案有1 2 3 4 4 n 10时 方案有1 2 9 9 n 2时 方案有1种 n 3时 方案有2种 n 4时 方案有6种 递推 2000p 2 有2 n的一个长方形方格 用一个1 2的骨牌铺满方格 例如n 3时 为2 3方格 此时用一个1 2的骨牌铺满方格 共有3种铺法 试对给出的任意一个n n 0 求出铺法总数的递推公式 2000t 2 设有一个共有n级的楼梯 某人每步可走1级 也可走2级 也可走3级 用递推公式给出某人从底层开始走完全部楼梯的走法 例如 当n 3时 共有4种走法 即1 1 1 1 2 2 1 3 F 1 1F 2 2F 3 4F N F N 3 F N 2 F N 1 N 4 2007p 2 最短路线 某城市的街道是一个很规整的矩形网络 见下图 有7条南北向的纵街 5条东西向的横街 现要从西南角的A走到东北角的B 最短的走法共有多少种 210 1111 111111 234567 3610152128 41020355684 5153570126210 2009p 1 小陈现有2个任务A B要完成 每个任务分别有若干步骤如下 A a1 a2 a3 B b1 b2 b3 b4 b5 在任何时候 小陈只能专心做某个任务的一个步骤 但是如果愿意 他可以在做完手中任务的当前步骤后 切换至另一个任务 从上次此任务第一个未做的步骤继续 每个任务的步骤顺序不能打乱 例如 a2 b2 a3 b3 是合法的 而 a2 b3 a3 b2 是不合法的 小陈从B任务的b1步骤开始做 当恰做完某个任务的某个步骤后 就停工回家吃饭了 当他回来时 只记得自己已经完成了整个任务A 其他的都忘了 试计算小陈饭前已做的可能的任务步骤序列共有种 70 a3014102035a201361015a101234511111b1b2b3b4b5然后把a3那一行加起来1 4 10 20 35 70 1998p 1 已知一个数列U1 U2 U3 UN 往往可以找到一个最小的K值和K个数a1 a2 ak使得数列从某项开始都满足 UN K a1UN K 1 a2UN K 2 akUN A 例如对斐波拉契数列1 1 2 3 5 可以发现 当K 2 a1 1 a2 1时 从第3项起 即N 1 都满足Un 2 Un 1 Un 试对数列12 22 32 n2 求K和a1 a2 aK使得 A 式成立 当K 3 a1 a2 ak为a1 3 a2 3 a3 1时 Un Un Un 1 Un 猜想 是 则可得下列方程 展开可得 可得方程组 解得 a1 3 a2 3 a3 1 递归 2007p 1 子集划分 将n个数 1 2 n 划分成r个子集 每个数都恰好属于一个子集 任何两个不同的子集没有共同的数 也没有空集 将不同划分方法的总数记为S n r 例如 S 4 2 7 这7种不同的划分方法依次为 1 234 2 134 3 124 4 123 12 34 13 24 14 23 当n 6 r 3时 S 6 3 90 对任一元素an 必然出现以下两种情况 an 是r个子集合中的一个 于是我们只要把a1 a2 an 1划分为r 1个子集 便解决了本题 这种情况下的划分数共有s n 1 r 1 an 不是r个子集合中的一个 则an必与其它的元素构成一个子集 则问题相当于先把a1 a2 an 1划分为r个子集 这种情况下的划分数共有s n 1 r 然后再把元素an加入到r个子集合中的任一个中去 共有r种加入方式 这样对于an的每一种加入方式 都可以使集合划分为r个子集 因此根据乘法原理 划分数共有r s n 1 r 确定边界 首先不能把n个元素不放进任何一个集合中去 即r 0时 s n r 0 也不可能在不允许空集的情况下把n个元素放进多于n的r个集合中去 即r n时 s n r 0 再者 把n个元素放进一个集合或把n个元素放进n个集合 方案数显然都是 即r 1或r n时 s n r 1 varn r integer functions n r integer longint beginif n r or r 0 thens 0elseif r 1 or r n thens 1elses s n 1 r 1 r s n 1 r end beginreadln n r writeln s n r end 2002t 1 在书架上放有编号为1 2 n的n本书 现将n本书全部取下然后再放回去 当放回去时要求每本书都不能放在原来的位置上 例如 n 3时 原来位置为 123放回去时只能为 312或231这两种问题 求当n 5时满足以上条件的放法共有多少种 44种 解 第一步 第一本书不放在原来的第一个位置 有n 1种放法 第二步 假设第一本书放在第2个位置 则第二本书的放法又可以分为两类 第一类 第二本书恰好放在第一个位置 则余下的n 2本书有An 2种放法 第二类 第二本书不放在第一个位置 则就是第二本书不放在第一个位置 第三本书不放在第三个位置 第四本书不放在第四个位置 第n本书不放在第n个位置 所以有An 1种放法 由分步计数原理和分类计数原理 我们便得到了递归公式 边界 varn integer functiond n integer longint begincasenof1 d 0 2 d 1 elsed n 1 d n 1 d n 2 end end beginreadln n writeln d d n end 分治 1996p 9 已知 A1 A2 A81共有81个数 其中只有一个数比其它数大 要用最少的比较运算次数 把这个值大的数找出来 假设两个数比较一次能决定出大于 小于或等于这三种情况 请将以下算法补充完整 constn 81 vara array 1 n ofinteger m n1 i k k0 s1 s2 integer beginfori 1tondoa i 10 randomize k0 random 81 1 a k0 a k0 1 writeln number a k0 测试数据 n1 n k 0 whilen1 1dobeginn1 n1div3 三分法 s1 0 s2 0 fori k 1tok n1dos1 s1 a i fori k n1 1tok 2 n1dos2 s2 a i 分别求前两组数据和 ifs1 s2thenk k n1elseifs1 s2thenk k 2 n1 确定大数在哪一组 end writeln a k 1 end 2006p 1 现有80枚硬币 其中有一枚是假币 其重量稍轻 所有真币的重量都相同 如果使用不带砝码的天平称重 最少需要称几次 就可以找出假币 你还要指出第1次的称重方法 请写出你的结果 4次 第一步 分成3组 27 27 26 将前2组放到天平上 数据结构 2003p 2 无向图G有16条边 有3个4度顶点 4个3度顶点 其余顶点的度均小于3 则G至少有个顶点 3 4 4 3 2 x 2 16x 43 4 4 11 图中各顶点的度数总和是边数的2倍 1999p 1 在磁盘的目录结构中 我们将与某个子目录有关联的目录数称为度 如下图所示 该图表达了A盘的目录结构 D1 D11 均表示子目录的名字 在这里 根目录的度为2 D1子目录的度为3 D11子目录的度为4 D2 D12 D111 D112 D113的度均为1 若不考虑子目录的名字 则可简单的图示为如右边的树结构 现知道一个磁盘的目录结构中 度为2的子目录有2个 度为3的子目录有1个 度为4的子目录有3个 试问度为1的子目录有几个 答 应把树结构看作图 并假设度为1的子目录有x个 则该图共有6 x个结点 共有5 x条边 就可以列出以下方程 2 5 x 3 4 1 3 2 2 x 1解得x 9 1997p 8 下图中用点表示城市 点与点之间的联系表示城市间的道路 试问 能否找出一条从A城市出发 经过图中所有道路一次后又回到出发点的通路来 能否从A出发 找出去每个城市且只去一次的通路来 若能 则写出通路 否则说明理由 能 全是偶点 只去一次的通路不存在 从A出发只能到达其中的3个点 每个点只能去一次 因此要找到这样的通路是不可能的 一笔画 只有当一个连通图的顶点全是偶点或仅有两个奇点时才能实现一笔画 把无向图不重复地一笔画出 如果没有奇点 则可以从任意一点出发开始一笔画 此时图中存在经过每条边一次且仅一次的回路 称欧拉回路 如果仅有两个奇点 则可以从其中一个奇点出发一笔画 此时图中存在经过每条边一次且仅一次的路径 称欧拉路径 V1 V3 V2 V4 V1 V3 V2 V4 1998t 3 用邻接矩阵表示下面的无向图 2008p 2 有6个城市 任何两个城市之间有一条道路连接 6个城市之间两两之间的距离如下表表示 则城市1到城市6的最短距离为 基本思想 设置两个顶点的集合S和T V S 集合S中存放已找到最短路径的顶点 集合T存放当前还未找到最短路径的顶点 初始状态时 集合S中只包含源点v0 然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中 集合S每加入一个新的顶点u 都要修改顶点v0到集合T中剩余顶点的最短路径长度值 集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值 此过程不断重复 直到集合T的顶点全部加入到S中为止 迪杰斯特拉算法是解决单源最短路径问题的贪心算法 138 30 32V2 8 13 1330 32V1 13 13302220V3 13 192220V4 19 2120V6 20 32 vara array 1 20 1 20 ofinteger v array 1 20 ofboolean i j max n p integer flag boolean beginreadln n fori 1tondoforj 1tondoread a i j fillchar v sizeof v false v 1 true 源点 forj 2tondo n 1次贪心 beginmax maxint fori 1tondo 寻找源点到其它顶点的最短权值 ifnotv i and a 1 i 0 and a 1 i 0 and a p i 0 thenif a 1 i a 1 p a p i or a 1 i 0 thena 1 i a 1 p a p i end fori 2tondowrite a 1 i end 原来是无路的 1 2 3 5 4 4 29 4 4 6 3 6 504294020003060040000600400 41147 样例 有6个城市 任何两个城市之间有一条道路连接 6个城市之间两两之间的距离如下表表示 则城市1到城市6的最短距离为 0230810 0030510 000058 000007 2000p 1 已知 按中序遍历二叉树的结果为 abc问 有多少种不同形态的二叉树可以得到这一遍历结果 并画出这些二叉树 1998t 2 给出一棵二叉树的中序遍历 DBGEACHFI与后序遍历 DGEBHIFCA 画出此二叉树 2001t 1 已知一棵二叉树的结点名为大写英文字母 其中序与后序遍历的顺序分别为 CBGEAFHDIJ与CGEBHFJIDA则该二叉树的先序遍历的顺序为 ABCEGDFHIJ 1996t 7 下面是一个利用完全二叉树特性 用顺序表来存储的一棵二叉树 结点数据为字符型 结点层次号从小到大 同一层从左到右顺序存储 表示空结点 表示存储数据结束 现要求画出对应该存储结构的二叉树示意图 123456789101112131415 1997p 9 为了便于处理表达式 常常将普通表达式 称为中缀表示 转换为前缀 运算符在前 如X Y写为 XY 和后缀 运算符在后 如X Y写为XY 的表达形式 在这样的表示中可以不用括号即可确定求值的顺序 如 P Q R S PQ RS或 PQ RS 试将下面的表达式改写成前缀与后缀的表示形式 A B C DA C D B E 试将下面的前缀表示还原成中缀的表示形式 同时写出后缀表示 A B C 前缀式中 表示一元运算符取负号 如 A表示 A A BCD ABC D A CD BE ACD BE 中缀形式为 A B C 后缀形式为 A BC 标识符树 1 标识符树的定义将算术表达式用二叉树来表示 称为标识符树 2 标识符树的特点 1 运算对象都是叶结点 2 运算符都是根结点 3 从表达式产生标识符树的方法 1 读入表达式的一部分产生相应二叉树后 再读入运算符时 运算符与二叉树根结点的运算符比较优先级的高低 读入优先级高于根结点的优先级 则读入的运算符作为根的右子树 原来二叉树的右子树 成为读入运算符的左子树 读入优先级等于或低于根结点的优先级 则读入运算符作为树根 而原来二叉树作为它的左子树 2 遇到括号 先使括号内的表达式产生一棵二叉树 再把它的根结点连到前面已产生的二叉树根结点的右子树上去 3 单目运算符 加运算对象 表示0 例如 A 表示为 A 4 应用举例 1 画出表达式 A B C的标识符树 并求它的前序序列和后序序列 2 画出表达式 A B C 的标识符树 并求它的前序序列和后序序列 3 画出表达式 A B C D的标识符树 并求它的前序序列和后序序列 4 画出 A B C D E F G H 的标识符树 并求它的前序序列和后序序列 2002p 2 345213421532145324513425132415321543542132541 如下图 有一个无穷大的的栈S 在栈的右边排列着1 2 3 4 5共五个车厢 其中每个车厢可以向左行走 也可以进入栈S让后面的车厢通过 现已知第一个到达出口的是3号车厢 请写出所有可能的到达出口的车厢排列方案 345354 1997p 4 设数组A 10 100 20 100 以行优先的方式顺序存储 每个元素占4个字节 且已知A 10 20 的地址为1000 则A 50 90 的地址是 14240 1000 50 10 100 20 1 90 20 4 其他 2006t 1 将2006个人分成若干不相交的子集 每个子集至少有3个人 并且 1 在每个子集中 没有人认识该子集的所有人 2 同一子集的任何3个人中 至少有2个人互不认识 3 对同一子集中任何2个不相识的人 在该子集中恰好只有1个人认识这两个人 则满足上述条件的子集最多能有个 将2006个人分成若干不相交的子集 每个子集至少有3个人 并且 1 在每个子集中 没有人认识该子集的所有人 2 同一子集的任何3个人中 至少有2个人互不认识 3 对同一子集中任何2个不相识的人 在该子集中恰好只有1个人认识这两个人 则满足上述条件的子集最多能有个 2006 5 401 2006p 2 取石子游戏 现有5堆石子 石子数依次为3 5 7 19 50 甲乙两人轮流从任一堆中任取 每次只能取自一堆 不能不取 取最后一颗石子的一方获胜 甲先取 问甲有没有获胜策略 即无论乙怎样取 甲只要不失误 都能获胜 如果有 甲第一步应该在哪一堆里取多少 请写出你的结果 为了解决这类一般情况 我们需要用到整数的二进位制 把m元数组 a1 a2 am 中的每一个分量用二进位制数表示 ai 1 i m 写在第i行 同时对齐二进位制数的位数 在列上作十进位制加法 其和写在第 m 1 行 记为 n1 n2 nj nl 如果所有这些和数nj 1 j l 均为偶数 我们称这个m元数组为偶数组 若nj 1 j l 中有一个数为奇数 则称之为非偶数组 例如 对于3元数组 2 3 5 a12010a23011a35101 22n1n2n3因为其中n1 1 所以 2 3 5 是非偶数组 同样 对于3元数组 2 3 1 a1210a2311a310122n1n2由于nj j 1 2 为偶数 则 2 3 1 为偶数组 偶数组与非偶数组在T变换下具有如下性质 1 偶数组经过一次T变换之后一定变为非偶数组 2 对于非偶数组 一定可以找到某一个T变换 使其变为偶数组 这样我们容易判定 如果给定的m元数组是偶数组 则后取者必有获胜策略 相反 若给定m元数组为非偶数组 则先取者有方法获胜 因为给定的m元数组为偶数组 先取者无论怎样取 只能将偶数组变为非偶数组 后取者则有策略将此时的非偶数组变为偶数组 由于每次取走石子 剩下石子数目一定越来越小 而 0 0 0 是偶数组 所以后取者获胜 同理可证相反情况 例 有三堆石子 各堆数目分别是2 3 6 两人轮流取 取完的人为胜者 若甲先乙后 谁取胜 解 a12010a23011a36110131n1n2n3所以 2 3 6 为非偶数组 我们可以判定 先取者甲获胜 只需将a3 6变为1 可以验证 2 3 1 是偶数组 应用 19010011700011150001013000011010010 18 10也就是 还要18才能变成 必负局 所以50 18 32所以第1次只能在第5堆石子中取32粒 使得取出32粒后为 必负局 例 桌上放着一堆小石子一共100颗 两人 甲 乙 轮流取 每次可以取1至10颗 取完的人为胜者 怎样才能取胜 容易看出11是取胜的关键数字 因为到此时 不论对方 甲 取多少颗 大于0且小于11 总留下大于0且小于11颗石子 这样乙方一次取完即获得胜利 同样地分析 要取到11必须取到22 33 44 55 66 77 88 99 这样我们就知道了获胜之道 先取1颗石子 留下99颗 然后对方取a 1 a 10 颗 己方取 11 a 颗 就总能掌握这种致胜的关键数 从而确保获胜 如果对方先取 己方只需利用对方不知道其中奥秘 争取到一个致胜数 就总能依 中方法取到下一个致胜数 最后取得胜利 下面是另一类游戏 2005t 2 取火柴游戏 取火柴游戏的规则如下 一堆火柴有N根 A B两人轮流取出 每人每次可以取1根或2根 最先没有火柴可取的人为败方 另一方为胜方 如果先取者有必胜策略则记为1 先取者没有必胜策略记为0 当N分别为100 200 300 400 500时 先取者有无必胜策略的标记顺序为 回答应为一个由0或1组成的字符串 是取胜的关键数字 传球问题 4个人进行篮球训练 互相传球接球 要求每个人接球后马上传给别人 开始由甲发球 并作为第一次传球 第五次传球后 球又回到甲手中 问有多少种传球方式 60 设有棱长为1米的正四面体ABCD 一只蚂蚁从顶点A出发 遵循下列规则爬行 在每个顶点相交的3条棱中选一条 然后沿这条棱到另一个顶点 求蚂蚁爬行了7米路之后 又回到顶点A的方法总数 设从点A出发走过n米回到点A的走法为an种 由于从A出发走n 1米的走法共有3n 1种 其中有an 1种是走到A的 下一步一定离开A 除去这an 1种 其它的每一种都可以再走1米到达A点 因此 an 3n 1 an 1 一个学生暑假在A B C三个城市游览 他今天在这个城市 明天就到另一个城市 假设他第一天在A市 第五天又回到A市 问他有几种不同的游览方案 a1 0 a2 21 0 2 a3 22 2 2 A4 23 2 6 出栈序列统计 问题描述 栈是常用的一种数据结构 有n个元素在栈顶端一侧等待进栈 栈顶端另一侧是出栈序列 你已经知道栈的操作有两种 push和pop 前者是将一个元素进栈 后者是将栈顶元素弹出 现在要使用这两种操作 由一个操作数序列可以得到一系列的输出序列 请你编程求出对于给定的n 计算并输出由操作数序列1 2 n 经过一系列操作可能得到的输出序列总数 输入 就一个数n 1 n 100 输出 一个数 即可能输出序列的总数目 样例 stack instack out35 123 132 213 231 321 分析 根据第一个数的出栈顺序来分类 如果操作数只有1个 那么输出序列的总数也只有1种 如果操作数有2个 那么输出序列的总数就有2种 即 如果操作数有3个 那么输出序列的总数就有5种 即 如果操作数有4个 那么输出序列的总数就有14种 即 如果操作数有5个 那么输出序列的总数就有42种 即 由此我们不难发现递推的规律 即有N个操作数时计算方法为 f n 2 f n 1 f 1 f n 2 f j f n j 1 f n 2 f 1