问题描述:
整数大到超过所有的基本数据所能表示的数据范围时的加法运算.
算法思路:
递归的将大整数分割成二段,直至分割后的段可以用基本类型表示.
由低段到高段的顺序,合并各段.值得注意的是,这种顺序是不可颠倒的,因为高段需要用到低段的进位.也就是说,低段的进位要参入紧挨的下一段的加和运算.所以,add(mid+1,endIndex);在add(beginIndex,mid);语句前.
实现程序:
/**
* Copyright (c) 2011 Trusted Software and Mobile Computing(TSMC)
* All right reserved.
*
* Created on 2011
*
* http://jarg.iteye.com/
*
*/
// Contributors: Jarg Yee <yeshaoting@gmail.com>
import java.util.*;
/*
* 大整数加法
* @author jarg
* @version 1.0
*/
public class BigIntAdd
{
/** 加数 */
private static String x = "123456789012345678901234567890123456789012";
/** 加数 */
private static String y = "123456789012345678901234567890625";
/** 边界,段最大长度 */
private static final int wLen = String.valueOf(Long.MAX_VALUE).length()-1;
/** 大整数加法结果 */
private static String result = "";
/**
补齐二加数.
使得二加数长度一致,省去了很多不繁琐的边界检测.
*/
private static void init()
{
int maxLength = getMaxLength(x,y); // 二加数最大长度
int minLength = getMinLength(x,y); // 二加数最小长度
/* 补齐二加数 */
for(int i=0;i<maxLength-minLength;i++)
{
if(x.length()==minLength)
x = "0" + x;
else
y = "0" + y;
}
}
/** for debugging. */
public static void main(String[] args)
{
init(); /* 补齐加数,使二加数等长 */
add(0,getMaxLength(x,y)-1);
System.out.println("result:" + result);
}
/** 大整数加法 */
private static int add(int beginIndex,int endIndex)
{
long value = 0; // 加和值
int carry = 0; // 进位
long weight = (long)Math.pow(10,endIndex-beginIndex+1); // 权值
if(endIndex-beginIndex+1<=wLen)
{
/* 单段加法 */
value = Long.parseLong(x.substring(beginIndex,endIndex+1)) + Long.parseLong(y.substring(beginIndex,endIndex+1));
}
else
{
int mid = (beginIndex + endIndex)/2; // 中间,从中间将大整数分割成二段
/* 二个add的函数,有先后顺序,得先求出进位,然后加到高位上 */
/* 进位 */
carry = add(mid+1,endIndex);
/* 合并结果,将结果与权值的余数保存到结果中 */
value = carry + add(beginIndex,mid);
}
if(value%weight!=0)
result = (value%weight) + result;
System.out.println("begin:" + beginIndex + "\tend:" + endIndex + "\tvalue:" + value + "\t进位:" + (int)(value/weight));
/* 返回进位 */
return (int)(value/weight);
}
/** 计算二字符串最大字符长度 */
private static int getMaxLength(String strX,String strY)
{
return strX.length()>strY.length()?strX.length():strY.length();
}
/** 计算二字符串最小字符长度 */
private static int getMinLength(String strX,String strY)
{
return strX.length()<=strY.length()?strX.length():strY.length();
}
}
分享到:
相关推荐
素数问题,整数趣题,数学问题求解,矩阵,回文素数,求100~200之间的素数,阿姆斯特朗数,特殊的完全平方数,求1000以内的完全数,三重回文数,亲密数,自守数,神奇的数字6174,一数三平方,二分法求解方程,牛顿...
7.13 递归函数的非递归求解 7.14 任意长度整数加法 第8章 数值计算问题 8.1 递推化梯形法求解定积分 8.2 求解低阶定积分 8.3 迭代法开平方运算 8.4 牛顿法解方程 8.5 欧拉方法求解微分方程 8.6 改进的欧拉方法求解...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 ...
第三部分 数值计算与趣味数学篇 075 绘制余弦曲线和直线的迭加 076 计算高次方数的尾数 077 打鱼还是晒网 078 怎样存钱以获取最大利息 079 阿姆斯特朗数 080 亲密数 ...119 超长正整数的加法
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 129 飘带图案...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 129...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...
119 超长正整数的加法 第四部分 图形篇 120 绘制直线 121 绘制圆 122 绘制圆弧 123 绘制椭圆 124 设置背景色和前景色 125 设置线条类型 126 设置填充类型和填充颜色 127 图形文本的输出 128 金刚石图案 ...