主题：第50次编程比赛
bpttc [专家分：8790] 发布于 2007-03-07 19:10:00
一个好汉三个帮，三个好汉九个帮，九个好汉二十七个帮，...停，今天不是让你算n个好汉几个帮（有兴趣的网友可以自己算），我们来看这个集合
{ 1, 3, 9, 27, 81, ... }
这个集合是一个递增的无限集，每个元素都是3的幂。
我们把这个集合的所有子集按照元素和从小到大的顺序排好： {}(空集), { 1 }, { 3 }, { 1, 3 }, { 9 }, { 1, 9 }, { 3, 9 }, { 1, 3, 9 }, ...
现在给定一个正整数n，求第n个子集的所有元素，并按从大到小的顺序排列好
例：
n的值 结果
1 { }
4 { 3, 1 }
6 { 9, 1 }
500 { 6561, 2187, 729, 243, 81, 3, 1 }
细节要求：
1. n的范围： n >= 1 ，unsigned int
2. 接口： void HeroNeedThree(INT64* subset, unsigned int n);
其中INT64是指64位整数，可以用 typedef long long INT64; 也可以自定义
subset就是存放结果的数组，其中subset[0]存放结果子集的元素个数，
然后子集元素从大到小存入subset[1],subset[2],......
3. 提供一个简单的测试例程，供大家测试结果是否正确
#include <stdio.h>
#include <stdlib.h>
#define MAX ( 50 ) //子集结果数组最大容量
#define N ( 1e8 ) //要测试的N
typedef long long INT64;
void HeroNeedThree(INT64* subset, unsigned int n);
int main(int argc, char *argv[])
{
INT64 subset[MAX] = {0};
int i;
HeroNeedThree(subset, N);
printf("\n{ ");
for (i = 1; i <= subset[0]; ++i)
{
printf("%I64d, ", subset[i]);
}
printf("}\n");
system("pause");
return 0;
}
截止到周日3月11日晚。
第一次出题，考虑不周的地方请多多包含。有什么问题请发短信给我。
最后更新于：2007-03-07 19:20:00
回复列表 （共47个回复）
31 楼
windboyzsj [专家分：0] 发布于 2007-03-09 18:02:00
//如果定义 typedef long long INT64;
//我用VC6.0编译时报错
//现在定义:
//typedef __int64 INT64;
/*****************************************************************
/算法分析:
/假设集合A每个元素都是3的幂,A的元素个数为i,由组合知识知道其
/子集的个数为pow(2,i)(一个元素可以存在或不存在,所以2*2*2*2.....),
/把A当作等比数列:{pow(3,0),pow(3,1),pow(3,2),...,pow(3,i-1)}
/可以发现:
/前i项之和 (pow(3,i)-1)/2
/第i+1项 pow(3,i)
/即前i项之和<第i+1项 (这个结论很重要)
/由这结论我们可以知道,前i项组成的任意子集排在{第i+1项}这个子集后面;
/而排在{第i+1项}后面的子集是由{第i+1项}|{前i项组成的任意子集中的一个}
/如此一来求第n个元素和最少的子集(记为集合Q)时,可以先求出符合pow(2,i)<n<=pow(2,i+1)的i值
/即集合A元素个数为i时,所有可能的子集数<n,集合A元素个数为i+1时,所有可能的子集数>=n,
/由前面的结论可知,所求的子集一定包含集合A的第i+1个元素,即pow(3,i),记为f
/并且是最大的一个.那么求Q时就可以 {f}并上{含i个元素的集合A所有子集的其中的一个子集}
/记为B|C,此时集合C同用同样的方法求符合pow(2,j)<n'<=pow(2,j+1)的j值,最大值pow(3,j),记为g
/其中n'=n-pow(2,i),即距离所求第n个子集还需要排多少个,
/那么求Q时就可以 {f}|{g}|{含j个元素的集合A所有子集的其中的一个子集}到此可以看出这道题目可以
/用递归的方法做，理论终止条件为n-pow(2,i)==0,实际编程n-pow(2,i)==1终止即可
/因为最后一个并上的一定是空集
***************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX ( 50 ) //子集结果数组最大容量
typedef __int64 INT64;
void HeroNeedThree(INT64* subset,unsigned int n);
int main(int argc, char *argv[])
{
INT64 subset[MAX] = {0};
int i;
unsigned int n;
printf("Input a Integer n: ");
scanf("%d",&n);
//非法数
if(n<1)
{
printf("You should input a integer whitch is more than 0 !\n");
system("pause");
return 0;
}
//调用
HeroNeedThree(subset,n);
//打印
printf("\n{ ");
for (i=1;i<subset[0];i++)
{
printf("%I64d, ", subset[i]);
}
if(subset[0]>0)
printf("%I64d ", subset[i]); //为了美观最后一个元素另外打印
printf("}\n"); //目的是少打印一个","
system("pause");
return 0;
}
void HeroNeedThree(INT64* subset,unsigned int n)
{
unsigned int s=1; //集合A的子集个数
unsigned int i=0; //集合A的元素个数
static int j=1; //数组下标
if(n==1) //递归终止条件
{
subset[0]=j-1; //存入所求子集元素的个数
j=1; //由于j是静态变量,结束后需要复位才可以重复调用
return;
}
//求最子集数最接近n的集合A的元素个数i
while(s<n)
{
i++;
s*=2; //这里用自乘代替pow(2,i)会效率很多
}
subset[j]=(INT64)pow(3,i-1); //i多了一次自增,所以i-1
j++; //准备下一个储存位置的下标
HeroNeedThree(subset,(n-s/2)); //s多了一次*2,所以/2
//(n-s/2)为目前剩余的距离
}
32 楼
lewsn2008 [专家分：1010] 发布于 2007-03-09 21:38:00
#include<stdio.h>
#include<math.h>
#define MAX 50
typedef long long INT64;
int func(int n)
{
int i = 0;
while(!(pow(2,i)<=n && pow(2,i+1)>n)) ++i;
return(i);
}
void HeroNeedThree(INT64* subset, unsigned int n)
{
static count = 0;
int r, s;
if(!n)
{
subset[0] = count;
return;
}
else
{
r = func(n);
subset[++count] = pow(3, r);
s = n-pow(2,r);
HeroNeedThree(subset, s);
}
}
main()
{
INT64 subset[MAX] = {0};
int i, p;
printf("\nPlease input:");
scanf("%d", &p);
HeroNeedThree(subset, p-1);
printf("{ ");
for (i = 1; i < subset[0]; ++i)
{
printf("%ld, ", subset[i]);
}
if(p>1) printf("%ld", subset[subset[0]]);
printf(" }\n");
getch();
return 0;
}
有个问题，大伙帮我解决一下：
我的这个程序中有点问题，数组输出是用的 长整型 输出格式 %ld
请问自定义类型 INT64 应该用什么 格式控制 啊？
这样好像不行吧：
printf("%I64d, ", subset[i]);
33 楼
lewsn2008 [专家分：1010] 发布于 2007-03-09 22:32:00
#include<stdio.h>
#include<math.h>
#define MAX 50
typedef long long INT64;
int func(int n)
{
int i = 0;
while(!(pow(2,i)<=n && pow(2,i+1)>n)) ++i;
return(i);
}
void HeroNeedThree(INT64* subset, unsigned int n)
{
static count = 0;
int r, s;
if(!n)
{
subset[0] = count;
return;
}
else
{
r = func(n);
subset[++count] = pow(3, r);
s = n-pow(2,r);
HeroNeedThree(subset, s);
}
}
main()
{
INT64 subset[MAX] = {0};
int i, p;
printf("\nPlease input:");
scanf("%d", &p);
HeroNeedThree(subset, p-1);
printf("{ ");
for (i = 1; i < subset[0]; ++i)
{
printf("%ld, ", subset[i]);
}
if(p>1) printf("%ld", subset[subset[0]]);
printf(" }\n");
getch();
return 0;
}
34 楼
forjane [专家分：5670] 发布于 2007-03-09 23:12:00
void HeroNeedThree(INT64* subset, unsigned int n)
{
static INT64 powof3[32];
static int initialized=0;
int i;
if(!initialized)
{
//你也可以在定义时直接初始化这个数组,如果你有耐心写一堆数字的话^_^
for(i=1,powof3[0]=1;i<32;i++)
{
powof3[i]=powof3[i-1]*3;
}
initialized=1;
}
for(i=31,subset[0]=0,n--;i>=0;i--)
{
if(n&(1<<i)) //检查对应2进制位是否为1
{
subset[++subset[0]]=powof3[i];
}
}
}
35 楼
雪光风剑 [专家分：27190] 发布于 2007-03-10 07:50:00
早晨灵光一闪阿
#include <stdio.h>
#include <stdlib.h>
#define MAX ( 50 )
#define N ( 1e8 )
typedef long long INT64;
void HeroNeedThree(INT64* subset, unsigned int n);
int main(int argc, char *argv[])
{
INT64 subset[MAX] = {0};
int i;
HeroNeedThree(subset, (unsigned int)N);
printf("\n{ ");
for (i = 1; i <= subset[0]; ++i)
{
printf("%I64d, ", subset[i]);
}
printf("}\n");
system("pause");
return 0;
}
//算法分析：实质上就是把n转化为2进制形式再逐位转化成3的相应次幂
void HeroNeedThree(INT64* subset, unsigned int n)
{
int tobin[MAX]={0},pows=0,temp;
INT64 thispos=1;//tobin存放n转化成2进制后的每一位，pows记录最高次幂 ,thispos为某一位对应的数值
//把n转换成2禁制形式
while(n)
{
tobin[pows++]=n%2;
n/=2;
}
pows--;
//按位赋回3的n次幂 ,由于存在顺序问题故需要统计两次
for(int i=0;i<=pows;i++)
if(tobin[i])
subset[0]++;
temp=subset[0];
for(int i=0;i<=pows;i++)
{
if (tobin[i])
{
subset[temp--]=thispos;
}
thispos*=3;
}
}
不过没想到多少可以优化的地方
36 楼
小黑骑DK [专家分：610] 发布于 2007-03-10 12:42:00
void HeroNeedThree(INT64* subset, unsigned int n)
{
int exp = 0;
INT64 element = 1;
unsigned int combineNum = 1;
unsigned int nNext = n;
while ((n / 2) != 0)
{
exp++;
element *= 3;
combineNum *= 2;
n /= 2;
}
nNext -= combineNum;
if (nNext == 0)//in this case, we find all.
{
int index = *subset + 1;
while (index < (*subset + exp + 1))
{
element /= 3;
subset[index++] = element;
}
*subset += exp;//subset[0] is original Num,it should be added exp.
return;
}
else
{
*subset += 1;// find one .store Num in subset[0].
subset[*subset] = element;
HeroNeedThree(subset, nNext);//continue to find the next one.
}
}
//我用的机器不支持C99,long long通不过(我只好用unsigned long).所以测试的N只能到1e6. 哪位好心的帮我测试下,1e8有没有错.
ps:一般支持C99的编译器有哪些啊 ？
37 楼
nuciewth [专家分：670] 发布于 2007-03-10 14:50:00
#include<stdio.h>
long a[]={1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907};
int main()
{
int n,length;
int data[15];
while(EOF!=(scanf("%d",&n))&&n!=0)
{
length=0;
n--;
while(n>0)//根据数据关系,化成二进制
{
data[length++]=n%2;
n/=2;
}
/******************输出部分*****************/
printf("{ ");
if(length!=0)
{
printf("%ld",a[--length]);
}
while(--length>=0)
{
if(data[length]==1)
{
printf(", %ld",a[length]);
}
}
printf(" }\n");
/******************************************/
}
return 0;
}
38 楼
nuciewth [专家分：670] 发布于 2007-03-10 14:54:00
#include<stdio.h>
#include<math.h>
int main()
{
int n,length;
int data[15];
while(EOF!=(scanf("%d",&n))&&n!=0)
{
length=0;
n--;
while(n>0)//根据数据关系,化成二进制
{
data[length++]=n%2;
n/=2;
}
/******************输出部分*****************/
printf("{ ");
if(length!=0)
{
printf("%ld",(long)pow(3,--length));
}
while(--length>=0)
{
if(data[length]==1)
{
printf(", %ld",(long)pow(3,length));
}
}
printf(" }\n");
/******************************************/
}
return 0;
}
39 楼
BigCarrot [专家分：10] 发布于 2007-03-10 15:14:00
INT64 arr[MAX];
void HeroNeedThree(INT64* subset, unsigned int n)
{
INT64 num=1;
int count=0;
n--;
while (n != 0)
{
if ((n & 1) != 0)
{
arr[count] = num;
count++;
}
num = num + num + num;
n = n >> 1;
}
*subset = count;
for (int i=count-1; i>=0; i--)
{
subset++;
*subset = arr[i];
}
}
40 楼
capskov [专家分：0] 发布于 2007-03-10 17:24:00
/* 第一次参加比赛啊，我实在太菜了，不过非常非常想参加比赛，*\
请不要打击我啊~~楼主（自己测试了下似乎没有什么问题vc6.0），
拜托了。我会努力学习的！*/
/*****************************************这个是之前写的，现在作废
//#include<iostream.h>
#include<math.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX ( 50 ) //子集结果数组最大容量
#define N ( 500 ) //要测试的N
long BitL = 0 ; //目标集合
long BitMask = (1<<30); //判定工具
typedef long INT64;
void HeroNeedThree(INT64 *subset, unsigned int n)
{
for (BitL=1 ; BitL<=(n-1); BitL++) //第n行子集处理
{
for(int p=31;p>0;p--) //判定子集元素
{ //cout<<BitL<<'\t'<<temp<<'\t'<<p<<endl;
if(((BitMask>>(31-p)) & BitL) && BitL==(n-1))
{
*subset = pow(3,p-1);
subset++;
}
}
//cout<<endl;
}
} ***********************************/
用这个刚修改的。应该没什么问题吧
//#include<iostream.h>
#include<math.h>
//#include <stdio.h>
//#include <stdlib.h>
//#define MAX ( 50 ) //子集结果数组最大容量
//#define N ( 500 ) //要测试的N
long BitL = 0 ; //目标集合
long BitMask = (1<<30); //判定工具
//typedef long INT64;
void HeroNeedThree(INT64 *subset, unsigned int n)
{
for (BitL=1 ; BitL<=(n-1); BitL++) //第n行子集处理
{
for(int p=31;p>0;p--) //判定子集元素
{ //cout<<BitL<<'\t'<<temp<<'\t'<<p<<endl;
if(((BitMask>>(31-p)) & BitL) && BitL==(n-1))
{
*subset = pow(3,p-1);
subset++;
}
}
//cout<<endl;
}
}
//[em1][em2]
我来回复
您所在位置：