2014年4月2日 星期三

遞迴跟排序

各種遞回方法
以下Fibonacci forLoop
import java.io.*;
import java.util.*;
import java.awt.*;
class fibonacci{
public static void main(String arg[])throws IOException
{
  double i=new Date().getTime();//取起始時
  double g=fib(10000);
double j=new Date().getTime();//取終止時
double k=j-i;
  System.out.println("needed time  : "+k);
  System.out.println("begin  : "+i);
System.out.println("end  : "+j);
System.out.println("answer  : "+g);

}
public static double fib(int n)
  {
    double i=2,j=3,k=0;//5以上才用for回圈
    if(n==0)
      return 0;
      if(n==1)
      return 1;
      if(n==2)
      return 1;
     if(n==3)
      return 2;
      if(n==4)
      return 3;
else{
    for(int g=5;g<n+1;g++)
   {
       k=i+j;//儲存上兩個數
     i=j;
     j=k;
   }return k;}
}}
以下是Fibonacci for recurtive
import java.io.*;
import java.util.*;
import java.awt.*;
class fibonacci{
public static void main(String arg[])throws IOException
{
  long i=new Date().getTime();
  long g=fib(60);
long j=new Date().getTime();
long k=j-i;
  System.out.println("needed time  : "+k);
  System.out.println("begin  : "+i);
System.out.println("end  : "+j);
System.out.println("answer  : "+g);

}
public static long fib(int n)//用遞回結果會生爆炸性
  {
    if(n<=1)
      return n;
      else
       return fib(n-1)+fib(n-2);
}}
以下是Hanoi for recursive
import java.io.*;
import java.util.*;
import java.awt.*;
class fibonacci{
public static void main(String arg[])throws IOException
{
 
  long i=new Date().getTime();
int h=move_tower(30,1,3);
long j=new Date().getTime();
long k=j-i;
  System.out.println("needed time  : "+k);
 
  System.out.println("begin  : "+i);
System.out.println("end  : "+j);
System.out.println("move times  : "+h);

}
 public static int move_tower(int m, int i, int j)
      {
      if(m==1)
      return m;
      else

      {        //會傳回要搬動之次數
            return move_tower(m-1, i, 6-i-j)+1+move_tower(m-1, 6-i-j,j);
          }
      }

}
各種排序方法的比較
import java.io.*;
import java.util.*;
class doit
{
  public static void main(String args[])throws IOException
  {
   BufferedReader br=new BufferedReader(new FileReader("do.dat"));//讀檔
   BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(new        
    FileOutputStream(new File("do.dat"))));//寫檔
    
   String line=null;
   int k=100000;//在此改變數值可產生不同亂數數目
   int b[]=new int[k];
   for(int i=0;i<k;i++)
   {
     b[i]=(int)(Math.random()*k);//生亂數
   }
   //insertionSort(b);//可決定是否要排序
    for(int i=0;i<k;i++)
   {
   // System.out.print(b[i]);//可觀查陣列
   // System.out.println();
      bw.write(b[i]+"");//寫到檔案中
      bw.newLine();
   }
   bw.flush();
   bw.close();
  }
  public static void insertionSort(int []a)
  {
   for(int p=1;p<a.length;p++)
   {
     int tmp = a[p];
     int j = p;
     for(; j>0&& tmp>(a[j-1]);j--)//<則由大到小排,>則反之
      a[j]=a[j-1];
      a[j]=tmp;
   }}}
    以下是我的sorting工具:
import java.io.*;
import java.util.*;
public class oo
{
 public static void main(String [] args)throws IOException  //main
  {
  BufferedReader br = new BufferedReader (new InputStreamReader(new   
  FileInputStream(new File("do.dat"))));//讀檔
  String s=null;
  Vector v=new Vector();
  while (true){
  String k=br.readLine();
         if (k==null)
            break;
         if (k.length()!=0)
            v.addElement(k);//把所讀的儲到vector
    }
    int [] g =new int[100000];//改變數字可決定數字數目
    for (int i=0;i<v.size();i++){
       String y=(String)v.elementAt(i);
       int b=Integer.parseInt(y);//再一一取出轉成Int再儲入g[I]
       g[i]=b;
     }
     //display(g);//可決定是否要印
    System.out.println("start: "+new Date().getTime());//印出起始時間
    int f=g.length;
    //qsort(g,f);
  //g=bubbleSort(g);
   //insertionSort(g);      //可決定要做哪個sorting
   //selectSort(g);
    bis(g);
         System.out.println("end  : "+new Date().getTime());// 印出sorting結束時間
     //display(g);//決定是否看結果
  }
      public static void display(int[] a)                     //show element
        {
        for (int i=0;i<a.length;i++)
          System.out.print(a[i]+"  ");
        System.out.println();
        }
    public static int[] bubbleSort(int[] a)                //use bubble sort
      {
      int t;
      for(int i=0; i<a.length; i++)
        {
        for (int j=0;j<a.length-i-1;j++)
          {
          if (a[j]>a[j+1])
            {
            t=a[j];
            a[j]=a[j+1];
            a[j+1]=t;
            }
           }
          }
        return a;
        }
       
     public static void swapReferences(int []a,int i,int j)//做交換位置用
  {
   int t;
       t=a[j];
            a[j]=a[i];
            a[i]=t;
     
      public static void qsort(int a[],int lo0,int hi0,int k){
     int lo = lo0;                 //看書得知而研發的最快之selection quick sorting
        int hi = hi0;
        int i=0,j,key,temp;
       
     if(lo+10 > hi)          //若數量不大於10insertiinsort較快
           insertionSort(a);
         else
         {
       int middle= (lo+hi)/2;
           if(a[middle]>a[lo])
             swapReferences(a,lo,middle);   //做三數比較,使a[hi]是中間值
           else if(a[hi]>a[lo])
             swapReferences(a,lo,hi);
           else if(a[hi]>a[middle])
              swapReferences(a,middle,hi);
                        
           else swapReferences(a,middle,hi);
        if(hi>lo)   
       {
                    key=a[hi];
         i=lo-1;
         j=hi;
         while(true)
         {
           while(a[++i]<key);        //左右夾攻交換法
           while(a[--j]>key);
           if(i>=j)break;
           temp=a[i];
           a[i]=a[j];
           a[j]=temp;
         }
         temp=a[i];
         a[i]=a[hi];
         a[hi]=temp;
        
     if(k<i)
      qsort(a,lo0,i-1,k);         //選擇作遞回,才不讓二遞回衝到cpu
      else if(k>i)
      qsort(a,i+1, hi0,k);}}
}
public static void qsort (int a[], int n){     //constructor
  qsort(a,0,n-1,20);   //指定k=20
}
  public static void insertionSort(int []a)   //insertsort
  {
   for(int p=1;p<a.length;p++)
   {
     int tmp = a[p];
     int j = p;
     for(; j>0&& tmp<(a[j-1]);j--)   //找到比較小的數,插到其後
      a[j]=a[j-1];
      a[j]=tmp;
   }}
 
public static void selectSort(int []a)
  {
   int small=0;
     int p=0;         
     int j=0;
     int i=0;
     int temp=0;
   for(p=0;p<a.length-1;p++)
   {
       small=a[p];
    
       for( i=p+1; i<a.length ;i++){    //由前到後一遍遍的找最小數插到前面去
   if(a[i]<small)
        {small=a[i];
         j=i;}
        }
      temp=a[j];
      a[j]=a[p];
      a[p]=temp;
      }  
  }

public static int find(int [] a,int x,int y)        //binary search
    {                                                   //可幫助binarysearch找值
      int low =0;
      int high = y;
      int mid=0;
    
      while (low<=high)
      {
        mid = (low+high)/2;
          if(a[mid]<x)                    
          low=mid+1;
        else if(a[mid]>x)
          high=mid-1;
     else
          return mid;            }                   
             return low; //關鍵處,此數必是找不到相同值的最適插入點
       }//解釋起來要長篇大論的,學長應可理解 
      
 public static void bis(int a[])  //改良後的binaryinsertionsort
        {
   for(int p=1;p<a.length;p++)
        {
         int tmp=a[p];
         int j=p;
           //int k=find(a,tmp,p-1);
           int low =0;
      int high = p-1;
      int mid=0;
     int k=0;
      while (low<=high)      //在內部做binarysearch
      {
        mid = (low+high)/2;
          if(a[mid]<tmp)                    
          low=mid+1;
        else if(a[mid]>tmp)
          high=mid-1;
     else
           {k=mid;break;}
         }
         if(k!=mid)
              k=low;
        for( ;j>0&&j>k;j--)   //思維關鍵處所在  插入點後到p的數字全退一位  
           a[j]=a[j-1];
           a[k]=tmp;
        }
      }
               }

沒有留言: