0/1串中找出 首次出现m个1的位置

//A1.java

public class A1 {

	final static int N = 1000;// 数组长度
	final static int m = 10;// 待查找的1串的长度
	private static int amount1 = 0;
	private static int amount2 = 0;

	public static void main(String[] args) {
		int a[] = new int[N];
		makeArray(a);
		printArray(a);

		System.out.println("\n");

		int result = exec1(a, m);
		if (result != -1) {
			for (int i = 0; i < N; i++) {
				if (i == result) {
					System.out.println();
				}
				System.out.print(a[i]);
			}
			System.out.println();
		} else {
			System.out.println("没有结果");
		}

		System.out.println("\n改进算法比较的次数：\t" + amount1);
		exec2(a);
		System.out.println("简单循环算法比较的次数：\t" + amount2);
	}

	// 生成0/1数组
	static void makeArray(int a[]) {
		for (int i = 0; i < a.length; i++) {
			a[i] = (int) (Math.random() * 2);
		}
	}

	// 打印数组
	static void printArray(int a[]) {
		for (int i = 0; i < N; i++) {
			System.out.print(a[i]);
		}
	}

	// 在数组a[]中找出长度为m的1串的首次出现位置
	static int exec1(int a[], int m) {
		int i = m - 1, j = 1, k = 1, n;
		for (int count = 1; count < m && i < a.length; i += (m - 1)) {
			count = 1;
			amount1++;
			if (a[i] == 1) {
				n = (i == m - 1) ? m : (m - 1);
				// 往上，遍历到到i-(m-2)
				// 除了i=m-1时，遍历到i-(m-1)
				for (j = 1; j < n; j++) {
					amount1++;
					if (a[i - j] == 1) {
						count++;
					} else {
						break;
					}
				}
				// 往下，遍历到i+(m-1)
				for (k = 1; k < m; k++) {
					amount1++;
					if (i + k < a.length && a[i + k] == 1) {
						count++;
					} else {
						break;
					}
				}
			}
		}
		return (i < a.length) ? (i - (m - 1) - (j - 1)) : (-1);
	}

	// 简单循环方法
	public static void exec2(int a[]) {

		for (int i = 0, count = 0; i < a.length; i++) {
			if (count == 10) {
				break;
			}
			amount2++;
			if (a[i] == 1) {
				count++;
			} else {
				count = 0;
			}
		}
	}
}

 

0010000110111101011010101000101001110111000110010001111010111100011000011111111110100100001111110001101011010001000101011100011100111000110010010111100101101011100010110100111010000001000101110101111000001111100110101010010101011011010110011010101000111011001001110111000011001110111001100010001001010100111001111111110100000110001100010101101000011111011000011111111101100000010000000111111000000101111011110101101110101101100100001011110110010110111001110110001011110000111100000000010011101100101010101100101110000011100100010000101100101001001001000101001100010100011000110001011010101010000101000111000101011100111011101101110010100110001011011100110001110010010010101101111001101101100100100011001110111111110100001001001110101101100111101101000110000101000111000001011111010000110000011110001111100100010011100001010111011110011011101010101011011101100011110001101011110100011100011100110111110010101110011101000000011100111000111001001101000011100011001110100110110100111100111011000000011000

00100001101111010110101010001010011101110001100100011110101111000110000
11111111110100100001111110001101011010001000101011100011100111000110010010111100101101011100010110100111010000001000101110101111000001111100110101010010101011011010110011010101000111011001001110111000011001110111001100010001001010100111001111111110100000110001100010101101000011111011000011111111101100000010000000111111000000101111011110101101110101101100100001011110110010110111001110110001011110000111100000000010011101100101010101100101110000011100100010000101100101001001001000101001100010100011000110001011010101010000101000111000101011100111011101101110010100110001011011100110001110010010010101101111001101101100100100011001110111111110100001001001110101101100111101101000110000101000111000001011111010000110000011110001111100100010011100001010111011110011011101010101011011101100011110001101011110100011100011100110111110010101110011101000000011100111000111001001101000011100011001110100110110100111100111011000000011000

改进算法比较的次数： 27
简单循环算法比较的次数： 81

 

0011111110101100100011001000100000110110110011110100100100011011010001111010111101111011111101111001000010111101101010010011010001101010001100111001111110000100000101001110000000111000011011010010111010111010000001100011111101010001000010001010100110011111111000100000001000010110101000011100100011011101011011101110111101001111100001010111010111001001101000001000101001000011001001000010111011101011000011011001000110000110110101011011101011010100101111001101110011001000011011010110010000100011110110010011100110001011011101111111000110000111000101011101010101111001001000000111101101011010111010010100111101001010001111101111100110000111000000110001010001000011000101100011111101101010101101000010010100110100010101001110111110110000111001010101101000001100001100110011010010111101011111110010110011111111001010001010101101111011010110110100010000101000000100000010100001110010110000001000101011010000010011011101100011110100000011001110001100001111011111001001010010101111100001010101000010101111

没有结果

改进算法比较的次数： 339
简单循环算法比较的次数： 1000