第二章数组，P31。
题目：设计一个可容纳40位数的注n!的程序
我们先来设计一个可用于超长位数加乘法的数据类，有点类似于Integer一样。其测试代码如下：
package cn.com.chengang.algorithms.ch02.array02;
import junit.framework.TestCase;
/**
* 对LongNumber类进行测试
*
* @author 陈刚 2006-9-6 from http://www.ChenGang.com.cn
*/
public class LongNumberTest extends TestCase {
/**
* 测试构造函数
*
*/
public void testNew() {
LongNumber n = new LongNumber();
assertEquals("0", n.value());// 默认值为0
n = new LongNumber("0123456789");
assertEquals("0123456789", n.value());
try {
n = new LongNumber("abc88");
fail("当参数含有非数字字符时，应抛出异常");
} catch (Exception e) {
assertTrue(true);
}
}
/**
* 测试加法
*
*/
public void testAdd() {
// 普通
LongNumber n1 = new LongNumber("13");
LongNumber n2 = new LongNumber("4");
LongNumber n3 = n1.add(n2);
assertEquals("17", n3.value());
// 有进位的
n1 = new LongNumber("9");
n2 = new LongNumber("4");
n3 = n1.add(n2);
assertEquals("13", n3.value());
// 有一个数是零的
n1 = new LongNumber("13");
n2 = new LongNumber("0");
n3 = n1.add(n2);
assertEquals("13", n3.value());
// 位数特长的
n1 = new LongNumber("33333333333333333333333333333333333333333393");
n2 = new LongNumber("298");
n3 = n1.add(n2);
assertEquals("33333333333333333333333333333333333333333691", n3.value());
}
/**
* 测试乘法
*
*/
public void testMul() {
// 普通
LongNumber n1 = new LongNumber("3");
LongNumber n2 = new LongNumber("2");
LongNumber n3 = n1.mul(n2);
assertEquals("6", n3.value());
// 有进位
n1 = new LongNumber("3");
n2 = new LongNumber("4");
n3 = n1.mul(n2);
assertEquals("12", n3.value());
// 零
n1 = new LongNumber("3");
n2 = new LongNumber("0");
n3 = n1.mul(n2);
assertEquals("0", n3.value());
// 多位数
n1 = new LongNumber("98");
n2 = new LongNumber("67");
n3 = n1.mul(n2);
assertEquals("6566", n3.value());
// 位数特长的
n1 = new LongNumber("5897452665");
n2 = new LongNumber("8755445");
n3 = n1.mul(n2);
assertEquals("51634822448510925", n3.value());
}
}
然后，LongNumber的实现代码如下：
package cn.com.chengang.algorithms.ch02.array02;
/**
* 用于超长位数的加乘法，现在暂时不支持负数。<br>
* 同时这和Integer一样是一个不变类
*
* @author 陈刚 2006-9-6 from http://www.ChenGang.com.cn
*/
public class LongNumber {
private int[] data;
private String dataStr;
public LongNumber() {
data = new int[1];
data[0] = 0;
}
public LongNumber(String number) {
byte[] bytes = number.getBytes();
data = new int[bytes.length];
for (int i = 0; i < bytes.length; i++) {
data[i] = bytes[i] - 48;
if (data[i] < 0 || data[i] > 9)
throw new IllegalArgumentException("参数必须是数值");
}
}
/**
* 以字符串的形式返回数值
*
* @return
*/
public String value() {
if (dataStr == null)
dataStr = parseString(data);
return dataStr;
}
/**
* 一个工具方法，把一个int数组转化成字符串<br>
* new int[]{1,4,5}-->145
*
* @param array
* @return
*/
private static String parseString(int[] array) {
StringBuilder buf = new StringBuilder();
for (int c : array) {
buf.append(c);
}
return buf.toString();
}
/**
* 加法。注意：本类为不变类，本类的值不会改变
*
* @param number2 被加数
* @return 加法的结果
*/
public LongNumber add(LongNumber number2) {
int[] result = add(number2.data);
return new LongNumber(parseString(result));
}
/**
* 此方法为了和mul方法共享算法而分离出来的
*
* @param data2
* @return
*/
private int[] add(int[] data2) {
// 创建一个装相加结果的数组data3
int len1 = data.length;
int len2 = data2.length;
int len3 = (len1 > len2 ? len1 : len2) + 1; // 有可能有进位，所以多加一位
int[] data3 = new int[len3];
for (int i = 0; i < len3; i++) {
// 得到index值（从未位开始相加）。
int index1 = len1 - i - 1;
int index2 = len2 - i - 1;
int index3 = len3 - i - 1;
// 相加
if (index1 > -1)
data3[index3] += data[index1];
if (index2 > -1)
data3[index3] += data2[index2];
// 进位判断
if (data3[index3] > 9) {
data3[index3] = data3[index3] - 10;
data3[index3 - 1] = 1;
}
}
// 第一位数是否存在，不存在则剪去，并把剩下的值放到一个新数组中
int[] result = data3;
if (data3[0] == 0) {
result = new int[data3.length - 1];// 新数组位数减1
System.arraycopy(data3, 1, result, 0, result.length);// 数据复制
}
return result;
}
/**
* 乘法
*
* @param number2 被乘数
* @return 相乘的结果
*/
public LongNumber mul(LongNumber number2) {
int len2 = number2.data.length;
LongNumber result = new LongNumber();
for (int i = 0; i < len2; i++) {
int n2 = number2.data[len2 - i - 1];
int[] temp = singleMul(n2);
if (i != 0) {// 向左移位，补零
int[] newTemp = new int[temp.length + i];
System.arraycopy(temp, 0, newTemp, 0, temp.length);
temp = newTemp;
}
String str = parseString(result.add(temp));
result = new LongNumber(str);
}
return result;
}
/**
* number2是个位数:0~9
*/
private int[] singleMul(int number2) {
// 创建一个装相乘结果的数组data3
int len1 = data.length;
int len3 = len1 + 1; // 最大可能位数
int[] data3 = new int[len3];
for (int i = 0; i < len1; i++) {
// 得到index值（从未位开始相加）。
int index1 = len1 - i - 1;
int index3 = len3 - i - 1;
data3[index3] += data[index1] * number2;
// 进位
if (data3[index3] > 9) {
data3[index3 - 1] = data3[index3] / 10;
data3[index3] = data3[index3] % 10;
}
}
// 第一位数是否存在，不存在则剪去，并把剩下的值放到一个新数组中
int[] result = data3;
if (data3[0] == 0) {
result = new int[data3.length - 1];// 新数组位数减1
System.arraycopy(data3, 1, result, 0, result.length);// 数据复制
}
return result;
}
}
说明：由于此类现在是为了求N!，所以暂时不支持负数
接下来我们来实现求N！，先写它的测试代码，如下：
package cn.com.chengang.algorithms.ch02.array02;
import junit.framework.TestCase;
/**
* 对MathUtils类进行测试
*
* @author 陈刚 2006-9-6 from http://www.ChenGang.com.cn
*/
public class MathUtilsTest extends TestCase {
public void testCalculus() {
assertEquals("1", MathUtils.calculus(1));
assertEquals("2", MathUtils.calculus(2));
assertEquals("6", MathUtils.calculus(3));
assertEquals("24", MathUtils.calculus(4));
assertEquals("120", MathUtils.calculus(5));
assertEquals("720", MathUtils.calculus(6));
assertEquals("87178291200", MathUtils.calculus(14));
assertEquals("10888869450418352160768000000", MathUtils.calculus(27));
}
}
然后，再写它的实现代码如下：
package cn.com.chengang.algorithms.ch02.array02;
/**
* 一个数学工具类
*
* @author 陈刚 2006-9-6 from http://www.ChenGang.com.cn
*/
public class MathUtils {
/**
* 求N!
*
* @param n
* @return
*/
public static String calculus(int n) {
LongNumber result = new LongNumber("1");
for (int i = 2; i <= n; i++) {
LongNumber temp = new LongNumber("" + i);
result = result.mul(temp);
}
return result.value();
}
}
从测试代码来看，原书自27！之后全部算错了。仔佃观察原书P35的27！的值第一位少了一个1，也许就是从这里开始出错的吧，具体错误原因我没有去给他找。