斐波那契真的牛掰

題目鏈接

題目描述：

小Y在研究數(shù)字的時(shí)候，發(fā)現(xiàn)了一個(gè)神奇的等式方程 ，他屈指算了一下有很多正整數(shù)x滿足這個(gè)等式，比如1和2，現(xiàn)在問(wèn)題來(lái)了，他想知道從小到大第N個(gè)滿足這個(gè)等式的正整數(shù)，請(qǐng)你用程序幫他計(jì)算一下。
(表示按位異或運(yùn)算)

輸入描述:

第一行是一個(gè)正整數(shù) T<=100，表示查詢次數(shù)。
接著有T行，每行有一個(gè)正整數(shù)N(N<=1e12)，表示小Y的查詢。
輸出描述:：
對(duì)于每一個(gè)查詢N，輸出第N個(gè)滿足題中等式的正整數(shù)，并換行。
示例1

輸入：

4
1
2
3
10

輸出：

1
2
4
18

打表列出前100個(gè)數(shù)，找下規(guī)律

#include<bits/stdc++.h> #define ll long long #define N 100005 int inf = 0x3f3f3f3f; using namespace std; string solve(int n){ //將十進(jìn)制轉(zhuǎn)換成二進(jìn)制 string s;char c;while(n){c = '0' + n % 2;s = c + s;n /= 2;}return s; } int main (){ int now=0; printf("查詢次數(shù) 答案 二進(jìn)制形式\n"); for(int i=1;;i++){if(((i ^ (2 * i)) == 3 * i)){string s;int n;s = solve(i);printf("%4d%6d ",++now,i);cout << s << endl;} if(now == 100)break;} return 0; } 查詢次數(shù) 答案 二進(jìn)制形式1 1 1 //二進(jìn)制1位的有1個(gè) 2 2 10 //二進(jìn)制2位的有1個(gè) 3 4 100 4 5 101 //二進(jìn)制3位的有2個(gè)5 8 10006 9 10017 10 1010 //二進(jìn)制4位的有3個(gè)8 16 100009 17 1000110 18 1001011 20 1010012 21 10101 //二進(jìn)制5位的有5個(gè)13 32 100000 14 33 10000115 34 10001016 36 10010017 37 10010118 40 10100019 41 10100120 42 101010 //二進(jìn)制6位的有8個(gè)21 64 1000000 22 65 100000123 66 100001024 68 100010025 69 100010126 72 100100027 73 100100128 74 100101029 80 101000030 81 101000131 82 101001032 84 101010033 85 1010101 //二進(jìn)制7位的有13個(gè)34 128 1000000035 129 1000000136 130 1000001037 132 1000010038 133 1000010139 136 1000100040 137 1000100141 138 1000101042 144 1001000043 145 1001000144 146 1001001045 148 1001010046 149 1001010147 160 1010000048 161 1010000149 162 1010001050 164 1010010051 165 1010010152 168 1010100053 169 1010100154 170 1010101055 256 10000000056 257 10000000157 258 10000001058 260 10000010059 261 10000010160 264 10000100061 265 10000100162 266 10000101063 272 10001000064 273 10001000165 274 10001001066 276 10001010067 277 10001010168 288 10010000069 289 10010000170 290 10010001071 292 10010010072 293 10010010173 296 10010100074 297 10010100175 298 10010101076 320 10100000077 321 10100000178 322 10100001079 324 10100010080 325 10100010181 328 10100100082 329 10100100183 330 10100101084 336 10101000085 337 10101000186 338 10101001087 340 10101010088 341 10101010189 512 100000000090 513 100000000191 514 100000001092 516 100000010093 517 100000010194 520 100000100095 521 100000100196 522 100000101097 528 100001000098 529 100001000199 530 1000010010100 532 1000010100

找規(guī)律：

答案對(duì)應(yīng)的二進(jìn)制的位數(shù)符合斐波那契數(shù)，（打表斐波那契）

N和斐波那契的和有關(guān)，給定一個(gè)N可以判斷，此時(shí)答案的二進(jìn)制位數(shù)。（打表斐波那契的和）

舉一個(gè)例子：當(dāng)N等于70，答案的二進(jìn)制為：100100010，根據(jù)打表的斐波那契的和，可以判斷答案的二進(jìn)制是9位（55對(duì)應(yīng)1000000000），余下的100010，剛好是N-55的二進(jìn)制。遞推！

代碼實(shí)現(xiàn)：

#include<bits/stdc++.h> #define ll long long #define N 100005 int inf = 0x3f3f3f3f; ll f[N],sum[N],ans[N]; using namespace std; int main (){ f[1] = f[2] = 1;sum[1] = 1; sum[2] = 2;for(int i = 3; i <= 60; i++){ //打表斐波那契、斐波那契的和 f[i] = f[i-1] + f[i-2];sum[i] = sum[i-1] + f[i]; }int t;cin>>t;while(t--){ll n;cin>>n;ll ans=0;while(n){for(int i = 1; i <= 60; i ++){if(n <= sum[i] && n > sum[i-1]){ //找到n對(duì)應(yīng)答案的二進(jìn)制位數(shù) ans += 1LL << i-1;n -= sum[i-1] + 1LL;//ans += (ll) pow(2, i-1LL);//pow前面要加longlong要不然會(huì)爆數(shù)據(jù) break;}} }cout<<ans<<endl; }return 0; } 與50位技術(shù)專家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛 F- 1 + 2 = 3? (好难的找规律题)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。