JAVA算法题目集合.doc

程序习题:A:基础题B:深入题C:综合题A1.取两个数的最小公倍数/最大公约数并显示。（1）两种方法：穷举方法（2）先用碾除法求出最大公约数，在用n*m/k求出最小公倍数2.百鸡百脚（穷举法）每只母鸡3元,公鸡4元,小鸡0.5元每只,请问如何100块买100只鸡.苹果 1元/个， 桔子 2 元/个， 芒果 4元/个，若是用10元去买，有几种组合呢？已知有三个苹果,五个橙子,六个草莓.从中选出8个水果,满足一下条件:1.至少有一个橙子2.橙子数目不小于苹果,不多于草莓3.判断是否为质数（素数，通过循环判断）求100以内所有的质数求N以内所有的质数4.求一个三位数每个位数上的数字.（水仙花数字）三位数中有些满足:其每个位数的立方的和等于其自身,求出这些数.金额大小写转换。输入小写的数字金额形式，将其转换成大写的金额形式。（条件判断）金额的大小写转换，可以先定义两个文本串，一个用于存放大写的数字，比如：壹，贰，参等；一个用存放对应每一个金额数字位的名称，比如：分，角，元，拾，佰等。转换时，只要找出每一个小写数字的对应大写形式和它的数字位名称即可。6.找数组中最大/最小的数给歌手打分:在歌星大奖赛中，有10个评委为参赛的选手打分，分数为1100分。选手最后得分为：去掉一个最高分和一个最低分后，其余8个分数的平均值。现求出其中一个歌手的最后得分。输入10个分数，传入到一个数组中，排序，计算1-8的总和/87.折半查找:设查找元素储存在一个一维数组中，已经按关键字递增（或递减）的方式排列的情况下，可进行折半查找，其方法是：首先将要查的关键字值与数组中间位置上的记录的关键字比较。1 若相等，则查找成功；2 若大于中间位置的关键字则说明要查记录只可能在后半段中，下一步应在后半部分再进行折半查找；8.显示所有位数不超过8位的其平方具有对称性质的数(也称回文数)。 例如：1111=121，121就是回文数。对于要判断的数，计算出其平方后，将平方的每一位进行分解,再按从低到高的顺序将这些分解出来的数恢复成一个数K(如n=13，则a=169，且k=961)，若a等于k则可判定n为回文数。9.8:猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个,第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少。采取逆向思维的方法，从后往前推断。9:10:给出三角形的三个边长为a，b，c，求三角形的面积。提示：根据海伦公式来计算三角形的面积： S(a+b+c)/2；Area s(s-a)(s-b)(s-c) 1输入的三角形三边长a,b,c要满足“任意两边长的和大于第三边长”。 2按海伦公式计算： s=（a+b+c）/2；x=s*(s-a)*(s-b)*(s-c) 这时若x=0，则求面积：area=X ，并输出area的值。条件判断，要考虑多种条件11:将5，6，7，8，9添加下面的空格里，使他们的积有最大值。_ _ _ _ _使用穷举法，把5个数字循环判断放入数组，最大的值就是要找的值。B1.组合找出从自然数1，2，. n中任取r个数的组合。例如n=5，r=3。hint:可用这样的递归思想来考虑组合函数的算法，设子程序计算分组子程序(m，k) 即找出自然数1，2.m中任取k个数的所有组合。当组合的第一个数字选定时，其后面的数字是从余下的m-1个数中取k-1个数的所有组合。【问题】 组合问题 问题描述：找出从自然数1、2、n中任取r个数的所有组合。例如n=5，r=3的所有组合为： （1）5、4、3 （2）5、4、2 （3）5、4、1 （4）5、3、2 （5）5、3、1 （6）5、2、1 （7）4、3、2 （8）4、3、1 （9）4、2、1 （10）3、2、1 分析所列的10个组合，可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、m中任取k个数的所有组合。当组合的第一个数字选定时，其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a 存放求出的组合的数字，约定函数将确定的k个数字组合的第一个数字放在ak中，当一个组合求出后，才将a 中的一个组合输出。第一个数可以是m、m-1、k，函数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未去顶组合的其余元素，继续递归去确定；或因已确定了组合的全部元素，输出这个组合。细节见以下程序中的函数comb。 【程序】 # include # define MAXN 100 int aMAXN; void comb(int m,int k) int i,j; for (i=m;i=k;i-) ak=i; if (k1) comb(i-1,k-1); else for (j=a0;j0;j-) printf(“%4d”,aj); printf(“n”); void main() a0=3; comb(5,3); 2.冒泡排序 选择排序 局部有序排序3求35的阶乘问题描述：编写程序，对给定的n（n100），计算并输出k的阶乘k！（k=1，2，n）的全部有效数字。 由于要求的整数可能大大超出一般整数的位数，程序用一维数组存储长整数，存储长整数数组的每个元素只存储长整数的一位数字。如有m位成整数N用数组a 存储： N=am10m-1+am-110m-2+ +a2101+a1100 并用a0存储长整数N的位数m，即a0=m。按上述约定，数组的每个元素存储k的阶乘k！的一位数字，并从低位到高位依次存于数组的第二个元素、第三个元素。例如，5！=120，在数组中的存储形式为： 3 0 2 1 首元素3表示长整数是一个3位数，接着是低位到高位依次是0、2、1，表示成整数120。 计算阶乘k！可采用对已求得的阶乘(k-1)！连续累加k-1次后求得。例如，已知4！=24，计算5！，可对原来的24累加4次24后得到120Java ： 应用大整数BigInteger 4.1到9九个数字任意组合成一个三行三列的九宫，使每行每列每一斜行的和都相同。通过此算法计算出所有结果。思路：（1）得到所有可能组合信息（3*3），赋值1-9 （9*9 循环） （2）判断得到所有满足要求数组5.构造 4行、4列的拉丁方阵，使方阵中的每一行和每一列中数字1到4只出现一次。 4阶拉丁方阵见如下：1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3构造拉丁方阵的方法很多，这里给出最简单的一种方法。观察给出的例子，可以发现：若将每一行中第一列的数字和最后一列的数字连起来构成一个环，则该环正好是由1到4顺序构成；对于第i行，这个环的开始数字为i。按照此规律可以很容易的写出程序。思路：（1）赋值（组合） （4*4） (2) 判断 （每一行判断）6.在直角三角形中，两个直角边的平方和等于斜边的平方，也就是非常著名的“勾股定理”，那么这100以内的数字中，就存在着这样的一些数，比如：3，4，5，3的平方加上4的平方等于5的平方，这三个数就可以组成一个直角三角形。现在我们要求出这些数（要求相同度数的直角三角形的三条边使用最小值，比如：6，8，10就要变成3，4，5）。首先设法得到从3到100之间的数的两组合。利用二重循环可以达到这一目的。令外循环变量为A，A从1到99。令内循环的循环变量为B，B从A+1到100。然后在循环体内判断A和B是否满足等式（1）。将满足等式的A和B及C打印出来。为了缩短机器运算时间，我们可以利用勾股数的奇偶特性。即在A和B中一个是奇数，另一个必定是偶数。那么可以让B从A+1开始，每次增加步长为2。因为A若是奇数，A+1就是偶数。以后步长是2，B总是为偶数。如果A是偶数，A+1就是奇数。以后步长是2，B总为奇数。我们用整型变量循环变量1、循环变量2、变量分别代表A、B、C。7.随机取一定范围内的指定数量不重复数，比如从1-100中随机取30个不重复数字。使用排除法，先初始化范围，然后放到一个数组中，取出一个后，将这个位置的内容删除，那么下次就不会再重复取了，随机取的不是数字，而是位置。8奶牛问题:一个农场有头母牛，现在母牛才一岁，要到四岁才能生小牛，四岁之后，每年生一头小牛。假设每次生的都是母牛，并且也遵守4年才生育并生母牛的原则，并且无死亡，问： N年后共有多少头牛？1，2，4，8，16.9.美丽的莱茵河畔，每边都分布着5个城市，两边的城市都是唯一对应的友好城市，现需要在友好城市开通航线以加强往来。但因为莱茵河常年大雾,如果开设的航线发生交叉现象就有可能出现碰船的现象。现在要求近可能多地开通航线并且使航线不能相交！求出最多能开通的航线数和城市？分析:用一个数组来存放对应的友好城市的代码和友好城市的对数，然后在规划时先从倒数第二个城市开始，找出可以设置的航线条数和下一条航线开始的城市。如果正在规划的城市的航线数大于已知的航线条数，则存储这个航线条数和城市的代码，这样一直找下去，把最多的航线数都找出来，最后把最多的航线数和对应的友好城市显示出来。10:任意给出从1到N的一个自然数，求出这N个自然数的各种全排列。如N=3时，共有以下6种排列方式：123，132，213，231，312，321。应用回溯法，每个数的取法都有N个方向（1N），当取够N个数时，输出一个排列，然后退后一步，取前一个数的下一个方向（即前一个数+1），并且要保证所有数字不能重复。当前数字的所有方向都取完时，继续退一步，一直重复到第一个数为止。public class AllShunXu static String str = 12345;static char a = str.toCharArray();static int n = 5;static void swap(int arg1, int arg2) char temp;temp = aarg1;aarg1 = aarg2;aarg2 = temp;static void sort(int index) int i;if (index = n) for (i = 0; i n; i+) System.out.print(ai);System.out.println();return;for (i = index; i n; i+) swap(index, i);sort(index + 1);swap(index, i);public static void main(String args) for (int s = 0; s n; s+) sort(s);package com.syj.csdn; import java.util.ArrayList; import java.util.Arrays; import java.util.List; /* * * Title:全排列算法 * * * * Copyright: /sunyujia/ * * * author 孙钰佳 * main * date 2009-04-25 23:57:23 PM */ public class FullSort /将NUM设置为待排列数组的长度即实现全排列 private static int NUM = 3; /* * 递归算法：将数据分为两部分，递归将数据从左侧移右侧实现全排列 * * param datas * param target */ private static void sort(List datas, List target) if (target.size() = NUM) for (Object obj : target) System.out.print(obj); System.out.println(); return; for (int i = 0; i b - c -a 。倒酒的规则如下：1) 按a - b - c -a的顺序。 2) b倒空后才能从a中取。 3) c装满后才能向a中倒。22:随机出现十种物品，每个重量100千克以内。设定一个背包的载重上限，计算出一种装物品的方法使物品重量正好等于背包载重上限。对每个物品考虑选择放入和不放入背包两种情况。首先，考查物品被放入的情况，这种可能性当且仅当包含它不会超出背包上限时才是可行的。继续考查下一个物品。其次，还要考查物品不被放入背包的情况，这种可能性当且仅当不包含物品其它物品也能找到合理的组合。考查完物品后，继续考查下一个物品依次类推，最终找到一个合理组合或没有合理组合。23:日本一位中学生发现一个奇妙的“定理”，请角谷教授证明，而教授无能为力，于是产生角谷猜想。猜想的内容是：任给一个自然数，若为偶数除以2，若为奇数则乘3加1，得到一个新的自然数后按照上面的法则继续演算，若干次后得到的结果必然为1。判断给定的一个自然数，若为偶数除以2，若为奇数则乘3加1，得到一个新的自然数后按照上面的法则继续演算，一直到结果变为1，并且将每一步的运算过程和得到的新的自然数显示出来。24:某人有四张3分的邮票和三张5分的邮票，用这些邮票中的一张或若干张可以得到多少种不同的邮资？将问题进行数学分析，不同张数和面值的邮票组成的邮资可用下列公式计算：S=3*i+5*j，其中i为3分邮柰的张数，j为5分的张数，按题目的要求，3分的邮票可以取0、1、2、3、4张，5分的邮票可以取0、1、2、3张。采用穷举方法进行组合，可以求出这些不同面值不同张数的邮标组合后的邮资。25:一辆重型卡车欲穿过1000公里的沙漠，卡车耗油为1升/公里，卡车总载油能力为500公升。显然卡车一次是过不了沙漠的。因此司机必须设法在沿途建立几个储油点，使卡车能顺利穿越沙漠。试问司机如何建立这些储油点？每一储油点应存多少油，才能使卡车以消耗最少油的代价通过沙漠？编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。No. Distance(k.m.) oil(litre) 1 X X X X 2 X X X X 3 X X X X. . .设disi为第i个贮油点至终点(i=0)的距离； oili为第i个贮油点的存贮油量；我们可以用倒推法来解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及存油量。26:将一个正整数分解质因数。将一个正整数分解质因数表示成素数的乘积，并显示。对n进行分解质因数，应先找到一个最小的质数k，然后按下述步骤完成：(1) 如果这个质数恰等于n，则说明分解质因数的过程已经结束。(2) 如果nk，但n能被k整除，则应显示出k的值，并用n除以k的商，作为新的正整数, 重复执行第一步。(3) 如果n不能被k整除，则用k+1作为k的值，重复执行第一步。 27:把十进制数转换成二进制数并显示。 将十进制数转换成二进制数，一般采用除二取余法。如果用一个数组b来存入二进制数，可以依次把所得的余数存入b0，b1，bn，最后按bn，bn-1，b1，b0的顺序输出这些余数，就得到了相应的二进制数。并显示。将任意的一个正整数进行2-36进制之间的转换。28:计算任何一天是星期几。最常见的公式：W = Y-1 + (Y-1)/4 - (Y-1)/100 + (Y-1)/400 + D，Y是年份数，D是这一天在这一年中的累积天数，也就是这一天在这一年中是第几天。蔡勒（Zeller）公式：“w=y+y/4+c/4-2c+26(m+1)/10+d-1公式中的符号含义如下，w：星期；c：世纪-1；y：年（两位数）； m：月（m大于等于3，小于等于14，即在蔡勒公式中，某年的1、2月要看作上一年的13、14月来计算，比如2003年1月1日要看作2002年的13月1日来计算）；d：日； 代表取整，即只要整数部分。27:中国有句俗语叫“三天打鱼两天晒网”。某人从1990年1月1日起开始“三天打鱼两天晒网”。问这个人在以后的某一天中是“打鱼”还是“晒网”。根据题意可以将解题过程分为三步：1)计算从1990年1月1日开始至指定日期共有多少天；2)由于“打鱼”和“晒网”的周期为5天，所以将计算出的天数用5去除；3)根据余数判断他是在“打鱼”还是在“晒网”； 若余数为1，2，3，则他是在“打鱼” 否则是在“晒网” 在这三步中，关键是第一步。求从1990年1月1日至指定日期有多少天，要判断经历年份中是否有闰年，二月为29天，平年为28天。闰年的方法可以用伪语句描述如下： 如果 (年能被4除尽 且 不能被100除尽)或 能被400除尽) 则 该年是闰年； 否则 不是闰年。28:求九位累进可除数。所谓九位累进可除数就是这样一个数：这个数用1到9这九个数字组成，每个数字刚好只出现一次。这个九位数的前两位能被2整除，前三位能被3整除.前N位能被N整除，整个九位数能被9整除。问题本身可以简化为一个穷举问题：只要穷举每位数字的各种可能取值，按照题目的要求对穷举的结果进行判断就一定可以得到正确的结果。 问题中给出了“累进可除”这一条件，就使得我们可以在穷举法中加入条件判断。在穷举的过程中，当确定部分位的值后，马上就判断产生的该部分是否符合“累进可除”条件，若符合，则继续穷举下一位数字；否则刚刚产生的那一位数字就是错误的。这样将条件判断引入到穷举法之中，可以尽可能早的发现矛盾，尽早地放弃不必要穷举的值，从而提高程序的执行效率。为了达到早期发现矛盾的目的，不能采用多重循环的方法实行穷举，那样编出的程序质量较差。程序中使用的算法不再是穷举法，而是回朔法。29九连环游戏是中国人自己发明的，它的历史非常悠久，据说是起源于战国时期。九连环主要是由一个框架和九个圆环组成：每个圆环上连有一个直杆，而这个直杆则在后面一个圆环内穿过，九个直杆的另一端用一块木板或圆环相对固定。计算九连环游戏中取下某一个环需要几步？正确的拆解是先以第 9 环为目标，先拆下它，简化为拆一个 8 连环。接着再以第 8 环为目标，拆下它，简化为拆一个 7 连环。以此类推，直至全部拆解。深刻的理解了上面所说的规律后，就会发现，安装上第 9 环后，问题可以被简化为装一个 7 连环，而当装上第 7 环后，问题就被简化为装一个 5 连环了.,最后找出九连环跟递归一定有联系。那么整个游戏所需步数=取下第1个环所需步数+.+取下第9个环所需步数。我们就用递归来实现这个问题。30公安人员审问四名窃贼嫌疑犯。已知，这四人当中仅有一名是窃贼，还知道这四人中每人要么是诚实的，要么总是说谎的。在回答公安人员的问题中：甲说：“乙没有偷，是丁偷的。”乙说：“我没有偷，是丙便的。” 丙说：“甲没有偷，是乙偷的。”丁说：“我没有偷。”请根据这四人的答话判断谁是盗窃者。假设A、B、C、D分别代表四个人，变量的值为1代表该人是窃贱。 由题目已知：四人中仅有一名是窃贱，且这四个人中的每个人要么说真话，要么说假话，而由于甲、乙、丙三人都说了两句话：“X没偷，X偷了”，故不论该人是否说谎，他提到的两人中必有一人是小偷。故在列条件表达式时，可以不关心谁说谎，谁说实话。这样，可以列出下列条件表达式：甲说：”乙没有偷，是丁偷的。”B+D=1乙说：“我没有偷，是丙偷有。”B+C=1丙说：“甲没有偷，是乙偷的。”A+B=1丁说：“我没有偷。”A+B+C+D=1其中丁只说了一句话，无法判定其真假，表达式反映了四人中仅有一名是窃贱的条件。根据上面所列出的公式可以编程找出窃贼。31.按递增次序生成集合M的最小的n个数。M定义如下：（1）1M（2）若xM，则2x+1M,3x+1M（3）无别的数属于M 表示属于。要生成数组M中的最小的n个数，首先1为这n个数中的第一个数，再由1递推出余下的n-1个数。设n个数在数组M中，2x+1与3x+1均做为一个队列，从两队列中选一排头（数值最小者）送入数组M中，所谓“排头”就是队列中尚未选入M的第一个小的数.用“下标变量2”表示2x+1这一列的排头，用下标变量3表示3x+1这一列的排头。通过上面规律可以推导出结果。32:一个农夫带着一只狼，一只羊和一些菜过河。河边只有一条渔船，由 于船太小，只能装下农夫和他的一样东西。在无人看管的情况下，狼要吃羊，羊 要吃菜；请问农夫如何才能使三样东西平安过河。只求出一种方案即可。 只要分清楚狼羊菜三者之间的关系，可以通过判断目前状态，来确定下一步走法。33:设有n个城市（或景点），今从某市出发旅游各城市，使之旅费相对较少（即找出一条令人满意的比较省钱的线路不一定是旅费最少的线路）。设矩阵元素aij 表示从第1号城市到第j号城市之旅费。并设城市间往返旅费可以不等（即aij aji ）。aii 是没有意义的，由于问题是求最少，因此aii 不应为零，今试为无穷（）。各城市间旅费如下表： 17 13 24 10 10 20 9 6 17 29 21 28 12 10 22 19 12 18 31 20 问题的算法是在表每行中找最小元素，并用该数减该行非元素。再对每列也施同样工作，形成一个新表（保证每行、每列均不少于1个为零），所有减数累加为min（其含义为旅费下界，即旅费不会少于min）。旅行路程因成环路，故可设起点是第0号城市。若选第i号到第j号城市，则表上bij 表示还需旅费，同时由于选了ij，则i不可能再选向其它城市，则第i行全填，同理，由于j已由i过来，则第j城市不可能再由其它城市过来，第j列也全填上。对新矩阵再施每行至少有一个0，每列至少有一个0，找出余下城市遍历所需旅费下界mj 。对于不同的j，比较mj +bij 以最小的一个为选定从i到达的城市，并将选择路径记下。如此重复直到选完。33:马克思手稿中有一道趣味数学问题：有30个人，其中有男人、女人和小孩，在一家饭馆吃饭花了50元；每个男人花3元，每个女人花2元，每个小孩花1元；问男人、女人和小孩各有几人？设x，y，z分别代表男人、女人和小孩。按题目的要求，可得到下面的方程： x+y+z=30 (1) 3x+2y+z=50 (2) 用程序求此不定方程的非负整数解，可先通过(2)(1)式得： 2x+y=20 (3)由(3)式可知，x变化范围是010。通过上面规律可以推导出结果。34:某人上台阶，他一步可以迈一个台阶或两个台阶，共有8个台阶，编程输出他所有可能上法。思路：1,2 中选一个，穷举法（8层循环，每一次循环之前先判断和是否已经到8，如果是8，则退出。35:用二分法求一元二次方程x2-2-x=0在0，3区间的根。二分法属于数学问题，但为了说清楚问题就再说一下原理。先取二元方程f(x)的两个初略解x1和x2，若f(x1)与f(x2)的符号相反，则方程f(x)=0在x1，x2区间至少有一个根；若f(x)在x1，x2区间单调，则至少有一个实根；所以取x3=(x1+x2)/2，并在x1和x2中舍去和f(x3)同号者，那么解就在x3和另外那个没有舍去的初略解组成的区间里；如此反复取舍，直到xn与xn-1之差满足要求时，那么xn便是方程f(x)的近似根。所以有算法：while(误差给定误差)if(f(x)=0)x就是根，不在迭代else if(f(x)*f(x1)0) /*这里的x相当于上面所说的x3*/x2=x；elsex1=x；思路：通过一个死循环，满足条件后退出！36.编写程序，实现数字与IP地址间的转换。数字和IP地址之间的转换：先将数字除以256的3次方，得出的数字就是IP地址中的第一组数值，然后再将要转换的数字减去第一组数值乘以256的3次方，接着再将求出的数字除以256的2次方，得出IP地址中的第二组数，然后再像第一组数值那样做，用减去第一组之后剩余的数字减去第二组数值乘以256的2次方一直到将IP地址全部转换完毕。比如：将数字3232235521转换成IP地址，则先3232235521/(256的3次方)，得出192，再用3232235521192(256的3次方)，用求出的数除以256的2次方，得出168，这样一直求出0和1，最后的IP地址为。IP地址和数字之间的转换：其实就是上面的方法逆运算。先将IP地址中的每一组数值取出，然后分别用它们与256的余数去乘以256的3次方，2次方，1次方，0次方，最后将这些所得的数字全部相加在一起，就是最后转换出来的数字。37.求N阶幻方，使其在任意一个方向上的数求和相等。求N阶幻方，幻方的元素都是从1到n的整数，且每数出现且只出现一次，使其在任意一个方向上的数求和相等，并显示。利用循环求解。37.使用数组精确计算M/N(0MN=100)的值。如果M/N是无限循环小数，则计算并输出它的第一循环节，同时要求输出循环节的起止位置(小数位的序号)。使用数组精确计算M/N(0MN=100)的值。如果M/N是无限循环小数，则计算并输出它的第一循环节，同时要求输出循环节的起止位置(小数位的序号)。由于计算机字长的限制，常规的浮点运算都有精度限制，为了得到高精度的计算结果，就必须自行设计实现方法。为了实现高精度的计算，可将商存放在一维数组中，数组的每个元素存放一位十进制数，即商的第一位存放在第一个元素中，商的第二位存放在第二个元素中，依次类推。这样就可以使用数组表示一个高精度的计算结果。进行除法运算时可以模拟人的手工操作，即每次求出商的第一位后，将余数乘以10，再计算商的下一位，重复以上过程，当某次计算后的余数为0时，表示M/N为有限不循环小数,某次计算后的余数与前面的某个余数相同时，则M/N为无限循环小数，从该余数第一次出现之后所求得的各位数就是小数的循环节。38.假设提供了数目不限的面值为25美分，10美分，5美分，及1美分的硬币求找130000美分的算法。 先从输入的钱数里面找出25美分的最多个数，然后再从剩余的钱数里找出10美分的最多个数，再从剩余的钱数中找出5美分的最多个数，最后从剩余的钱数中找出1美分的个数。如果在找的过程中，余钱数不足要找的面值，找下一个面值的个数。39.(分治法)设有n位选手参加网球循环赛。循环赛共进行n-1天，每位选手要与其他n-1位选手赛一场，且每位选手每天赛一场，不轮空。试按此要求为比赛安排日程。首先，设N位选手的编号为1，2，3，N，比赛日程表是一个N行N-1列的表，第i行第j列的内容是第i号选手第j天的比赛对手。用分治法设计日程表，就是从其中一半选手的比赛日程，导出全体选手的比赛日程。从众所周之的只有两位选手比赛日程出发，反复这一过程，直至为n位选手安排好比赛日程为止。40有两组不同长度的数列分别为从小到大排列，设计一种算法把两列数合并成一列从小到大排列的数列。首先，比较两列数的第一个数，选出较小的数存储并用该组的下一个数继续与较大数比较。然后，每次选出一个较小的数后都继续用该组的下一个数与上一次比较后的较大数比较。依此类推，直至有一组数列全部被比较完。把有剩余组的数按顺序加入到结果数列的尾部。41.模拟投掷两只一样的色子，产生随机的结果，并且计算出百分比。把每次随机产生的色子数存储到二维数组中。如：产生一对6和5的点数则在原“出现次数数组65”的基础上加1次出现的次数。42.有十二个同样形状的球，其中一个或重于或轻于其他的球，用天平称找出这个球，而且分出这个球是重还是轻于其他的球。请设计一种算法。 将12个球分为1、2、3组各4球，称1、2组，如果平衡异常球在3组中，如果不平衡将天平的倾斜记录下来；区别对待：A、1、2组平衡时，坏球在第三组 B、1、2组不平衡时，坏球在两组之一，拿第1组与第3组比较平衡则2组有坏球，不平衡则1组有坏球。 比较4个小球 区别对待： 第1球与第2球等重，比较第1个与第3个，等重则第4球为坏球；不等则3球为坏球。 第1球与第2球不等重，比较第1个与第3个，等重则第2球为坏球，不等则第1各为坏球。 由此可以扩展为n球问题。43:有一组无序排列的整数，通过算法计算使它们成为从小到大依次排列？如果在一次循环中，最后的某些元素没有交换过，则说明后面这些元素的顺序已排序，下次循环可不对其进行比较。本方法主要考虑要排序的数组元素的范围，而不是每一轮排序都将数组元素的范围减少1。44:从键盘上任意输入一个110之间的整数N，就产生一个N N阶的方阵，并且此方阵是一个螺旋方阵。求一个螺旋方阵，其实就是分别往下、往右、往上、往左四个方向来依次填充数字，那么就是想办法判定什么时候向什么方向填充数字。本算法采用四个子程序来分别控制往下、往右、往上、往左四个方向的填充，设四个变量，用于标识四个方向每次填充的起始位置，每填充一个方向后起始位置加1。再用一个二维数组存放要填充的数字先将这个数组数据全部置为0，在每个方向填充时，每填充一个数字，就将这个数字存放到数组中相应的位置，通过判断要填充的位置所对应的数组数据是否为0，来确定是否终止该方向的数字填充。45:射击运动员m发打中n环有多少种可能，编写程序计算出来，并显示出结果，0环和10环均有效。循环+递归调用。每层递归计算给定的环数和子弹数可以有多少重可能。直到所有可能都被取为止。46-70遍历数字1-9。产生一个6位数y和一个3位数x，使y=x*x，并且组成y与x的9个数各不相同。首先依次比较每一个平方后是6位数的3位数，记录下3位数和平方后的6位数。 然后比较3位数的每一位和6位数的每一位是否合格。合格则输出。比较下一个3位数。47-71输入10个数字，利用桶排序将它们按从小到大排序显示出来。桶排序的思想是若待排序的记录的关键字在一个明显有限范围内(整型)时，可设计有限个有序桶，每个桶装入一个值；顺序输出各桶的值，将得到有序的序列。48-72n 个造币厂生产同一种硬币，但其中某些厂由于材料问题造出了非标准的硬币。设标准的硬币重c克(已知)，非标准的硬币只有一种重量，重c(1+e)克，其中e是个不为0的未知数，可以取正数或负数。为了查出哪些厂生产的硬币是非标准的，从各厂中抽出一些样品(个数相同)放在一起进行称重，设计一种算法查出哪个厂子的硬币是不合格的。将所有造币厂的硬币等分为1、2、3组如有剩余划为第4组，称1、2组。1 如果平衡异常的硬币不在1，2组中，比较1，3组如果平衡则不合格的在4组中如果不平衡不合格的在三组中。递归把该组分为最多4组。2 如果不平衡将天平的倾斜记录下来，比较1，3组如果平衡不合格的在2组中，如果不平衡不合格在1组中。递归把该组分为最多四组。依此类推直至最后剩余1个或两个小球和标准重量比较后找出不合格的造币厂的编号。49-73有一组无序排列的整数，通过算法计算使它们成为从小到大依次排列？每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。50-7436块砖，36人搬，男的搬4块，女的搬3块，2个小儿抬1块，要求1次全部搬完，问需男、女、小孩各多少人?首先已知共36人和36块砖，男人女人小孩36人，男人 4 女人 3 小孩 2 36块砖。51公共汽车包括起始站和终点站共15站,有一车辆，除终点站外，每一站上车的乘客都恰好有一位到以后的每一站下车。为了使每一位乘客都有座位，这车辆公车至少要有多少个座位？这辆车至少售出多少张票？先求票数，票数应该是等于上车或是下车的总人数，再求出座位数。52任意一个四位数(每位上的数字都不相同)，经有限次“重排求差”操作，得到的黑洞数为6174。编写程序验证。:黑洞数又称陷阱数，是类具有奇特转换特性的整数。任何一个数字不全相同整数，经有限次重排求差操作，总会得某一个或一些数，这些数即为黑洞数。重排求差操作即组成该数的数字重排的最大数减去重排的最小数。如：1234重排后得最大数4321，最小数1234，有它们两个相减，将得到的差再进行重排求差，一直到差数为6174或0。53:计算两个矩阵A、B的乘积矩阵C。矩阵A1,2,3,4,5,6；矩阵B7,8,9,10,11,12。:两个矩阵的乘积仍然是矩阵。若A矩阵有m行p列，B矩阵有p行n列,则它们的乘积C矩阵有m行n列。C=A*B的算法：Cij= (i=0，1，m-1；j=0，1，n-1)设A