《问题解答专题.pptx》由会员分享，可在线阅读，更多相关《问题解答专题.pptx（103页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1问题解答专题问题解答专题基础题基础题第1页/共103页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.
2、04第2页/共103页2004p-12004p-1一个家具公司生产桌子和椅子。现在有113个单位的木材。每张桌子要使用20个单位的木材，售价是30元；每张椅子要使用16个单位的木材，售价是20元。使用已有的木材生产桌椅（不一定要把木材用光），最多可以卖元钱。20 x+16y113030+720=140130+520=130230+420=140330+320=150430+220=160530+020=150第3页/共103页2004p-275名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游
3、乐场总共收入700，可知有名儿童没有玩过其中任何一种。20*15=30035*10=35010*5=5075-55-10=10第4页/共103页2009t-22009t-2某个国家的钱币面值有1,7,72,73共计四种，如果要用现金付清10015元的货物，假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通张钱币。29+1+3+2=3529*343=681*49=193*7=-22*1=0第5页/共103页2009p-22009p-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;现在
4、要把这段程序分配到若干台（数量充足）用电缆连接的PC上做并行执行。每台PC执行其中的某几个语句，并可随时通过电缆与其他PC通讯，交换一些中间结果。假设每台PC每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在单位时间内执行完毕。注意：任意中间结果只有在某台PC上已经得到，才可以被其他PC引用。例如若语句4和6被分别分配到两台PC上执行，则因为语句6需要引用语句4的计算结果，语句6必须在语句4之后执行。5第6页/共103页2001p-12001p-1在a,b,c,d,e,f六件物品中，按下面的条件能选出的物品是：(1)a,b两样至少有一样(2)a,d不能同时取(3)a,e,f
5、中必须有2样(4)b,c要么都选，要么都不选(5)c,d两样中选一样(6)若d不选，则e也不选a,b,c,f假定取，根据（）则不取，根据（）也不取，根据（）取，根据（）取，最后（）矛盾假定都取，根据（）则不取，根据（）也不取，根据（）取，根据（）取，最后（）能做到第7页/共103页2004t-22004t-2已知a,b,c,d,e,f,g七个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“ab”开头写出你的安排方案：。a
6、bdfgec第8页/共103页2005p-2有3个课外小组：物理组，化学组和生物组。今有张、王、李、赵、陈、5名同学，已知张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员。如果要在3个小组分别选出3位组长，一位同学最多只能担任一个小组的组长，共有_种选择方案。张王李赵陈陈张王陈李王陈赵王陈李张陈赵张李赵王赵李王李赵张赵李张李张王赵张王第9页/共103页1998p-2某班有50名学生，每位学生发一张调查卡，上写a，b，c三本书的书名，将读过的书打，结果统计数字如下：只读a者8人；只读b者4人；只读c者3人；全部读过的有2人；读过a，b两本书的有4人；读过a，c两本书的有2人；读
7、过b，c两本书的有3人.（1）读过a的人数是()（2）一本书也没有读过的人数是()8+(4+2-2)=128+4+3+(4+2-2)+(3-2)=2050-20=30第10页/共103页1995p-51995p-5有红、黄、黑、白四色球各一个，放置在一个内存编号为1、2、3、4四个格子的盒中，每个格子放置一只球，它们的顺序不知。甲、乙、丙三人猜测放置顺序如下：甲：黑编号1，黄编号2；乙：黑编号2，白编号3；丙：红编号2，白编号4。结果证明甲乙丙三人各猜中了一半。写出四色球在盒子中放置情况及推理过程。1234黑黑红红白白黄黄假定：黑为1黄为2黑为2白为3红为2白为4黄为4第11页/共103页19
8、95t-21995t-2ABCD4312有标号为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号球匹配。请写出这四对球匹配的情况。1，22BB,C2，AAA,334DD第12页/共103页1998p-31998p-3任给自然数n，k(1K9)，按如下计算步骤求序列XJ
9、XJ-1X0的步骤：1.j=02.如果N=K则转第3步，否则转第7步3.Xj=NMODK4.N=NDIVK5.j=j+16.回第2步7.Xj=N8.结束试求当：N=1998，K=3时，XJXJ-1X0之值。2202000(三进制数)第13页/共103页排排 序序第14页/共103页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,
10、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基本思想：首先在所有数据中选最小的数据，把它与第一个数据交换；然后在其余的数据中再选出最小的数据与第二个数据交换，依次类推，直到全部排完。第15页/共103页 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:=（）
11、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-1i+1 to nk:=jki第16页/共103页排列组合排列组合第17页/共103页2008p-1 书架上有四本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这四本书摆在书架上，满足所有黑皮的书都排在一起的摆法有（）种。满足A必须比C靠左，所有红皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有（）种摆法。第18页/共103页2009p-1小陈现有2
12、个任务A，B要完成，每个任务分别有若干步骤如下：A=a1-a2-a3，B=b1-b2-b3-b4-b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如a2-b2-a3-b3是合法的，而a2-b3-a3-b2是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有种。70第19页/共103页排列组合+加法原理:B任务中的b1一定做，而
13、且肯定是第一个做的。除了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。第20页/共103页2002p-22002p-2将N个红球和M个黄球排成一行。例如:N=2,M=3可得到10种排法。问题:当N=4,M=3时有种不同排法?7!/(4!*3!)=35第21页/共103页2001p-2 平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同
14、直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？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第22页/共103页2001t-平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？21*10+21*15+21*5*6+10*15+10*6*7+15*5*7=2250第23页/共103页归纳归纳第24页/共103页1999p-21999p-2根据Nocomachns定
15、理，任何一个正整数n的立方一定可以表示成n个连续的奇数的和。例如：131233533791143=13+15+17+19在这里，若将每一个式中的最小奇数称为X，那么当给出n之后，请写出X与n之间的关系表达式。X=N2-N+1第25页/共103页1995p-41995p-4已知如下N*(N+1)/2个数据，按行的顺序存入数组A1，A2中：a11a21a22a31a32a33an1an2an3ann其中：第一个下标表示行，第二个下标表示列。若：aij(ij,j,i=1,2,n)存贮在Ak中，试问：k和i，j之间的关系如何表示？给定k值（kn*(n+1)/2)后，写出能决定相应的i，j值的算法。k=
16、(i-1)*i/2+jj:=k;i:=1;whilejidobeginj:=j-i;i:=i+1;end;第26页/共103页2002t-2n0=(k-1)nk+1设有一棵k叉树，其中只有度为0和k两种结点，设n0，nk，分别表示度为0和度为k的结点个数，试求出n0和nk之间的关系（n0=数学表达式，数学表达式仅含nk、k和数字）。n0=n2+1n0=2*n3+1n0=3*n4+1第27页/共103页1999t将Ln定义为求在一个平面中用n条直线所能确定的最大区域数目。例如：当n=1时，L1=2.进一步考虑，用n条折成角的直线（角度任意），放在平面上，能确定的最大区域数目Zn是多少？例如：当n
17、=1时，Z1=2（如下图所示）当给出n后，请写出以下的表达式：Ln=_Zn=_12Ln=n(n+1)/2+1(n0)Zn=L2n-2n=2n2-n+1第28页/共103页12345678910112=1+14=1+1+27=1+1+2+311=1+1+2+3+4第29页/共103页Zn=L2n-2n=2n2-n+1第30页/共103页2006t-22006t-2将边长为n的正三角形每边n等分，过每个分点分别做另外两边的平行线，得到若干个正三角形，我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最下面一行位于中间的小三角形。在通路中，只允许由一个小三角形走
18、到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上（图中是n=5时一条通路的例子）。设n=10，则该正三角形的不同的通路的总数为。第31页/共103页n=5时，方案有12344!n=10时，方案有1299!n=2时，方案有1种。n=3时，方案有2种。n=4时，方案有6种。第32页/共103页递递推推第33页/共103页2000p-22000p-2有2n的一个长方形方格，用一个12的骨牌铺满方格。例如n=3时，为23方格。此时用一个12的骨牌铺满方格，共有3种铺法：试对给出的任意一个n（n0），求出铺法总数的递推公式。对给出的任意一个n（n0），用F（n
19、）表示其铺法的总数的递推公式为:F（1）=1F（2）=2F（n）=F（n-2）+F（n-1）（n3）第34页/共103页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（N3）F（N2）F（N1）（N4）第35页/共103页2007p-2:最短路线最短路线 某城市的街道是一个很规整的矩形网络（见下图），有7条南北向的纵街，5条东西向的横街。现要从西南角的A走到东北角的B，最短的走法共有多少种？_21011111
20、111112345673610152128410203556845153570126210第36页/共103页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步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任
21、务A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有种。70第37页/共103页a3014102035a201361015a101234511111b1b2b3b4b5然后把a3那一行加起来1+4+10+20+35=70。第38页/共103页1998p-11998p-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、22，32，n2,求K和a1,a2,aK使得（A）式成立。当K=3,a1,a2,ak为a1=3,a2=-3,a3=1时。Un+=Un+Un+1Un第39页/共103页猜想是，则可得下列方程：展开可得：可得方程组：解得：a1=3,a2=-3,a3=1第40页/共103页递递归归第41页/共103页2007p-1:子集子集划分划分 将n个数（1，2，n）划分成r个子集。每个数都恰好属于一个子集，任何两个不同的子集没有共同的数，也没有空集。将不同划分方法的总数记为S(n,r)。例如，S(4,2)=7，这7种不同的划分方法依次为(1),(234)，(2),(134)，(3),(124)，(4),(12
23、3)，(12),(34)，(13),(24)，(14),(23)。当n=6，r=3时，S(6,3)=_。90第42页/共103页对任一元素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个子集。因此根据乘法原理，
24、划分数共有r*s(n-1,r)。第43页/共103页确定边界：首先不能把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。第44页/共103页varn,r:integer;functions(n,r:integer):longint;beginif(n1dobeginn1:=n1div3;三分法s1:=0;s2:=0;fori:=k+1tok+n1dos1:=s1+ai;fori:=k
25、+n1+1tok+2*n1dos2:=s2+ai;分别求前两组数据和ifs1=2*16x=43+4+4=11图中各顶点的度数总和是边数的2倍。第55页/共103页1999p-11999p-1在磁盘的目录结构中，我们将与某个子目录有关联的目录数称为度。如下图所示：该图表达了A盘的目录结构：D1，D11，均表示子目录的名字。在这里，根目录的度为2，D1子目录的度为3，D11子目录的度为4，D2，D12，D111，D112，D113的度均为1。若不考虑子目录的名字，则可简单的图示为如右边的树结构。现知道一个磁盘的目录结构中，度为2的子目录有2个，度为3的子目录有1个，度为4的子目录有3个。试问度为1
26、的子目录有几个？答：应把树结构看作图，并假设度为1的子目录有x个，则该图共有6+x个结点，共有5+x条边。就可以列出以下方程：2*(5+x)=3*4+1*3+2*2+x*1 解得x=9 第56页/共103页1997p-81997p-8下图中用点表示城市，点与点之间的联系表示城市间的 道路。试问：能否找出一条从A城市出发，经过图中所有道路一次后又回到出发点的通路来？能否从A出发，找出去每个城市且只去一次的通路来？若能，则写出通路，否则说明理由。EFABCD 能，全是偶点。只去一次的通路不存在。从A出发只能到达其中的3个点（每个点只能去一次），因此要找到这样的通路是不可能的。第57页/共103页一
27、笔画一笔画 只有当一个连通图的顶点全是偶点或仅有两个奇点时才能实现一笔画。（把无向图不重复地一笔画出）如果没有奇点，则可以从任意一点出发开始一笔画；此时图中存在经过每条边一次且仅一次的回路，称欧拉回路。如果仅有两个奇点，则可以从其中一个奇点出发一笔画。此时图中存在经过每条边一次且仅一次的路径，称欧拉路径。V1V3V2V4V1V3V2V4V1V3V2V4第58页/共103页1998t-31998t-3用邻接矩阵表示下面的无向图 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0
28、 0 0 1 1 1 0A=1当i与j两个结点相邻时0 当i与j两个结点不相邻时，或i=jAi，j=第59页/共103页2008p-22008p-2有6个城市，任何两个城市之间有一条道路连接，6个城市之间两两之间的距离如下表表示，则城市1到城市6的最短距离为_。城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市615125920第60页/共103页基本思想：设置两个顶点的集合S和T=V-S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点v0，然后不断从
29、集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改顶点v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入到S中为止。迪杰斯特拉算法是解决单源最短路径问题的贪心算法。第61页/共103页1383032V2:813-133032V1:13-13302220V3:13-192220V4:19终点从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj-2120V6:2051643203285623013717
30、9第62页/共103页vara:array1.20,1.20ofinteger;v:array1.20ofboolean;i,j,max,n,p:integer;flag:boolean;beginreadln(n);fori:=1tondoforj:=1tondoread(ai,j);fillchar(v,sizeof(v),false);v1:=true;源点forj:=2tondon-1次贪心beginmax:=maxint;fori:=1tondo寻找源点到其它顶点的最短权值ifnotviand(a1,i0)and(a1,imax)thenbeginmax:=a1,i;打擂台p:=i;
31、end;vp:=true;已求出标志fori:=1tondo更新权值if(a1,p0)and(ap,i0)thenif(a1,ia1,p+ap,i)or(a1,i=0)thena1,i:=a1,p+ap,i;end;fori:=2tondowrite(a1,i,);end.原来是无路的第63页/共103页123544294463650 4 29 4 02 0 0 0 30 6 0 0 40 0 0 0 60 0 4 0 04 11 4 7样例第64页/共103页有6个城市，任何两个城市之间有一条道路连接，6个城市之间两两之间的距离如下表表示，则城市1到城市6的最短距离为_。城市1城市2城市3城
32、市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市6151259200 2 3 0 8 100 0 3 0 5 100 0 0 0 5 80 0 0 0 0 7第65页/共103页2000p-12000p-1已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。第66页/共103页1998t-2给出一棵二叉树的中序遍历：DBGEACHFI与后序遍历：DGEBHIFCA,画出此二叉树。第67页/共103页2001t-1已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序
33、分别为：CBGEAFHDIJ与CGEBHFJIDA则该二叉树的先序遍历的顺序为()ABCEGDFHIJABDECGFHIJ第68页/共103页1996t-71996t-7下面是一个利用完全二叉树特性，用顺序表来存储的一棵二叉树，结点数据为字符型（结点层次号从小到大，同一层从左到右顺序存储，#表示空结点，表示存储数据结束）。现要求画出对应该存储结构的二叉树示意图。123456789101112131415第69页/共103页1997p-91997p-9为了便于处理表达式，常常将普通表达式（称为中缀表示）转换为前缀运算符在前，如X/Y写为/XY和后缀运算符在后，如X/Y写为XY/的表达形式。在这样
34、的表示中可以不用括号即可确定求值的顺序，如：（P+Q）*（R-S）*+PQ-RS或PQ+RS-*试将下面的表达式改写成前缀与后缀的表示形式：A+B*C/DA-C*D+BE试将下面的前缀表示还原成中缀的表示形式，同时写出后缀表示：+A*BC前缀式中表示一元运算符取负号，如A表示（-A）+A/*BCDABC*D/+-A*CDBEACD*-BE+中缀形式为：A+B*（C）；后缀形式为：ABC*+第70页/共103页标识符树标识符树1、标识符树的定义 将算术表达式用二叉树来表示，称为标识符树。2、标识符树的特点：（1）运算对象都是叶结点；（2）运算符都是根结点。3、从表达式产生标识符树的方法：（1）读
35、入表达式的一部分产生相应二叉树后，再读入运算符时，运算符与二叉树根结点的运算符比较优先级的高低：读入优先级高于根结点的优先级，则读入的运算符作为根的右子树，原来二叉树的右子树，成为读入运算符的左子树；读入优先级等于或低于根结点的优先级，则读入运算符作为树根，而原来二叉树作为它的左子树（2）遇到括号，先使括号内的表达式产生一棵二叉树，再把它的根结点连到前面已产生的二叉树根结点的右子树上去；（3）单目运算符+、-，加运算对象（表示0）。例如：-A，表示为：-A第71页/共103页4、应用举例（1）画出表达式：A*B*C的标识符树，并求它的前序序列和后序序列。*CBA前序序列：*A B C 后序序列
36、：A B*C*第72页/共103页（2）画出表达式：A*（B*C）的标识符树，并求它的前序序列和后序序列。B*C*A前序序列：*A*B C 后序序列：A B C*第73页/共103页（3）画出表达式：-A+B-C+D 的标识符树，并求它的前序序列和后序序列。+-+D-CBA前序序列：+A B C D后序序列：A B+C D+第74页/共103页（4）画出（A+（B-C）/（D+E）*（F+G-H）的标识符树，并求它的前序序列和后序序列。/A-CB+DE+*F-HG+前序序列：/+AB C*+D E+F G H后序序列：AB C+D E+F G+H*/第75页/共103页2002p-22002p
37、-2345213421532145324513425132415321543542132541如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列方案。32145345354第76页/共103页1997p-41997p-4设数组A10.100,20.100以行优先的方式顺序存储，每个元素占4个字节，且已知A10，20的地址为1000，则A50，90的地址是。142401000+（50-10）*（100-20+1）+（90-20）*4第77页/共1
38、03页其他其他第78页/共103页2006t-12006t-1将2006个人分成若干不相交的子集，每个子集至少有3个人，并且：（1）在每个子集中，没有人认识该子集的所有人。（2）同一子集的任何3个人中，至少有2个人互不认识。（3）对同一子集中任何2个不相识的人，在该子集中恰好只有1个人认识这两个人。则满足上述条件的子集最多能有个？第79页/共103页将2006个人分成若干不相交的子集，每个子集至少有3个人，并且：（1）在每个子集中，没有人认识该子集的所有人。（2）同一子集的任何3个人中，至少有2个人互不认识。（3）对同一子集中任何2个不相识的人，在该子集中恰好只有1个人认识这两个人。则满足上述
39、条件的子集最多能有个？20065401第80页/共103页2006p-2:2006p-2:取石子游戏取石子游戏取石子游戏取石子游戏现有5堆石子,石子数依次为3，5，7，19，50，甲乙两人轮流从任一堆中任取（每次只能取自一堆，不能不取）,取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略（即无论乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果.第81页/共103页为了解决这类一般情况，我们需要用到整数的二进位制，把m元数组a1，a2，am中的每一个分量用二进位制数表示，ai(1im)写在第i行，同时对齐二进位制数的位数，在列上作十进位制加法，其和写在第
40、(m+1)行，记为n1，n2，nj，nl，如果所有这些和数nj(1jl)均为偶数，我们称这个m元数组为偶数组；若nj(1jl)，中有一个数为奇数，则称之为非偶数组。例如：对于3元数组2，3，5；a12010a23011a3510122n1n2n3因为其中n1=1，所以2，3，5是非偶数组。同样，对于3元数组2，3，1：a1210a2311a310122n1n2由于nj(j=1，2)为偶数，则2，3，1为偶数组。第82页/共103页偶数组与非偶数组在T变换下具有如下性质：(1)偶数组经过一次T变换之后一定变为非偶数组；(2)对于非偶数组，一定可以找到某一个T变换，使其变为偶数组。这样我们容易判定
41、：如果给定的m元数组是偶数组，则后取者必有获胜策略；相反，若给定m元数组为非偶数组，则先取者有方法获胜，因为给定的m元数组为偶数组，先取者无论怎样取，只能将偶数组变为非偶数组，后取者则有策略将此时的非偶数组变为偶数组，由于每次取走石子，剩下石子数目一定越来越小，而0，0，0是偶数组，所以后取者获胜，同理可证相反情况。第83页/共103页例：有三堆石子，各堆数目分别是2、3、6，两人轮流取，取完的人为胜者，若甲先乙后，谁取胜？解：a12010a23011a36110131n1n2n3所以2，3，6为非偶数组，我们可以判定：先取者甲获胜，只需将a3=6变为1，可以验证2，3，1是偶数组第84页/共
42、103页应用：19010011700011150001013000011010010(18)10也就是，还要18才能变成“必负局”，所以501832所以第1次只能在第5堆石子中取32粒，使得取出32粒后为“必负局”。第85页/共103页例：桌上放着一堆小石子一共100颗，两人(甲、乙)轮流取，每次可以取1至10颗，取完的人为胜者，怎样才能取胜？容易看出11是取胜的关键数字，因为到此时，不论对方(甲)取多少颗(大于0且小于11)，总留下大于0且小于11颗石子，这样乙方一次取完即获得胜利。同样地分析，要取到11必须取到22，33，44，55，66，77，88，99，这样我们就知道了获胜之道：先取1
43、颗石子，留下99颗，然后对方取a(1a10)颗，己方取(11a)颗，就总能掌握这种致胜的关键数，从而确保获胜。如果对方先取，己方只需利用对方不知道其中奥秘，争取到一个致胜数，就总能依中方法取到下一个致胜数，最后取得胜利。下面是另一类游戏第86页/共103页2005t-22005t-2：取火柴游戏取火柴游戏取火柴游戏取火柴游戏取火柴游戏的规则如下：一堆火柴有N根，A、B两人轮流取出。每人每次可以取1根或2根，最先没有火柴可取的人为败方，另一方为胜方。如果先取者有必胜策略则记为1，先取者没有必胜策略记为0。当N分别为100，200，300，400，500时，先取者有无必胜策略的标记顺序为_（回答应
44、为一个由0或1组成的字符串）是取胜的关键数字第87页/共103页传球问题传球问题传球问题传球问题4个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方式？60第88页/共103页第89页/共103页设有棱长为1米的正四面体ABCD，一只蚂蚁从顶点A出发，遵循下列规则爬行：在每个顶点相交的3条棱中选一条，然后沿这条棱到另一个顶点。求蚂蚁爬行了7米路之后，又回到顶点A的方法总数。设从点A出发走过n米回到点A的走法为an种。由于从A出发走n-1米的走法共有3n-1种,其中有an-1种是走到A的，下一步一定离开A，
45、除去这an-1种，其它的每一种都可以再走1米到达A点。因此，an=3n-1-an-1。第90页/共103页一个学生暑假在A、B、C三个城市游览。他今天在这个城市，明天就到另一个城市。假设他第一天在A市，第五天又回到A市，问他有几种不同的游览方案？a1=0,a2=21-0=2,a3=22-2=2,A4=23-2=6.第91页/共103页出栈序列统计出栈序列统计出栈序列统计出栈序列统计【问题描述】栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作数序
46、列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，n，经过一系列操作可能得到的输出序列总数。【输入】就一个数n(1n100).【输出】一个数，即可能输出序列的总数目。【样例】stack.instack.out351 2 3,1 3 2,2 1 3,2 3 1,3 2 1第92页/共103页分析(根据第一个数的出栈顺序来分类)如果操作数只有1个，那么输出序列的总数也只有1种。如果操作数有2个，那么输出序列的总数就有2种。即：如果操作数有3个，那么输出序列的总数就有5种。即：如果操作数有4个，那么输出序列的总数就有14种。即：第93页/共103页如果操作数有5个，
47、那么输出序列的总数就有42种。即：第94页/共103页由此我们不难发现递推的规律，即有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。第95页/共103页vara:array0.50oflongint;n,j,i,m:longint;beginreadln(n);a1:=1;初值fori:=2tondobeginm:=ai-1*2;forj:=1toi-2dom:=m+aj*ai-j-1;ai:=m;end;writeln(an);end.第96页/共103页求路径数求路径数求路径数求路径数 一
48、个儿童从A进入如图所示的曲径，他有几条路径（最短）可以到达Y点？第97页/共103页整数分划问题整数分划问题整数分划问题整数分划问题将正整数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；第98页/共103页前面的几个例子中，问题本身都具有比较明显的递归关系，因而容
49、易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。第99页/共103页(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，可以分为两
50、种情况：(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的关系，考虑以下几种情况：第100页/共103页Varn:integer;functionq(a,b:integer):longint;beginif(a=1)or(b=1)thenq:=1elsebeginifabthenq:=q(a,b-1)+q(a-b,