一道算法题（二）

[原题]

        http://www.iteye.com/topic/15295

       这是一个老贴子了，并且3楼帖了答案，但是我认为，这个答案是不标准的，正确与否姑且不论，题中假设的26位长的数据那个是不支持的，因为极易出内存溢出，于是我重新设计了一种算法，我认为在内存上和时间中都比原来的优秀。

其实在后面还有更好的解法，欢迎读原贴。

[解题思路]

       一开始，我也受到了找到数据间的数学关系的影响。别说，还真找到了一个，只是数学太差，无法表达出来，假设为5位数，那么数据的分布是1,4,3,2,2,3,4,1...1,4,3,2,2,3,4,1.....，有什么用呢，好像没用。。

      终于偶然间恍然大悟，有个最简单的规律就是，假设这是一个从a开始，每次都有A,B两种可能，但是上级已出现的概率决定了下级出现的概率，由于不需要枚举出各个数据，那么可以只要知道上级中最后的那个数出现的位置，就决定了下级有那些可能会出现的情况。

[代码实现]

import java.math.BigInteger;

public class Main {

	/**
	 * 数组相加
	 * 
	 * @param arr1
	 * @param arr2
	 * @return
	 */
	private static BigInteger[] add(BigInteger[] arr1, BigInteger[] arr2) {
		if (arr1.length != arr2.length)
			return null;
		for (int i = 0; i < arr1.length; i++) {
			arr1[i] = arr1[i].add(arr2[i]);
		}
		return arr1;
	}

	/**
	 * 数组集体相乘一个倍数
	 * 
	 * @param arr
	 * @param num
	 * @return
	 */
	private static BigInteger[] multiply(BigInteger[] arr, BigInteger num) {
		if (arr == null)
			return null;
		for (int i = 0; i < arr.length; i++) {
			arr[i] = arr[i].multiply(num);
		}
		return arr;
	}

	/**
	 * 求解一个字符串中加入一个新的字符位置分布<br>
	 * 
	 * 对一个定长length的字符中，在一定位置index中的前后（charAt)加入一个字符<br>
	 * 其将产生一个数组，可以记录新加字符所在位置<br>
	 * 在index前加入一个字符时，从0-index之间都有一种可能<br>
	 * 在index后加入一个字符时，从index+1-length之间也有一种可能
	 * 
	 * @param length
	 * @param index
	 * @param charAt
	 * @return
	 */
	private static BigInteger[] child(int length, int index, char charAt) {
		BigInteger[] arr = new BigInteger[length + 1];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = new BigInteger("0");
		}
		if (charAt == 'A') {
			for (int i = index + 1; i <= length; i++) {
				arr[i] = new BigInteger("1");
			}
		} else {
			for (int i = 0; i <= index; i++) {
				arr[i] = new BigInteger("1");
			}
		}
		return arr;
	}

	/**
	 * 取出对应字符所在位置的分布数组<br>
	 * 
	 * 对于一个已经存在的数组分布来说，扩展一个charAt的字符，那么产生的新数组分布也是一定的<br>
	 * 遍历现存的数组分布，对其每个值进行求对应的数组分布可能，并将结果与现在记录个数相乘，累加后的结果即一个全新的数组分布
	 * 
	 * @param sizes
	 * @param charAt
	 * @return
	 */
	private static BigInteger[] step(BigInteger[] sizes, char charAt) {
		BigInteger[] newSizes = new BigInteger[sizes.length + 1];
		for (int i = 0; i < newSizes.length; i++) {
			newSizes[i] = new BigInteger("0");
		}
		for (int i = 0; i < sizes.length; i++) {
			newSizes = add(newSizes, multiply(child(sizes.length, i, charAt), sizes[i]));
		}
		return newSizes;
	}

	/**
	 * 根据AB字符串取出符合条件的个数
	 * 
	 * @param str
	 * @return
	 */
	private static BigInteger test(String str) {
		BigInteger[] sizes = new BigInteger[] { new BigInteger("1") };
		BigInteger sum = new BigInteger("0");
		for (int i = 0; i < str.length(); i++) {
			sizes = step(sizes, str.charAt(i));
		}
		for (int i = 0; i < sizes.length; i++) {
			sum = sum.add(sizes[i]);
		}
		return sum;
	}

	public static void main(String[] args) {
                System.out.println(test("AAA"));
                System.out.println(test("AAB"));
                System.out.println(test("ABA"));
                System.out.println(test("ABAA"));
                System.out.println(test("ABAB"));
                System.out.println(test("AABAAABAAABAAABAAABAAABABB"));
	}
}

[结论 ]

       运算结果如下：

1
3
5
9
16
23469961608638992720

       查看结果的前几个，还是正确的，就是无法对后面的结论进行验证了，寒。。。

       在使用BigInteger代替int后，不但可以实现对26位数据的计算，那怕是假设为62位，也是秒杀的。

       这个算法最大的好处是不占用内存，那怕对1000的数据计算时，理论上也就约占2x1000多的数组。但是数据约大，计算的时间还是成指数倍的增长了。

       PS：谁想知道1000的数据有多少种可能么？试试就知道了。我的机器上花了7分钟，居然算过来了。。