数字排列组合程序,以及程序优化的切身感受

发布时间:2016-12-10 1:22:48 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"数字排列组合程序,以及程序优化的切身感受",主要涉及到数字排列组合程序,以及程序优化的切身感受方面的内容,对于数字排列组合程序,以及程序优化的切身感受感兴趣的同学可以参考一下。

使用说明:        例如: 输入数字9,程序会在屏幕上输出1~9的所有数字组合(同一组合中不能重复使用同一数字),以及组合的种类数和所用时间。   体会: 这个程序使我深刻体户到优化的作用,优化程序后运行速度比原来快了60%~70%。   优化思路:        1、数组结合链表,使两者互补,扬长避短。        2、减少的循环数量。        3、减少System.out.print的使用次数   下面是两个版本的程序代码:   1、优化后的版本(考虑到页面宽度限制,所有注释写在代码行的上方)   import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*;   public class PermutationAndCombination {        //要排列组合的元素个数        private static int MAX_INDEX;        //当前排列中需要填入数字的索引位置        private static int finishIndex;        //已经完成的排列的数量        private static int finishCount;        //记录排列元素的数组        private int[] num;        //当前的排列组合        private LinkedList<Integer> savedNum;               public PermutationAndCombination(int max)        {               MAX_INDEX = max;               finishIndex = 0;               finishCount = 0;               num = new int[MAX_INDEX];               savedNum = new LinkedList<Integer>();               for(int i=0; i<MAX_INDEX; i++)               {                      num[i] = i+1;               }        }               public void doPermutationAndCombination()        {               saveNum(num);               System.out.println("一共 " + finishCount + "种组合!");        }        //完成排列组合,并输出到屏幕        private void saveNum(int[] num)        {               //循环数量由所处的递归层数决定               for(int i=0; i<MAX_INDEX-finishIndex; i++)               {                      //添加选中的元素到链表                      savedNum.addLast(num[i]);                      //记录已经选取的元素                      int numBuf = num[i];                      //记录以完成的排列组合数量                      if(finishIndex == (MAX_INDEX-1))                      {                             finishCount++;                      }                      //创建传入递归下一层要用的数组                      int nextNum[] = new int[MAX_INDEX - (finishIndex+1)];                      int m = 0;                      //拷贝未选用的数字                      for(int n=0; n<MAX_INDEX-finishIndex; n++)                      {                             if(num[n] == numBuf)                             {                                    continue;                             }                             else                             {                                    nextNum[m] = num[n];                                    m++;                             }                      }                      //是否继续递归                      if((MAX_INDEX - (finishIndex+1)) != 0)                      {                             //递归层数计数加1                             finishIndex++;                             saveNum(nextNum);                      }                      else                      {                             //输出这一轮递归生成的数字组合                             System.out.println(savedNum);                      }               }               try               {                      //判断是否是递归的最后一层                      if(finishIndex == (MAX_INDEX-1))                      {                             //移除排列组合的最后一位元素                             savedNum.removeLast();                             //移除排列组合的最后一位元素                             savedNum.removeLast();                      }                      else                      {                             //移除排列组合的最后一位元素                             savedNum.removeLast();                      }               }               catch(Exception e){}               finally               {                      //回到上一层,递归层数要减1                      finishIndex--;               }        }               public static void main(String[] args)        {               String theMaxString = null;               int theMax = 0;               try               {                      System.out.print("请输入数字: ");                      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                      theMaxString = br.readLine().trim();               }               catch(Exception e)               {                      e.printStackTrace();               }               try               {                      theMax = Integer.parseInt(theMaxString);               }               catch(Exception e)               {                      System.out.println("输入的数字格式不正确!");               }               PermutationAndCombination p = new PermutationAndCombination(theMax);               Date date = new Date();               p.doPermutationAndCombination();               System.out.println("用时" + (new Date().getTime() - date.getTime()) + "毫秒");        } }     2、未优化的版本   import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Date;   public class PermutationAndCombination2 {          private static int MAX_INDEX;        private static int finishIndex;        private static int finishCount;        private int[] num;        private int[] savedNum;               public PermutationAndCombination2(int max)        {               MAX_INDEX = max;               finishIndex = 0;               finishCount = 0;               num = new int[MAX_INDEX];               savedNum = new int[MAX_INDEX];               for(int i=0; i<MAX_INDEX; i++)               {                      num[i] = i+1;               }        }               public void doPermutationAndCombination()        {               saveNum(num);               System.out.println("一共 " + finishCount + "种组合!");        }               private void printNum()        {               for(int i=0; i<MAX_INDEX; i++)               {                      System.out.print(savedNum[i]);               }               System.out.println("");        }               private void saveNum(int[] num)        {                               for(int i=0; i<MAX_INDEX; i++)               {                      if(num[i] == 0)                      {                             continue;                      }                      int nextNum[] = new int[MAX_INDEX];                      for(int n=0; n<MAX_INDEX; n++)                      {                             nextNum[n] = num[n];                      }                      savedNum[finishIndex] = num[i];                      nextNum[i] = 0;                                           if(finishIndex == (MAX_INDEX-1))                      {                             finishCount++;                      }                        if((MAX_INDEX - (finishIndex+1)) != 0)                      {                             finishIndex++;                             saveNum(nextNum);                      }                      else                      {                             printNum();                      }               }               finishIndex--;        }               public static void main(String[] args)        {               String theMaxString = null;               int theMax = 0;               try               {                      System.out.print("请输入数字: ");                      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                      theMaxString = br.readLine().trim();               }               catch(Exception e)               {                      e.printStackTrace();               }               try               {                      theMax = Integer.parseInt(theMaxString);               }               catch(Exception e)               {                      System.out.println("输入的数字格式不正确!");               }               PermutationAndCombination2 p = new PermutationAndCombination2(theMax);               Date date = new Date();               p.doPermutationAndCombination();               System.out.println("用时" + (new Date().getTime() - date.getTime()) + "毫秒");        } }   接上篇! 今天是休息日。在昨天回家的路上,我又想了想《数字排列组合》那个程序,感觉影响程序速度的主要因素还是在于System.out.print。我做上一版优化的时候为了解决这个问题特意用了LinkedList存储排列好的数字,因为LinkedList有toString(),可以做到一列数字只用一个System.out.println就可以搞定,确实取得了很大的效果。 既然这样,那我把数组里的数字先转存到StringBuffer(试过直接用StringBuffer存数字,结果反而更慢),然后打印,速度会不会更快?于是,《数字排列组合》的第2版优化,应该也是最后一版出炉了,第二版优化程序运行时间比第一版缩短45%,比最初的原始版缩短了70%。   第2版优化程序源代码: import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Date;   public class PermutationAndCombination3 {          private static int MAX_INDEX;          private static int finishIndex;          private static int finishCount;          private int[] num;          private int[] savedNum;                   public PermutationAndCombination3(int max)          {                    MAX_INDEX = max;                    finishIndex = 0;                    finishCount = 0;                    num = new int[MAX_INDEX];                    savedNum = new int[max];                    for(int i=0; i<MAX_INDEX; i++)                    {                             num[i] = i+1;                    }          }                   public void doPermutationAndCombination()          {                    saveNum(num);                    System.out.println("一共 " + finishCount + "种组合!");          }            private void printNum()          {                    StringBuffer str = new StringBuffer();                    for(int i=0; i<MAX_INDEX; i++)                    {                             str.append(savedNum[i]);                    }                    System.out.println(str.toString());          }                   private void saveNum(int[] num)          {                    for(int i=0; i<MAX_INDEX-finishIndex; i++)                    {                             savedNum[finishIndex] = num[i];                             int numBuf = num[i];                             int nextNum[] = new int[MAX_INDEX - (finishIndex+1)];                             int m = 0;                             for(int n=0; n<MAX_INDEX-finishIndex; n++)                             {                                      if(num[n] == numBuf)                                      {                                                continue;                                      }                                      else                                      {                                                nextNum[m] = num[n];                                                m++;                                      }                             }                             if(finishIndex == (MAX_INDEX-1))                             {                                      finishCount++;                             }                             if((MAX_INDEX - (finishIndex+1)) != 0)                             {                                      finishIndex++;                                      saveNum(nextNum);                             }                             else                             {                                      printNum();                                                      }                    }                    finishIndex--;          }                   public static void main(String[] args)          {                    String theMaxString = null;                    int theMax = 0;                    try                    {                             System.out.print("请输入数字: ");                             BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                             theMaxString = br.readLine().trim();                    }                    catch(Exception e)                    {                             e.printStackTrace();                    }                    try                    {                             theMax = Integer.parseInt(theMaxString);                    }                    catch(Exception e)                    {                             System.out.println("输入的数字格式不正确!");                    }                    PermutationAndCombination3 p = new PermutationAndCombination3(theMax);                    Date date = new Date();                    p.doPermutationAndCombination();                    System.out.println("用时" + (new Date().getTime() - date.getTime()) + "毫秒");          } }

上一篇:在Option条目中填充前导空格的方法
下一篇:再练知言—“数学好玩”(摘)

相关文章

相关评论