作者jellyfishuan (jellyfishuan)
看板C_and_CPP
标题[问题] 大数阶乘运算
时间Thu Apr 27 16:52:27 2017
开发平台(Platform): (Ex: Win10, Linux, ...)
win10
编译器(Ex: GCC, clang, VC++...)+目标环境(跟开发平台不同的话需列出)
Visual Studio 2015
额外使用到的函数库(Library Used): (Ex: OpenGL, ...)
问题(Question):
各位版大好,小弟目前得写大数计算机,期末实习的project QQ
然後目前卡在阶乘的部分惹,网路上搜寻发现大部分资料皆为几十上百的阶乘
例如50!或170!之类的
但我们的大数计算机希望能做到真正的大数那种可能可以处理几十万!的
然後现在有个方向是字串读入输入的数字
输入的数字可能过大而int塞不下
然後分解4位并透过stringstream塞入int[8]
int[0]~int[8] 每个阵列里各有四位数字
举例来说就是string(123456789012)会变int[0]=1234,int[1]=5678,int[2]=9012这样
然後再透过int阵列去做阶乘
答案的int矩阵假如计算後大於9999,
则int[7]=int[8]/9999,int[8]=int[8]%9999;
But 卡在不知道如何去抓input的长度从而可以塞入阵列里面
试着编译过之後 VS的整个专案废掉说不给用
出现out of range然後说什麽档案已消失之类的QQ
发问是希望有大大可以指点一下QQ
并顺便看一下想的方向正确吗 因为做到现在有点疑惑,感觉写到一半觉得方向好像有点
错Q
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.118.146.57
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1493283149.A.B50.html
※ 编辑: jellyfishuan (140.118.138.73), 04/27/2017 16:53:29
1F:→ Hazukashiine: 楼下借我一颗水晶球04/27 16:53
2F:→ Hazukashiine: 都天大地大的学校惹 为什麽还不会问问题ㄋ04/27 16:55
因为整个程式码在VS爆掉之後通通不见惹QQ
所以想说先把想法丢上来请教大家看看w
※ 编辑: jellyfishuan (140.118.138.73), 04/27/2017 16:57:05
3F:→ Hazukashiine: 哇靠... 通通不见还真的蛮屌的 屌 爆 了04/27 16:57
4F:→ Hazukashiine: 如果很懒的话就用 "GNU MP Bignum Library"04/27 16:59
5F:→ Hazukashiine: 至少不用想那些 trivial 的问题 有现成的库可以用04/27 16:59
哦哦好的感谢大大提供的资讯!! 等等来参考一下
6F:推 jerryh001: string 不是有 length() 可以用?04/27 17:09
我知道有size,length等函数可以抓噢,是有点不太确定要怎麽抓出长度之後用长度去对
应到阵列里面这样,这部分我有点卡关
7F:推 tuyutd0505: 不限定使用第三方函式库的话 推荐 GMP library 或 MPI04/27 17:10
8F:→ tuyutd0505: R library(在Win平台我觉得比较好装) 精度是吃记忆体04/27 17:10
9F:→ tuyutd0505: 大小的 记忆体越大可以算得越多04/27 17:10
好的,谢谢大大!!!
10F:→ LPH66: 先给你个心理准备, 几十万阶乘会有上百万位数04/27 20:58
11F:→ LPH66: 就算四位一组 (顺带一提这里是 10000 不是 9999)04/27 20:58
12F:→ LPH66: 还是会需要那麽大的一个阵列, 写得出来不一定跑得出来04/27 20:59
所以果然想的不够周全www
13F:→ pttworld: 以int的2147483647来说,二数相乘不能超过,所以取四位 04/27 21:23
14F:→ pttworld: 数是至多了。取余是取一万余,不是9999。因为是到几十04/27 21:23
15F:→ pttworld: 万,乘法写法必须每回圈乘完做加总後的进位判断,因为04/27 21:23
16F:→ pttworld: 加了几十万次有可能溢位,但如果只是几千,9999的几千04/27 21:23
17F:→ pttworld: 次也放得下,可全部乘完再一次进位处理。04/27 21:23
18F:→ pttworld: 如果觉得一般的乘法太慢,可以考虑傅立叶转换的大数乘04/27 21:33
19F:→ pttworld: 法,不过花费记忆体多。04/27 21:33
哦哦哦感谢大大点出盲点!!!
20F:→ HamalAri: 10 万阶乘 43万位,本人的洨笔电三秒就跑完,gmp很强的 04/27 23:25
21F:→ HamalAri: 洨笔电还只有 2g 呢 04/27 23:26
22F:→ HamalAri: 要相信发展了二十年的东西绝对比自干的东西好04/27 23:26
好的谢谢板上大大们的提醒!!
我会去看完之後再来看怎麽解决的w
※ 编辑: jellyfishuan (140.118.138.42), 04/28/2017 02:50:29
23F:推 school4303: 连.cpp都不见? 04/28 06:47
就消失了我找不到QQ 我猜可能路径乱掉之类的吧就认份重写了,还好还写不多几十行而
已
24F:→ MOONRAKER: 还 满 屌 的 屌 爆 了 04/28 10:18
25F:→ descent: 先把程式码放在版本控制系统吧 04/28 10:54
26F:推 LPH66: >HamalAri 他现在就是要想自己写, 那自己写就会有这个问题04/28 14:35
27F:→ LPH66: 先不说 gmp, 光是大阶乘我在几年前就有看过快速实作 04/28 14:36
28F:→ LPH66: 那个做法在十几年前的电脑十万阶乘也能几秒内跑出来 04/28 14:40
30F:→ LPH66: 不过原 PO 只是要写个期末 project 而且应该不用玩这麽大04/28 14:42
31F:→ LPH66: 而已* 04/28 14:42
32F:→ LPH66: 所以我只是要提醒原 PO 量力而为, 目标订太大可能会失望 04/28 14:45
嗯嗯其实能过期末实习的就ok了
感谢大大翻出的旧档案!!
※ 编辑: jellyfishuan (140.118.138.42), 04/28/2017 15:36:09