大数乘法和阶乘代码,Java代码库,德仔网

代码语言

代码分类

【Java】大数乘法和阶乘

作者:Dezai.CN / 发布于2011/7/13/ 649

大数乘法的实现是基于印度的格子乘法,使用这种方法，计算 m 位数乘以 n 位数只需要创建一个 m+n 位的数组保存结果即可。

<div>public class BigMultiply {

 public static void main(String[] args) {
 System.out.println(factorial("1000"));
 }

 /**
 * 阶乘
 *
 * @param n 要进行阶乘的数字
 *
 * @return 阶乘结果
 */
 private static String factorial(String n) {
 if (Integer.parseInt(n) <= 1) {
 return "1";
 } else {
 return bigMultiply(n, factorial(String.valueOf(Integer.parseInt(n) - 1)));
 }
 }

 /**
 * 大数字乘法
 *
 * @param number1 数字1
 * @param number2 数字2
 *
 * @return 乘法结果
 */
 private static String bigMultiply(String number1, String number2) {
 short[] numbers1 = toIntArray(number1);
 short[] numbers2 = toIntArray(number2);

 short[] result = multiply(numbers1, numbers2);
 return toString(result);
 }

 private static short[] multiply(short[] numbers1, short[] numbers2) {
 short[] result = new short[numbers1.length + numbers2.length];

 for (int i = 0; i < numbers1.length; i++) {
 for (int j = 0; j < numbers2.length; j++) {
 int tenth = i + j;
 int cellResult = numbers1[i] * numbers2[j];

 put(result, tenth + 1, cellResult % 10);
 put(result, tenth, cellResult / 10);
 }
 }

 return result;
 }

 /**
 * put <i>number</i> into <i>index</i> position of <i>result</i>
 *
 * @param result -
 * @param index -
 * @param number -
 */
 private static void put(short[] result, int index, int number) {
 result[index] += number;

 carryFrom(result, index);
 }

 /**
 * 进位
 *
 * @param result 数组
 * @param index 开始进位的位置
 */
 private static void carryFrom(short[] result, int index) {
 if (index < 0) {
 return;
 }

 if (result[index] >= 10) {
 result[index - 1]++;
 result[index] = (short)(result[index] - 10);
 carryFrom(result, index - 1);
 }
 }

 private static short[] toIntArray(String numbers) {
 short[] result = new short[numbers.length()];
 for (int i = 0; i < numbers.length(); i++) {
 result[i] = (short)(Integer.parseInt(numbers.substring(i, i + 1)));
 }
 return result;
 }

 private static String toString(short[] ints) {
 int start = 0;
 while (ints[start] == 0) {
 start++;
 }

 String str = "";
 while (start < ints.length) {
 str += ints[start];
 start++;
 }

 return str;
 }
}

试试其它关键字

　大数乘法和阶乘　

同语言下

可能有用的

Dezai.CN贡献的其它代码(4037)