Problem H
Time Limit : 3000/1000ms (Java/Other) Memory Limit :32768/32768K (Java/Other)
Total Submission(s) : 1 Accepted Submission(s) : 1
Problem Description
A有1数m,B来猜.B每猜一次,A就说"太大","太小"或"对了" 。 <br>问B猜n次可以猜到的最大数。 <br>
Input
第1行是整数T,表示有T组数据,下面有T行 <br>每行一个整数n (1 ≤ n ≤ 30) <br>
Output
猜n次可以猜到的最大数<br>
Sample Input
2
1
3
Sample Output
1
7
算法分析:
题意能理解:
最多猜n次一定可以猜到1至m(闭区间)内的任意数字,求m的最大值。
要猜到的最大的数字m,即在1到m间的每一个数,你都能在n次内把它猜出来。所以说在最坏的情况下,在1到m间,你最多只要猜log2(m+1)(取整)次,所以易知m=2^n - 1,即猜n次,你能猜到的最大的数为2^n - 1。
二分实现:假设要查找的最大数是m, 则,
第一次查找,(m+1)/2=m;得m=1;
第二次查找,((m+1)/2+1+m)/2=m;得m=3;
第三次查找,(((m+1)/2+1+m)/2+1+m)=m;得m=7;
归纳:m=2^n-1;
代码实现:
#include<bits/stdc++.h>
using namespace std;
int main()
{int T;cin>>T;while(T--){int n;cin>>n;int maxx=pow(2,n)-1;cout<<maxx<<endl;}return 0;
}