5种算法思想

算法思想"/>

5种算法思想

package BaseAlgo;import java.util.Scanner;/** 递归算法：不断反复调用自身来解决问题。要求问题能够分解为相同问题的一个子问题。* 直接递归：调用本身* 间接递归：a 调用b b 再调用a；（用的不多）* 递归前一般有一个if语句作为递归出口，否则无限调用自身，引发堆栈溢出。* * 实例：阶乘问题*/
public class Digui {public static int fact(int n){if(n<=1){return 1;//出口}else{return n* fact(n-1);}}public static void main(String[] args) {System.out.println("输入要求阶乘的一个整数：");Scanner input = new Scanner(System.in);int n = input.nextInt();System.out.println("阶乘的结果为：" + fact(n));}}

package BaseAlgo;import java.util.Scanner;/** 递推算法：根据已有的数据和关系，逐步推导而得到结果。常用于数学场合，能够抽象出数学公式* 1.根据已知结果和关系（明确逻辑关系），求中间结果。* 2. 判断是否达到要求，如果没达到，则继续求，如果满足要求，则表示寻找到一个正确答案* * 实例：一对两个月大的兔子以后每一个月都可以生一对小兔子，而新生兔子要出生两个月后才能生小兔子。如1月出生，* 3月才能产仔。问一年后有几对兔子？* 规律：每月兔子总数等于前两个月的兔子数之和。*/public class ditui {public static int fibonacci(int n){int t1, t2;if(n == 1 || n==2){return 1;}else{t1 = fibonacci(n-1);t2 = fibonacci(n-2);//递归return t1 + t2 ;}}public static void main(String[] args) {System.out.println("递推算法求兔子产仔问题！");System.out.println("输入时间月数：");Scanner input = new Scanner(System.in);int n = input.nextInt();int num =  fibonacci(n);System.out.println("一对兔子经过" + n +"个月的繁殖后" + "共有" + num + "对兔子！" );}}

package BaseAlgo;import java.util.Scanner;/** 穷举算法 Exhaustive Attack method* 依赖计算机强大的计算能力，来穷尽每一种可能的情况。选出符合要求的结果。* 执行步骤：1.对于一种可能的情况，计算其结果。2，判断结果是否满足需求，如不满足进行第一步。* * 实例：鸡兔同笼问题：上有三十五头，下有九十四足，问兔鸡各几何？*/
public class ExhaustiveAttackmethod {static int chichen,rabbit;public static int qiongju(int foot, int head){int re ,j ,i;re=0;for(i=0;i<=head;i++){j=head-i;if(i*4+j*2 == foot){re=1;chichen = j;rabbit = i;}}return re;}public static void main(String[] args) {int re , foot,head;System.out.println("用穷举算法计算鸡兔同笼问题：");Scanner input = new Scanner(System.in);System.out.println("请输入头数：");head = input.nextInt();System.out.println("请输入脚数：");foot = input.nextInt();re = qiongju(foot,head);if(re==1){System.out.println("鸡有" + chichen + "只，" + "兔有" + rabbit +"只。");}else{System.out.println("无解！");}}
}

package BaseAlgo;import java.util.Scanner;/** 分治算法：将一个计算复杂的问题分为规模小，计算简单的小问题来求解。然后再综合各个小问题，而得到最终的答案。* 执行过程：* 1.对于一个规模为N的问题，若该问题可以容易地解决，则直接解决，否则执行以下步骤。* 2.分解问题为M个规模的子问题，这些子问题是相互独立的，并且与原问题形式相同。* 3.递归地解决这些子问题* 4.然后，将子问题的解合并得到原问题的解。* * 实例：有30个硬币，其中有一枚是假币，知假币比真币轻，问如何找到假币？* * 分析：将硬币均分为两堆，放到天平上去称，较轻的一堆包含假币，重复上述操作，* 直到剩下两枚时，就可以直接用天平找出假币。* */public class Fenzhi {static final int MAXNUM = 30;static int FindFalseCoin(int coin[], int low ,int high){int i ,sum1,sum2,sum3;int re = 0;sum1=sum2=sum3=0;//两枚硬币时if(low+1 == high){if(coin[low]<coin[high]){re = low + 1;//数组初始下标为0 ，需加一return re;}else{re = high+1;return re;}}//大于2且为偶数时if((high - low +1)%2 == 0){for(i=low;i<=low+(high-low)/2;i++){sum1 = sum1 + coin[i];//总重量
            }for(i= low + (high-low)/2+1; i<=high;i++){sum2 = sum2 + coin[i];//另一对待的总重量
            }if(sum1<sum2){re = FindFalseCoin(coin, low, low+(high-low)/2);return re;}else if(sum1>sum2){re = FindFalseCoin(coin, low+(high-low)/2+1, high);return re;}else{}}//奇数else{for(i=low;i<=low+(high-low)/2-1;i++){sum1 = sum1 +coin[i];}for(i=low+(high-low)/2+1;i<=high;i++){sum2 = sum2 + coin[i];}sum3=coin[low+(high-low)/2];//中间数if(sum1>sum2){re = FindFalseCoin(coin, low+(high-low)/2+1, high);return re;}else if(sum1<sum2){re = FindFalseCoin(coin, low, low+(high-low)/2-1);return re;}else{}if(sum2+sum3 == sum1+sum3) {re = low+(high-low)/2+1;return re;}}return re;}public static void main(String[] args) {int[] coin = new int[MAXNUM];int i,n,posion;System.out.println("分治算法求解假硬币问题！");System.out.println("请输入硬币总个数：");Scanner input = new Scanner(System.in);n =input.nextInt();System.out.println("输入各个硬币的总量：");for(i=0;i<n;i++){coin[i] = input.nextInt();}posion= FindFalseCoin(coin, 0, n-1);System.out.println("在上述" + n + "个硬币中，第" + posion + "个是假硬币！" );}}

package BaseAlgo;import java.util.Scanner;/** 概率算法：用概率统计思路来解决问题，不能得到问题的实际接，但可得到近似值。* 基本步骤：* 1.将问题转化为相应的几何图形S,S的面积是容易计算的，为题的结果往往对应几何图形中的某一部分S1的面积。* 2.然后，向几何图形随机撒点。* 3.统计几何图形S中和S1中的点数。根据S面积和S1面积的关系以及各图形中的点数来计算得到结果。* 4.判断上述结果是否在需要的精度之内，如果未达到精度则再进行步骤二。* * 数值概率算法：蒙特卡罗（Monte Carlo）、拉斯维加斯（Las Vegas）、舍伍德（Sherwood）。* * Monte Carlo实例：计算圆周率π。*/
public class Gailv {static double MontePI(int n ){double PI;double x,y;int i,sum;sum = 0;for(i=1;i<n;i++){x= Math.random();y=Math.random();if(x*x + y*y <= 1 ){sum++;}}PI=4.0*sum/n;return PI;}public static void main(String[] args) {int n;double PI;System.out.println("蒙特卡罗概率算法计算π：");Scanner input = new Scanner(System.in);System.out.println("输入点的数量：");n = input.nextInt();PI = MontePI(n);System.out.println("π=" + PI);}
}

转载于:.html