新手学网站建设看什么书好,seo优化关键词,drupal vs wordpress,全国学校网站建设场景
1、分治算法的基本思想是将一个计算复杂的问题分成规模较小、计算简单的小问题求解#xff0c;
然后综合各个小问题#xff0c;得到最终答案。
2、穷举(又称枚举)算法的基本思想是从所有可能的情况中搜索正确的答案。
3、迭代法(Iterative Method) 无法使用公式一次…场景
1、分治算法的基本思想是将一个计算复杂的问题分成规模较小、计算简单的小问题求解
然后综合各个小问题得到最终答案。
2、穷举(又称枚举)算法的基本思想是从所有可能的情况中搜索正确的答案。
3、迭代法(Iterative Method) 无法使用公式一次求解而需要使用重复结构(即循环)重复执行
一段代码来得到答案。
4、递归调用是一个方法在其方法体内调用其自身方法。
5、递推算法是一种理性思维模式的代表其根据已有的数据和关系逐步推导而得到结果。
6、动态规划法(Dynamic Programming Algorithm,DPA)类似于分治法动态规划法的主要做法
如果一个问题的答案与子问题相关就能将大问题拆解成各个小问题
其中与分治法最大的不同是可以让每一个子问题的答案被存储起来以供下次求解时直接取用。
这样的做法不仅可以减少再次计算的时间而且可以将这些解组合成大问题的解可以解决重复计算的问题。
7、回溯法也是枚举法的一种它的特点就是在搜索过程中寻找问题的解当发现不满足求解条件时就回溯(返回)
尝试别的路径避免无效搜索。
8、贪心法(Greed Method)又称贪婪算法从某一起点开始在每一个解决问题的步骤使用贪心原则
即采用在当前状态下最有利或最优化的选择不断地改进该解答持续在每一个步骤中选择最佳的方法
并且逐步逼近给定的目标当达到某一个步骤不能再继续前进时算法就停止以尽可能快的方法求得更好的解。
注
博客霸道流氓气质的博客_CSDN博客-C#,架构之路,SpringBoot领域博主
实现
1、分治算法
举个例子:要以人工的方式将散落在地上的打印纸从第一个排序整理到第100页一种方式是逐一捡起稿纸
按照页码顺序插入到正确的位置。这样的排序和整理的过程比较复杂且浪费时间可以采用分治法的原理
先将页码1到10放在一起页码11到20放到一起以此列推将原来的100页分类成10个页码区间
然后对10堆页码进行整理最后从页码小到大的分组合并。
代码实例-求最大值 public static int getMax(int[] a,int begin,int end){//元素小于2个直接找出最大值if(end -begin 1){if(a[begin]a[end])return a[begin];elsereturn a[end];//否则进入递归}else {int center (beginend)/2;int left getMax(a,begin,center);int right getMax(a,center,end);return leftright?left:right;}}public static void main(String[] args) {int[] a new int[]{2,5,8,45,65,2,44,532,33};System.out.println(最大值:getMax(a,0,a.length-1));}
2、穷举实例-鸡兔同笼 static int chichen; //鸡的个数static int habbit; //兔的个数public static int qiongju(int head,int foot){int re,i,j;re 0;for(i0;ihead;i){j head - i;if(i*2 j*4 foot){re 1;chichen i;habbit j;}}return re;}public static void main(String[] args) {int re,head,foot;System.out.print(输入头数:);Scanner input new Scanner(System.in);head input.nextInt();System.out.print(输入脚数:);foot input.nextInt();re qiongju(head,foot);if (re 1){System.out.println(鸡有chichen只兔有habbit只。);}else {System.out.println(无法求解);}}
3、迭代实例-for循环计算n! public static void main(String[] args) {int sum 1;for(int i 1;i8;i){for(int j i;j0;j--){sum sum * j;}System.out.println(i!sum);sum 1;}}
4、递归调用 static long fact(int n){if(n1)return 1;elsereturn n*fact(n-1);}public static void main(String[] args) {int i;System.out.print(请输入一个要阶乘的数);Scanner input new Scanner(System.in);i input.nextInt();System.out.println(i的阶乘结果为:fact(i));}
5、递推算法 1、根据已知结果和关系求解中间结果。 2、判断是否达到要求如果没有达到则继续根据已知结果和关系求解中间结果如果满足要求则表示寻找到一个正确的答案 数学里面的斐波那契数列是使用递推算法的经典例子 兔子产仔问题如果一对两个月大的兔子以后每一个月都可以生一对小兔子而一对新生的兔子出生两个月后才可以生小兔子。 也就是说1月份出生3月份才可产仔。那么假定一年内没有发生兔子死亡事件那么一年后共有多少对兔子 第一个月1对兔子 第二个月1对兔子 第三个月2对兔子 第四个月3对兔子 第五个月5对兔子 从第三个月开始每个月的兔子总对数等于前两个月兔子数的综合 public static int fibonacci(int n){int t1,t2;if(n1 || n 2){return 1;}else{t1 fibonacci(n-1);//递归调用t2 fibonacci(n-2);return t1t2;}}public static void main(String[] args) {System.out.print(请先输入时间);Scanner input new Scanner(System.in);int n input.nextInt();int num fibonacci(n);System.out.println(经过n月的时间共繁殖成num对兔子);}
6、动态规划-斐波那契优化 public static int output[] new int[1000];public static int fib(int n){int result;result output[n];if(result0){if(n0)return 0;if(n1)return 1;elsereturn (fib(n-1)fib(n-2));}output[n] result;return result;}public static void main(String[] args) {int fib fib(8);System.out.println(fib);}
7、回溯法示例-老鼠走迷宫
老鼠走迷宫采用尝试错误的方法找到出口在走错路时就退回来并把走过的路记下来避免下次走重复的路就这样找到出口为止。
老鼠需要遵守以下三个原则:
1、一次只能走一格。
2、遇到墙无法往前走则退回一步寻找其它路。
3、走过的路不再走第二次。
使用二维数组代表地图值为1则代表不能通行值为0则代表可以通行。
假设老鼠从左上角[1][1]进入从右下角[8][10]出来。
可以使用链表来记录走过的位置并且将走过的位置所对应的数组元素内容标记为2然后将这个位置放入堆栈再进行下一个方向
或路的选择。如果走到死胡同并且还没有抵达终点就退回到上一个位置再选择其他的路。由于每次新加入的位置必定会在堆栈的
顶端因此堆栈顶端指针所指向的方格编号就是当前老鼠的位置如此重复直至走到迷宫出口为止。
public class HuiSu {// 记录老鼠迷宫的行进路径public static int ExitX 8; //定义出口的X坐标在第8列public static int ExitY 10; //定义出口的Y坐标在第10行public static int [][] MAZE {//声明迷宫数组{1,1,1,1,1,1,1,1,1,1,1,1},{1,0,0,0,1,1,1,1,1,1,1,1},{1,1,1,0,1,1,0,0,0,0,1,1},{1,1,1,0,1,1,0,1,1,0,1,1},{1,1,1,0,0,0,0,1,1,0,1,1},{1,1,1,0,1,1,0,1,1,0,1,1},{1,1,1,0,1,1,0,1,1,0,1,1},{1,1,1,1,1,1,0,1,1,0,1,1},{1,1,0,0,0,0,0,0,1,0,0,1},{1,1,1,1,1,1,1,1,1,1,1,1}};public static void main(String args[]) throws IOException{int i,j,x,y;TraceRecord pathnew TraceRecord();x1;y1;System.out.print([迷宫的路径(0的部分)]\n);for(i0;i10;i){for(j0;j12;j)System.out.print(MAZE[i][j]);System.out.print(\n);}while(xExitXyExitY){MAZE[x][y]2;if(MAZE[x-1][y]0){x - 1;path.insert(x,y);}else if(MAZE[x1][y]0){x1;path.insert(x,y);}else if(MAZE[x][y-1]0){y-1;path.insert(x,y);}else if(MAZE[x][y1]0){y1;path.insert(x,y);}else if(chkExit(x,y,ExitX,ExitY)1)break;else{MAZE[x][y]2;path.delete();xpath.last.x;ypath.last.y;}}System.out.print([老鼠走过的路径(2的部分)]\n);for(i0;i10;i){for(j0;j12;j)System.out.print(MAZE[i][j]);System.out.print(\n);}}public static int chkExit(int x,int y,int ex,int ey){if(xexyey){if(MAZE[x-1][y]1||MAZE[x1][y]1||MAZE[x][y-1] 1||MAZE[x][y1]2)return 1;if(MAZE[x-1][y]1||MAZE[x1][y]1||MAZE[x][y-1] 2||MAZE[x][y1]1)return 1;if(MAZE[x-1][y]1||MAZE[x1][y]2||MAZE[x][y-1] 1||MAZE[x][y1]1)return 1;if(MAZE[x-1][y]2||MAZE[x1][y]1||MAZE[x][y-1] 1||MAZE[x][y1]1)return 1;}return 0;}static class Node{int x;int y;Node next;public Node(int x,int y){this.xx;this.yy;this.nextnull;}}static class TraceRecord{public Node first;public Node last;public boolean isEmpty(){return firstnull;}public void insert(int x,int y){Node newNodenew Node(x,y);if(this.isEmpty()){firstnewNode;lastnewNode;}else{last.nextnewNode;lastnewNode;}}void delete(){Node newNode;if(this.isEmpty()){System.out.print([队列已经空了]\n);return;}newNodefirst;while(newNode.next!last)newNodenewNode.next;newNode.nextlast.next;lastnewNode;}}
}
即迷宫路线如下 运行结果 8、贪心算法示例-零钱最少找零 public static void greedMoney(int money){System.out.println(需要找零:money);int[] moneyLevel {1,5,10,20,50,100};for(int i moneyLevel.length -1;i0;i--){int num money/moneyLevel[i];int mod money % moneyLevel[i];money mod;if(num0)System.out.println(需要num张moneyLevel[i]块);}}public static void main(String[] args) {greedMoney(1562);} //输出结果: //需要找零:1562 //需要15张100块 //需要1张50块 //需要1张10块 //需要2张1块
如果不限制纸币的金额那这种情况还适合用贪心算法么。 比如1元2元3元4元8元15元的纸币用来支付K元至少多少张纸币
经我们分析这种情况是不适合用贪心算法的因为我们上面提供的贪心策略不是最优解。
比如纸币1元5元6元要支付10元的话按照上面的算法至少需要1张6元的4张1元的而实际上最优的应该是2张5元的。
所以贪心算法是一种在某种范围内局部最优的算法。
