试题解析.ppt

试题解析,【题目描述】五位好朋友相聚。第一位朋友带来了很多糖块赠送给各位朋友，使每人的糖块在各自原有的基础上翻了一倍；接着第二位好友也同样向每人赠送糖块，同样使每人的糖块在各自原有的数量基础上翻了一倍；第三、第四、第五位好友都照此方法操作。经过这样的赠送之后，每人的糖块恰好都为 n(n=32) 块。问各位好友原有的糖块数分别是多少?,【试题1:分糖果】,【题目分析】 由题意可知，第五个人分完以后，每个人糖块数都是32，并且其它四个人都是在原来基础上翻了一倍，故可以推算出第五个人分之前每个人的糖块数，依次倒推，可得解也。,1 2 3 4 5,【算法设计】,外循环,内循环,【例程】,program ex1; var sum,i,n:integer; num:array15 of integer; begin for n:=1 to 5 do numn:=32; 初始化 for n:=5 downto 1 do 处理五个人分发情况 begin sum:=0; 累加器清零 for i:=1 to 5 do 求四个接收者 if in then begin numi:=numi div 2; sum:=sum+numi; 求分发者分发出总量 end; numn:=numn+sum; 求分发者分发前总量 for i:=1 to 5 do write(numi:3,' '); writeln; end; end.,【题目描述】 某幼儿园里，有5个小朋友编号为：1、2、3、4、5，他们按自己的编号顺序围坐在一张圆桌旁。他们身上都有若干个糖果，现在他们做一个分糖果游戏。从1号小朋友开始，将他的糖果均分3份(如果有多余的，则他将多余的糖果吃掉），自己留1份，其余2份分给他的相邻的两个小朋友。接着2号、3号、4号、5号小朋友也这样做。问一轮后，每个小朋友手上分别有多少糖果(0=糖果数=1000）？,【试题2:分糖果】,【题目分析】 由题意可知，对于每个人的操作都是先平分三份，自己留一份，再将其它两份分给相邻的两个小朋友，所以从一号到五号顺序处理即可。,【算法设计】,【题目描述】 要求用户输入一个小写字母字符，求出该字母字符的前驱和后继字符，例如，c字符的前驱和后继分别是b和d，a字符的前驱和后继分别是z和b，z字符的前驱和后继分别是y和a。,【试题3:小写字母转盘】,【题目分析】 求前驱字母并不是简单地减1，如:a的前驱是z就不能通过减1来实现。在没有学条件控制之前，我们可以利用取余的特性，即任何一个整数除以26(26个字母)的余数只能在025之间。我们可以以z为参考点，首先求出输入的字符ch(假设是w)与z之间的字符偏移数n='z'-ch='z'-'w'=3，而(n+1) mod 26=4则是ch(字母w)的前驱字母相对于z的偏移数，'z'-(n+1) mod 26=122-4=118(即字母v)就是ch(字母w)的前驱字母。如下图:,求一个字母的后继也不是简单地加1就行，比如，z的后继是a就不能通过加1来实现。此时，可以a为参考点，首先求出输入的字符ch(假设是w)与a之间的字符偏移数n=ch-a=w-a=22，而(n+1) mod 26=23则是ch(字母w)的后继字母相对于a的偏移数，a+(n+1) mod 26=97+23=120(即字母x)就是ch(字母w)的后继字母。,a b c d e f g h i j k l m n o p q r s t u v w x y z,后继偏移数23,【问题描述】 输入两个数，按先后顺序分别代表x、y坐标，判断这两个数确定的点是否在给定的圆环内。圆环为圆心为(0,0)的同心圆。 【输入格式】 输入由两行组成。 第一行有两个数，分别表示横坐标和纵坐标。 第二行有两个数，表示圆环的下界和上界(上下界为平方数，如：1 9，分别表示半径为1的圆和半径为3的圆组成的圆环)。 【输出格式】 输出文件包含一行，TRUE或者FALSE，分别表示在与不在圆环内。,【试题:确定点位置】,【题目分析】,|OA|*|OA|=x*x+y*y,【试题:约瑟夫环】,【问题描述】 用循环线性链表解决约瑟夫问题。,【题目分析】,人员编号,指针：指向下一人,1,5,4,3,2,Next,5,4,3,2,1,Order,3,2/0,5,2/0,3,1,3,2/0,5,1,3,1,1,5,P,1,2/0,1,0,C,3,5,3,3,program joseph(input,output); const num=5; type node=record order:integer; next:integer; end; var circle:array1num of node; p,c,i,n,m:integer; begin m:=2; for i:=1 to num do begin circlei.order:=i; circlei.next:=i+1; end;,p:=i; c:=0;circlep.next:=1; while circlep.nextp do begin c:=c+1; if cm then p:=circlep.next else begin i:=circlep.next; circlep.next:=circlecirclep.next.next; circlei.order:=0; circlei.next:=0; c:=0; end; end; end.,【题目描述】数位求和,【试题:】,【题目描述】填充魔方阵,【试题:魔方阵】,何谓魔方阵？ 4 9 2 3 5 7 8 1 6 定义：由n*n个数字所组成的n阶方阵，具有各对角线，各横列与纵行的数字和都相等的性质，称为魔方阵。而这个相等的和称为魔术数字。若填入的数字是从1到n*n，称此种魔方阵为n阶正规魔方阵。,1.n = 2k + 1(奇数时)(k=1,2,3,4,5) (1)1放在第一行的中间位置上； (2)下一个数放在当前位置的上一行、下一列； (3)若当前位置是第一行，下一个数放在最后一行；若当前位置是最后一列，下一个数放在第一列； (4)若下一个数要放的位置上已经有了数字，则下一个数字放在当前位置的下一行，相同列。 根据此规则填充的3阶魔方阵如下：,2.n = 4k (4的整数倍时)(n=4,8,12,16k=1,2,3,4,5) 先说明一个定义： 互补：如果两个数的和，等于幻方最大数和最小数的和，即n*n+1，称为互补。 先看看4阶幻方的填法：将数字从左到右、从上到下按顺序填写：,这个方阵的对角线，已经用红色标出。将对角线上的数字，换成与它互补的数字。 这里，n*n+1 = 4*4+1 = 17； 把1换成17-1 = 16；把6换成17-6 = 11；把11换成17-11 = 6换完后就是一个四阶幻方。,对于n=4k阶幻方，我们先把数字按顺序填写。填好后，把它划分成k*k个4*4的方阵。因为n是4的倍数，一定能用4*4的小方阵分割。然后如同构造4阶幻方那样，把对角线上的数字换成与它互补的数字，就构成n阶幻方。 下面以8阶幻方的构造法为例： (1)先把数字按顺序填。然后，按4*4把它分割成2*2个小方阵；,(2)每个小方阵对角线上的数字，换成和它互补的数。,3.n = 4k + 2(n为偶数，且不能被4整除)(n=6，10，14，18，22; k=1，2，3，4，5) 这是三种里面最复杂的幻方。 以n=10为例。这时，k=2,(1) 把方阵分为A，B，C，D四个象限，这样每一个象限肯定是奇数阶。然后依次在A象限，D象限，B象限，C象限按奇数阶幻方的构造法填充。,(2)在A象限从中间格开始，按自左向右的方向，标记k个格。A象限的其它行则标记最左边的k个格。,(3)将A象限标记的格子和C象限中对应位置格子中的数字互换。,(4)在B象限从任一行的中间格，自右向左，标记出k-1列。,(5)将B象限标记的这些数，和D象限相对位置上的数进行交换，即可完成填充。,【题目描述】 现有一批战利品，数量为n（1=n=20），编号为1n。每一个战利品都有一定的体积v（1=v=100）和价值p（1=p=1000），假定你有一个总容量为s的背包，你可以在不超过背包容量的前提下随意从战利品中挑选m件战利品。编程序计算出能使自己所选战利品总价值最大的选择方案。 【输入输出样例】 输入： 12 4 3 4 4 5 5 7 8 10 输出： 1 2 3 16,【题目描述】 金明今天很开心，因为今天是他的生日，妈妈给了N元钱。今天一早，金明就开始做预算了，他从因特网上查到了M件物品的价格（每件物品的价格都不相同）。他希望从中购买一些物品能恰好将N元钱花完。请你帮助计算一下共有多少种不同的购物方案。 【输入文件】 第一行两个正整数N,M。第二行M个空格隔开的互不相等的正整数，表示M中物品的价格。 【输出文件】 一个正整数，为不同的购物方案数（所有数据都不超整形范围）。,【试题:购物(shopping.pas/c/cpp)】,样例： 输入文件：shopping.in 5 6 1 2 3 4 5 6 输出文件：shopping.out 3 样例说明：共3种方案： （1）a(1)+a(4)=1+4=5 （2）a(2)=a(3)=2+3=5 （3）a(5)=5,