主题：第54次编程比赛
yxs0001 [专家分：9560] 发布于 2007-05-27 17:06:00
题目1（60分）：对于一个自然数n，可以把它转换成对应的二进制数a[k] a[k-1] ..... a[1] a[0]，其
中：n= ∑a[i] * 2^i 而且 a[i]=0 或1 （0=< i < k) , a[k]=1。如：10 转换为1010；5 转换为 101。
我们统计一下a[0]......a[k]这k+1 个数中的0 的个数和1 的个数。如果在这k+1 个数中，0 的个数比1
个数多，就称n为A类数。给定m，求1~m (包含1,m)中A类数的个数。
函数接口：int solve(int m)
例如：m=3 return 0
题目2（40分）：已知n∈Q，则2n+1∈Q，4n+5∈Q；且 1∈Q，求Q中第k小元素。
函数接口：int Q(int k)
判分要求：
1、结果正确得分，错误该题0分。
2、结果正确者，计分方法：该题用时最少者满分，其他按与满分者用时比计算。（例如，第一题最佳时
间1s,某人用时2s,则 1/2*60 = 30）
3、二题得分之和最大者胜出。
格式要求：所有代码包含在参赛者名字的名字空间中。例如：
//名字空间
namespace yxs0001
{
//以下为参赛代码
int solve(int m)
{
return 0;
}
int Q(int k)
{
return 0;
}
}
或
namespace yxs0001
{
int solve(int m)
{
return 0;
}
}
namespace yxs0001
{
int Q(int k)
{
return 0;
}
}
回复列表 （共34个回复）
21 楼
wangfangbob [专家分：380] 发布于 2007-05-29 11:05:00
static int base2[30] = { 0, 0, 1, 2, 7, 13, 35, 64, 157, 287, 673, 1235, 2821, 5201,
11677, 21626, 47959, 89185, 195947, 365713, 797623, 1493483, 3237919, 6080145,
13116675, 24693591, 53047723, 100098287, 214257715, 405134411 };
int i, j, k, sum, bound, temp;
bound = ( int )log2( m ) + 1;
k = ( bound & 1 ) == 0 ? ( bound >> 1 ) - 1 : ( bound >> 1 );
temp = 1 << ( bound - 2 );
for ( i = bound - 1, sum = base2[i - 1], j = 1; i >= 1; temp >>= 1, --i )
{
if ( ( m & temp ) != 0 )
{
bound = k - j++;
if ( bound == 0 )
{
return sum + 1;
}
if ( bound > i - 1 )
{
return sum + ( ( ( temp << 1 ) - 1 ) & m ) + 1;
}
sum += base[i - 1][bound];
}
}
j <= k ? ++sum : NULL;
return sum;
}
}
22 楼
wangfangbob [专家分：380] 发布于 2007-05-29 11:08:00
[code=c]
namespace wangfangbob
{
int Q( int k )
{
static int sou[46] = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169,
63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903 };
int i, sum = 1;
for ( i = 45; i >= 1 && sou[i] > k; --i )
{}
k = k - sou[i--] + 1;
while ( i >= 2 )
{
if ( k > sou[--i] )
{
sum = 4 * sum + 5;
k -= sou[i--];
}
else
{
sum = 2 * sum + 1;
}
}
i == 1 ? sum = 2 * sum + 1 : NULL;
return sum;
}
}
[/code]
23 楼
shen08343 [专家分：2360] 发布于 2007-05-29 11:14:00
//Prog 54
//envir: Borland C++ Builder 4
#include <iostream.h>
#include <set>
namespace shen08343{
bool A_type(int x);
int solve(int m)
{
int count=0;
for (int i=1; i<=m; ++i)
if (A_type(i)) count++;
return count;
} //---------------------------
bool A_type(int x)
{
int bit, b[2]={0,0};
do {
bit=x%2;
x/=2;
b[bit]++;
}while (x);
return (b[0]>b[1]);
} //-----------------------------
int Q(int k){
set<int> myset;
myset.insert(1);
int j;
set<int>::iterator i;
for (i=myset.begin(),j=0; i!=myset.end()&& j<k; ++i, ++j)
{
myset.insert((*i)*2+1);
myset.insert((*i)*4+5);
}
for (i=myset.begin(),j=1; i!=myset.end()&& j<k; ++i, ++j);
return *i;
} //-------------------------------
}
int main(){
int M=1000000;
cout<<"when M="<<M<<endl;
cout<<"total number of A_type is: "<<shen08343::solve(M)<<endl;
cout<<"B's result: "<<shen08343::Q(M)<<endl;
system("pause");
}
24 楼
owen198608 [专家分：0] 发布于 2007-05-29 12:27:00
hehe
25 楼
bicholas [专家分：0] 发布于 2007-05-29 17:07:00
.
26 楼
SeZhang [专家分：2970] 发布于 2007-05-29 18:20:00
namespace SeZhang{
//给定m，求1~m (包含1,m)中A类数的个数。
int solve(int m)
{
int a[64];
int n=0,sum=0;
int j,k;
for(int i=1;i<=m;i++)
{
k=i;
while(k){
a[j]=k%2;
k=k/2;
j++;
}
for(k=0;k<j;k++)
if(a[k]==0)
n++;
if(n>(j/2))
sum++;
}
return sum;
}
//题目2（40分）：已知n∈Q，则2n+1∈Q，4n+5∈Q；且 1∈Q，求Q中第k小元素。
int Q(int k)
{
int (*ss)[3]=new int[k][3];
ss[0][0]=1;
ss[0][1]=3;
ss[0][2]=9;
int m=0,n=0;
for(int i=1;i<k;i++){
if(ss[m][1]>ss[n][2]){
ss[i][0]=ss[n][2];
ss[i][1]=ss[n][2]*2+1;
ss[i][2]=ss[n][2]*4+5;
n++;
}
else{
ss[i][0]=ss[m][1];
ss[i][1]=ss[m][1]*2+1;
ss[i][2]=ss[m][1]*4+5;
m++;
}
}
return ss[k-1][0];
}
}
27 楼
milord [专家分：0] 发布于 2007-05-30 11:06:00
dfad
28 楼
arfi [专家分：850] 发布于 2007-05-30 13:38:00
namespace arfi
{
/* 对于一个自然数n，可以把它转换成对应的二进制数a[k] a[k-1] ..... a[1] a[0]，
* 其中：n= ∑a[i] * 2^i 而且 a[i]=0 或1 （0=< i < k) , a[k]=1。如：10 转换为1010；5 转换为 101。
* 我们统计一下a[0]......a[k]这k+1 个数中的0 的个数和1 的个数。如果在这k+1 个数中，0 的个数比1
* 个数多，就称n为A类数。给定m，求1~m (包含1,m)中A类数的个数。
*/
int IsA(int m)
{
int M = 0;
int M_right = 0;
int M_left = 0;
int iNum_1 = 0;
int iNum_0 = 0;
int iTotal = 0; /* 总bit位数 */
M = m;
while(M != 0)
{
M_right = M;
M = M>>1; /* 循环条件 */
M_left = M<<1;
iNum_1 = iNum_1 + (M_right ^ M_left);
iTotal = iTotal+1;
}
iNum_0 = iTotal - iNum_1;
if(iNum_1 < iNum_0) /* 是A类数 */
{
return 1;
}
else/* 不是A类数 */
{
return 0;
}
}
int solve(int m)
{
int i = 1;
int iNum_A = 0; /* A类数的个数 */
if(m <= 0)
{
printf("请输入一个自然数!\n");
return -1;
}
for( ; i <= m ; i++)
{
iNum_A = iNum_A + IsA(i);
}
return iNum_A;
}
}
29 楼
surgeonlao [专家分：210] 发布于 2007-05-30 14:05:00
#include<iostream>
using namespace std;
int solve(int m)
{
int num=0;
int a[100][12];
for(int i=1;i<=m;i++)
{
int n=i,n1=0;
while(n!=0)
{
a[i-1][n1++]=n%2;
n=n/2;
}
int k=0,p=0,q=0;
while(k<=n1-1)
{
if(a[i-1][k]==0)p++;
else q++;
k++;
}
if(p>q) num++;
}
return num;
}
void main()
{
int mm;
cout<<"Please input number:"<<endl;
cin>>mm;
int number=solve(mm);
cout<<number<<" numbers belong to class A!!"<<endl;
}
30 楼
wuchengwei [专家分：1650] 发布于 2007-05-30 14:24:00
第二题
#define MAX_K 1346269 //可查询的k的上限，程序无k值的合法性判断
namespace wuchengwei
{
int fib[]={1,
1, 2, 3, 5, 8, 13, 21, 34, 55,
144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,
17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269
};
int cal_value(unsigned int index)
{
int t=index, exp=1, result=1;
while(t>>=1)
exp<<=1;
while(exp!=1)
{
index&=(exp-1), exp>>=1;
if(index & exp)
result=(result<<=2)+5;
else
result=(result<<=1)+1;
}
return result;
}
int Q(int k)
{
int i=1, index, r;
while(fib[i]<=k)
i++;
index=1<<(i-2);
k-=fib[i-1];
while(k)
{
i=1;
while(fib[i]<=k)
i++;
k-=fib[i-1];
r=index&(1<<(i-1)-1);
(((index>>=(i-1))|=1)<<=(i-2))|=r;//合并index左起第i和第i-1个0为1
}
return cal_value(index);
}
}
我来回复
您所在位置：