UVa 11121 - Base -2
來源：程序員人生 發布時間：2014-11-12 08:22:10 閱讀次數：2172次
題目：計算以⑵為基數的數的表示。
分析：數論。寫出不同位數能表示的數字區間就能夠找到規律。
長度為1：[1，1]； 長度為2：[⑵，⑴]； 長度為3：[2，5]；
視察發現，區間長度增長為1，2，4，8，..，2^k，并且奇偶間隔開；
這樣可以按順序找到對應的1的位置，每次減去對應的基底（⑵^k）尋覓下1個1的位置便可。
說明：又是數論。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
long long l[40],r[40],b[40];
int ans[40];
int main()
{
l[0] = 1; r[0] = 1; b[0] = 1;
l[1] = ⑵;r[1] = ⑴;b[1] = ⑵;
long long base = 4;
for (int i = 2 ; i < 33 ; ++ i) {
if (i%2) {
r[i] = l[i⑵]⑴;
l[i] = l[i⑵]-base;
}else {
l[i] = r[i⑵]+1;
r[i] = r[i⑵]+base;
}
base <<= 1;
b[i] = b[i⑴]*⑵;
}
int n,m,s,e;
while (~scanf("%d",&n))
for (int i = 1 ; i <= n ; ++ i) {
scanf("%d",&m);
printf("Case #%d: ",i);
for (int i = 0 ; i < 33 ; ++ i)
ans[i] = 0;
s = 32;
while (s >= 0) {
if (m >= l[s] && m <= r[s]) {
ans[s] = 1;
m -= b[s];
}
s --;
}
e = 32;
while (e > 0 && !ans[e]) e --;
while (e >= 0) printf("%d",ans[e --]);
printf("
");
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
