第37次编程比赛第1题题目（延长到周一晚8:00)

主题：第37次编程比赛第1题题目（延长到周一晚8:00)

neverPE [专家分：1620] 发布于 2006-08-13 14:32:00

    不知道这次的题目是不是难了一点，参加的人很少。[color=FF0000][size=4]结贴时间延长到周一晚8:00[/color]。[/size]其实看懂了题挺好动手的，只是到最好并不容易。

猴子舞
    某马戏团决定增加一项新的表演项目---猴子舞。猴子舞是由N只猴子同时进行的。开始时，地上有N个圈，每个圆圈上站了一只猴子。地上还有N个箭头，[color=FF0000]每个圆圈恰好是一个箭头的起点和另一个箭头的终点，并且没有一个圆圈同时是某个箭头的起点和终点[/color]。表演开始时，所有的猴子同时按它所站的圆圈的箭头的方向跳向另一个圆圈中，这作为一步。当所有的猴子都回到自己原来所占的圆圈时，表演便结束了。马戏团的导演希望表演的步数尽可能的多，这可以通过聪明地安排箭头的画法来达到。现在给出N，请编写程序求出达到的最大步数的末4位。

说明：
1 [color=FF0000]1<N<=200[/color]，每个N的时限是1000ms。但如果大家程序都很快，我会增加N的值，但保证最大的步数一定不会大于2^64-1。内存占用没有严格限制，我AthlongXP2000+,768M，所以不超过500M的内存占用是没有问题的，而如果真的占用500M，估计不可能在1000ms内出解了。

2 当n比较大，最大步数会超过long的范围，因为编译器的原因，不好统一使用long long或者int64，而高精度会大大影响效率，所以只输出后4位。这一改变不会对计算过程产生影响，各位只要在求出最大步数后简单的%10000就可以了。

3 题意不是那么容易理解，请仔细考虑每一个细节。我不太喜欢太直接的题，我们必须在题目给的情境里自己寻找合适的算法。如果有太多人不能理解题意，我会在“关于关于第37次编程比赛第1题”帖子里做简单解释。

函数原型：
// n － n只猴子
// maxStep - 存放最大步数的末4位。
void MonkeyDance(const int n, int* maxStep);

例：
n=5    maxStep=6
n=8    maxStep=15

有人反应看不懂，加个例子：
n=5
5只猴子所在的圈编号依次1，2，3，4，5
一种可能的情况是：1->2(1号圈指向2号) 2->3 3->1   4->5,5->4
表演开始后，
1号猴子的位置：1,2,3,1,2,3,1*,2……
2号猴子：2,3,1,2,3,1,2*,……
3号：3,1,2,3,1,2,3*……
4号：4,5,4,5,4,5,4*,5,……
5号：5,4,5,4,5,4,5*……

在走了6步以后，每只猴子都回到自己的位置。

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

回复列表（共22个回复）

21 楼

jackin0627 [专家分：1270] 发布于 2006-08-14 17:38:00

//总体思路是找出尽量多的互异素数使其相加的结果接近n，
//这几个素数的乘积即为最大步数
#include <math.h>
#include <malloc.h>

int PriNum(int n,int * p)    //求出<=n的所有素数，放入p中，返回求出的素数的个数
{
    char *flag;
    int i,j,m;

    flag=(char*)malloc(n+1);
    for(i=2;i<=n;i++)
    {
        flag[i]=1;
    }
    m=(int)sqrt(n);
    for(i=2;i<=m;i++)
    {
        if(!flag[i])continue;
        for(j=2*i;j<=n;j+=i)
        {
            flag[j]=0;
        }
    }
    for(i=2,j=0;i<=n;i++)
    {
        if(flag[i])
        {
            p[j]=i;
            j++;
        }
    }
    free(flag);
    return j;
}

// n － n只猴子
// maxStep - 存放最大步数的末4位。
void MonkeyDance(const int n, int* maxStep)
{
    int *pri;    //存放素数
    int mPri;    //存放素数个数
    int max,x1,x0,t;
    int sum=0;
    int i;

    if(n<2)
    {
        *maxStep=1;
        return;
    }
    pri=(int*)malloc(n*sizeof(int));
    mPri=PriNum(n,pri);

    for(max=0;max<mPri;max++)
    {
        sum+=pri[max];
        if(sum>=n)
        {
            if(sum>n)
            {
                sum-=pri[max];
                max--;
            }

            x1=max+1;
            break;
        }
    }
    if(sum==n)
    {
        x0=max+1;
    }
    else
    {
        t=n-sum;
        for(;x1<mPri;x1++)
        {
            if(pri[x1]-pri[max]>=t)
            {
                if(pri[x1]-pri[max]>t)
                {
                    x1--;
                }
                break;
            }
        }
        for(x0=max;x0>=0;x0--)
        {
            if(pri[x1]-pri[x0]>=t)
            {
                if(pri[x1]-pri[x0]>t)
                {
                    x0++;
                }
                break;
            }
        }
        if(t-(pri[x1]-pri[x0])==1)
        {
            x0++;
        }
    }

    /////////////

    sum=1;
    for(i=0;i<=max;i++)
    {
        if(i==x0)
        {
            t=pri[x1];
        }
        else
        {
            t=pri[i];
        }
        sum*=t;
        sum=sum%10000;
    }
    *maxStep=sum;
    free(pri);
}

22 楼

xyhx [专家分：0] 发布于 2006-08-14 19:35:00

#include<malloc.h>
void MonkeyDance(const int n, int* maxStep)
{
    int i,count,num,temp;
    int *mon,*str;//指向数组
    int *pback,*pforw;//指向数组元素
    long int max=0,mid,t;
    int gcd(int a,int b);
    int ComNum(int *mark,int count);
    for(i=2,count=0,num=0;num+i<=n;i++,count++)
        num+=i;
    num-=(i-1);
    str=mon=(int * )calloc(count+1,sizeof(int));
    if(mon==NULL)
        printf("Allocat memory failed!\n");
    else
    {
        for(i=0;i<count-1;i++)
            *mon++=i+2;
        *mon=n-num;
        if(count==1)
            max=str[0];
        else
        {
            pback=str+count-2;pforw=pback+1;
            do
            {
                temp=(*pback)+(*pforw);
                if( temp>=((*pback)+2)*3)
                {
                    (*pback)++;
                    while(1)
                    {
                        if(temp>=(*pback+1)*3)
                        {
                            temp-=*pback;
                            *pforw=(*pback)+1;
                            pback++;pforw++;
                            count++;
                        }
                        else
                        {
                            *pforw=temp-(*pback);
                            mid=ComNum(str,count);
                            max=mid>max?mid:max;
                            break;
                        }
                    }
                }
                   mid=ComNum(str,count-2);
                while(1)
                {
                    if( *pback+2<*pforw )
                    {
                        t=(*pback)*(*pforw)/gcd(*pback,*pforw);
                        t=mid*t/gcd(mid,t);
                        max=t>max?t:max;
                    }
                    else
                    {
                        *pback+=(*pforw);
                        if(pback!=str)
                            pback--;
                        pforw--;
                        count--;
                         t=*pforw*mid/gcd(mid,*pforw);
                        max=t>max?t:max;
                        //Print(str,count); */
                        break;
                    }
                }

            }while(pforw!=str);
        }
    }
    max=str[0]>max?str[0]:max;
    *maxStep=max%10000;
}
int gcd(int a,int b)
{
    if (a%b==0) return b;
    return gcd(b,a%b);
}
int ComNum(int *mark,int count)
{
    int i,res=1;
    for(i=0;i<count;i++)
        res=mark[i]*res/gcd(mark[i],res);
    return res;
}

我来回复

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

主题：第37次编程比赛第1题题目（延长到周一晚8:00)

回复列表（共22个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：第37次编程比赛第1题题目（延长到周一晚8:00)

回复列表 （共22个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共22个回复）