第50次编程比赛 — 编程爱好者社区

主题：第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

本帖地址： http://bbs.pfan.cn/post/220004.html

回复列表（共47个回复）

11 楼

poorb [专家分：180] 发布于 2007-03-08 12:20:00

//思路是这样，但类型搞的头晕，第一次参加，自己先给点鼓励，嘿嘿。
INT64 a[31] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,9192,
               16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,
               8388608,16777216,33554432,67108864,134217728,268435456,536870912,};

INT64 mpow(int pow)
{
    int i;
    INT64 radix = 3;
    if(pow == 0)
    return 1;
    for(i = 1; i < pow; i++)
    {
        radix = radix * 3;
    }
    return radix;
}
void HeroNeedThree(INT64* subset,unsigned int n)
{
    int i,j;
    int step;
    INT64 nnum = n-1;
    for(i = 0; i <= 30; i++)
    {
       if(a[i] > nnum)
            break;
    }
    for(j = i-1,step = 1; j >= 0; j--)
    {
        if(a[j] <= nnum)
        {
            subset[step++] = mpow(j);
            nnum = nnum - a[j];
        }
        if(nnum == 0)
        break;
    }
    subset[0] = step-1;
}

12 楼

poorb [专家分：180] 发布于 2007-03-08 12:22:00

#include <stdio.h>
#include <stdlib.h>

#define MAX     ( 50  )        //子集结果数组最大容量
#define N       ( 1e8 )       //要测试的N
typedef long long INT64;

INT64 a[31] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,9192,
               16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,
               8388608,16777216,33554432,67108864,134217728,268435456,536870912,};

INT64 mpow(int pow)
{
    int i;
    INT64 radix = 3;
    if(pow == 0)
    return 1;
    for(i = 1; i < pow; i++)
    {
        radix = radix * 3;
    }
    return radix;
}
void HeroNeedThree(INT64* subset,unsigned int n)
{
    int i,j;
    int step;
    INT64 nnum = n-1;
    for(i = 0; i <= 30; i++)
    {
       if(a[i] > nnum)
            break;
    }
    for(j = i-1,step = 1; j >= 0; j--)
    {
        if(a[j] <= nnum)
        {
            subset[step++] = mpow(j);
            nnum = nnum - a[j];
        }
        if(nnum == 0)
        break;
    }
    subset[0] = step-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("%I64d, ", subset[i]);
        }
        printf("}\n");

        system("pause");
        return 0;
}
上面发那个好像有错，如果有用这个，这个是全的。。

13 楼

BlackBlizzard [专家分：50] 发布于 2007-03-08 12:25:00

#include <stdio.h>
#include <stdlib.h>
#define MAX 100                  //子集结果数组最大容量
typedef __int64 INT64;
void HeroNeedThree(int *subset, unsigned int n)
{
unsigned int i=0,temp,k;
int s=1;
if(n)
{
while(n)
{      temp=n%2;
        subset[i]=temp;
        n=n/2;
        i++;
}
  printf("对应的子集为：\n");
for(k=0;k<i;k++)

{    if(subset[k])
     printf("%d ",s);
      s*=3;
}
}
else
printf("对应空集合");
}

void main()
{
    int subset[MAX];
    unsigned int n;
    printf("请输入 n:\n");
    scanf("%u",&n);
    HeroNeedThree(subset,n-1);

}

14 楼

ccpp [专家分：9360] 发布于 2007-03-08 12:47:00

/*
设置子集中元素的位置号，有则是1，否则为0
其序号减1恰等于得到的二进制数，如：
{       } = 0 0 0 = 0
{      1} = 0 0 1 = 1
{   3   } = 0 1 0 = 2
{   3  1} = 0 1 1 = 3
{9      } = 1 0 0 = 4
{9     1} = 1 0 1 = 5
{9  3   } = 1 1 0 = 6
{9, 3, 1} = 1 1 1 = 7
所以序号减1后转换成二进制后，即可求出子集元素
*/
void HeroNeedThree(INT64* subset, unsigned int n)
{
    int i,j,r,t;
    i = r = 1;
    n--;                         //序号减1
    while(1)                     //序号转换成二进制
    {
        if(n%2 == 1){
            subset[i++] = r;
        }
        n /= 2;
        r *= 3;
        if(n == 1){              //商为1时，结束循环
            subset[i] = r;
            break;
        }
    }
    subset[0] = i;
    for(j = 1; j < i; i--,j++)//反转数组
    {
        t = subset[j];
        subset[j] = subset[i];
        subset[i] = t;
    }
}

15 楼

euc [专家分：4310] 发布于 2007-03-08 14:29:00

typedef long long unsigned INT64;

void HeroNeedThree (INT64* subset, unsigned int n)
{
    static INT64 three[41];
    static bool ini = false;

    if (ini == false) {
        INT64 a = 1;
        for (int i = 0; i < 41; ++i, a*=3) {
            three[i] = a;
        }
        ini == true;
    }

    int bitn = 31;
    unsigned int mask = (1 << 31);

    for (; bitn >= 0 && ((mask&n)==0); --bitn, mask >>= 1);

    int amount = 0;
    for (int i = 1; bitn >= 0; mask>>=1, --bitn) {
        if (n > mask) {
            subset[i] = three[bitn];
            amount++;
            n -= mask;
            i++;
        }
    }
    subset[0] = amount;
}
方法:这跟二进制有点关系.

16 楼

ghbxx2004 [专家分：610] 发布于 2007-03-08 15:05:00

/*在DEV-CPP下的C编译器测试通过,不过楼主这个题目有一个地方出的不好,因为不同的编译器对INT型占用的空间是有不同的处理的,有的是4个字节,有的是2个字节,如果是4个字节的话INT64是不够的,会产生溢出错误*/
#include "stdio.h"
typedef long long INT64;
INT64 subset[10000000];
unsigned int n;
void HeroNeedThree(INT64 *subset, unsigned int n)
{
     INT64 i=0;
     INT64 j=1;
     INT64 temp=1;
     n--;
     while(n>0)
     {
         if(n&1){subset[++i]=temp;}
         temp*=3;
         n>>=1;
     }
     subset[0]=i;
     for(;j<i;j++,i--){temp=subset[j];subset[j]=subset[i];subset[i]=temp;}
}
int main()
{
    INT64 i=1;
    scanf("%d",&n);
    HeroNeedThree(subset,n);
    printf("{ ");
    for(i=1;i<=subset[0];i++){printf("%lld,",subset[i]);}
    printf("}");
    return 0;
}

17 楼

baihecao [专家分：160] 发布于 2007-03-08 15:06:00

新年好

18 楼

iAkiak [专家分：8460] 发布于 2007-03-08 15:30:00

void HeroNeedThree(INT64* subset, unsigned int n)
{
    INT64 pow[32] =
    {
        1, 3, 9, 27, 81,
    };
    bool inited = false;
    if (!inited)
    {
        inited = true;
        for (int count = 5; count < 32; count++)
            pow[count] = pow[count-1] * 3;
    }
    int count, i;
    n--;
    for(count = 0, i = 31; n; i--)
    {
        if (n & (1<<i))
        {
            subset[++count] = pow[i];
            n ^= 1<<i;
        }
    }
    subset[0] = count;
}

要从大到小的...搞反了,失态失态- -...

19 楼

eastcowboy [专家分：25370] 发布于 2007-03-08 15:39:00

void HeroNeedThree(INT64* subset, unsigned int n)
{
    // 处理n==0的情况
    // 可在这里加入各种错误处理
    if( n == 0 )
    {
        return;
    }

    // 将subset解释为更容易理解的类型：
    // 第一个元素为数量，后面若干元素为实际内容
    INT64& count = subset[0];
    INT64* content = &(subset[1]);

    // 程序主体
    // 思路：将n减1后，观察其二进制的各位，从低到高分别对应了1, 3, 9, 27, ...
    //        先从最低位开始测，完成后再将整个数列反转
    count = 0;
    --n;
    INT64 i = 1;
    while( n != 0 )
    {
        if( n & 0x0001 )
        {
            content[count++] = i;
        }
        n >>= 1;
        i *= 3;
    }
    INT64 mid = count / 2;
    for(i=0; i<mid; ++i)
    {
        INT64 tmp = content[i];
        content[i] = content[count-i-1];
        content[count-i-1] = tmp;
    }
}

20 楼

iAkiak [专家分：8460] 发布于 2007-03-08 15:44:00

第一个版本固定32次循环，这个版本减少为平均16个循环。不过每个循环内的计算量增加了。自己用随机数测试，这个方法只比前一个略微快一点而已。有种吃力不讨好的感觉...
void HeroNeedThree(INT64* subset, unsigned int n)
{
    INT64 pow[33] =
    {
        1, 3, 9, 27, 81,
    };
    bool inited = false;
    if (!inited)
    {
        inited = true;
        for (int count = 5; count < 33; count++)
            pow[count] = pow[count-1] * 3;
    }
    int count;
    unsigned int t = n - 1; // 又忘了反过来...好像这么以来更加有种吃力不讨好的感觉了...
    for(count = 0; t; t &= t - 1)
        count++;
    subset[0] = count;
    for(n--; n; n &= n - 1)
    {
        float t = INT64(n ^ n - 1) + 1; // 本来应该取n^n-1就可以了，不过float的精度不足以保存32个1，所以再多加1。求得的指数比目标数的指数大1。
        int exp = ((*(unsigned int *)&t) >> 23) - 128; // 然后在这里取出指数后多减去1（另注：按float的移码算，指数应该减127）
        subset[count--] = pow[exp];
    }
}

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：第50次编程比赛

回复列表（共47个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：第50次编程比赛

回复列表 （共47个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共47个回复）