`
xinyoulinglei
  • 浏览: 123809 次
社区版块
存档分类
最新评论
收藏列表
标题 标签 来源
“大整数相加”的递归解法 “大整数相加”的递归解法
String addBigInt(StringBuffer num1, StringBuffer num2); 

思路分析: 
1、如果用递归的思想来看,其实就是第i位的数字相加,剩余的i-1位组成的大数,继续进行递归流程 
2、目标相加的字符串需要先倒序,保证位对齐,而结果再倒序,则可以得到正确的答案 
/**
 * @author Micah
 * 
 */
public class Calculator {

	/**
	 * use the recursion to add the big integer.
	 * 
	 * @param num1
	 * @param num2
	 * @param isCarry
	 * @param result
	 */
	public static void addBigInt(StringBuffer num1, StringBuffer num2, int pos,
			boolean isCarry, StringBuffer result) {
		if (pos < num1.length() || pos < num2.length()) {
			int value = 0;
			if (isCarry) {
				value++;
			}
			char temp1 = pos < num1.length() ? num1.charAt(pos) : '0';
			char temp2 = pos < num2.length() ? num2.charAt(pos) : '0';
			value += add(temp1, temp2);
			if (value >= 10) {
				isCarry = true;
				value -= 10;
			} else {
				isCarry = false;
			}
			result.append(value);
			addBigInt(num1, num2, ++pos, isCarry, result);
		} else {
			if (isCarry) {
				result.append('1');
				addBigInt(num1, num2, ++pos, false, result);
			}
		}

	}

	/**
	 * add method for big number.
	 * 
	 * @param num1
	 * @param num2
	 */
	public static String addBigInt(StringBuffer num1, StringBuffer num2) {
		StringBuffer result = new StringBuffer();

		num1.reverse();
		num2.reverse();

		addBigInt(num1, num2, 0, false, result);

		result.reverse();

		return result.toString();
	}

	// TODO: need to decrease the conversion between different types, maybe a
	// array to priorly store all the data.
	private static int add(char num1, char num2) {
		return Integer.parseInt(String.valueOf(num1))
				+ Integer.parseInt(String.valueOf(num2));
	}
}
Global site tag (gtag.js) - Google Analytics