作者asdfg1597860 (Jay)
看板C_and_CPP
标题[问题]试找出1~N 有几种挑数字的方法(子集)不包含连续数
时间Mon Aug 27 12:09:14 2018
开发平台(Platform): (Ex: Win10, Linux, ...)
编译器(Ex: GCC, clang, VC++...)+目标环境(跟开发平台不同的话需列出)
额外使用到的函数库(Library Used): (Ex: OpenGL, ...)
问题(Question)：
各位高手好 小弟写了一个程式想解这个问题(政大解题系统上的题目)
但在最後一个查验点失败了
想请问各位高手能告诉小弟犯了什麽愚蠢错误
因为小弟看了很多次还是觉得可行
喂入的资料(Input)：
1<=n<=10^7
预期的正确结果(Expected Output)：
245459220446488920
错误结果(Wrong Output)：
-1
程式码(Code)：(请善用置底文网页, 记得排版，禁止使用图档)
#include <iostream>
using namespace std;
long long int pow(unsigned int a) {
if (a == 0)
return 1;
else
return 2* pow(a-1);
};
int main()
{
unsigned int input,odditem,evenitem;
while(cin>>input){
if (input % 2 == 0){
evenitem = (input / 2);
odditem = evenitem;
}
else {
evenitem = (input - 1) / 2;
odditem = (input + 1) / 2;
}
cout << pow(odditem) + pow(evenitem) - 1 << endl;
}
return 0;
}
补充说明(Supplement)：
什麽数字都没选也算一种
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 59.127.200.146
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1535342957.A.A65.html
※ 编辑: asdfg1597860 (59.127.200.146), 08/27/2018 12:10:07
1F：→ john2007: 想法是错的 n = 4的时候正确答案是8 你的输出结果是7 08/27 13:49
2F：→ john2007: 而用简单的观察法可以知道你2的觅次 碰到1e7会爆掉 08/27 13:53
3F：→ john2007: 给个提示，用DP 取/不取的分法 应该解得出来 08/27 14:00
想请问n=4时 我能列出来的有 空集合、{1}、{2}、{3}、{4}、{1,3}、{2,4} 这7种
不知道是少哪一个集合?
※ 编辑: asdfg1597860 (59.127.200.146), 08/27/2018 14:54:25
4F：→ john2007: {1, 4} 08/27 15:01
谢谢前辈 我竟然犯了这麽大的错
※ 编辑: asdfg1597860 (59.127.200.146), 08/27/2018 17:32:37
5F：推 cutekid: f(n) = f(n - 1) + f(n - 2) 08/27 18:58
前辈这是费式数列吗?
※ 编辑: asdfg1597860 (59.127.200.146), 08/29/2018 15:37:45
6F：推 oToToT: 楼上那就是本题的答案啊，只是f(1)=2,f(2)=3 08/29 16:01
谢谢前辈 我完全没想过用费事数列来解这个问题 好厉害呀
※ 编辑: asdfg1597860 (59.127.200.146), 08/30/2018 09:10:41
7F：嘘 Sidney0503: 有Prob_Solve版 08/31 09:27