java算法:数组

java算法:数组

数组是最基本的数据结构。在java和大多数编程语言中都被定义为简单类型。数组的使用是开发有效算法的基础。

数组是相同类型数据的固定集合,它是连续存储的,通过下标来访问数组元素。由于它是与计算机的内存系统直接通讯,可以看成是最基本的数据结构。

例一:埃拉托色尼筛,打印出小于给定N的所有素数。

Java代码
  1. publicclassPrimes{
  2. publicstaticvoidmain(String[]args){
  3. intN=Integer.parseInt(args[0]);
  4. boolean[]a=newboolean[N];
  5. for(inti=2;i
  6. a[i]=true;
  7. }
  8. for(inti=2;i
  9. if(a[i]!=false){
  10. for(intj=i;j*i
  11. a[i*j]=false;
  12. }
  13. }
  14. }
  15. for(inti=2;i
  16. if(i>N-100){
  17. if(a[i]){
  18. System.out.println(""+i);
  19. }
  20. }
  21. }
  22. }
  23. }
public class Primes {
	public static void main(String[] args) {
		int N = Integer.parseInt(args[0]);
		boolean [] a = new boolean[N];
		for(int i = 2; i < N ; i++){
			a[i] = true;
		}
		for(int i = 2; i < N ; i++){
			if(a[i] != false){
				for(int j = i; j * i < N; j++){
					a[i * j] = false;
				}
			}
		}
		for(int i = 2; i < N ; i++){
			if(i > N - 100){
				if(a [i]){
					System.out.println(" " + i);
				}
			}
		}
	}

}

上述代码,计算一个布尔型的数组,如果i是素数,a[i]为true,否则,a[i]为false。首先,把数组中的所有元素置为true,然后把对应下标为非素数(是已知素数的倍数)的数组元素设为false。如果在所有较小素数的倍数都被设为false值后,a[i]的值仍为true,那么它肯定是一个素数。

对于其他对象而言,对数组的引用很有价值,因为它们可以把数组作为高级对象来有效地使用。

例二:健壮的数组分配

如果程序使用者敲入一个巨大的数作为命令行参数,它可能产生OutOfMemoryError异常错误,因此:

Java代码
  1. boolean[]a;
  2. try{
  3. a=newboolean[N];
  4. }catch(OutOfMemoryExceptione){
  5. System.out.println("Outofmemory.");
  6. }
boolean [] a;
try{
	a = new boolean[N];
}catch(OutOfMemoryException e){
	System.out.println("Out of memory.");
}

数组不仅准确地反映在大多数计算机上访问内存数据的基本方法,而且在应用中获得了广泛的应用,如,数组直接对应着向量,是描述具有下标的对象列表的数学术语。

例三:掷硬币模拟

Java代码
  1. publicclassCoinFlip{
  2. staticbooleanheads(){
  3. returnMath.random()<0.5;
  4. }
  5. publicstaticvoidmain(String[]args){
  6. inti,j,cnt=0;
  7. intN=Integer.parseInt(args[0]);
  8. intM=Integer.parseInt(args[1]);
  9. int[]f=newint[N+1];
  10. for(j=0;j<=N;j++){
  11. f[j]=0;
  12. }
  13. for(i=0;i
  14. for(cnt=0,j=0;j<=N;j++){
  15. if(heads()){
  16. cnt++;
  17. }
  18. }
  19. }
  20. for(j=0;j<=N;j++){
  21. if(f[j]==0){
  22. System.out.print(".");
  23. }
  24. for(i=0;i10){
  25. System.out.print("*");
  26. }
  27. System.out.println("");
  28. }
  29. }
  30. }
public class CoinFlip {
	static boolean heads(){
		return Math.random() < 0.5;
	}
	public static void main(String[] args) {
		int i,j,cnt = 0;
		int N = Integer.parseInt(args[0]);
		int M = Integer.parseInt(args[1]);
		int  [] f = new int[N + 1];
		for (j = 0; j <= N; j++) {
			f[j]=0;
		}
		for (i = 0; i < M; i++, f[cnt]++) {
			for(cnt = 0, j = 0; j <= N; j++){
				if(heads()){
					cnt++ ;
				}
			}
		}
		for(j = 0; j <= N; j++){
			if(f[j] == 0){
				System.out.print(".");
			}
			for(i = 0; i < f[j]; i+= 10){
				System.out.print("*");
			}
			System.out.println("");
		}
	}
}

从某种意义上说,当我们使用一个计算过的值来访问大小为N的数组时,只用一个操作就可以把N种可能性都考虑进去,效率上有了很大的提高。

例四:最近点计算

Java代码
  1. publicclassClosePoints{
  2. publicstaticvoidmain(String[]args){
  3. intcnt=0;
  4. intN=Integer.parseInt(args[0]);
  5. doubled=Double.parseDouble(args[1]);
  6. Point[]a=newPoint[N];
  7. for(inti=0;i
  8. a[i]=newPoint();
  9. }
  10. for(inti=0;i
  11. for(intj=i+1;j
  12. if(a[i].distance(a[j])
  13. cnt++;
  14. }
  15. }
  16. }
  17. System.out.println(cnt+"pairscloserthan"+d);
  18. }
  19. }
public class ClosePoints {

	public static void main(String[] args) {
		 int cnt = 0;
		 int N = Integer.parseInt(args[0]);
		 double d = Double.parseDouble(args[1]);
		 Point [] a = new Point[N];
		 for(int i = 0; i < N; i++){
			 a[i] = new Point();
		 }
		 for(int i = 0; i < N; i++){
			 for(int j = i + 1; j < N; j++){
				 if(a[i].distance(a[j]) < d){
					 cnt++;
				 }
			 }
		 }
		 System.out.println(cnt + " pairs closer than " + d);
	}

}

作为一个原型二次算法,它检查了N个数据项集合的所有数据对时,因此所花的时间与N平方成正比。

你可能感兴趣的