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

11 楼

ccpp [专家分：9360] 发布于 2006-08-13 18:34:00

怎么多出一贴

12 楼

liyanguestc [专家分：90] 发布于 2006-08-13 22:20:00

第一次正式参加不知道是否有什么格式要求?VC++编译通过！
#include <iostream>
#include <time.h>
#include <iomanip>
using namespace std;
int q[]={2,3,4,5,7,8,9,11,13,16,
        17,19,23,25,27,29,31,32,37,41,

        //////////////////////////////
        43,47,49,53,59,61,64,67,71,73,
        79,81,83,89,97,101,103,107,109,113,
        121,125,127,128,131,137,139,149,151,157,
        163,167,169,173,179,181,191,193,197};
#define QN 20
void maxdance(int *b);///求这组选择step为多少，并以max表示最大step/////
int check(int *a);//检查是否所有数字互质
double max=0;//最大step
void main()
{int N;
int a[QN];//表示q[]的选择情况
double start,end;//计算运行时间
start=clock();

int qcount;
qcount=sizeof(q)/sizeof(q[0]);//qcount=60
cout<<"请输入猴子数目N:"<<endl;//2^30=1073741824
cin>>N;

for(int j=0;j<=1048576;j++)//2^20=1048576
{int flag=1;
   int tmp=j;
   for(int t=0;t<QN;t++)
     a[t]=0;//初始化数组
  for(int k=0;k<QN;k++)
    {a[k]=j%2;j/=2;flag*=2;//设置数组的值
    if(flag>tmp)
        break;
  }
   if(!check(a))//如果不互质则进行下一轮循环
    {j=tmp;
    continue;
   }
    int madd=0;
for(t=0;t<QN;t++)
  if(a[t]==1)
     madd+=q[t];//madd为所选数据的和
  if(madd<=N&&madd!=N-1)//如果madd>N或者madd==N-1则进行下一轮循环
     maxdance(a);//求这组数据的step并与max比较，max取较大值
  j=tmp;
  }

int anwser=max-int(max/10000)*10000;
cout<<"max="<<setprecision(15)<<max<<endl;//最后结果
cout<<"anwser="<<anwser<<endl;//最终结果的末4位
end=clock();
cout<<"run for"<<(double)(end-start)/CLK_TCK<< "seconds"<<endl;

}
///求这组选择step为多少，并以max表示最大step/////
void maxdance(int *b)
{double maxtmp=1;
int t=0;
    for(;t<QN;t++)
  if(b[t]==1)
     maxtmp*=q[t];
  if(maxtmp>max)
      max=maxtmp;
}
//检查是否所有数字互质/////
int check(int* a)
{if(a[0]+a[2]+a[5]+a[9]+a[17]>1)
return 0;
if(a[1]+a[6]+a[14]>1)
return 0;
if(a[3]+a[13]>1)
return 0;
return 1;
}

13 楼

太没劲了 [专家分：2050] 发布于 2006-08-13 22:21:00

给个 200 内版本，VC6 下测试通过

int getcdiv(int n1,int n2)
{
    int min,max,cur;

    if( n1>n2 )
        min = n2, max =n1;
    else max = n2, min = n1;
    while( (cur = max%min) )
        max = min, min = cur;

    return(min);
}

int getcmul(int n1,int n2)
{
    int getcd=getcdiv(n1,n2);

    return( n1/getcd*n2);
}

#define CACHE_NUM       1024

int getmaxstep(int n)
{
    int i,j,curmax;
    static int preset[CACHE_NUM] = {0,0,2,3,4,6},effnum=6;

    if( n<effnum ) return( preset[n] );
    if( n> effnum )
        for(i=effnum;i<n; ++i) getmaxstep(i);

    curmax = n;
    for(i=n/2; i>1 ; --i)
    {
        int lval = n-i,calcv[2],val[4]={0,0,0,0},curmax1;

        calcv[0] = getmaxstep(i);
        calcv[1] = getmaxstep(lval);
        if( calcv[1]!=lval )
            val[0] = getcmul(i,calcv[1]);
        val[1] = getcmul(i,lval);
        val[2] = getcmul(calcv[0],lval);
        val[3] = getcmul(calcv[0],calcv[1]);
        for(j=0,curmax1=0;j<4; ++j)
            if( val[j]>curmax1 ) curmax1 = val[j];
        if( curmax1>curmax ) curmax = curmax1;
    }

    if( n>=effnum && n<CACHE_NUM )
        preset[n] = curmax, ++effnum;
    return(curmax);
}

void MonkeyDance(const int n, int* maxStep)
{
    *maxStep = getmaxstep(n)%10000;
}

14 楼

yxd2050 [专家分：0] 发布于 2006-08-14 00:29:00

hao ya

15 楼

浩然 [专家分：560] 发布于 2006-08-14 00:53:00

理解不来，感觉有几个圈就只用跳几次!yun~

16 楼

hyerty [专家分：1110] 发布于 2006-08-14 10:24:00

#include <stdio.h>
#define MAXN 62  /*最大数组下标，即最大猴子数 */
long f[MAXN],maxj;  /*f[j]表示j只猴子的最大步数，maxj表示已经求出的最大猴子数*/
long mintimes(long a,long b); /*求最小公倍数 */
void MonkeyDance(const int n, int* maxStep);

int main()
{int n,maxStep;
f[2]=2; f[3]=3; maxj=3;
//scanf("%d",&n);
for (n=2;n<=MAXN;n++)
{MonkeyDance(n,&maxStep);
  printf("maxStep=%d\n",maxStep);
}
getchar();  /*暂停 */
//getchar();
}

long mintimes(long a,long b) /*求最小公倍数 */
{int i,j,r;
i=b;  j=a;  r=i%j;
while (r!=0)
  {i=j;  j=r;  r=i%j; }
return(a/j*b);
}
void MonkeyDance(const int n, int* maxStep)
{int i,j,t;
long nowstep;
if (n>62) {*maxStep=7800; return; }  //俺就想作个弊
if (n<2) {printf("Input error!\n"); return; }
for (j=maxj+1;j<=n;j++)
  {for (i=2,t=j/2+1;i<t;i++)
    {nowstep=mintimes(f[i],f[j-i]);
     if (f[j]<nowstep) f[j]=nowstep;
    }
   if (f[j]<j) f[j]=j;
  }
if (maxj<n) maxj=n;
//printf("f[%d]=%ld\n",n,f[n]);  /*调试程序时用来看各个值的 */
*maxStep=f[n]%10000L;
return;
}

// 好象从62起以后的值全部是7800，不知道什么意思。

17 楼

joekings [专家分：550] 发布于 2006-08-14 10:44:00

int minMultiple(int num1,int num2)//求最小公倍数
{
    int a,b;
    int temp;
    int result;

    a=num1;
    b=num2;
    if(a<b)
    {
        temp=a;
        a=b;
        b=temp;
    }
    while(b!=0)/*利用辗除法，直到b为0为止*/
    {
        temp=a%b;
        a=b;
        b=temp;
    }
    result=num1*num2/a;
    return result;
}

void MonkeyDance(const int n, int* maxStep)
{
    int i,j,k,l;
    if(n<=6)
    {
        if(n==5)
            *maxStep=6;
        else
            *maxStep=n;
    }
    if(n>6)
    {
        if(n%4==0)
            i=(n-1)/2;
        else
            i=n/2;
        j=n-i;
        *maxStep=minMultiple(i,j);
        MonkeyDance(i,&k);
        MonkeyDance(j,&l);
        k=minMultiple(k,j);
        l=minMultiple(l,i);
        if(*maxStep<k||*maxStep<l)
        {
            *maxStep=k;
            if(k<l)
                *maxStep=l;
        }

    }
    //*maxStep=*maxStep%10000;//我仔细考虑了一下，如果用这句，因为递归调用，当递归中的数据超过10000时，对结果会有影响，因此注销。
}//不知道数据超过int范围了怎么解决，int范围内应该是对的。

18 楼

joekings [专家分：550] 发布于 2006-08-14 12:38:00

int minMultiple(int num1,int num2)//求最小公倍数
{
    int a,b;
    int temp;
    int result;

    a=num1;
    b=num2;
    if(a<b)
    {
        temp=a;
        a=b;
        b=temp;
    }
    while(b!=0)/*利用辗除法，直到b为0为止*/
    {
        temp=a%b;
        a=b;
        b=temp;
    }
    result=num1*num2/a;
    return result;
}
int iCount=0; //定义全局变量，只在最终结果取4位。
void MonkeyDance(const int n, int* maxStep)
{
    int i,j,k,l;
    iCount++;
    if(n<=6)
    {
        if(n==5)
            *maxStep=6;
        else
            *maxStep=n;
    }
    if(n>6)
    {
        if(n%4==0)
            i=(n-1)/2;
        else
            i=n/2;
        j=n-i;
        *maxStep=minMultiple(i,j);
        MonkeyDance(i,&k);
        MonkeyDance(j,&l);
        k=minMultiple(k,j);
        l=minMultiple(l,i);
        if(*maxStep<k||*maxStep<l)
        {
            *maxStep=k;
            if(k<l)
                *maxStep=l;
        }

    }
    if(iCount==1)//记数，在返回最终结果时保留末4位。
      *maxStep=*maxStep%10000;
    iCount--;
}
//我在VC6.0试了一下，int型最高可以到亿位不溢出，所以，直接用int应该可以。
//为了只输出末4位，所以采用全局变量iCount记数，当然也可以直接输出最终结果。

19 楼

magicalking [专家分：150] 发布于 2006-08-14 13:17:00

这题应该可以理解为把n化为a1+a2+...an使得他们的最小公倍数最大

20 楼

boxertony [专家分：23030] 发布于 2006-08-14 16:06:00

// vc6编译通过
// 没有想到好的算法，速度达不到要求啊
#include <stdio.h>
#include <time.h>
#include <string.h>
#include <assert.h>
#include <conio.h>

#define MAXBUFFSIZE    256

typedef __int64        I64;

template <class T>
__inline Swap(T &x, T &y)
{
    T    temp;
    temp = x;
    x = y;
    y = temp;
}

// 求两个数的最大公约数
// 使用辗转相除法（欧几里德法）
template <class T>
T GCD(T m, T n)
{
    assert(m >= 0 && n >= 0);

    if(m == 0)
        return n;

    if(n == 0)
        return m;

    if(m < n)
    {
        Swap(m, n);
    }

    T        d = m % n;
    while(d > 0)
    {
        m = n;
        n = d;
        d = m % n;
    }

    return n;
}

// 求最小公倍数
I64 lcm(I64 m, I64 n)
{
    I64    x;

    x = m / GCD(m, n);

    return x*n;
}

// 求若干数的最小公倍数
I64 lcm(int *nums, int n)
{
    int        i;
    I64    min;

    min = nums[1];
    for(i=2; i<=n; ++i)
    {
        min = lcm(min, nums[i]);
    }

    return min;
}

// 检查x是否能被数组nums的某个数整除
bool Check(int *nums, int n, int x)
{
    for(int i=1; i<=n; ++i)
    {
        if(x%nums[i] == 0)
            return false;
    }

    return true;
}

void MonkeyDance0(int steps[], const int n, int k, I64 *max)
{
    int            i;

    if(n <= 0)
    {
        I64        temp = lcm(steps, k);
        if(temp > *max)
        {
            *max = temp;
        }

        return;
    }
    else if(Check(steps, k-1, n) == true)
    {
        steps[k] = n;
        MonkeyDance0(steps, 0, k, max);
    }

    if(n >= 5)
    {
        for(i=steps[k-1]+1; i<=(n-1)/2; ++i)
        {
            if(Check(steps, k-1, i) == true)
            {
                steps[k] = i;
                MonkeyDance0(steps, n-i, k+1, max);
            }
        }
    }
}

void MonkeyDance(const int n, int* maxStep)
{
    int        steps[MAXBUFFSIZE] = {1};

    I64    max = n;
    MonkeyDance0(steps, n, 1, &max);
    *maxStep = (int)(max % 10000);
}

我来回复

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

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

回复列表（共22个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

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

回复列表 （共22个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共22个回复）