最近毕业在即,经常流连于各大公司的笔试面试之间,不断的面试,不断的杯具……
最后发现好多题目都是似曾相识,这里就介绍一条经典的题目——编程实现两个大整数的相加
函数接口如下:
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));
}
}
哈,第一次在JavaEye上面发东西,大家多多指教啦~~
分享到:
相关推荐
汉诺塔的非递归解法,十分神奇,值得借鉴! 汉诺塔的非递归解法,十分神奇,值得借鉴! 汉诺塔的非递归解法,十分神奇,值得借鉴! 汉诺塔的非递归解法,十分神奇,值得借鉴! 汉诺塔的非递归解法,十分神奇,值得...
最大公约数的递归解法,这是一个cpp程序,运行正常,是求输入的2个数的最大公约数的递归算法
八皇后问题是一种回溯思想的体现,可以用C语言里面的递归算法实现
大整数乘法实现(未用分治与递归) 大整数乘法是计算机科学中的一种基本运算,它在密码学、数据加密、科学计算等领域中有着广泛的应用。在本文中,我们将实现大整数乘法的算法,着重于探讨未使用分治与递归的实现...
汉诺塔问题c++递归解法
作者:西电软院 coder_jack@126.com 去我的...用google搜素关键字“风中之哨”排名第一的就是我的博客!够牛X吧!?学习严蔚敏的数据结构时老师布置的实践作业,采用递归解法求解迷宫中的通路。源码在VC6.0下编译通过!
queen问题的递归解法 此文档包含详细的注释 (分享)
但是他很严格,所以我老老实实的做完了他布置的作业,这是迷宫的非递归解法!完全是我自己想出来的!声明下!欢迎你来我的blog交流,在google搜索关键字“风中之哨”排名第一的就是我的博客!很牛吧!
C++编写汉诺塔的非递归解法,可直接运行 有文档解释.
程序可用递归算法计算出多边形游戏所计算出的最大值。
[6.3.1]--410找零兑换问题的递归解法.srt
[6.3.1]--410找零兑换问题的递归解法.mp4
Ackermann函数的递归与非递归解法 为Visual C++ 6.0工程 有测试函数
将河内塔问题的经典递归算法改写为非递归算法,对所有递归问题化解为非递归问题有参考价值
大整数的乘法 c++ 源码 内容: 输入两个n位数X和Y,用递归的方式实现乘积运算,并使时间复杂度为O(n1.59)
此程序可以实现对两个整数求最大公约数,所用得法为递归算法。
任何时候大盘子不能放在小盘子上面。 尽管规则简单明了,但汉诺塔问题的解决却需要巧妙的思考和策略。这个问题最引人入胜的地方在于其递归性质。递归,简单来说,就是一个函数调用自身的过程。在汉诺塔问题中,为了...
算法分析与设计 用递归分治算法解决大整数乘积问题(用java语言)
各位相加给定一个非负整数 num,反复将各个位上的数字相加,直到结果为一位数。示例:输入: 38输出: 2解释: 各位相加的过程为:3 + 8 = 11, 1