以下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) //若數量不大於10做insertiinsort較快
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;
}
}
}
沒有留言:
張貼留言