a**********2
发帖数: 340 | 1 Design the data structure to provide the mathematical operations +, - ,/ , *
etc for the very very large numbers also implement the + function for two
such very very large numbers ...say numbers with 1 Million digits.
这道题怎么答比较好？用linked list，还是string？ |
f*******t
发帖数: 7549 | 2 1. binary tree, post-order traversal
2. linked list太费空间，感觉用string存好点，类似于linked list那样把数倒过来
存 |
a**********2
发帖数: 340 | 3 binary tree能详细说一下吗？这个难道不比list费空间吗？
【在 f*******t 的大作中提到】
: 1. binary tree, post-order traversal
: 2. linked list太费空间，感觉用string存好点，类似于linked list那样把数倒过来
: 存
|
k****n
发帖数: 369 | 4 string is not good. each char cost 8 bit, wasting more than half bits.
for pure storage aim, Lucene use VInt, which use the highest bit as the
indicator whether
there are more bytes. Which is probably enough.
for calculation, I would use an integer array. which should be enough.
【在 f*******t 的大作中提到】
: 1. binary tree, post-order traversal
: 2. linked list太费空间，感觉用string存好点，类似于linked list那样把数倒过来
: 存
|
f*******t
发帖数: 7549 | 5 binary tree用来存储+ - * /运算操作，大数字用string存
举个例子：
1 + 2 * 3
建成树就是
+
/ \
1 *
/ \
2 3
用post-order traversal计算式子的值。
实现+的问题，因为数字很大，考虑到效率问题我觉得用string存比较好，比如1234567890存成字符
串“0987654321”，加的时候跟普通的链表相加题类似
【在 a**********2 的大作中提到】
: binary tree能详细说一下吗？这个难道不比list费空间吗？
|
c****p
发帖数: 6474 | 6 用字符串太浪费了，做起来也费事
可以用定长的char数组存，每个字节存0-99，满百向高位进位。若干字节（比如说1K，
或者1M）为一段，不够用了就申请新的段。每个段可以附带若干信息域，比如当前段有
多少字节是有效位（最高段有可能字节用不满），指向更高段的指针，如此等等。
做计算和打印都很方便。【 在 fantasist (fan) 的大作中提到: 】 |
a**********2
发帖数: 340 | 7 那你这个打算逆序存储还是正序存储？
【在 c****p 的大作中提到】
: 用字符串太浪费了，做起来也费事
: 可以用定长的char数组存，每个字节存0-99，满百向高位进位。若干字节（比如说1K，
: 或者1M）为一段，不够用了就申请新的段。每个段可以附带若干信息域，比如当前段有
: 多少字节是有效位（最高段有可能字节用不满），指向更高段的指针，如此等等。
: 做计算和打印都很方便。【 在 fantasist (fan) 的大作中提到: 】
|
c****p
发帖数: 6474 | 8 无所谓吧。。统一就可以。。
我觉得比较方便的一个是对于1234567890，
a[0] = 90, a[1] = 78, a[2] = 56 ……
做加法的时候让i从0到最高位数循环就得了。
【在 a**********2 的大作中提到】
: 那你这个打算逆序存储还是正序存储？
|
d*******l
发帖数: 338 | 9 以前需要用到高精度的时候一般就直接拿int数组存的，每个元素表示4位。这样比
string每个元素表示一位要高效不少。通常a[0]保存大整数的低位，从高位往低位输出
的结果正好就是数的正常表示，还挺方便的。
【在 a**********2 的大作中提到】
: 那你这个打算逆序存储还是正序存储？
|
f*******t
发帖数: 7549 | 10 这个方法不错
【在 c****p 的大作中提到】
: 用字符串太浪费了，做起来也费事
: 可以用定长的char数组存，每个字节存0-99，满百向高位进位。若干字节（比如说1K，
: 或者1M）为一段，不够用了就申请新的段。每个段可以附带若干信息域，比如当前段有
: 多少字节是有效位（最高段有可能字节用不满），指向更高段的指针，如此等等。
: 做计算和打印都很方便。【 在 fantasist (fan) 的大作中提到: 】
|
c****p
发帖数: 6474 | 11 用32位的int存10^9也不错，，这个应该效率更高。。。
【在 f*******t 的大作中提到】
: 这个方法不错
|
a********m
发帖数: 15480 | 12 恩。把10进制变成10^9进制。
【在 c****p 的大作中提到】
: 用32位的int存10^9也不错，，这个应该效率更高。。。
|
