作者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/m.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