算法设计原则

在平时的工作中遇到纯粹的算法设计的工作内容并不多，但是算法在编程中的重要性是不言而喻的，再怎么拔高算法的地位都不为过。

那么在设计算法中有什么可以遵循的原则吗？

答案是有的，算法在设计的过程中可以遵循如下五个原则。

1.穷举算法思想

穷举算法思想就是从所有的可能结果中一个一个的试验，知道试出正确的结果。具体的操作步骤如下：

1)对每一种可能的结果，计算其结果；

2)判断结果是否符合题目要求，如果符合则该结果正确，如果不符合则继续进行第1)步骤。

穷举算法思想的经典例子为鸡兔同笼为题（又称龟鹤同笼问题），题目为“一个笼子里有鸡兔，共15个头、46条腿，问鸡兔各有多少只？”。代码如下：

public static void main(String[] args) {

int head = 0; int leg = 0; System.out.println( "输入鸡兔头数："); Scanner input=new Scanner(System.in); head = input.nextInt(); System.out.println( "输入鸡兔腿数："); Scanner input1=new Scanner(System.in); leg = input1.nextInt(); boolean existence = false; for( int i = 0; i <= head; i++){ if( 2 * i + 4 * ( head - i) == leg){ System.out.println( "鸡的个数 :" + i); System.out.println( "兔的个数 :" + ( head - i)); existence = true; } } if( !existence){ System.out.println( "你输入的数据不正确"); } }

2.递推算法思想

递推算法算法就是根据已知条件，利用特定关系推导出中间推论，直到得到结果的算法。

递推算法思想最经典的例子是斐波那契数列 : 1,1,2,3,5,8,13......

上面的数列符合F(n) = F(n-1) + F(n-2).代码如下：

public static void main(String[] args) { Scanner input=new Scanner(System.in); int n = input.nextInt(); System.out.println( fibonacci( n)); } public static int fibonacci( int n){ if( n == 1){ return 1; }else if( n == 2){ return 1; }else{ return fibonacci( n - 1) + fibonacci( n - 2); } }

3.递归算法思想

递归算法思想是把大问题转换成同类问题的子问题，然后递归调用函数表示问题的解。

在使用递归的时候一定要注意调回递归函数的终止条件。

递归算法比较经典的例子是求阶乘。代码如下：

public static void main(String[] args) { System.out.println( "输入一个大于零的数："); Scanner input=new Scanner(System.in); int n = input.nextInt(); System.out.println( factorial( n)); } public static int factorial( int n){ if( n == 0){ return 1; }else if( n == 1){ return 1; }else{ return ( n * factorial( n-1)); } }

4.分治算法思想

分治算法思想就是把一个大问题分解成若干个规模较小的子问题，且这些子问题的都是相互独立的、与原问题性质一致。逐个求出这些子问题的解就能够得到原问题的解了。

分治算法思想有一个比较经典的例子就是查找假币问题。

题目描述：现有35枚硬币，其中只有一枚是假币。已知假币与真币外表完全一样，只是比真币轻一点。请找出假币。代码如下：

public static void main(String[] args) { int index = 0; System.out.println( "输入金币总数："); Scanner input = new Scanner( System.in); index = input.nextInt(); int[] arrayInt = new int[ index]; for( int i=0; i arrayInt[high]){ return high; }else{ return low; } } tmp = high - low + 1; if( tmp % 2 == 0){ int tmp1 = totalWeight( arrayInt, low, low + tmp/2 -1); int tmp2 = totalWeight( arrayInt, low + tmp/2, high); if( tmp1 > tmp2){ return findFalseCoin( arrayInt, low + tmp/2, high); }else{ return findFalseCoin( arrayInt, low, low + tmp/2 -1); } }else{ int tmp1 = totalWeight( arrayInt, low, low + tmp/2 -1); int tmp2 = totalWeight( arrayInt, low + tmp/2 +1, high); if( tmp1 > tmp2){ return findFalseCoin( arrayInt, low + tmp/2 +1, high); }else if( tmp1 < tmp2){ return findFalseCoin( arrayInt, low, low + tmp/2 -1); }else{ return low + tmp/2; } } } public static int totalWeight( int[] arrayInt, int low, int high){ int sum = 0; for( int i = low; i <= high; i++){ sum += arrayInt[ i]; } return sum; }

5.概率算法思想

51.数值概率算法

5.2蒙特卡罗算法

5.3拉斯维加斯算法

5.4舍伍德算法

这个算法思想还没有理解，欢迎大家补充。