数据结构和算法示例一

程序等于数据架构加算法，一个好的算法可以有效的提高程序整体的性能体现。举一个最简单的例子：解析三元一次方程组，假设现在手上有一块的硬币，还有合计50个1分、2分、5分的硬币，现在要把1块钱的硬币全部换成以分为单位的硬币，大概有多少种换法？

根据题意，假设最后换成的硬币组成包括i枚1分的硬币、j枚2分的硬币、k枚5分的硬币，则可列出三元一次方程组如下：i+j+k=50;i+2j+5k=100;

方程组的解析用程序来实现有三种实现方式，分别对应的运算次数为n的立方、n的平方、n。

1. 第一种计算方式是直接用三层嵌套循环来运算，这样能算出来结果，但算法复杂度为n的立方，如示例代码中的doMethod1方法。
2. 第二种计算方式是用两层嵌套循环来运算，算法复杂度为n的平方，如示例代码中的doMethod2。
3. 第三计算方式是只用一层循环来运算，但需要通过转换，将两个方程左右分别相减，最后得到一个二元一次方程，这样就只需要循环一次即可，如示例代码中的doMethod3。

   package dataStructure;
   import java.util.Arrays;
   /*
    * 通过分硬币问题，研究算法对性能的影响
    * 假设1块钱，还有一分、2分、5分的硬币共50枚，现在讲1块钱全部换成分的硬币，大概有多少分法
    * 假设1分、2分、五分分别为x、y、z枚，则
    * x+y+z=50
    * x+2y+5z=100
    */
   public class Demo1 {
      public static void main(String args[]) {
   	   doMethod1();//循环三次，算法时间复杂度为n的立方
   	   System.out.println("---------");
   	   doMethod2();//循环两次，算法时间复杂度为n的平方
   	   System.out.println("---------");
   	   doMethod3();//循环一次，算法时间复杂度为n
      }
      
      public static void doMethod1() {
   	   //分别定义x,y,z的个位数为i,j,k
   	   for(int i=0;i<51;i++) {
   		   for(int j=0;j<51;j++) {
   			   for(int k=0;k<51;k++) {
   				   if((i+j+k==50)&& (i+2*j+5*k == 100)) {
   					   int[] array = {i,j,k};
   					   System.out.println("个数分别为："+Arrays.toString(array));
   				   }
   			   }
   		   }
   	   }
      }
      
      public static void doMethod2() {
   	   //分别定义x,y的个位数为i,j,则y的个数为50-i-j
   	   for(int i=0;i<51;i++) {
   		   for(int j=0;j<51;j++) {
   				   if(i+2*j+5*(50-i-j)== 100) {
   					   int[] array = {i,j,50-i-j};
   					   System.out.println("个数分别为："+Arrays.toString(array));
   			   }
   		   }
   	   }
      }
      /*
       *  分别定义x,y，z的个位数为i,j,k，
       *  i+2j+5k=100 
       *  i+j+k=50
       *  将两个方程分别左右相减，得到
       *  j+4k=50;
       */
      public static void doMethod3() {
   	   for(int j=0;j<51;j++) {
   		   for(int k=0;k<13;k++) {
   				   if(j+4*k == 50) {
   					   int[] array = {50-j-k,j,k};
   					   System.out.println("个数分别为："+Arrays.toString(array));
   			   }
   		   }
   	   }
      }
   }