主题：第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个回复）
沙发
bpttc [专家分：8790] 发布于 2007-03-07 19:11:00
test
板凳
neverPE [专家分：1620] 发布于 2007-03-07 19:44:00
最近实习， 没空做题了。 还是顶一下帖子， 精神上支持一下。
n的值 n-1对应的2进制 对应的集合
1 00000 { , , , , }
2 00001 { , , , , 1}
4 00011 { , , , 3, 1}
11 01010 { ,27, , 3, }
16 11111 {81 27, 9, 3, 1}
呵呵， 规律容易看出来，只要把n转换成二进制， 再计算3的幂就可以。 证明过程略。
n < 2 ^ 32 - 1， 集合内最大的数是3^32， 不超过64bit，放心大胆的算就可以了。
3 楼
雨中飞燕 [专家分：18980] 发布于 2007-03-07 20:33:00
void HeroNeedThree(INT64* subset, unsigned int n)
{
INT64 num[MAX],*p=num,n1=1;
for(n--;n>0;n>>=1,n1+=n1<<1)if(n&1)*p++=n1;
for(*subset=p-num;p!=num;)*++subset=*--p;
}
4 楼
SonicLing [专家分：6260] 发布于 2007-03-07 20:39:00
unsigned bit_count(unsigned int n, unsigned &c)
{
c = 0;
for(int i=0; i<sizeof(unsigned)*8; i++)
{
c += (n >> i) & 0x00000001;
if(n < (1<<i)) return i;
}
return sizeof(unsigned)*8;
}
void HeroNeedThree(INT64* subset, unsigned int n)
{
unsigned c, t = bit_count(--n, c), s = 1;
subset[0] = c;
for(int i=0; i<t; i++)
{
if((n&(1<<i))!=0) subset[c--] = s;
#define nexttriexp(prev) ((prev)<<1)+(prev) // next = prev*3
s = nexttriexp(s);
}
}
5 楼
xunlei842 [专家分：0] 发布于 2007-03-07 20:48:00
[em13]想看一下隐藏的贴.
6 楼
ITER [专家分：680] 发布于 2007-03-07 21:59:00
/*题目不错 呼呼 就是我一直没写代码 脑子不清晰 代码编得有点乱：）
再加上要准备一个月后的2+2 所以没多少时间 匆匆写了个 也没来得及注释
主要算法是递归 用到了些类似解决背包问题的方法 。。。
还有就是我电脑上的VC6貌似没有INT64 所以还是改成int了*/
#include <iostream>
using namespace std;
int method(int result[],int *xiabiao,int count[],int data[],int n)
{
int i=0;
int j=0;
while(count[i]<n)
{
i++;
j++;
}
if(n!=count[i])
{ //如果不能正好减完则返回到前一地址
j--;
}
n-=count[j];
result[*xiabiao] = data[i];
*xiabiao+=1;
if(0==n)
{
return count[j];//函数返回当前被减的集合个数
}
return method(result,xiabiao,count,data,n);
}
int way(int x)
{ // 返回x个数是的集合总数 2^x
int i=0;
int sum=1;
while(i++<x)
{
sum*=2;
}
return sum;
}
void HeroNeedThree(int *subset,int n)
{
int i=1;
int l1=1;
int sum(0);
int data[100]={0}; //存放3的各个幂值
int count[100]={0}; //存放相应集合总个数
int *x = new int;
*x = 1;
if(1==n)
{//如果n为1则直接返回结果（空集）
subset[0] = 0;
subset[1] = '\0';
return;
}
data[0]=0;
count[0]=1;
while(sum+1<=n)
{
sum = way(l1);
count[l1] = sum;
data[l1] = i;
i*=3;
l1++;
}
int bb=method(subset,x,count,data,n);
if(bb!=2)
{//收尾处理
if(1==bb)
{
subset[*x-1] = '\0';
*x-=1;
}
else
{
for(int aa=1;bb!=count[aa+1];aa++);
for(;aa>=1;aa--)
{
subset[*x] = data[aa];
*x+=1;
}
subset[*x] = '\0';
}
}
subset[0] = *x-1;//一共保存的个数赋给subset首地址
}
main()
{
int subset[10] = {0};
HeroNeedThree(subset,500);
for(int i=0;i<7;i++)
{
cout<<subset[i]<<" ";
}
}
7 楼
bloodybg [专家分：1510] 发布于 2007-03-07 23:58:00
void HeroNeedThree(INT64* subset, unsigned int n)
{
int i, nCount = 0;
n --;
if (0 == n)
return;
for (i = 0; i < 4096; i ++)
{
if (pow(2, i) > n)
break;
}
if (4096 <= i && i < 0)
return;
if (i > 0)
{
subset[nCount] = (INT64)pow(3, i-1);
nCount ++;
HeroNeedThree(subset, n - (unsigned int)pow(2, i - 1) + 1);
}
}
8 楼
renew [专家分：200] 发布于 2007-03-08 00:58:00
第一回参加不知道你们对输入输出是怎样规定的=,=
按自己的方式写了一个
#include <stdio.h>
//Viusal C++ 6.0
#define BIGINT __int64
#define FORMAT "%I64d"
/*
mingw use this macro
#define BIGINT long long
#define FORMAT "%I64d"
linux use this macro
#define BIGINT long long
#define FORMAT "%lld"
*/
BIGINT ThreePower[32];
void HeroNeedThree(BIGINT* subset, BIGINT n)
{
int t, p;
BIGINT m;
m = n-1;
for (t = 0; m; m&=m-1) t++;
p = 0; m = n-1; subset[0] = t;
while (t)
{
if (m & 1) subset[t--] = ThreePower[p];
p++;
m >>= 1;
}
}
int main()
{
int i;
BIGINT n, subset[33];
ThreePower[0] = 1;
for (i = 1; i < 32; i++) ThreePower[i] = ThreePower[i-1]*3;
while (EOF != scanf(FORMAT, &n))
{
HeroNeedThree(subset, n);
printf("{ ");
for (i = 1; i < subset[0]; i++) printf(FORMAT", ", subset[i]);
if (subset[0]) printf(FORMAT" ", subset[subset[0]]);
puts("}");
}
return 0;
}
9 楼
香脆饼干 [专家分：2040] 发布于 2007-03-08 04:22:00
//It take a couple of seconds to display
#include <stdio.h>
#include <stdlib.h>
#define MAX ( 50 ) //×Ó¼¯½á¹ûÊý×é×î´óÈÝÁ¿
//Because the speed is too slow, therefore reduce to 1e4
#define N ( 1e4 ) //Òª²âÊÔµÄN ***
#ifndef NULL
#define NULL 0
#endif
typedef long INT64; //My Version of VC doesn't support typedef long long something,
//Therefore I just use long.
struct single
{
INT64* subset;
struct single *pNext;
};
typedef struct single SINGLE;
//Global
SINGLE* pHead;
//Declare function prototype
void InitSubSet();
void ExpandSubSet(subset,n,StartNumber);
void AppendSingle(SINGLE *pHead,SINGLE* pAppendSingle);
void AppendSingleToHeadNew(SINGLE** ppHeadNew,SINGLE* pAppendSingle);
SINGLE* FindSingle(SINGLE *pHead,unsigned int n);
void FreeSingle(SINGLE* pHead);
void HeroNeedThree(INT64* subset, unsigned int n);
void InitSubSet()
{
pHead=(SINGLE*)malloc(sizeof(SINGLE));
pHead->subset=(INT64*)malloc(sizeof(INT64));
pHead->subset[0]=0;
pHead->pNext=NULL;
}
void ExpandSubSet(INT64 *subset,unsigned int n,INT64 StartNumber)
{
static unsigned int nCount=1;
SINGLE *pNext,*pHeadNew;
pHeadNew=NULL;
if(nCount>=n)
{
SINGLE *pLastSingle;
int i;
pLastSingle=FindSingle(pHead,n);
for(i=0;i<=pLastSingle->subset[0];i++)
subset[i]=pLastSingle->subset[i];
FreeSingle(pHead);
return;
}
//snapshot
pNext=pHead;
while(pNext!=NULL)
{
int i,nFactor;
INT64 *pI64;
SINGLE *pSingle;
nFactor=pNext->subset[0];
pI64=(INT64*)malloc(sizeof(INT64)*(nFactor+1+1));
pSingle=(SINGLE*)malloc(sizeof(SINGLE));
for(i=0;i<=nFactor;i++) //Copy old Data and add current one
{
pI64[i]=pNext->subset[i];
}
(*pI64)++;
*(pI64+*pI64)=StartNumber;
pSingle->subset=pI64;
pSingle->pNext=NULL;
AppendSingleToHeadNew(&pHeadNew,pSingle);
nCount++; // We append one item to the table
pNext=pNext->pNext;
} //End of While
AppendSingle(pHead,pHeadNew);
ExpandSubSet(subset,n,StartNumber*3);
}
void AppendSingle(SINGLE *pHead,SINGLE* pAppendSingle)
{
SINGLE* pNext;
if(pHead==NULL)
{
pHead=pAppendSingle;
return;
}
pNext=pHead;
while(pNext->pNext!=NULL)
pNext=pNext->pNext;
pNext->pNext=pAppendSingle;
}
void AppendSingleToHeadNew(SINGLE** ppHeadNew,SINGLE* pAppendSingle)
{
SINGLE *pNext;
if(*ppHeadNew==NULL)
{
*ppHeadNew=pAppendSingle;
return;
}
else
{
pNext=*ppHeadNew;
while(pNext->pNext!=NULL)
{
pNext=pNext->pNext;
}
pNext->pNext=pAppendSingle;
}
}
SINGLE* FindSingle(SINGLE *pHead,unsigned int n)
{
SINGLE *pNext;
unsigned int i;
pNext=pHead;
for(i=1;i<n;i++)
{
pNext=pNext->pNext;
}
return pNext;
}
void FreeSingle(SINGLE* pHead)
{
SINGLE *pNext;
SINGLE *pSave;
pNext=pHead;
while(pNext->pNext!=NULL)
{
pSave=pNext->pNext;
free(pNext);
pNext=pSave;
}
free(pNext);
pHead=NULL;
}
void HeroNeedThree(INT64* subset, unsigned int n)
{
InitSubSet();
if(n==1)
{
*subset=0;
return;
}
ExpandSubSet(subset,n,1); //
}
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("%d, ", subset[i]);// I change &I64 to %d as well.
}
printf("}\n");
system("pause");
return 0;
}
10 楼
lt1234 [专家分：470] 发布于 2007-03-08 10:13:00
void HeroNeedThree(INT64* subset, unsigned int n)
{
int c=0,m,i=1;
int flag=0;
while(1)
{
m=n;
c=log2(n);
n=1<<c;
n=m-n;
switch(n)
{
case 0 :
{
while(c)
{
subset[i++]=(long)pow(3,(c-1));
c--;
}
flag=1;
break;
}
case 1:
{
subset[i++]=(long)pow(3,c);
flag=1;
break;
}
default : subset[i++]=(long)pow(3,c);
}
if(flag)
break;
}
subset[0]=i-1;
}
我来回复
您所在位置：