作者ddchris (克里斯)
看板C_and_CPP
标题[问题] 大数问题(费氏数列计算) 利用阵列
时间Tue Jul 18 17:49:33 2017
开发平台(Platform): (Ex: Win10, Linux, ...)
Win10
编译器(Ex: GCC, clang, VC++...)+目标环境(跟开发平台不同的话需列出)
Visual studio 2017
问题(Question):
当测试值小时执行都蛮正常
但是当 N>650(第650项) 或 W>450(阵列数字位数)时会出现执行错误讯息(不知为何?)
错误结果(Wrong Output):
发生未处理的例外状况: 0xC00000FD: Stack overflow (参数: 0x00000000,
0x01202000)。
程式码(Code):(请善用置底文网页, 记得排版)
http://ideone.com/KqN9Qq
补充说明(Supplement):
想法是利用二维矩阵纪录每一个费氏数列的值(由左而右)
最後答案再由右而左反着印出来
自学C++的程式超新手
还请各位大神鞭小力一点... 感谢!!
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.166.238.99
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1500371377.A.283.html
1F:推 Zero0910: stack空间不够你放这麽大的阵列啦 请用new/delete去配置 07/18 17:57
2F:→ Zero0910: 记忆体空间 07/18 17:57
3F:推 Zero0910: 置底十三诫第10点 07/18 18:00
感谢! 虽然stack空间这词对我很陌生,等会试试看利用动态阵列!
改正过後变成这样
http://ideone.com/SFFUMe
编译器可以过了~
但是ZeroJudge 还是过不了!! 是因为测资的记忆体限制吗? 这又能如何克服?
错误讯息为:
系统呼叫了 abort 函式!
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
Aborted (core dumped)
补上题目:
https://zerojudge.tw/ShowProblem?problemid=d283
4F:推 Yshuan: 你只需要N-2跟N-1去算第N项 从0到N-3的空间根本不用 07/18 19:37
5F:推 remizu: bad_alloc exception是new失败所产生的 通常是要太多 07/18 19:41
6F:→ remizu: 记忆体 改用Y大的方法就可以解决 07/18 19:42
7F:推 moebear: 我建议做二维动态阵列new一次 然後把它截成二维的样子 07/18 19:43
感谢几位热心的回复! 但小弟资质驽钝一时还无法了解 Orz
像Y大说 只利用 N-2跟N-1项去算第N项? 但不是还得先算出 N-1跟 N-2项?
然要算 N-1项又要先算 N-2 N-3,不是等於全部都要算一次吗XD
看来我需要冷静一下 先吃个饭 晚点继续研究~
9F:→ moebear: 前面的丢掉会算太久吧 07/18 20:25
10F:→ Littlechozy: F20000不超过6000位,如果用1个int表示10000,一个数 07/18 21:09
11F:→ Littlechozy: 要1200个int,以记忆体有500MB来看,可以算看看 07/18 21:11
最後试了以下几点修正:
1.修改了阵列类型为long long (用10^18进位让阵列能储存更多位数减少宣告位数W?)
2.进位部分补上之前漏掉的等号(行31)
3.Output部分第二项开始加上数字前必须补'0'(行50)
题目:
https://zerojudge.tw/ShowProblem?problemid=d283
历经千辛万苦最终版本
http://ideone.com/qHosrs 终於通过测试!
这题让我学到了不少观念 谢谢各位指导~ 也欢迎提供更有效的做法 <(__)>
※ 编辑: ddchris (60.245.65.179), 07/19/2017 11:18:13