posts - 73, 
comments - 55, 
trackbacks - 0


          
	

          

          
	
					





          
	
          
						  
	
          

	
			
			1。自然數是0，1，2……
          2。素數是2，3，5……（不包括1的只能背1和它本身整除的自然數）

          public class Test 
          { 
          ?/*
          ? * 最普通的算法：
          ? * 打印num以內的素數并返回素數個數
          ? * n、m分別為外、內層循環，i是第幾個素數，s是素數個數
          ? */
          ?public int prime(int num){
          ??int n,m,i=0,s=0; 
          ??label1: 
          ??for(n=2;n<=num;n++) 
          ??{ 
          ???for(m=2;m<=n/2;m++) 
          ???{ 
          ????if(n%m==0) 
          ????continue label1; 
          ???} 
          ???s++; 
          ???i++; 
          ???System.out.println("第"+i+"個素數是："+n); 
          ??} 
          ??return s; 
          ?}
          ?
          ?public static void main(String args[]){ 
          ??Test test = new Test();
          ??int sum = test.prime(1000);
          ??System.out.println("共"+sum+"個素數");
          ?} 
          } 

          【1】求10000以內的所有素數。
          素數是除了1和它本身之外再不能被其他數整除的自然數。由于找不到一個通項公式來表示所有的素數，所以對于數學家來說，素數一直是一個未解之謎。像著名的 哥德巴赫猜想、孿生素數猜想，幾百年來不知吸引了世界上多少優秀的數學家。盡管他們苦心鉆研，嘔心瀝血，但至今仍然未見分曉。
          自從有了計算機之后，人們借助于計算機的威力，已經找到了2216091以內的所有素數。
          求素數的方法有很多種，最簡單的方法是根據素數的定義來求。對于一個自然數N，用大于1小于N的各個自然數都去除一下N，如果都除不盡，則N為素數，否則N為合數。
          但是，如果用素數定義的方法來編制計算機程序，它的效率一定是非常低的，其中有許多地方都值得改進。
          第一，對于一個自然數N，只要能被一個非1非自身的數整除，它就肯定不是素數，所以不
          必再用其他的數去除。
          第二，對于N來說，只需用小于N的素數去除就可以了。例如，如果N能被15整除，實際
          上就能被3和5整除，如果N不能被3和5整除，那么N也決不會被15整除。
          第三，對于N來說，不必用從2到N一1的所有素數去除，只需用小于等于√N(根號N)的所有素數去除就可以了。這一點可以用反證法來證明：
          如果N是合數，則一定存在大于1小于N的整數d1和d2，使得N=d1×d2。
          如果d1和d2均大于√N，則有：N＝d1×d2>√N×√N＝N。
          而這是不可能的，所以，d1和d2中必有一個小于或等于√N。
          基于上述分析，設計算法如下：
          (1)用2，3，5，7逐個試除N的方法求出100以內的所有素數。
          (2)用100以內的所有素數逐個試除的方法求出10000以內的素數。
          首先，將2，3，5，7分別存放在a[1]、a[2]、a[3]、a[4]中，以后每求出一個素數，只要不大于100，就依次存放在A數組中的一個單元 中。當我們求100—10000之間的素數時，可依次用a[1]－a[2]的素數去試除N，這個范圍內的素數可以不保存，直接打印。

          【2】用篩法求素數。
          簡單介紹一下厄拉多塞篩法。厄拉多塞是一位古希臘數學家，他在尋找素數時，采用了一種與眾不同的方法：先將2－N的各數寫在紙上：

          在2的上面畫一個圓圈，然后劃去2的其他倍數；第一個既未畫圈又沒有被劃去的數是3，將它畫圈，再劃去3的其他倍數；現在既未畫圈又沒有被劃去的第一個數 是5，將它畫圈，并劃去5的其他倍數……依次類推，一直到所有小于或等于N的各數都畫了圈或劃去為止。這時，表中畫了圈的以及未劃去的那些數正好就是小于 N的素數。

          這很像一面篩子，把滿足條件的數留下來，把不滿足條件的數篩掉。由于這種方法是厄拉多塞首先發明的，所以，后人就把這種方法稱作厄拉多塞篩法。
          在計算機中，篩法可以用給數組單元置零的方法來實現。具體來說就是：首先開一個數組：a[i]，i=1，2，3，…，同時，令所有的數組元素都等于下標 值，即a[i]=i，當i不是素數時，令a[i]=0 。當輸出結果時，只要判斷a[i]是否等于零即可，如果a[i]=0，則令i=i+1，檢查下一個a[i]。
          篩法是計算機程序設計中常用的算法之一。

          【3】用6N±1法求素數。
          任何一個自然數，總可以表示成為如下的形式之一：
          6N，6N+1，6N+2，6N+3，6N+4，6N+5 (N=0，1，2，…)
          顯然，當N≥1時，6N，6N+2，6N+3，6N+4都不是素數，只有形如6N+1和6N+5的自然數有可能是素數。所以，除了2和3之外，所有的素數都可以表示成6N±1的形式(N為自然數)。
          根據上述分析，我們可以構造另一面篩子，只對形如6 N±1的自然數進行篩選，這樣就可以大大減少篩選的次數，從而進一步提高程序的運行效率和速度。

          在程序上，我們可以用一個二重循環實現這一點，外循環i按3的倍數遞增，內循環j為0－1的循環，則2(i+j)-1恰好就是形如6N±1的自然數。
			
          posted @ 2006-11-16 10:58 保爾任 閱讀(415) | 評論 (0) | 編輯 收藏
          
		
			
          
		
			
			
		
				
          插入排序:
          
				
          package org.rut.util.algorithm.support;
          
				
          import org.rut.util.algorithm.SortUtil;
          /**
          ?* @author treeroot
          ?* @since 2006-2-2
          ?* @version 1.0
          ?*/
          public class InsertSort implements SortUtil.Sort{
          
				
          ??? /* (non-Javadoc)
          ???? * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
          ???? */
          ??? public void sort(int[] data) {
          ??????? int temp;
          ??????? for(int i=1;i<data.length;i++){
          ??????????? for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
          ??????????????? SortUtil.swap(data,j,j-1);
          ??????????? }
          ??????? }??????? 
          ??? }
          
				
          }
          冒泡排序:
          
				
          package org.rut.util.algorithm.support;
          
				
          import org.rut.util.algorithm.SortUtil;
          
				
          /**
          ?* @author treeroot
          ?* @since 2006-2-2
          ?* @version 1.0
          ?*/
          public class BubbleSort implements SortUtil.Sort{
          
				
          ??? /* (non-Javadoc)
          ???? * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
          ???? */
          ??? public void sort(int[] data) {
          ??????? int temp;
          ??????? for(int i=0;i<data.length;i++){
          ??????????? for(int j=data.length-1;j>i;j--){
          ??????????????? if(data[j]<data[j-1]){
          ??????????????????? SortUtil.swap(data,j,j-1);
          ??????????????? }
          ??????????? }
          ??????? }
          ??? }
          
				
          }
          
				
          選擇排序:
          
				
          package org.rut.util.algorithm.support;
          
				
          import org.rut.util.algorithm.SortUtil;
          
				
          /**
          ?* @author treeroot
          ?* @since 2006-2-2
          ?* @version 1.0
          ?*/
          public class SelectionSort implements SortUtil.Sort {
          
				
          ??? /*
          ???? * (non-Javadoc)
          ???? * 
          ???? * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
          ???? */
          ??? public void sort(int[] data) {
          ??????? int temp;
          ??????? for (int i = 0; i < data.length; i++) {
          ??????????? int lowIndex = i;
          ??????????? for (int j = data.length - 1; j > i; j--) {
          ??????????????? if (data[j] < data[lowIndex]) {
          ??????????????????? lowIndex = j;
          ??????????????? }
          ??????????? }
          ??????????? SortUtil.swap(data,i,lowIndex);
          ??????? }
          ??? }
          
				
          }
          
				
          Shell排序:
          
				
          package org.rut.util.algorithm.support;
          
				
          import org.rut.util.algorithm.SortUtil;
          
				
          /**
          ?* @author treeroot
          ?* @since 2006-2-2
          ?* @version 1.0
          ?*/
          public class ShellSort implements SortUtil.Sort{
          
				
          ??? /* (non-Javadoc)
          ???? * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
          ???? */
          ??? public void sort(int[] data) {
          ??????? for(int i=data.length/2;i>2;i/=2){
          ??????????? for(int j=0;j<i;j++){
          ??????????????? insertSort(data,j,i);
          ??????????? }
          ??????? }
          ??????? insertSort(data,0,1);
          ??? }
          
				
          ??? /**
          ???? * @param data
          ???? * @param j
          ???? * @param i
          ???? */
          ??? private void insertSort(int[] data, int start, int inc) {
          ??????? int temp;
          ??????? for(int i=start+inc;i<data.length;i+=inc){
          ??????????? for(int j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){
          ??????????????? SortUtil.swap(data,j,j-inc);
          ??????????? }
          ??????? }
          ??? }
          
				
          }
          
				
          快速排序:
          
				
          package org.rut.util.algorithm.support;
          
				
          import org.rut.util.algorithm.SortUtil;
          
				
          /**
          ?* @author treeroot
          ?* @since 2006-2-2
          ?* @version 1.0
          ?*/
          public class QuickSort implements SortUtil.Sort{
          
				
          ??? /* (non-Javadoc)
          ???? * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
          ???? */
          ??? public void sort(int[] data) {
          ??????? quickSort(data,0,data.length-1);??????? 
          ??? }
          ??? private void quickSort(int[] data,int i,int j){
          ??????? int pivotIndex=(i+j)/2;
          ??????? //swap
          ??????? SortUtil.swap(data,pivotIndex,j);
          ??????? 
          ??????? int k=partition(data,i-1,j,data[j]);
          ??????? SortUtil.swap(data,k,j);
          ??????? if((k-i)>1) quickSort(data,i,k-1);
          ??????? if((j-k)>1) quickSort(data,k+1,j);
          ??????? 
          ??? }
          ??? /**
          ???? * @param data
          ???? * @param i
          ???? * @param j
          ???? * @return
          ???? */
          ??? private int partition(int[] data, int l, int r,int pivot) {
          ??????? do{
          ?????????? while(data[++l]<pivot);
          ?????????? while((r!=0)&&data[--r]>pivot);
          ?????????? SortUtil.swap(data,l,r);
          ??????? }
          ??????? while(l<r);
          ??????? SortUtil.swap(data,l,r);??????? 
          ??????? return l;
          ??? }
          
				
          }
          改進后的快速排序:
          
				
          package org.rut.util.algorithm.support;
          
				
          import org.rut.util.algorithm.SortUtil;
          
				
          /**
          ?* @author treeroot
          ?* @since 2006-2-2
          ?* @version 1.0
          ?*/
          public class ImprovedQuickSort implements SortUtil.Sort {
          
				
          ??? private static int MAX_STACK_SIZE=4096;
          ??? private static int THRESHOLD=10;
          ??? /* (non-Javadoc)
          ???? * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
          ???? */
          ??? public void sort(int[] data) {
          ??????? int[] stack=new int[MAX_STACK_SIZE];
          ??????? 
          ??????? int top=-1;
          ??????? int pivot;
          ??????? int pivotIndex,l,r;
          ??????? 
          ??????? stack[++top]=0;
          ??????? stack[++top]=data.length-1;
          ??????? 
          ??????? while(top>0){
          ??????????? int j=stack[top--];
          ??????????? int i=stack[top--];
          ??????????? 
          ??????????? pivotIndex=(i+j)/2;
          ??????????? pivot=data[pivotIndex];
          ??????????? 
          ??????????? SortUtil.swap(data,pivotIndex,j);
          ??????????? 
          ??????????? //partition
          ??????????? l=i-1;
          ??????????? r=j;
          ??????????? do{
          ??????????????? while(data[++l]<pivot);
          ??????????????? while((r!=0)&&(data[--r]>pivot));
          ??????????????? SortUtil.swap(data,l,r);
          ??????????? }
          ??????????? while(l<r);
          ??????????? SortUtil.swap(data,l,r);
          ??????????? SortUtil.swap(data,l,j);
          ??????????? 
          ??????????? if((l-i)>THRESHOLD){
          ??????????????? stack[++top]=i;
          ??????????????? stack[++top]=l-1;
          ??????????? }
          ??????????? if((j-l)>THRESHOLD){
          ??????????????? stack[++top]=l+1;
          ??????????????? stack[++top]=j;
          ??????????? }
          ??????????? 
          ??????? }
          ??????? //new InsertSort().sort(data);
          ??????? insertSort(data);
          ??? }
          ??? /**
          ???? * @param data
          ???? */
          ??? private void insertSort(int[] data) {
          ??????? int temp;
          ??????? for(int i=1;i<data.length;i++){
          ??????????? for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
          ??????????????? SortUtil.swap(data,j,j-1);
          ??????????? }
          ??????? }?????? 
          ??? }
          
				
          }
          
				
          歸并排序:
          
				
          package org.rut.util.algorithm.support;
          
				
          import org.rut.util.algorithm.SortUtil;
          
				
          /**
          ?* @author treeroot
          ?* @since 2006-2-2
          ?* @version 1.0
          ?*/
          public class MergeSort implements SortUtil.Sort{
          
				
          ??? /* (non-Javadoc)
          ???? * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
          ???? */
          ??? public void sort(int[] data) {
          ??????? int[] temp=new int[data.length];
          ??????? mergeSort(data,temp,0,data.length-1);
          ??? }
          ??? 
          ??? private void mergeSort(int[] data,int[] temp,int l,int r){
          ??????? int mid=(l+r)/2;
          ??????? if(l==r) return ;
          ??????? mergeSort(data,temp,l,mid);
          ??????? mergeSort(data,temp,mid+1,r);
          ??????? for(int i=l;i<=r;i++){
          ??????????? temp[i]=data[i];
          ??????? }
          ??????? int i1=l;
          ??????? int i2=mid+1;
          ??????? for(int cur=l;cur<=r;cur++){
          ??????????? if(i1==mid+1)
          ??????????????? data[cur]=temp[i2++];
          ??????????? else if(i2>r)
          ??????????????? data[cur]=temp[i1++];
          ??????????? else if(temp[i1]<temp[i2])
          ??????????????? data[cur]=temp[i1++];
          ??????????? else
          ??????????????? data[cur]=temp[i2++];??????????? 
          ??????? }
          ??? }
          
				
          }
          
				
          改進后的歸并排序:
          
				
          package org.rut.util.algorithm.support;
          
				
          import org.rut.util.algorithm.SortUtil;
          
				
          /**
          ?* @author treeroot
          ?* @since 2006-2-2
          ?* @version 1.0
          ?*/
          public class ImprovedMergeSort implements SortUtil.Sort {
          
				
          ??? private static final int THRESHOLD = 10;
          
				
          ??? /*
          ???? * (non-Javadoc)
          ???? * 
          ???? * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
          ???? */
          ??? public void sort(int[] data) {
          ??????? int[] temp=new int[data.length];
          ??????? mergeSort(data,temp,0,data.length-1);
          ??? }
          
				
          ??? private void mergeSort(int[] data, int[] temp, int l, int r) {
          ??????? int i, j, k;
          ??????? int mid = (l + r) / 2;
          ??????? if (l == r)
          ??????????? return;
          ??????? if ((mid - l) >= THRESHOLD)
          ??????????? mergeSort(data, temp, l, mid);
          ??????? else
          ??????????? insertSort(data, l, mid - l + 1);
          ??????? if ((r - mid) > THRESHOLD)
          ??????????? mergeSort(data, temp, mid + 1, r);
          ??????? else
          ??????????? insertSort(data, mid + 1, r - mid);
          
				
          ??????? for (i = l; i <= mid; i++) {
          ??????????? temp[i] = data[i];
          ??????? }
          ??????? for (j = 1; j <= r - mid; j++) {
          ??????????? temp[r - j + 1] = data[j + mid];
          ??????? }
          ??????? int a = temp[l];
          ??????? int b = temp[r];
          ??????? for (i = l, j = r, k = l; k <= r; k++) {
          ??????????? if (a < b) {
          ??????????????? data[k] = temp[i++];
          ??????????????? a = temp[i];
          ??????????? } else {
          ??????????????? data[k] = temp[j--];
          ??????????????? b = temp[j];
          ??????????? }
          ??????? }
          ??? }
          
				
          ??? /**
          ???? * @param data
          ???? * @param l
          ???? * @param i
          ???? */
          ??? private void insertSort(int[] data, int start, int len) {
          ??????? for(int i=start+1;i<start+len;i++){
          ??????????? for(int j=i;(j>start) && data[j]<data[j-1];j--){
          ??????????????? SortUtil.swap(data,j,j-1);
          ??????????? }
          ??????? }
          ??? }
          
				
          }
          堆排序:
          
				
          package org.rut.util.algorithm.support;
          
				
          import org.rut.util.algorithm.SortUtil;
          
				
          /**
          ?* @author treeroot
          ?* @since 2006-2-2
          ?* @version 1.0
          ?*/
          public class HeapSort implements SortUtil.Sort{
          
				
          ??? /* (non-Javadoc)
          ???? * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
          ???? */
          ??? public void sort(int[] data) {
          ??????? MaxHeap h=new MaxHeap();
          ??????? h.init(data);
          ??????? for(int i=0;i<data.length;i++)
          ??????????? h.remove();
          ??????? System.arraycopy(h.queue,1,data,0,data.length);
          ??? }
          
				
          
						
          ???? private static class MaxHeap{
          ???????? 
          ??????? 
          ??????? void init(int[] data){
          ??????????? this.queue=new int[data.length+1];
          ??????????? for(int i=0;i<data.length;i++){
          ??????????????? queue[++size]=data[i];
          ??????????????? fixUp(size);
          ??????????? }
          ??????? }
          ???????? 
          ??????? private int size=0;
          
				
          ??????? private int[] queue;
          ??????????????? 
          ??????? public int get() {
          ??????????? return queue[1];
          ??????? }
          
				
          ??????? public void remove() {
          ??????????? SortUtil.swap(queue,1,size--);
          ??????????? fixDown(1);
          ??????? }
          ??????? //fixdown
          ??????? private void fixDown(int k) {
          ??????????? int j;
          ??????????? while ((j = k << 1) <= size) {
          ??????????????? if (j < size && queue[j]<queue[j+1])
          ??????????????????? j++; 
          ??????????????? if (queue[k]>queue[j]) //不用交換
          ??????????????????? break;
          ??????????????? SortUtil.swap(queue,j,k);
          ??????????????? k = j;
          ??????????? }
          ??????? }
          ??????? private void fixUp(int k) {
          ??????????? while (k > 1) {
          ??????????????? int j = k >> 1;
          ??????????????? if (queue[j]>queue[k])
          ??????????????????? break;
          ??????????????? SortUtil.swap(queue,j,k);
          ??????????????? k = j;
          ??????????? }
          ??????? }
          
				
          ??? }
          
				
          }
          
				
          ?
          
				
          SortUtil:
          
				
          package org.rut.util.algorithm;
          
				
          import org.rut.util.algorithm.support.BubbleSort;
          import org.rut.util.algorithm.support.HeapSort;
          import org.rut.util.algorithm.support.ImprovedMergeSort;
          import org.rut.util.algorithm.support.ImprovedQuickSort;
          import org.rut.util.algorithm.support.InsertSort;
          import org.rut.util.algorithm.support.MergeSort;
          import org.rut.util.algorithm.support.QuickSort;
          import org.rut.util.algorithm.support.SelectionSort;
          import org.rut.util.algorithm.support.ShellSort;
          
				
          /**
          ?* @author treeroot
          ?* @since 2006-2-2
          ?* @version 1.0
          ?*/
          public class SortUtil {
          ??? public final static int INSERT = 1;
          
				
          ??? public final static int BUBBLE = 2;
          
				
          ??? public final static int SELECTION = 3;
          
				
          ??? public final static int SHELL = 4;
          
				
          ??? public final static int QUICK = 5;
          
				
          ??? public final static int IMPROVED_QUICK = 6;
          
				
          ??? public final static int MERGE = 7;
          
				
          ??? public final static int IMPROVED_MERGE = 8;
          
				
          ??? public final static int HEAP = 9;
          
				
          ??? public static void sort(int[] data) {
          ??????? sort(data, IMPROVED_QUICK);
          ??? }
          ??? private static String[] name={
          ??????????? "insert","bubble","selection","shell","quick","improved_quick","merge","improved_merge","heap"
          ??? };
          ??? 
          ??? private static Sort[] impl=new Sort[]{
          ??????????? new InsertSort(),
          ??????????? new BubbleSort(),
          ??????????? new SelectionSort(),
          ??????????? new ShellSort(),
          ??????????? new QuickSort(),
          ??????????? new ImprovedQuickSort(),
          ??????????? new MergeSort(),
          ??????????? new ImprovedMergeSort(),
          ??????????? new HeapSort()
          ??? };
          
				
          ??? public static String toString(int algorithm){
          ??????? return name[algorithm-1];
          ??? }
          ??? 
          ??? public static void sort(int[] data, int algorithm) {
          ??????? impl[algorithm-1].sort(data);
          ??? }
          
				
          ??? public static interface Sort {
          ??????? public void sort(int[] data);
          ??? }
          
				
          ??? public static void swap(int[] data, int i, int j) {
          ??????? int temp = data[i];
          ??????? data[i] = data[j];
          ??????? data[j] = temp;
          ??? }
          }
          
		          

			
          posted @ 2006-11-16 10:58 保爾任 閱讀(608) | 評論 (3) | 編輯 收藏
          
		
          僅列出標題
          
	共8頁: 上一頁 1 2 3 4 5 6 7 8 

          

          

				

          

          
	
		
          
			
          			
			
          
	
          
		
          <2025年5月>
          
	
          日一二三四五六
          27282930123
          45678910
          11121314151617
          18192021222324
          25262728293031
          1234567
          

          

			

          常用鏈接
          


          留言簿(4)
          




		
          隨筆分類
          
		
				
			
	
		
          隨筆檔案
          
		
				
			
	
		
          文章分類
          
		
				
			
	
		
          文章檔案
          
		
				
			
	




          搜索
          

            
	
          • 
		
          •  
	
            • 

          


          最新評論
	
          



          閱讀排行榜
          



          評論排行榜
          


          
	

          




    
          
        
	




主站蜘蛛池模板：
康保县|
永新县|
泰宁县|
应城市|
东港市|
苍梧县|
商洛市|
怀仁县|
鲁山县|
博爱县|
靖西县|
洪江市|
汨罗市|
河北省|
南投市|
孝感市|
克什克腾旗|
长治市|
岳普湖县|
汉寿县|
松桃|
延寿县|
郁南县|
肥乡县|
柳江县|
两当县|
烟台市|
楚雄市|
闽清县|
西峡县|
乾安县|
海伦市|
砀山县|
楚雄市|
乐至县|
西峡县|
涟水县|
静安区|
景谷|
同江市|
大城县|