《问题解答专题》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=1200 24000/30=8001200-800=400(加仑)400*1=400(美元),2.04,2004p-1,一个家具公司生产桌子和椅子。现在有113个单位的木材。每张桌子要使用20个单位的木材，售价是30元；每张椅子要使用16个单位的木材，售价是20元。使用已有的木材生产桌椅（不一定要把木材用光），最多可以卖 元钱。,20 x+16y113,030+720=140130+520=130230+420=140330+320=150430+220=160530+020=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会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“a b”开头写出你的安排方案：。,a b d f g e c,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(1K9)，按如下计算步骤求序列XJXJ-1X0的步骤：1.j=0 2.如果N=K 则转第3步，否则转第7步 3.Xj=N MOD K 4.N=N DIV K 5.j=j+1 6.回第2步 7.Xj=N 8.结束 试求当：N=1998，K=3时，XJXJ-1X0 之值。,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,基本思想：首先在所有数据中选最小的数据，把它与第一个数据交换；然后在其余的数据中再选出最小的数据与第二个数据交换，依次类推，直到全部排完。,const n=10;var a:array1.n of integer;k,i,j,temp:integer;begin randomize;for i:=1 to n do ai:=random(100);for i:=（）do begin k:=i;for j:=（）do if ajak then（）;if()then begin temp:=ak;ak:=ai;ai:=temp;end;end;for i:=1 to n do write(ai:3);writeln;end.,1 to n-1,i+1 to n,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 1 23 3 5 33 7 9 11 43=13+15+17+19 在这里，若将每一个式中的最小奇数称为X，那么当给出n之后，请写出X与n之间的关系表达式。,X=N2-N+1,1995p-4,已知如下N*(N+1)/2个数据，按行的顺序存入数组A1，A2中：a11a21 a22a31 a32 a33an1 an2 an3 ann其中：第一个下标表示行，第二个下标表示列。若：aij(ij,j,i=1,2,n)存贮在Ak中，试问：k和i，j之间的关系如何表示？给定k值（kn*(n+1)/2)后，写出能决定相应的i，j值的算法。,k=(i-1)*i/2+j,j:=k;i:=1;while ji do begin j:=j-i;i:=i+1;end;,2002t-2,n0=(k-1)nk+1,设有一棵k叉树，其中只有度为0和k两种结点，设n 0，n k，分别表示度为0和度为k的结点个数，试求出n 0 和n k之间的关系（n 0=数学表达式，数学表达式仅含n k、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(n0)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时，方案有12344!,n=10时，方案有1299!,n=2时，方案有1种。n=3时，方案有2种。n=4时，方案有6种。,递推,2000p-2,有2n的一个长方形方格，用一个12的骨牌铺满方格。例如n=3时，为23方格。此时用一个12的骨牌铺满方格，共有3种铺法：试对给出的任意一个n（n0），求出铺法总数的递推公式。,2000t-2,设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当n=3时，共有4种走法，即1+1+1,1+2,2+1,3。,F（1）1 F（2）2 F（3）4F（N）F（N3）F（N2）F（N1）（N4）,2007p-2:最短路线,某城市的街道是一个很规整的矩形网络（见下图），有7条南北向的纵街，5条东西向的横街。现要从西南角的A走到东北角的B，最短的走法共有多少种？_,210,1111,1 1 1 1 1 1,2 3 4 5 6 7,3 6 10 15 21 28,4 10 20 35 56 84,5 15 35 70 126 210,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,a3 0 1 4 10 20 35 a2 0 1 3 6 10 15a1 0 1 2 3 4 5 1 1 1 1 1 b1 b2 b3 b4 b5然后把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）都满足U n+2=Un+1+Un。试对数列12，22，32，n2,求K和a1,a2,aK使得（A）式成立。,当K=3,a1,a2,ak为a1=3,a2=-3,a3=1时。,U n+=Un+Un+1Un,猜想是，则可得下列方程：,展开可得：,可得方程组：,解得：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个集合中去，即rn时,s(n,r)=0；再者，把n个元素放进一个集合或把n个元素放进n个集合，方案数显然都是，即r=1或r=n时,s(n,r)=1。,var n,r:integer;function s(n,r:integer):longint;begin if(nr)or(r=0)then s:=0 else if(r=1)or(r=n)then s:=1 else s:=s(n-1,r-1)+r*s(n-1,r)end;begin readln(n,r);writeln(s(n,r)；end.,2002t-1,在书架上放有编号为1,2,n的n本书。现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：n=3时：原来位置为：1 2 3 放回去时只能为：3 1 2 或 2 3 1 这两种 问题：求当n=5时满足以上条件的放法共有多少种?,44种,解：第一步：第一本书不放在原来的第一个位置，有n-1种放法。第二步：假设第一本书放在第2个位置，则第二本书的放法又可以分为两类：第一类，第二本书恰好放在第一个位置，则余下的 n-2本书有An-2种放法；第二类，第二本书不放在第一个位置，则就是第二本书不放在第一个位置，第三本书不放在第三个位置，第四本书不放在第四个位置，第n本书不放在第n个位置，所以有An-1种放法。由分步计数原理和分类计数原理，我们便得到了递归公式：边界：,var n:integer;function d(n:integer):longint;begincase n of1:d:=0;2:d:=1;else d:=(n-1)*(d(n-1)+d(n-2);end;end;beginreadln(n);writeln(d=,d(n);end.,分治,1996p-9,已知：A1，A2，A81 共有81个数，其中只有一个数比其它数大，要用最少的比较运算次数，把这个值大的数找出来（假设两个数比较一次能决定出大于、小于或等于这三种情况），请将以下算法补充完整：,const n=81;var a:array1.n of integer;m,n1,i,k,k0,s1,s2:integer;begin for i:=1 to n do ai:=10;randomize;k0:=random(81)+1;ak0:=ak0+1;writeln(number=,ak0);测试数据 n1:=n;k:=0;while n11 do begin n1:=n1 div 3;三分法 s1:=0;s2:=0;for i:=k+1 to k+n1 do s1:=s1+ai;for i:=k+n1+1 to k+2*n1 do s2:=s2+ai;分别求前两组数据和 if s1s2 then k:=k+n1 else if s1=s2 then k:=k+2*n1;确定大数在哪一组 end;writeln(ak+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中为止。,迪杰斯特拉算法是解决单源最短路径问题的贪心算法。,1383032V2:8,13-133032V1:13,-13302220V3:13,-192220V4:19,-2120V6:20,32,var a:array1.20,1.20 of integer;v:array1.20 of boolean;i,j,max,n,p:integer;flag:boolean;begin readln(n);for i:=1 to n do for j:=1 to n do read(ai,j);fillchar(v,sizeof(v),false);v1:=true;源点 for j:=2 to n do n-1次贪心 begin max:=maxint;,for i:=1 to n do寻找源点到其它顶点的最短权值 if not viand(a1,i0)and(a1,i0)and(ap,i0)then if(a1,ia1,p+ap,i)or(a1,i=0)then a1,i:=a1,p+ap,i;end;for i:=2 to n do write(a1,i,);end.,原来是无路的,1,2,3,5,4,4,29,4,4,6,3,6,50 4 29 4 02 0 0 0 30 6 0 0 40 0 0 0 60 0 4 0 0,4 11 4 7,样例,有6个城市，任何两个城市之间有一条道路连接，6个城市之间两两之间的距离如下表表示，则城市1到城市6的最短距离为_。,0 2 3 0 8 10,0 0 3 0 5 10,0 0 0 0 5 8,0 0 0 0 0 7,2000p-1,已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。,1998t-2,给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历：DGEBHIFCA,画出此二叉树。,2001t-1,已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA则该二叉树的先序遍历的顺序为(),ABCEGDFHIJ,1996t-7,下面是一个利用完全二叉树特性，用顺序表来存储的一棵二叉树，结点数据为字符型（结点层次号从小到大，同一层从左到右顺序存储，#表示空结点，表示存储数据结束）。现要求画出对应该存储结构的二叉树示意图。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,1997p-9,为了便于处理表达式，常常将普通表达式（称为中缀表示）转换为前缀运算符在前，如X/Y写为/XY 和后缀 运算符在后，如X/Y写为XY/的表达形式。在这样的表示中可以不用括号即可确定求值的顺序，如：（P+Q）*（R-S）*+PQ-RS 或 PQ+RS-*试将下面的表达式改写成前缀与后缀的表示形式：A+B*C/D A-C*D+BE 试将下面的前缀表示还原成中缀的表示形式，同时写出后缀表示：+A*BC 前缀式中表示一元运算符取负号，如A表示（-A）,+A/*BCD,ABC*D/+,+-A*CDBE,ACD*-BE+,中缀形式为：A+B*（C）；后缀形式为：ABC*+,标识符树,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,34521 34215 32145 32451 34251 32415 32154 35421 32541,如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列方案。,3 4 5 3 5 4,1997p-4,设数组A10.100,20.100 以行优先的方式顺序存储，每个元素占4个字节，且已知A10，20的地址为1000，则A50，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 个人认识这两个人。则满足上述条件的子集最多能有 个？,20065401,2006p-2:取石子游戏,现有5堆石子,石子数依次为3，5，7，19，50，甲乙两人轮流从任一堆中任取（每次只能取自一堆，不能不取）,取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略（即无论乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果.,为了解决这类一般情况，我们需要用到整数的二进位制，把m元数组a1，a2，am中的每一个分量用二进位制数表示，ai(1im)写在第i行，同时对齐二进位制数的位数，在列上作十进位制加法，其和写在第(m+1)行，记为n1，n2，nj，nl，如果所有这些和数nj(1jl)均为偶数，我们称这个m元数组为偶数组；若nj(1jl)，中有一个数为奇数，则称之为非偶数组。例如：对于3元数组2，3，5；a1 2 0 1 0 a2 3 0 1 1 a3 5 1 0 1 22 n1 n2 n3 因为其中n1=1，所以2，3，5是非偶数组。同样，对于3元数组2，3，1：a1 2 1 0 a2 3 1 1 a3 1 0 1 22 n1n2 由于nj(j=1，2)为偶数，则2，3，1为偶数组。,偶数组与非偶数组在T变换下具有如下性质：(1)偶数组经过一次T变换之后一定变为非偶数组；(2)对于非偶数组，一定可以找到某一个T变换，使其变为偶数组。这样我们容易判定：如果给定的m元数组是偶数组，则后取者必有获胜策略；相反，若给定m元数组为非偶数组，则先取者有方法获胜，因为给定的m元数组为偶数组，先取者无论怎样取，只能将偶数组变为非偶数组，后取者则有策略将此时的非偶数组变为偶数组，由于每次取走石子，剩下石子数目一定越来越小，而0，0，0是偶数组，所以后取者获胜，同理可证相反情况。,例：有三堆石子，各堆数目分别是2、3、6，两人轮流取，取完的人为胜者，若甲先乙后，谁取胜？,解：a1 2 0 1 0 a2 3 0 1 1 a3 6 1 1 0 1 3 1 n1 n2 n3 所以2，3，6为非偶数组，我们可以判定：先取者甲获胜，只需将a3=6变为1，可以验证2，3，1是偶数组,应用：19 0100117 0001115 0001013 000011 010010(18)10也就是，还要18才能变成“必负局”，所以501832 所以第1次只能在第5堆石子中取32粒，使得取出32粒后为“必负局”。,例：桌上放着一堆小石子一共100颗，两人(甲、乙)轮流取，每次可以取1至10颗，取完的人为胜者，怎样才能取胜？,容易看出11是取胜的关键数字，因为到此时，不论对方(甲)取多少颗(大于0且小于11)，总留下大于0且小于11颗石子，这样乙方一次取完即获得胜利。同样地分析，要取到11必须取到22，33，44，55，66，77，88，99，这样我们就知道了获胜之道：先取1颗石子，留下99颗，然后对方取a(1a10)颗，己方取(11a)颗，就总能掌握这种致胜的关键数，从而确保获胜。如果对方先取，己方只需利用对方不知道其中奥秘，争取到一个致胜数，就总能依中方法取到下一个致胜数，最后取得胜利。,下面是另一类游戏,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(1n100).【输出】一个数，即可能输出序列的总数目。【样例】stack.instack.out 3 5,1 2 3,1 3 2,2 1 3,2 3 1,3 2 1,分析(根据第一个数的出栈顺序来分类)如果操作数只有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）初始条件f（1）=1。,var a:array0.50of longint;n,j,i,m:longint;begin readln(n);a1:=1;初值 for i:=2 to n do begin m:=ai-1*2;for j:=1 to i-2 do m:=m+aj*ai-j-1;ai:=m;end;writeln(an);end.,求路径数,一个儿童从A进入如图所示的曲径，他有几条路径（最短）可以到达Y点？,整数分划问题,将正整数n表示成一系列正整数之和，n=n1+n2+.+nk，其中n1=n2=.=nk=1,k=1。正整数n的这种表示称为正整数n的划分。正整数n的不同的划分个数称为正整数n的划分数，记作P(n)例如正整数6有如下11种不同的划分，所以p(6)=11。6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1；,前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。,(1)当n=1时，不论m的值为多少（m0)，只有一种划分即1;(2)当m=1时，不论n的值为多少，只有一种划分即n个1，1,1,1,.,1;(3)当n=m时，根据划分中是否包含n，可以分为两种情况：(a)划分中包含n的情况，只有一个即n；(b)划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有(n-1)划分。因此 f(n,n)=1+f(n,n-1);(4)当nm时，根据划分中是否包含最大值m，可以分为两种情况：(a)划分中包含m的情况，即m,x1,x2,.xi,其中x1,x2,.xi的和为 n-m，其中可能再次出现m，因此是（n-m）的m划分，因此这种划分 个数为f(n-m,m);(b)划分中不包含m的情况，则划分中所有值都比m小，即n的(m-1)划 分，个数为f(n,m-1);因此 f(n,m)=f(n-m,m)+f(n,m-1);,根据n和m的关系，考虑以下几种情况：,Var n:integer;function q(a,b:integer):longint;begin if(a=1)or(b=1)then q:=1 else begin if ab then q:=q(a,b-1)+q(a-b,b);end;end;begin read(n);writeln(q(n,n);end.,var n,i,j:integer;a:array0.100 of integer;procedure sum(kx:integer);kx指向要拆分的