2014年第五届蓝桥杯省赛试题及详解（Java本科B组)
分糖果 /** * @author Wcy * @Date 2022/3/28 17:23 */ import java.util.Arrays; import java.util.Scanner; /** 有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果，然后进行下面的游戏： 每个小朋友都把自己的糖果分一半给左手边的孩子。 一轮分糖后，拥有奇数颗糖的孩子由老师补给1个糖果，从而变成偶数。 反复进行这个游戏，直到所有小朋友的糖果数都相同为止。 你的任务是预测在已知的初始糖果情形下，老师一共需要补发多少个糖果。 【格式要求】 程序首先读入一个整数N(2<N<100)，表示小朋友的人数。 接着是一行用空格分开的N个偶数（每个偶数不大于1000，不小于2） 要求程序输出一个整数，表示老师需要补发的糖果数。 例如：输入 3 2 2 4 程序应该输出： 4 资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。 注意：主类的名字必须是：Main，否则按无效代码处理。 */ public class 分糖果 { public static void main(String[] args) { int add=0; Scanner scanner = new Scanner(System.in); int people=scanner.nextInt(); int[] num=new int[people]; for(int i=0;i<people;i++) num[i]= scanner.nextInt(); while(true){ int fir=num[0]/2; for(int i=0;i<num.length-1;i++){ num[i]=num[i]/2+num[i+1]/2; } num[num.length-1]=num[num.length-1]/2+fir; //2 2 4 2 3 3 // System.out.println(Arrays.toString(num)); for(int i=0;i<num.length;i++) if(num[i]%2!=0) { add++; num[i]=num[i]+1; } // System.out.println(Arrays.toString(num)); boolean judge=true; for(int i=0;i<num.length-1;i++) if(num[i]!=num[i+1]){ judge=false; } if(judge) { System.out.println(add); break; } } } } 切面条 /** * @author Wcy * @Date 2022/3/28 15:20 */ /** * 一根高筋拉面，中间切一刀，可以得到2根面条。 * * 如果先对折1次，中间切一刀，可以得到3根面条。 * * 如果连续对折2次，中间切一刀，可以得到5根面条。 * * 那么，连续对折10次，中间切一刀，会得到多少面条呢？ * * 答案是个整数，请通过浏览器提交答案。不要填写任何多余的内容。 * */ public class 切面条 { /** * n-1:对折次数 * 解析 1=1/2+2^(n-1)*(1/2^n) * n=1时：1=1/2+1/2 * n=2时：1=1/2+1/4+1/4 * n=3时：1=1/2+1/8+1/8+1/8+1/8 * @param args */ public static void main(String[] args) { System.out.println(1+1024); } } 圆周率 /** * @author Wcy * @Date 2022/3/28 15:52 */ /** * 数学发展历史上，圆周率的计算曾有许多有趣甚至是传奇的故事。其中许多方法都涉及无穷级数。 * * 图1.png中所示，就是一种用连分数的形式表示的圆周率求法。 * * 下面的程序实现了该求解方法。实际上数列的收敛对x的初始值 并不敏感。 * * 结果打印出圆周率近似值（保留小数点后4位，并不一定与圆周率真值吻合）。 * * * 4/pai=1+x * * double x = 111; * for(int n = 10000; n>=0; n--){ * int i = 2 * n + 1; * x = 2 + (i*i / x); * } * * * * System.out.println(String.format("%.4f", ______________)); */ public class 圆周率 { public static void main(String[] args) { double x = 111; for(int n = 10000; n>=0; n--){ int i = 2 * n + 1; x = 2 + (i*i / x); } System.out.println(String.format("%.4f", 4/(x-1))); } } 地宫取宝 /** * @author Wcy * @Date 2022/3/28 17:44 */ import java.util.Scanner; /** * X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。 * 地宫的入口在左上角，出口在右下角。 * 小明被带到地宫的入口，国王要求他只能向右或向下行走。 * 走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。 * 当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。 * 请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。 * 【数据格式】 * 输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12) * 接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值 * 要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。 * 例如，输入： * 2 2 2 * 1 2 * 2 1 * 程序应该输出： * 2 * * 再例如，输入： * 2 3 2 * 1 2 3 * 2 1 5 * 程序应该输出： * 14 * * 资源约定： * 峰值内存消耗（含虚拟机） < 256M * CPU消耗 < 2000ms * * 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。 * * 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 * 注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。 * 注意：主类的名字必须是：Main，否则按无效代码处理。 */ public class 地宫取宝 { private static long N = 1000000007; private static int n,m,k; private static int map[][] = new int[50][50]; //记录迷宫 //dp中，四个参数各代表坐标X,Y、手中持有宝物数量、手中宝物的最大值 表示的是该状态到终点有多少条路径 private static int dp[][][][] = new int[50][50][15][15]; public static void init(){//初始化每个状态都是-1 所以-1就说明这个状态之后的路径没有计算过 for(int i=0;i<50;i++){ for(int j=0;j<50;j++){ for(int k=0;k<15;k++){ for(int l=0;l<15;l++) dp[i][j][k][l] = -1; } } } } /* 就是一个搜索的函数，来不断地搜索，每次搜索到底的时候， 也就是最后一个点的时候，虽然x、y是一样的，但是num和max也就是状态是不一样的 但是显然我们知道最后一个点不论是什么状态它到终点的路径也只有一条 所以会return一个1 然后回到递归的上一层 也就是上一个点的状态 可能它是往右到达最后这个点的 还是往下到达这个点的 它 也就是调用了这个return 1 的这次dfs的那个点的状态 它的s必须要加上这个1 然后一层一层往上递推 s是不断地增加的 直到初始点 的初始状态 它的dp值 也就是s 就是我们所要的答案 */ public static int DFS(int x, int y, int num, int max){ //首先函数的前面可以写一些代码来控制条件来剪枝 减少一些无用的搜索 //记忆化搜索，首先先检查该路径是否已经走过 if(dp[x][y][num][max+1]!=-1){ //说明已经走过这个条路径，就不用再次走（这个状态之前已经到过了，所以不用再计算了，直接返回之前得出的该状态的数值） //因为宝物有可能为0所以定义max时用最小值-1 这就导致无法作为下标使用 //实际上如果测试数据中宝物价值没有0,将所有的+1 去掉也是可以的 return dp[x][y][num][max+1]; } //到达边界 if(x==n-1 && y==m-1){ /*到达下角有两种情况成功 * 1.当前手中的数量正好等于题目所要的k，这时不拿会成功 * 2.当前手中的数量刚好差一个，然后地下的宝物大于手中的max，这时也会成功 */ if(num==k || (num==k-1 && max<map[x][y])){ return dp[x][y][num][map[x][y]]=1; //这里返回的1就是上文所提到的 这个状态到终点有一条路径 然后往外层递推一直递推到初始状态就是答案 }else{ return dp[x][y][num][max+1]=0; //不满足条件,这里的max+1原因同上 } } /*拿和不拿的两种情况： * 1.手中的max大于地下宝物价值，此时可拿可不拿 * 2.手中的max小于地下宝物价值，此时只能不拿 */ long s = 0; if(x<n-1){//向下搜索 if(max<map[x][y]){//可拿可不拿，不拿的情况可以想成是不符合条件所以不拿，这样来说就可以将其和不能拿一起处理 s += DFS(x+1, y, num+1, map[x][y]); } s += DFS(x+1, y, num, max);//不拿，与不能拿时写在一起,这点很重要！ s%=N; } if(y<m-1){//向右搜索 if(max<map[x][y]){//可拿可不拿，不拿的情况可以想成是不符合条件所以不拿，这样来说就可以将其和不能拿一起处理 s += DFS(x, y+1, num+1, map[x][y]); } s += DFS(x, y+1, num, max);//不拿，与不能拿时写在一起,这点很重要！ s%=N; } //说明本层内的都回溯完了 也就是本层dfs结束 此时要赋给这个状态s 即表示有多少条路径到达终点 return dp[x][y][num][max+1]=(int) s; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); n = scan.nextInt(); m = scan.nextInt(); k = scan.nextInt(); for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ map[i][j] = scan.nextInt(); } } init(); DFS(0, 0, 0, -1); System.out.println(dp[0][0][0][0]);//起点刚开始什么都没有的状态 这个状态的值就是答案 } } 大衍数列 /** * @author Wcy * @Date 2022/3/28 15:50 */ /** * 中国古代文献中，曾记载过“大衍数列”, 主要用于解释中国传统文化中的太极衍生原理。 * * 它的前几项是：0、2、4、8、12、18、24、32、40、50 ... * * 其规律是：对偶数项，是序号平方再除2，奇数项，是序号平方减1再除2。 * * 以下的代码打印出了大衍数列的前 100 项。 * * for(int i=1; i<100; i++) * { * if(________________) //填空 * System.out.println(i*i/2); * else * System.out.println((i*i-1)/2); * } * 请填写划线部分缺失的代码。通过浏览器提交答案。 * * 注意：不要填写题面已有的内容，也不要填写任何说明、解释文字。 * * i%2==0 */ public class 大衍数列 { public static void main(String[] args) { for (int i = 1; i < 100; i++) { if (i % 2 == 0) //填空 System.out.println(i * i / 2); else System.out.println((i * i - 1) / 2); } } } 奇怪的分式 /** * @author Wcy * @Date 2022/3/28 15:57 */ /** * 上小学的时候，小明经常自己发明新算法。一次，老师出的题目是： * * 1/4 乘以 8/5 * * 小明居然把分子拼接在一起，分母拼接在一起，答案是：18/45 （参见图1.png） * * 老师刚想批评他，转念一想，这个答案凑巧也对啊，真是见鬼！ * * 对于分子、分母都是 1~9 中的一位数的情况，还有哪些算式可以这样计算呢？ * * 请写出所有不同算式的个数（包括题中举例的）。 * * 显然，交换分子分母后，例如：4/1 乘以 5/8 是满足要求的，这算做不同的算式。 * * 但对于分子分母相同的情况，2/2 乘以 3/3 这样的类型太多了，不在计数之列! * * 注意：答案是个整数（考虑对称性，肯定是偶数）。请通过浏览器提交。不要书写多余的内容。 */ public class 奇怪的分式 { public static void main(String[] args) { // 好家伙，相当暴力 int ans=0; for(int a=1;a<10;a++) for(int b=1;b<10;b++) for(int c=1;c<10;c++) for(int d=1;d<10;d++) { int e = 10*a+c; int f = 10*b+d; if(a==b || c==d) continue; if(a*c*f==e*b*d) { ans++; System.out.println(a+"/"+b+" x "+c+"/"+d+" = "+e+"/"+f+" "+ans); } } } } 扑克序列 /** * @author Wcy * @Date 2022/3/28 15:59 */ import java.util.Arrays; /** * A A 2 2 3 3 4 4， 一共4对扑克牌。请你把它们排成一行。 * 要求：两个A中间有1张牌，两个2之间有2张牌，两个3之间有3张牌，两个4之间有4张牌。 * * 请填写出所有符合要求的排列中，字典序最小的那个。 * * 例如：22AA3344 比 A2A23344 字典序小。当然，它们都不是满足要求的答案。 * * * 请通过浏览器提交答案。“A”一定不要用小写字母a，也不要用“1”代替。字符间一定不要留空格。 */ //2342A3A4 public class 扑克序列 { // A比2大 所有A>=5 public static String result = "AAAAAAAA"; // 排列 public static void f(char[] a, int k) { if (k == a.length - 1) { work(a); return; } else { for (int i = k; i < a.length; i++) { { char t = a[k]; a[k] = a[i]; a[i] = t; } f(a, k + 1); { char t = a[k]; a[k] = a[i]; a[i] = t; } } } return; } // 筛选符合题意的 public static void work(char[] a) { char temp1 = 'A', temp2 = '2', temp3 = '3', temp4 = '4'; int dA = distance(a, temp1); int d2 = distance(a, temp2); int d3 = distance(a, temp3); int d4 = distance(a, temp4); // 两个A中间有1张牌，两个2之间有2张牌，两个3之间有3张牌，两个4之间有4张牌 if (dA == 1 && d2 == 2 && d3 == 3 && d4 == 4) { String A = ""; for (int i = 0; i < a.length; i++) { A += a[i]; } if (A.compareTo(result) < 0) result = A; return; } } // 计算相同字符之间的距离 public static int distance(char[] a, char temp) { for (int i = 0; i < a.length; i++) { for (int j = i + 1; j < a.length; j++) { if (a[i] == temp && a[j] == temp) { return j - (i + 1); } } } return 0; } public static void main(String[] args) { f("AA223344".toCharArray(), 0); System.out.println(result); } } 武功秘籍 /** * @author Wcy * @Date 2022/3/28 15:16 */ /** * 小明到X山洞探险，捡到一本有破损的武功秘籍（2000多页！当然是伪造的）。他注意到：书的第10页和第11页在同一张纸上，但第11页和第12页不在同一张纸上。 * * 小明只想练习该书的第81页到第92页的武功，又不想带着整本书。请问他至少要撕下多少张纸带走？ * * 这是个整数，请通过浏览器提交该数字，不要填写任何多余的内容。 */ public class 武功秘籍 { // 偶数页在正面，奇数页在反面 //此题无需代码 // （80，81） +(82,83)+(84,85)+(86,87)+(88.89),(90,91) +(92,93) public static void main(String[] args) { System.out.println(7); } } 猜字母 /** * @author Wcy * @Date 2022/3/28 15:28 */ import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * 把abcd...s共19个字母组成的序列重复拼接106次，得到长度为2014的串。 * * 接下来删除第1个字母（即开头的字母a），以及第3个，第5个等所有奇数位置的字母。 * * 得到的新串再进行删除奇数位置字母的动作。如此下去，最后只剩下一个字母，请写出该字母。 * * 答案是一个小写字母，请通过浏览器提交答案。不要填写任何多余的内容。 */ public class 猜字母 { public static void main(String[] args) { String[] str = new String[]{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s"}; List<String> strList = new ArrayList<>(); for (int i = 0; i < 106; i++) { strList.addAll(Arrays.asList(str)); } while (true) { for (int i = 0; i < strList.size(); i++) { if (i % 2 == 0) strList.set(i, ""); } //或者直接使用字符串的replace也可以 看个人喜好 System.out.println(Arrays.toString(strList.toArray())); while(strList.contains("")) { strList.remove(""); } if(strList.size()==1) { System.out.println(Arrays.toString(strList.toArray())); break; } } } } 矩阵翻硬币 /** * @author Wcy * @Date 2022/3/28 17:54 */ import java.math.BigInteger; import java.util.Arrays; import java.util.Scanner; /** * 小明先把硬币摆成了一个 n 行 m 列的矩阵。 * 随后，小明对每一个硬币分别进行一次 Q 操作。 * 对第x行第y列的硬币进行 Q 操作的定义：将所有第 i*x 行，第 j*y 列的硬币进行翻转。 * 其中i和j为任意使操作可行的正整数，行号和列号都是从1开始。 * 当小明对所有硬币都进行了一次 Q 操作后，他发现了一个奇迹——所有硬币均为正面朝上。 * 小明想知道最开始有多少枚硬币是反面朝上的。于是，他向他的好朋友小M寻求帮助。 * 聪明的小M告诉小明，只需要对所有硬币再进行一次Q操作，即可恢复到最开始的状态。然而小明很懒，不愿意照做。于是小明希望你给出他更好的方法。帮他计算出答案。 * 【数据格式】 * 输入数据包含一行，两个正整数 n m，含义见题目描述。 * 输出一个正整数，表示最开始有多少枚硬币是反面朝上的。 * 【样例输入】 * 2 3 * 【样例输出】 * 1 * 【数据规模】 * 对于10%的数据，n、m <= 10^3； * 对于20%的数据，n、m <= 10^7； * 对于40%的数据，n、m <= 10^15； * 对于10%的数据，n、m <= 10^1000（10的1000次方）。 * * 资源约定： * 峰值内存消耗（含虚拟机） < 256M * CPU消耗 < 2000ms */ /** * //第x行第y列被翻动的总次数 //考虑第1行，第y列，y有多少真因子，就会被翻动多少次，而所有的y中，只有平方数的真因子个数为奇数（约数总是成对出现的） //考虑第1列，第x行，x有多少真因子，就会被翻动多少次，而所有的x中，只有平方数的真因子个数为奇数 //x,y硬币被翻动的次数=x真因子个数*y真因子个数，只有奇数*奇数=奇数，所以，若要x,y为反面，必须x，y都是平方数 //因此，反面硬币总数=m中的平方数的个数*n中平方数的个数 //那么在m中有多少个平方数呢？答案是sqrt(m)向下取整个，如9内有三个平方数1，4，9；16里面有4个平方数1，4，9，16；25内有5个平方数 //因此此题等价于求sqrt(m)*sqrt(n)，那么怎么对一个很大的数开平方呢？ //假设一个数的长度为length，其平方根的长度为length/2（偶数）或者length/2+1(奇数) */ public class 矩阵翻硬币 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s1 = sc.next(); String s2 = sc.next(); System.out.println(sqrt(s1).multiply(sqrt(s2))); } private static BigInteger sqrt(String s) { int length = s.length(); int len = 0; if (length % 2 == 0) len = length / 2; else len = length / 2 + 1; char[] sArr = new char[len]; Arrays.fill(sArr, '0'); BigInteger target = new BigInteger(s); for (int pos = 0; pos < len; pos++) { for (char c = '1'; c <= '9'; c++) { sArr[pos] = c;//在pos这个位置上试着填入1-9 BigInteger pow = new BigInteger(String.valueOf(sArr)).pow(2);//平方 if (pow.compareTo(target) > 0)//试探数的平方更大 { sArr[pos] -= 1; break; } } } return new BigInteger(String.valueOf(sArr)); } }
2013年第四届蓝桥杯省赛试题及详解（Java本科B组)
世纪末的星期 /** * 曾有邪教称1999年12月31日是世界末日。当然该谣言已经不攻自破。 * 还有人称今后的某个世纪末的12月31日，如果是星期一则会.... * 有趣的是，任何一个世纪末的年份的12月31日都不可能是星期一!! * 于是，“谣言制造商”又修改为星期日...... * 1999年的12月31日是星期五，请问：未来哪一个离我们最近的一个世纪末年（即xx99年）的12月31日正好是星期天（即星期日）？ * 请回答该年份（只写这个4位整数，不要写12月31等多余信息） */ public class 世纪末的星期 { public static void main(String[] args) { //从2000年开始 int i = 2000; // 0 1 2 3 4 5 6 代表七天 int index = 4; while (true) { int days = 365; if ((i%100!=0 && i%4==0) || i%400==0) days = 366; int yu = days % 7; index = (index + yu) % 7; // System.out.println(i+":"+index); if (i % 100 == 99) if ((index == 6)) { System.out.println(i); break; } i++; } } } 马虎的算式 /** * 小明是个急性子，上小学的时候经常把老师写在黑板上的题目抄错了。 * * 有一次，老师出的题目是：36 x 495 = ? * * 他却给抄成了：396 x 45 = ? * * 但结果却很戏剧性，他的答案竟然是对的！！ * * 因为 36 * 495 = 396 * 45 = 17820 * * 类似这样的巧合情况可能还有很多，比如：27 * 594 = 297 * 54 * * 假设 a b c d e 代表1~9不同的5个数字（注意是各不相同的数字，且不含0） * * 能满足形如： ab * cde = adb * ce 这样的算式一共有多少种呢？ * * 请你利用计算机的优势寻找所有的可能，并回答不同算式的种类数。 * * 满足乘法交换律的算式计为不同的种类，所以答案肯定是个偶数。 * * 答案直接通过浏览器提交。 * 注意：只提交一个表示最终统计种类数的数字，不要提交解答过程或其它多余的内容。 */ public class 马虎的算式 { public static void main(String[] args) { //a>0 c>0 int total=0; for(int a=1;a<10;a++) // a for(int b=1;b<10;b++) //b if(a!=b) for(int c=1;c<10;c++) // c if((b!=c)&&(a!=c)) for(int d=1;d<10;d++) //d if((a!=d)&&(b!=d)&&(c!=d)) for(int e=1;e<10;e++) //e if((a!=e)&&(b!=e)&&(c!=e)&&(d!=e)) // ab * cde = adb * ce if((a*10+b)*(c*100+d*10+e)==(a*100+d*10+b)*(c*10+e)) total++; System.out.println(total); } } 振兴中华 /** * 小明参加了学校的趣味运动会，其中的一个项目是：跳格子。 * * 地上画着一些格子，每个格子里写一个字，如下所示：（也可参见p1.jpg） * * 从我做起振 * 我做起振兴 * 做起振兴中 * 起振兴中华 * * * 比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。 * * * 要求跳过的路线刚好构成“从我做起振兴中华”这句话。 * * 请你帮助小明算一算他一共有多少种可能的跳跃路线呢？ * * 答案是一个整数，请通过浏览器直接提交该数字。 * 注意：不要提交解答过程，或其它辅助说明类的内容。 */ //35 public class 振兴中华 { public static void main(String[] args) { int[][] dp = new int[6][6]; // 1 2 3 4 5 for(int i=1;i<=5;i++) //预处理 // 实际只用到[4][5] dp[i][1] = dp[1][i] = 1; // 2 3 4 5 即从第二位开始遍历递归 for(int i=2;i<=5;i++) for(int j=2;j<=5;j++) /* * 向上或向左搜寻 */ dp[i][j] = dp[i][j-1] + dp[i-1][j]; System.out.println(f(4,5)); } /* * 从我做起振 * 我做起振兴 * 做起振兴中 * 起振兴中华 */ static int f(int x,int y){ if(x==1 && y==1) return 1; if(x==1) return f(x,y-1); if(y==1) return f(x-1,y); return f(x-1,y) + f(x,y-1); } } 黄金连分数 import java.math.BigDecimal; import java.math.BigInteger; import java.math.RoundingMode; /** * 黄金分割数0.61803... 是个无理数，这个常数十分重要，在许多工程问题中会出现。有时需要把这个数字求得很精确。 * * 对于某些精密工程，常数的精度很重要。也许你听说过哈勃太空望远镜，它首次升空后就发现了一处人工加工错误，对那样一个庞然大物，其实只是镜面加工时有比头发丝还细许多倍的一处错误而已，却使它成了“近视眼”!! * * * 言归正传，我们如何求得黄金分割数的尽可能精确的值呢？有许多方法。 * * 比较简单的一种是用连分数： * * 1 * 黄金数 = --------------------- * 1 * 1 + ----------------- * 1 * 1 + ------------- * 1 * 1 + --------- * 1 + ... * * * * 这个连分数计算的“层数”越多，它的值越接近黄金分割数。 * * 请你利用这一特性，求出黄金分割数的足够精确值，要求四舍五入到小数点后100位。 * * 小数点后3位的值为：0.618 * 小数点后4位的值为：0.6180 * 小数点后5位的值为：0.61803 * 小数点后7位的值为：0.6180340 * （注意尾部的0，不能忽略） * * 你的任务是：写出精确到小数点后100位精度的黄金分割值。 * * 注意：尾数的四舍五入！ 尾数是0也要保留！ * * 显然答案是一个小数，其小数点后有100位数字，请通过浏览器直接提交该数字。 * 注意：不要提交解答过程，或其它辅助说明类的内容。 */ /** * 斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci） * 以兔子繁殖为例子而引入，故又称为“兔子数列”， * 指的是这样一个数列：1、1、2、3、5、8、13、21、34、…… * 在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*） * 在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。 */ public class 黄金连分数 { public static void main(String[] args) { BigInteger a=BigInteger.ONE; BigInteger b=BigInteger.ONE; //斐波那契数列的迭代形式 for (int i = 3; i < 500; i++) { BigInteger t=b; b=a.add(b);//大整数的加法 a=t; } //大浮点数的除法 BigDecimal divide = new BigDecimal(a,110).divide(new BigDecimal(b,110), BigDecimal.ROUND_HALF_DOWN); //截取字符串 System.out.println(divide.toPlainString().substring(0,103)); } //0.6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911375 /** * 0.6180339887 * 4989484820 * 4586834365 * 6381177203 * 0917980576 * 2862135448 * 6227052604 * 6281890244 * 9707207204 * 18939113748 * 向上取一位 */ } 有理数类 /** * 有理数就是可以表示为两个整数的比值的数字。一般情况下，我们用近似的小数表示。但有些时候，不允许出现误差，必须用两个整数来表示一个有理数。 * * 这时，我们可以建立一个“有理数类”，下面的代码初步实现了这个目标。为了简明，它只提供了加法和乘法运算。 */ public class Rational { private long ra; private long rb; // 辗转相除法取最简公因子 private long gcd(long a, long b){ if(b==0) return a; return gcd(b,a%b); } public Rational(long a, long b){ ra = a; rb = b; long k = gcd(ra,rb); if(k>1){ //需要约分 ra /= k; rb /= k; } } // 加法 // public Rational add(Rational x){ // return ________________________________________; //填空位置 // } public Rational add(Rational x){ return new Rational(ra*x.rb+rb*x.ra, rb*x.rb); //填空位置 answer } /** * * new Rational(ra*x.rb+rb*x.ra, rb*x.rb) * new Rational(this.ra * x.rb + x.ra * this.rb, this.rb * x.rb) * */ // 乘法 public Rational mul(Rational x){ return new Rational(ra*x.ra, rb*x.rb); } public String toString(){ if(rb==1) return "" + ra; return ra + "/" + rb; } } 三部排序 /** * 一般的排序有许多经典算法，如快速排序、希尔排序等。 * * 但实际应用时，经常会或多或少有一些特殊的要求。我们没必要套用那些经典算法，可以根据实际情况建立更好的解法。 * * 比如，对一个整型数组中的数字进行分类排序： * * 使得负数都靠左端，正数都靠右端，0在中部。注意问题的特点是：负数区域和正数区域内并不要求有序。可以利用这个特点通过1次线性扫描就结束战斗!! * * 以下的程序实现了该目标。 */ public class 三部排序 { public static void main(String[] args) { } static void sort(int[] x) { int p = 0; int left = 0; int right = x.length-1; while(p<=right){ if(x[p]<0){ int t = x[left]; x[left] = x[p]; x[p] = t; left++; p++; } else if(x[p]>0){ int t = x[right]; x[right] = x[p]; x[p] = t; right--; } else{ // _________________________; //代码填空位置 p++; //代码填空位置 answer } } } } /** * 如果给定数组： * 25,18,-2,0,16,-5,33,21,0,19,-16,25,-3,0 * 则排序后为： * -3,-2,-16,-5,0,0,0,21,19,33,25,16,18,25 */ 错误票据 import java.util.*; /** * 某涉密单位下发了某种票据，并要在年终全部收回。 * 每张票据有唯一的ID号。全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。 * 因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。 * 你的任务是通过编程，找出断号的ID和重号的ID。 * 假设断号不可能发生在最大和最小号。 * 要求程序首先输入一个整数N(N<100)表示后面数据行数。 * 接着读入N行数据。 * 每行数据长度不等，是用空格分开的若干个（不大于100个）正整数（不大于100000） * 每个整数代表一个ID号。 * * 要求程序输出1行，含两个整数m n，用空格分隔。 * 其中，m表示断号ID，n表示重号ID * * 例如： * 用户输入： * 2 * 5 6 8 11 9 * 10 12 9 * * 则程序输出： * 7 9 * * * 再例如： * 用户输入： * 6 * 164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196 * 172 189 127 107 112 192 103 131 133 169 158 * 128 102 110 148 139 157 140 195 197 * 185 152 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190 * 149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132 101 194 187 188 * 113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119 * * 则程序输出： * 105 120 * * * 资源约定： * 峰值内存消耗（含虚拟机） < 64M * CPU消耗 < 2000ms * * * 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。 * * 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 * 注意：不要使用package语句。不要使用jdk1.6及以上版本的特性。 * 注意：主类的名字必须是：Main，否则按无效代码处理。 */ public class 错误票据 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); ArrayList<Integer> list = new ArrayList<Integer>(); int N = sc.nextInt(); sc.nextLine();//吃掉整数后面的换行符 for (int i = 0; i < N; i++) { String line = sc.nextLine(); String[] split = line.split(" "); for (int j = 0; j < split.length; j++) { list.add(Integer.parseInt(split[j])); } } // System.out.println(list.size()); Collections.sort(list); int a = 0, b = 0; for (int i = 1; i < list.size(); i++) { if (list.get(i) - list.get(i - 1) == 2) a = list.get(i) - 1; if (list.get(i) - list.get(i - 1) == 0) b = list.get(i); } System.out.println(a + " " + b); } } 幸运数 /** * 幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成。 * * 首先从1开始写出自然数1,2,3,4,5,6,.... * * 1 就是第一个幸运数。 * 我们从2这个数开始。把所有序号能被2整除的项删除，变为： * * 1 _ 3 _ 5 _ 7 _ 9 .... * * 把它们缩紧，重新记序，为： * * 1 3 5 7 9 11 13 15 17 19.... 。这时，3为第2个幸运数，然后把所有能被3整除的序号位置的数删去。注意，是序号位置，不是那个数本身能否被3整除!! 删除的应该是5，11, 17, ... * * 此时7为第3个幸运数，然后再删去序号位置能被7整除的(19,39,...) * * 最后剩下的序列类似： * * 1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, ... * * 本题要求： * * 输入两个正整数m n, 用空格分开 (m < n < 1000*1000) * 程序输出 位于m和n之间的幸运数的个数（不包含m和n）。 * * 例如： * 用户输入： * 1 20 * 程序输出： * 5 * * 例如： * 用户输入： * 30 69 * 程序输出： * 8 * * 资源约定： * 峰值内存消耗（含虚拟机） < 64M * CPU消耗 < 2000ms * * * 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。 * * 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 * 注意：不要使用package语句。不要使用jdk1.6及以上版本的特性。 * 注意：主类的名字必须是：Main，否则按无效代码处理。 */ public class 幸运数 { public static void main(String[] args) { Scanner in = new Scanner(System.in); int m = in.nextInt(); int n = in.nextInt(); int[] a = new int[n+1]; for(int i=1;i<=n;i++) a[i] = i; for(int i=1;i<=n;i++) if(i%2==0) a[i] = Integer.MAX_VALUE; Arrays.sort(a); int t = n; for(int i=2;i<=t;i++) { int k = a[i]; if(k==Integer.MAX_VALUE) break; for(int j=k;j<=t;j+=k) a[j] = Integer.MAX_VALUE; Arrays.sort(a,1,t); for(int j=1;j<=t;j++) if(a[j]==Integer.MAX_VALUE) { t = j; break; } } int ans = 0; for(int i=1;i<=n;i++) { if(a[i]>m && a[i]<n) ans++; } System.out.println(ans); } } 带分数 import java.util.Scanner; /** * 100 可以表示为带分数的形式：100 = 3 + 69258 / 714 * * 还可以表示为：100 = 82 + 3546 / 197 * * 注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。 * * 类似这样的带分数，100 有 11 种表示法。 * * 题目要求： * 从标准输入读入一个正整数N (N<1000*1000) * 程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。 * 注意：不要求输出每个表示，只统计有多少表示法！ * * * 例如： * 用户输入： * 100 * 程序输出： * 11 * * 再例如： * 用户输入： * 105 * 程序输出： * 6 * * * 资源约定： * 峰值内存消耗（含虚拟机） < 64M * CPU消耗 < 3000ms * * * 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。 * * 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 * 注意：不要使用package语句。不要使用jdk1.6及以上版本的特性。 * 注意：主类的名字必须是：Main，否则按无效代码处理。 */ public class 带分数 { public static void main(String[] args) { Scanner in = new Scanner(System.in); x = in.nextInt(); dfs(0); System.out.println(ans); } static int ans = 0,n = 9,x; static int A[] = new int[] {1,2,3,4,5,6,7,8,9}; static void dfs(int m) { if(m>=9) { for(int i=1;i<n;i++) {// x = a + b/c x-a =b/c (x-a)*c=b int a=0; for(int k=0;k<i;k++) a = 10*a + A[k]; if(a>x) break; for(int j=i+1;j<n;j++) { int b=0,c=0; for(int k=i;k<j;k++) b = 10*b + A[k]; for(int k=j;k<n;k++) c = 10*c + A[k]; if((x-a)*c==b) ans++; } } return; } for(int i=m;i<n;i++) { swap(i,m); dfs(m+1); swap(i,m); } } private static void swap(int i, int j) { int t = A[i]; A[i] = A[j]; A[j] = t; } } 连号区间数 import java.util.Scanner; /** * 小明这些天一直在思考这样一个奇怪而有趣的问题： * * 在1~N的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是： * * 如果区间[L, R] 里的所有元素（即此排列的第L个到第R个元素）递增排序后能得到一个长度为R-L+1的“连续”数列，则称这个区间连号区间。 * * 当N很小的时候，小明可以很快地算出答案，但是当N变大的时候，问题就不是那么简单了，现在小明需要你的帮助。 * * 输入格式： * 第一行是一个正整数N (1 <= N <= 50000), 表示全排列的规模。 * 第二行是N个不同的数字Pi(1 <= Pi <= N)， 表示这N个数字的某一全排列。 * * 输出格式： * 输出一个整数，表示不同连号区间的数目。 * * 示例： * 用户输入： * 4 * 3 2 4 1 * * 程序应输出： * 7 * * 用户输入： * 5 * 3 4 2 5 1 * * 程序应输出： * 9 * * 解释： * 第一个用例中，有7个连号区间分别是：[1,1], [1,2], [1,3], [1,4], [2,2], [3,3], [4,4] * 第二个用例中，有9个连号区间分别是：[1,1], [1,2], [1,3], [1,4], [1,5], [2,2], [3,3], [4,4], [5,5] * * * 资源约定： * 峰值内存消耗（含虚拟机） < 64M * CPU消耗 < 5000ms * * * 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。 * * 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 * 注意：不要使用package语句。不要使用jdk1.6及以上版本的特性。 * 注意：主类的名字必须是：Main，否则按无效代码处理。 */ public class 连号区间数 { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] a = new int[n+1]; // int[][] max = new int[n+1][n+1]; // int[][] min = new int[n+1][n+1]; for(int i=1;i<=n;i++) a[i] = in.nextInt(); int ans=0; for(int i=1;i<=n;i++) { int max=-1,min=999999999; for(int j=i;j<=n;j++) { max = Math.max(max, a[j]); min = Math.min(min, a[j]); if(max-min<=j-i) ans++; } } System.out.println(ans); } }
先来介绍一下哈夫曼编码吧 哈夫曼树，二叉树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。哈夫曼编码则是根据字符出现频率(权重分布)，用最少的位数来表示。 (字符出现多的，用较短编码；字符出现少的，用较长编码)。 举个例子：好比这个字符串“abcddddddd”，如果用相同长度的编码来表示，4个不同数字则选用2位 (a->00,b->01,c->10,d->11)，那也就是需要 10 2 = 20长度； 而使用哈夫曼编码，则根据权重(a->010,b->011,c->00,d->1)，也就是需要:3+3+2+17 = 15长度。 在这个例子中相比平均编码则少了25%(当然这个例子比较夸张啦哈哈哈。权重分布一般不会这样，在这里主要是想说明哈夫曼编码能起到压缩编码长度的作用),但是在取哈夫曼编码的时候，要避开前缀(有可能某个数的编码刚好是另外某个数的编码前缀)，所以可以通过下面的方法计算出来。 一、基于建哈夫曼树的方法 算法过程： ①将输入的数值，每一个数值，分别都建立成一棵树(只有根节点的树)，就形成了森林。 ②将森林排序( 按权重，从大到小排序，选用插入排序即可，因为之后的排序每一次都只插入一个数值，只需要移动少量即可) ③取出后两棵树n1、n2，新创建一个根节点，然后将n1、n2作为其左右孩子，从而构成一棵新树(由新建根节点+n1(lchild)+n2(rchild)组成)，将这棵新树插入森林中。 ④重复②③，直到森林中只剩下一棵树，此时该树就是所求哈夫曼树。 ⑤遍历每一个叶子(每一个叶子就是输入数值)，根据遍历路径(往lchild则 +‘1’，往rchild 则 + ‘0’)，每一个叶子对应的数值+编码result，即是其哈夫曼编码。
BFS:Breadth First Search 广度优先搜索 DFS:Depth First Search 深度优先搜索 为了搜索 DFS，我们使用堆栈，为了搜索 BFS，我们使用队列。 广度优先搜索(BFS) 广度优先搜索(BFS):广度优先搜索构建一个广度优先的树，最初只包含它的根，也就是源顶点 s。每当搜索在扫描已经发现的顶点 u 的邻接表的过程中发现一个白色顶点 v 时，顶点 v 和边(u，v)就被添加到树中。我们说 u 是广度优先树中 v 的前 身或母体。因为顶点最多被发现一次，所以它最多有一个父顶点。广度优先树中的祖先和后代关系通常是相对于根 s 定义的:如果 u 在树中从根 s 到顶点 v 的简单路径上，那么 u 是 v 的祖先，v 是 u 的后代 BFS 算法的复杂性，取决于你是如何实现算法的。如果你用邻接矩阵来实现，那么复杂度就是O(n^2).如果你是通过邻接 表实现的，那么复杂度将是O(V+E)，其中E是边的数量。 graph={ 'a':['b','c'], 'b':['a','c','d'], 'c':['a','b','d','e'], 'd':['b','c','e','f'], 'e':['c','d'], 'f':['d'] } def BFS(graph, s): queue = [] queue.append(s) seen = set() seen.add(s) while(len(queue) > 0): v = queue.pop(0) nodes = graph[v] for w in nodes: if w not in seen: queue.append(w) seen.add(w) print(v) BFS(graph, 'a') 深度优先搜索：DFS 与广度优先搜索一样，深度优先搜索在搜索过程中对顶点进行着色，以指示它们的状态。每个顶点最初都是白色的，当在搜索中发现它时，它是灰色的，当它完成时，也就是说，当它的邻接表被完全检查时，它是黑色的。这种技术保证了每个顶点恰好在一个深度优先的树中结束，因此这些树是不相交的。除了创建深度优先的森林，深度优先搜索还会为每个顶点添加时间戳。每个顶点 v 都有两个时间戳:第一个时间戳 v.d 记录了第一次发现 v 的时间(并呈灰色)，第二个时间戳 v.f 记录了搜索完成检查 v 的邻接表的时间(并使 v 变黑)。这些时间戳提供了关于图结构的重要信息，通常有助于推理深度优先搜索的行为。 graph1 = { 'A' : ['B','S'], 'B' : ['A'], 'C' : ['D','E','F','S'], 'D' : ['C'], 'E' : ['C','H'], 'F' : ['C','G'], 'G' : ['F','S'], 'H' : ['E','G'], 'S' : ['A','C','G'] } def dfs(graph, node, visited): if node not in visited: visited.append(node) for n in graph[node]: dfs(graph,n, visited) return visited visited = dfs(graph1,'A', []) print(visited)
堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法. 而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。 排序的好处： 1、如果只是简单的进行数字的排序，那么稳定性将毫无意义。 2、如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性依旧将毫无意义（所谓的交换操作的开销已经算在算法的开销内了，如果嫌弃这种开销，不如换算法好了？） 3、如果要排序的内容是一个复杂对象的多个数字属性，但是其原本的初始顺序毫无意义，那么稳定性依旧将毫无意义。 4、除非要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法，例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。（当然，如果需求不需要保持初始的排序意义，那么使用稳定性算法依旧将毫无意义）。 插入排序算法(insert Sort) 插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开 始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相 等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。 插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 算法描述 一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下： 从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，将该元素移到下一位置；重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后； 重复步骤2~5。 void InsertSort(int a[], int n) { for(int i= 1; i<n; i++){ if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入 int j= i-1; int x = a[i]; //复制为哨兵，即存储待排序元素 a[i] = a[i-1]; //先后移一个元素 while(x < a[j]){ //查找在有序表的插入位置 a[j+1] = a[j]; j--; //元素后移 } a[j+1] = x; //插入到正确位置 } print(a,n,i); //打印每趟排序的结果 } } 归并排序（Merge Sord） 归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有 序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定 性。那么，在短的有序序列合并的过程中，稳定是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结 果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 算法描述 把长度为n的输入序列分成两个长度为n/2的子序列；对这两个子序列分别采用归并排序；将两个排序好的子序列合并成一个最终的排序序列。 //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n] void Merge(ElemType *r,ElemType *rf, int i, int m, int n) { int j,k; for(j=m+1,k=i; i<=m && j <=n ; ++k){ if(r[j] < r[i]) rf[k] = r[j++]; else rf[k] = r[i++]; } while(i <= m) rf[k++] = r[i++]; while(j <= n) rf[k++] = r[j++]; print(rf,n+1); } void MergeSort(ElemType *r, ElemType *rf, int lenght) { int len = 1; ElemType *q = r ; ElemType *tmp ; while(len < lenght) { int s = len; len = 2 * s ; int i = 0; while(i+ len <lenght){ Merge(q, rf, i, i+ s-1, i+ len-1 ); //对等长的两个子表合并 i = i+ len; } if(i + s < lenght){ Merge(q, rf, i, i+ s -1, lenght -1); //对不等长的两个子表合并 } tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf } } 快速排序(Quick Sort) 快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。 交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11， 现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 算法描述 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下： 从数列中挑出一个元素，称为 “基准”（pivot）； 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作； 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } int partition(int a[], int low, int high) { int privotKey = a[low]; /基准元素 while(low < high){ //从表的两端交替地向中间扫描 while(low < high && a[high] >= privotKey) --high; //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端 swap(&a[low], &a[high]); while(low < high && a[low] <= privotKey ) ++low; swap(&a[low], &a[high]); } print(a,10); return low; } void quickSort(int a[], int low, int high){ if(low < high){ int privotLoc = partition(a, low, high); //将表一分为二 quickSort(a, low, privotLoc -1); //递归对低子表递归排序 quickSort(a, privotLoc + 1, high);//递归对高子表递归排序 } } 二分查找（Binary Search） 二进制搜索(二分查找)算法是一种搜索算法。在每个步骤中，算法将输入元素(x)与数组中中间元素的值进行比较。如果值匹配，返回中间的索引。否则，如果 x 小于中间元素，则算法递归到中间元素的左侧，否则它递归到中间元素的右侧。 //二分查找函数 int Binary_search(SqList L,ElemType key) { int low = 0;int mid = 0;int high = L.length-1; while(low<=high) { mid = (low+high)/2; if(key==L.data[mid]) { return mid; } else if(key>L.data[mid]) { low = mid+1; } else { high = mid-1; } } return -1; } 冒泡排序（Bubble Sort） 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 算法描述 比较相邻的元素。如果第一个比第二个大，就交换它们两个； 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数； 针对所有的元素重复以上的步骤，除了最后一个； 重复步骤1~3，直到排序完成。 function bubbleSort(arr) { var len = arr.length; for (var i = 0; i < len - 1; i++) { for (var j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j+1]) { // 相邻元素两两对比 var temp = arr[j+1]; // 元素交换 arr[j+1] = arr[j]; arr[j] = temp; } } } return arr; } 选择排序（Selection Sort） 选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 算法描述 n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下： 初始状态：无序区为R[1..n]，有序区为空； 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；n-1趟结束，数组有序化了。 function selectionSort(arr) { var len = arr.length; var minIndex, temp; for (var i = 0; i < len - 1; i++) { minIndex = i; for (var j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { // 寻找最小的数 minIndex = j; // 将最小数的索引保存 } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } return arr; } 表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。 希尔排序（Shell Sort） 1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。 算法描述 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述： 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1； 按增量序列个数k，对序列进行k 趟排序； 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。 function shellSort(arr) { var len = arr.length; for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) { // 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行 for (var i = gap; i < len; i++) { var j = i; var current = arr[i]; while (j - gap >= 0 && current < arr[j - gap]) { arr[j] = arr[j - gap]; j = j - gap; } arr[j] = current; } } return arr; } 堆排序（Heap Sort） 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 算法描述 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区； 将堆顶元素R1与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]； 由于交换后新的堆顶R1可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R1与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。 var len; // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量 function buildMaxHeap(arr) { // 建立大顶堆 len = arr.length; for (var i = Math.floor(len/2); i >= 0; i--) { heapify(arr, i); } } function heapify(arr, i) { // 堆调整 var left = 2 * i + 1, right = 2 * i + 2, largest = i; if (left < len && arr[left] > arr[largest]) { largest = left; } if (right < len && arr[right] > arr[largest]) { largest = right; } if (largest != i) { swap(arr, i, largest); heapify(arr, largest); } } function swap(arr, i, j) { var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } function heapSort(arr) { buildMaxHeap(arr); for (var i = arr.length - 1; i > 0; i--) { swap(arr, 0, i); len--; heapify(arr, 0); } return arr; } 计数排序（Counting Sort） 计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。 算法描述 找出待排序的数组中最大和最小的元素；统计数组中每个值为i的元素出现的次数，存入数组C的第i项； 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。 function countingSort(arr, maxValue) { var bucket = new Array(maxValue + 1), sortedIndex = 0; arrLen = arr.length, bucketLen = maxValue + 1; for (var i = 0; i < arrLen; i++) { if (!bucket[arr[i]]) { bucket[arr[i]] = 0; } bucket[arr[i]]++; } for (var j = 0; j < bucketLen; j++) { while(bucket[j] > 0) { arr[sortedIndex++] = j; bucket[j]--; } } return arr; } 桶排序（Bucket Sort） 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。 算法描述 设置一个定量的数组当作空桶； 遍历输入数据，并且把数据一个一个放到对应的桶里去；对每个不是空的桶进行排序；从不是空的桶里把排好序的数据拼接起来。 function bucketSort(arr, bucketSize) { if (arr.length === 0) { return arr; } var i; var minValue = arr[0]; var maxValue = arr[0]; for (i = 1; i < arr.length; i++) { if (arr[i] < minValue) { minValue = arr[i]; // 输入数据的最小值 } else if (arr[i] > maxValue) { maxValue = arr[i]; // 输入数据的最大值 } } // 桶的初始化 var DEFAULT_BUCKET_SIZE = 5; // 设置桶的默认数量为5 bucketSize = bucketSize || DEFAULT_BUCKET_SIZE; var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1; var buckets = new Array(bucketCount); for (i = 0; i < buckets.length; i++) { buckets[i] = []; } // 利用映射函数将数据分配到各个桶中 for (i = 0; i < arr.length; i++) { buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]); } arr.length = 0; for (i = 0; i < buckets.length; i++) { insertionSort(buckets[i]); // 对每个桶进行排序，这里使用了插入排序 for (var j = 0; j < buckets[i].length; j++) { arr.push(buckets[i][j]); } } return arr; } 桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。 基数排序（Radix Sort） 基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。 算法描述 取得数组中的最大数，并取得位数；arr为原始数组，从最低位开始取每个位组成radix数组；对radix进行计数排序（利用计数排序适用于小范围数的特点）； var counter = []; function radixSort(arr, maxDigit) { var mod = 10; var dev = 1; for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { for(var j = 0; j < arr.length; j++) { var bucket = parseInt((arr[j] % mod) / dev); if(counter[bucket]==null) { counter[bucket] = []; } counter[bucket].push(arr[j]); } var pos = 0; for(var j = 0; j < counter.length; j++) { var value = null; if(counter[j]!=null) { while ((value = counter[j].shift()) != null) { arr[pos++] = value; } } } } return arr; } 基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。 基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。
找出问题的解集或什么解是满足约束条件的最佳解->回溯法 回溯法:搜索，或避免不必要搜索的穷举式搜索法。适用于解一些组合数相当大的问题。 在解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至任意一点时，先判断该结点是否包含问题的解。 如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。 基本思想 回溯法：类似穷举的搜索尝试过程，是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”（即回退），尝试别的路径。 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发搜索解空间树。 首先根结点成为活结点（自身已生成但其孩子结点没有全部生成的结点），同时也成为当前的扩展结点（正在产生孩子结点的结点）。 在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为新的活结点，并成为当前扩展结点。 如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点（由根结点到该结点构成的部分解不满足约束条件，或者其子结点已经搜索完毕）。 此时应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。 回溯法以这种方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点为止。 问题的解空间 •解向量：问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。 •解空间：所有满足约束条件的解向量组构成了问题的解空间。 •解空间树：问题的解空间一般用树形式来组织，也称为解空间树或状态空间，树中的每一个结点确定所求解问题的一个问题状态。 •例如，对于有n种可选择物品的0-1背包问题，当n=3时，其解空间是 {（0,0,0），（0,0,1），（0,1,0），（0,1,1），（1,0,0），（1,0,1），（1,1,0），（1,1,1）} 问题的解空间树 回溯法的解题步骤 根据上面0-1背包问题的例子，我们可以总结出回溯法解题的3大步骤： (1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构； (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 常用剪枝函数： 用约束函数在扩展结点处剪去不满足约束的子树； 用限界函数剪去得不到最优解的子树 • 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。 • 在任何时刻，算法只保存从根结点到当前扩展结点的路径。 • 如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。 • 而显式地存储整个解空间则需要O(2^h(n))或O(h(n)!)内存空间 旅行售货员问题 下面我们用回溯法的3大解题步骤来解旅行售货员问题 •某售货员要到若干城市去推销商品，已知各城市之间的路程（旅费），他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（总旅费）最小。 第一步，定义问题的解空间 旅行售货员问题的解空间是 • 1，2，3，4，1 • 1，2，4，3，1 • 1，3，2，4，1 • 1，3，4，2，1 • 1，4，2，3，1 • 1，4，3，2，1 第二步，确定解空间树 第三步，以深度优先搜索解空间树 回溯法的基本术语 • 活结点是指自身已生成但其孩子结点没有全部生成的结点 • 扩展结点是指正在产生孩子结点的结点 • 死结点是指由根结点到该结点构成的部分解不满足约束条件，或者其子结点已经搜索完毕 回溯法搜索解空间时，采用剪枝函数避免无效搜索，提高回溯的搜索效率: • 用约束函数在扩展结点处剪除不满足约束的子树； • 用限界函数剪去得不到问题解或最优解的子树。 • 子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。 • 排列树：当所给的问题是确定n个元素满足某种性质的排列时，相应的 解空间树称为排列树 回溯法的算法框架 非递归回溯框架(迭代回溯) int x[n]; //x存放解向量，全局变量 void Iterativebacktrack(void) //非递归框架 { int t=1; //根结点层次为1 while (t >0) //尚未回溯到头 { if(f(n,t)<=g(n,t)) //当前结点存在子结点 { for (int i=f(n,t);i<=g(n,t);i++) //用i枚举t所有可能的路径 { x[t]=h(i) //产生一个可能的解分量 h(i) if (constraint(t) && bound(t)) //x[i]满足约束条件或限界函数 { if (solution(t)) output(x); //到达叶子结点，输出一个可行解x else t++; //否则深度遍历下一层次 } } } else t--; //回溯：不存在子结点，返回上一层 } } 子集树递归算法框架 int x[n]; //x存放解向量，全局变量 void backtrack(int t) //求解子集树的递归框架 { if(t>n)Output(x); //搜索到叶子结点,输出一个可行解 else { for (int i=0;i<=1;i++) //用i枚举t所有可能的路径 { x[t]=i; //产生一个可能的解分量 … //其他操作 if (constraint(t) && bound(t)) backtrack(t+1); //满足约束条件和限界函数,继续下一层 } } } 排列树递归算法框架 遍历排列树需要O(n!)计算时间 int x[n]; //x存放解向量，并初始化 void backtrack(int t) //求解排列树的递归框架 { if(t>n)Output(x); //搜索到叶子结点,输出一个可行解 else { for (int i=t;i<=n;i++) //用i枚举t所有可能的路径 { … //第t层的结点选择x[i]的操作 swap(x[t],x[i]); //为保证排列中每个元素不同,通过交换来实现 if (constraint(t) && bound(t)) backtrack(t+1); //满足约束条件和限界函数，进入下一层 swap(x[t],x[i]); //恢复状态 … //第t层的结点选择x[i]的恢复操作 } } } n皇后问题 1.判断解是否可行的条件 我们从第一行开始放皇后，第一行有n个位置可以放，我们用x1来表示第一行的皇后所在的列，第二行有n-1个位置可以放，我们用x2来表示第二行皇后所在的列······因此，我们用一个数组x[n]来表示问题的解，x[i]表示皇后i放在第i行第x[i]列。 如何保证任何两个皇后不同一行，不同一列？ x[i]表示皇后i放在第i行第x[i]列。 x[k]表示皇后k放在第k行第x[k]列。 不同一行：i≠k  不同一列：x[i]≠x[k] 如何保证任何两个皇后不同一条斜线上？ 设两个皇后q1和q2放在（i，j）和（k，l）位置上，如果q1和q2在斜率为-1的对角线上，那么i - j = k - l成立。 如果在斜率为1的对角线上，那么i + j = k + l成立，由此可知只要 | i - k |≠ | j - l |成立，q1和q2就不再同一条斜线上。| i - k | ≠ | j 2.确定解空间 用完全n叉树表示解空间，现在以n=4为例： 皇后问题的解为：
贪心算法概念 • 贪心算法总是作出在当前看来最好的选择,不从整体最优考虑，在某种意义上的局部最优选择。希望得到的最终结果也是整体最优的。 • 贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路径问题，最小生成树问题等。 • 在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 贪心算法的基本要素 • 对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。 • 但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质 1、贪心选择性质 • 贪心选择性质：所求问题的整体最优解可通过一系列局部最优的选择，即贪心选择来达到。这是第一个基本要素，也是与动态规划算法的主要区别。 • 动态规划算法：自底向上，贪心算法：自顶向下，迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 • 对于一个具体问题，确定它是否具有贪心选择性质，须证明每一步所作的贪心选择最终导致问题的整体最优解。 2、最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 0-1背包问题： 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? • 背包问题： 与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。 用贪心算法解背包问题的基本步骤： • 计算每种物品单位重量的价值Vi/Wi • 依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包 • 若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包 • 依此策略一直地进行下去，直到背包装满为止。 • 具体算法可描述如下页：
• 最长公共子序列（LCS）的特征： 1、序列可连续，可不连续。 2、序列讲究顺序 3、答案不一定是唯一一个（有可能多个） 例如: X={ABCBDAB} ，Y={ BDCABA } 最长公共子序列有{BCBA}，{BDAB}，{BCAB} 穷举法：求LCS • 若要求两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列，先 取得X，Y的所有子序列，并进行一一比较，共有如下不同的组合： • X共有 个不同子序列， Y共有 个不同子序列， • 共要进行不同的比较：2m+n 次 • 可见穷举法产生指数级的时间复杂度为O(2m+n )，因此，对于长序列，这种方法不可行。 最长公共子序列的结构 设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，则 (1)若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。 (2)若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。 (3)若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。 由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质 子问题的递归结构 由最长公共子序列问题的最优子结构性质建立子问题最优值 的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。 其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。 故此时C[i][j]=0。由最优子结构性质可建立递归关系如下 计算最优值： 由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题， 因此，用动态规划算法自底向上地计算最优值能提高算法的效率 void LCSLength(int m，int n，char *x，char *y，int **c，int **b) { int i，j; for (i = 0; i <= m; i++) c[i][0] = 0; for (i = 1; i <= n; i++) c[0][i] = 0; for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) { if (x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1;} else if (c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2;} else { c[i][j]=c[i][j-1]; b[i][j]=3; } } } 【算法分析】 LCSlength算法中使用了两重循环，所以对于长度分别为m和n的序列，求其最长公共子序列的时间复杂度为O(m×n)。空间复杂度为O(m×n) 构造最长公共子序列 void LCS(int i，int j，char *x，int **b) { if (i ==0 || j==0) return; if (b[i][j]== 1){ LCS(i-1，j-1，x，b); //沿对角线方向，记为"↖ " cout<<x[i]; } //第一个字符存放在x[1]，所以第i个字符存放在x[i]中 else if (b[i][j]== 2) LCS(i-1，j，x，b); //向上记为，记为"↑" else LCS(i，j-1，x，b); //向左记为，记为"←" } 算法的改进 •在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元 素c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。 对于给定的数组元素c[i][j]，可以不借助于数组b而仅借助于c本身在时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。 •如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算c[i][j]时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n))