月之?dāng)?shù)

Problem Description 當(dāng)寒月還在讀大一的時(shí)候，他在一本武林秘籍中（據(jù)后來(lái)考證，估計(jì)是計(jì)算機(jī)基礎(chǔ)，狂汗-ing），發(fā)現(xiàn)了神奇的二進(jìn)制數(shù)。
如果一個(gè)正整數(shù)m表示成二進(jìn)制，它的位數(shù)為n（不包含前導(dǎo)0），寒月稱(chēng)它為一個(gè)n二進(jìn)制數(shù)。所有的n二進(jìn)制數(shù)中，1的總個(gè)數(shù)被稱(chēng)為n對(duì)應(yīng)的月之?dāng)?shù)。
例如，3二進(jìn)制數(shù)總共有4個(gè)，分別是4（100）、5（101）、6（110）、7（111），他們中1的個(gè)數(shù)一共是1＋2＋2＋3=8，所以3對(duì)應(yīng)的月之?dāng)?shù)就是8。 Input 給你一個(gè)整數(shù)T，表示輸入數(shù)據(jù)的組數(shù)，接下來(lái)有T行，每行包含一個(gè)正整數(shù) n（1<=n<=20）。 ? Output 對(duì)于每個(gè)n ，在一行內(nèi)輸出n對(duì)應(yīng)的月之?dāng)?shù)。 ? Sample Input 3 1 2 3 ? Sample Output 1 3 8

分析： 　　1二進(jìn)制數(shù)有1個(gè)： ?1 　　2二進(jìn)制數(shù)有2個(gè)：10 11 　　3二進(jìn)制數(shù)有4個(gè)：100 101 110 111 　　4二進(jìn)制數(shù)有8個(gè)：1000 1001 1010 1011 1100 1101 1110 1111 　　可以看到第n二進(jìn)制數(shù)是第(n-1)二進(jìn)制數(shù) 總數(shù)目的2倍，他們第一位都是1，所以多出來(lái)2ⁿ個(gè)1。 　　所有的數(shù)字中，一半是在1后邊加了第(n-1)二進(jìn)制數(shù)。另一半第一位是1，第二位是0，最后的各個(gè)位跟第(n-1)二進(jìn)制數(shù)中最后個(gè)各個(gè)位都相同，令f[n]表示第n二進(jìn)制數(shù)中1的個(gè)數(shù)。所以多出來(lái) f[n-1] + (f[n-1] - 2^n-1) = 2*f[n-1]-2^n-1 　　所以可以推導(dǎo)出：f[n] = 2ⁿ + 2*f[n-1] -2^n-1 = 2^n-1 + 2*f[n-1] 代碼如下： 1 # include<stdio.h> 2 int f[21]={0,1,3}; 3 void init(){ 4 int k=1; 5 for(int i=3; i<21; i++){ 6 k <<= 1; 7 f[i] = k + 2*f[i-1]; 8 } 9 } 10 int main(){ 11 int T; 12 init(); 13 scanf("%d",&T); 14 while(T--){ 15 int n; 16 scanf("%d",&n); 17 printf("%d\n",f[n]); 18 } 19 return 0; 20 }

?

總結(jié)

以上是生活随笔為你收集整理的HDU 2502 月之数（简单递推）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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