第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个回复）

21 楼

rickone [专家分：15390] 发布于 2007-03-08 16:21:00

#include "stdafx.h"
#include "iostream"
typedef __int64 INT64;
void HeroNeedThree(INT64* subset, unsigned int n)
{
    // base3[k]=3^k
    static INT64 base3[32]=
    {
        0x1,0x3,0x9,0x1b,0x51,0xf3,0x2d9,0x88b,
        0x19a1,0x4ce3,0xe6a9,0x2b3fb,0x81bf1,0x1853d3,0x48fb79,0xdaf26b,
        0x290d741,0x7b285c3,0x17179149,0x4546b3db,0xcfd41b91,0x26f7c52b3,0x74e74f819,0x15eb5ee84b,
        0x41c21cb8e1,0xc546562aa3,0x24fd3027fe9,0x6ef79077fbb,0x14ce6b167f31,0x3e6b41437d93,0xbb41c3ca78b9,0x231c54b5f6a2b
    };
    // base2[k]=2^k
    static unsigned int base2[32]=
    {
        0x1,0x2,0x4,0x8,0x10,0x20,0x40,0x80,
        0x100,0x200,0x400,0x800,0x1000,0x2000,0x4000,0x8000,
        0x10000,0x20000,0x40000,0x80000,0x100000,0x200000,0x400000,0x800000,
        0x1000000,0x2000000,0x4000000,0x8000000,0x10000000,0x20000000,0x40000000,0x80000000
    };
    INT64 num=0;
    n--;
    for(int i=31;i>=0;--i)
    {
        if(n & base2[i]) // 计算n的第i位上是否是1
        {
            subset[++num]=base3[i];
        }
    }
    subset[0]=num;
}

int main(int argc, char* argv[])
{

    unsigned int n;
    INT64 subset[40];
    std::cin>>n;
    HeroNeedThree(subset,n);
    printf("%I64d\n",subset[0]);
    for(INT64 i=0;i<subset[0];++i)
        printf("%I64d,",subset[i+1]);
    return 0;
}

22 楼

medie2005 [专家分：30] 发布于 2007-03-08 18:20:00

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

void    HeroNeedThree(_int64* subset, unsigned int n);

#define     MAX     ( 50  )

int main( int argc, char *argv[ ] )
{
        _int64 subset[ MAX ] = {0};
        int i;
        unsigned   int  N;
        scanf("%ud",&N);

        HeroNeedThree(subset, N);

        printf("\n{ ");
        for (i = 1; i <=subset[ 0 ]; ++i)
        {
                if( i==subset[ 0 ] )
            printf("%I64d ", subset[ i ]);
        else
            printf("%I64d, ", subset[ i ]);
        }
        printf("}\n");

        system("pause");
        return 0;
}

void    HeroNeedThree( _int64* subset, unsigned int n )
{

    int      len=32;
    int      i=len, j=1, temp;
    int      count=0;
    _int64   s;
    --n;

    while( i )
    {
        temp=i;
        if( n & (1<<(temp-1)) )
        {
            ++count;
            s=1;
            while( --temp )
                s*=3;
            subset[ j ]=s;
            ++j;
        }
        --i;
    }
    subset[ 0 ]=count;
}

23 楼

bloodybg [专家分：1510] 发布于 2007-03-08 18:53:00

//上一次的一个变量定义错了，以该处为准
int nCount = 0;
void HeroNeedThree(INT64* subset, unsigned int n)
{
    int i;
    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);
    }

}

24 楼

Kummerwu [专家分：0] 发布于 2007-03-08 20:06:00

void HeroNeedThree(INT64* subset, unsigned int n)
{
    static INT64 s_HelperCount[] =
    {
        1,              3,              9,              27,
        81,             243,            729,            2187,
        6561,           19683,          59049,          177147,
        531441,         1594323,        4782969,        14348907,
        43046721,       129140163,      387420489,      1162261467,
        3486784401,     10460353203,    31381059609,    94143178827,
        282429536481,   847288609443,   2541865828329,  7625597484987,
        22876792454961, 68630377364883, 205891132094649,617673396283947,
    };

    int idx = 32;
    int cnt = 0;

    n--;
    while(idx>0)
    {
        idx--;
        if(((n)&(1<<(idx))))
        {
            cnt++;
            subset[cnt] = s_HelperCount[idx];
        }


    }
    subset[0] = cnt;
}

25 楼

sunseed [专家分：20] 发布于 2007-03-08 20:24:00

看错题

26 楼

xchbcahz [专家分：50] 发布于 2007-03-08 20:29:00

/*
子集：{}(空集), { 1 }, { 3 }, { 1, 3 }, { 9 }, { 1, 9 }, { 3, 9 },
序号N：0          1      2        3       4        5         6
{ 1, 3, 9 }, {27}, {1,27}, {3,27}, {1,3,27}, {9,27}, {1,9,27},
      7         8      9      10       11      12        13
{3,9,27}, (1,3,9,27},{81}...
    14         15      16
观察上述数列发现：如果N=（2^a + 2^(a-1) + 2^(a-2) +...+ 2^0）（注：此处用2^a表示“2的a次方”，以下类同）,则第N个子集里的元素分别为{3^a,3^(a-1),3^(a-2),...,3^0 }。
比如求第15个子集，将15换算成2^3+2^2+2^1+2^0,根据上述规则将“2的次方”变成“3的次方”，可以得出第15个子集{3^3，3^2，3^1，3^0}，即{27，9，3，1}。
同理再求第12个子集，12=2^3+2^2,则子集为{3^3,3^2},即{27，9}。

如何将一个整数换算成“N = 2^a+2*(a-1)+2^(a-2)+...+2^0”？由“N - 2^a = 2*(a-1)+2^(a-2)+...+2^0”我们可以想到通过先求一个整数能被2整除几次，如果余数为1，再求剩下的数能被2整除几次，如此循环就能算出最终式子。
比如13，13可以被2整除3次，记下（2^3），再拿13-2^3,等于5，再计算5能被2整除几次，应该是2次，又得到（2^2）,再拿5-2^2,等于1，不能被2整除，则记为2^0,由此得到最终算式: 13=2^3+2^2+2^0。
再如12，12能被2整除3，余数为1，则再拿（12-2^3)=4来算，4能被2整除2次，余数为0，则最终结果为：12=2^3+2^2；
将上述算式中各项的底数由2换成3，就可以求出相应的子集元素，如上述的结果分别是{27，9，1}、{27，9}。
*/

#include <iostream.h>

unsigned int Divide(unsigned int n)  //此函数计算n能被2整除几次。
{
    unsigned int i=0,j=n;
    while((j=j/2)!=0)
        i++;
    return i;
}

int CiFang(int a,unsigned int b)  //此函数求a的b次方。
{
    if(b==0) return 1;
    unsigned int i;
    unsigned int result=1;
    for(i=0;i<b;i++)
        result=result*a;
    return result;
}

void HeroNeedThree(int subset[], unsigned int n)
{
    if(n<1)
    {
        cout<<"n<1,error!"<<endl;
        return;
    }
    subset[0]=0; //元素个数初始化为0；
    if(n==1)
    {
        subset[0]=1; //只有一个元素:空集。
        subset[1]=-1;//第1个子集总是空集，此处等于-1表示元素为空集！
        return;
    }
    n--;//此处将子集换算为从第0个开始排序,即原来要找的第n个子集在算法里是第n-1个.
    unsigned int dividend=n; //变量dividend为需要被2整除的被除数,初始化为n.
    unsigned int count=0; //记录被2整除的次数;
    int i=1; //既用作subset数组下标,也记录子集里的元素个数;初始化为1表示从subset[1]开始放置元素;

    while(dividend>0)  //如果被除数小于等于0则计算结束。
    {
        count=Divide(dividend);  //计算被2整除次数.
        subset[i]=CiFang(3,count); //计算3的count次方,并保存到结果数组中.
        dividend=dividend-CiFang(2,count); //计算下一次的被除数。
        i++; //下一个结果存到下一个数组元素中。
    }
    subset[0]=i-1; //保存最终元素个数。

    return;
}

27 楼

believefym [专家分：1550] 发布于 2007-03-08 21:30:00

/*思路：考虑3的幂次
1: 00 {}
2: 01 {3^0}
3: 10 {3^1}
4: 11 {3^1,3^0}
...

最后就变为unsigned int n－1以二进制表示，每位为1即该集合存在3的x幂次，为0即没有该3的幂次的元素

ps:如果把题目的底数3变成2，就直接变成了简单的二进制
*/

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

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

void HeroNeedThree(INT64* subset, unsigned int n)
{
    if(n==1)
    {
        subset[0] = 0;
        return;
    }

    n=n-1;
    int c=0;//统计个数
    int i=0;
    while((1<<++i) < n);
    while(i>0)
    {
        if(((1<<i)&n)==(1<<i))
            subset[++c]=(int)pow(3,i);
        --i;
    }

    if(n&1==1)
        subset[++c]=1;

    subset[0] = c;
}

int main(int argc, char *argv[])
{
        INT64 subset[MAX] = {0};
        int i;

        HeroNeedThree(subset, 500);

        printf("\n{ ");
        for (i = 1; i <= subset[0]; ++i)
        {
                printf("%I64d, ", subset[i]);
        }
        printf("}\n");

        system("pause");
        return 0;
}

28 楼

redlives [专家分：6090] 发布于 2007-03-08 21:37:00

郁闷，方法不难，但是手上只有devC++,这个用起来一点不顺手哦，害我弄了老半天。
好像没有unsigned的数据格式，不管了，发一个先。

#include <iostream>
using namespace std;

void HeroNeedThree(__int64* subset, unsigned int n)
{
     __int64 num = 0,i,j,k;
     __int64 a[30] = {0};
     __int64 b[30] = {0};
     for(i = 1,k = 0;i*2 < n;k ++)
            i *= 2;

     num = n - i - 1;
     for(j = 0;num > 0;j ++)
     {
             b[j] = num%2;
             num /= 2;
     }

     a[0] = 1;
     for(i = 1;i < 30;i ++)
           a[i] = 3*a[i-1];
     for(i = 0;i < k;i ++)
            a[i] *= b[i];
     for(i = 0,j = 1;i <= k;i ++)
     {
          if(a[i] != 0)
          {
                 *(subset+j) = a[i];
                 j ++;
          }
     }

     *subset = j - 1;
}

int main()
{
    __int64 * p = new __int64[50];
    int n;
    memset(p,0,50);

    scanf("%d",&n);
    HeroNeedThree(p,n);
    printf("元素个数为: %I64d\n",p[0]);
    printf("{ ");
    for(int i = 1;p[i] != 0;i ++)
            printf("%I64d ",p[i]);
    printf("}\n");
    system("pause");
    return 0;
}

29 楼

wuchengwei [专家分：1650] 发布于 2007-03-09 11:22:00

//VC6.0不支持64位整数类型，GCC可以，
//2^31 < 3^HIGH <2^63,所以VC下会溢出，GCC不会
#define HIGH  (8*sizeof(unsigned int)-1)
void HeroNeedThree(INT64* subset, unsigned int n)
{
    int i,pos=HIGH;

    for(--n, i=0; n; pos--)
    {
        if(n&(1<<pos))
        {
            subset[++i]=(INT64)pow(3,pos);//若需要多次测试，可先建立一张3的0--HIGH次幂表，我用的VC6.0，建不了表
            n-=1<<pos;
        }
    }
    subset[0]=i;
}

30 楼

cuiweican [专家分：160] 发布于 2007-03-09 16:27:00

//我的代码,最近在学C++,就写了这样的一个类,
#include <iostream>
using namespace std;

typedef long long T;

class CSet
{
private:
    T index[63];
    T data[39];
    int op;
public:
    CSet();
    bool binarry_search(int, int, int);
    void HeroNeedThree(T *, int &, int n);
};

CSet::CSet()
{
    int i = 0;

    index[1] = 1;
    for (i=2; i<=39; ++i)
    {
        index[i] = index[i-1] * 2;
    }

    data[1] = 1;
    for (i=2; i<=39; ++i)
    {
        data[i] = data[i-1] * 3;
    }
}

bool CSet::binarry_search(int l, int r, int n)
{
    int mid = 0;

    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (index[mid] < n)
        {
            l = mid + 1;
        }
        else if (index[mid] > n)
        {
            r = mid - 1;
        }
        else
        {
            op = mid;
            return true;
        }
    }

    op = l;
    return false;
}

void CSet::HeroNeedThree(T *result, int &top, int n)
{
    int l = 1;
    int r = 39;

    n -= 1;
    while (n > 0)
    {
        if (binarry_search(l, r, n))
        {
            n -= index[op];
            result[top++] = data[op];
        }
        else
        {
            n -= index[op-1];
            result[top++] = data[op-1];
        }
    }

}

int main()
{
    CSet set;
    int n;
    T result[51];
    int top = 0;
    int i = 0;

    while (cin >> n)
    {
        top = 0;
        set.HeroNeedThree(result, top, n);

        cout << "{";
        for (i=0; i<top; ++i)
        {
            cout << result[i];
            if (i != top - 1)
            {
                cout << ", ";
            }
        }
        cout << "}" << endl;
    }

    return 0;
}

我来回复

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

主题：第50次编程比赛

回复列表（共47个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：第50次编程比赛

回复列表 （共47个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共47个回复）