主题：第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步以后，每只猴子都回到自己的位置。
回复列表 （共22个回复）
沙发
neverPE [专家分：1620] 发布于 2006-08-11 20:24:00
test
板凳
ITER [专家分：680] 发布于 2006-08-12 00:05:00
貌似很难诶 先顶一下 沙发没得坐了 呵呵
3 楼
euc [专家分：4310] 发布于 2006-08-12 03:05:00
int lcm (const int a, const int b)
{
int n, m, r;
if (a >= b) {
n = a;
m = b;
}
else {
n = b;
m = a;
}
while (r = n % m) {
n = m;
m = r;
}
return a * b / m;
}
int maxize (int tab[], int n)
{
int max = 0;
for (int i = 0; i < n; ++i) {
if (max < tab[i])
max = tab[i];
}
return max;
}
void MonkeyDance (const int n, int *maxStep)
{
int *tab = new int[n+1];
tab[2] = 2;
tab[3] = 3;
tab[4] = 4;
for (int i = 5; i <= n; ++i) {
int max = i, m;
for (int j = 2; j <= i/2; ++j) {
int l[5];
l[0] = lcm (tab[i-j], tab[j]);
l[1] = lcm (tab[i-j], j);
l[2] = lcm (i - j, tab[j]);
l[3] = lcm (i - j, j);
l[4] = i;
m = maxize (l, 5);
if (max < m)
max = m;
}
tab[i] = max;
}
*maxStep = tab[n];
delete []tab;
}
4 楼
xgn2003 [专家分：0] 发布于 2006-08-12 09:39:00
真的很难懂啊
5 楼
ITER [专家分：680] 发布于 2006-08-12 10:23:00
/********************
昨天睡觉的时候想了一下 原来是求最小公倍数 呵呵
********************/
#include <iostream>
using namespace std;
int GB(int x,int y,int *h)
{
int r;
int a=x;
int b=y;
do
{
r=y%x;
y=x;
x=r;
}while(r!=0);
if(1==y)
*h=1;
return a*b/y;
}
void MonkeyDance(const int n, int* maxStep)
{
int k=n/2;
int a,b;
int tmp=0;
int flag=1;
int *biaoji=new int;
*biaoji=0;
int TP=-1;
if(n==k*2)
{
a=k-1;
b=k+1;
k-=2;
}
else
{
a=k;
b=k+1;
k--;
}
for(;k>0&&flag;k--,a--,b++)
{
TP=GB(a,b,biaoji);
if(TP>tmp)
tmp=TP;
if(*biaoji)
break;
}
*maxStep = tmp%10000;
}
main()
{
int *p=new int;
MonkeyDance(1000,p);
cout<<*p<<endl;
}
6 楼
hyerty [专家分：1110] 发布于 2006-08-13 10:25:00
#include <stdio.h>
#define MAXN 10000 /*最大数组下标，即最大猴子数 */
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<2 || n>MAXN) {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，不知道什么意思。
7 楼
liangbch [专家分：1270] 发布于 2006-08-13 13:09:00
//这个问题的数学抽象是将n,分为m个数x1,x2,x3,x4,...xm的和,使这m个数的最小公倍数为最大.
//我采用的方法是递归搜索(穷举法),目前没有直观有效的剪枝规则.在计算了100以内的数时,可以达到要求,大于是100速度很慢.孩子病了,先这样吧.
//本程序在VC++6.0 编译通过
// program_37match.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#define MAX_SEQUENCE 32
//#define OUTPUT_DETAIL
typedef unsigned __int64 UINT64;
typedef unsigned long DWORD;
//求最大公约数
UINT64 gcd(UINT64 a,UINT64 b)
{
UINT64 t;
while (1)
{
t= a % b;
if (t==0) return b;
a=b; b=t;
}
}
typedef struct _seq_tag
{
DWORD arr[MAX_SEQUENCE];
int n;
int len;
UINT64 prod;
}SEQUENCE;
SEQUENCE g_r;
UINT64 calcProd(SEQUENCE *p,int len)
{
int i;
UINT64 r=p->arr[0];
UINT64 d; //公约数
for (i=1;i<len;i++)
{
d=gcd(r,p->arr[i]);
if (d!=1)
r/=d;
r*=p->arr[i];
}
return r;
}
void print(SEQUENCE *p,int len)
{
int i;
printf("\n----------------\n");
printf("%d=",p->n);
UINT64 prod=calcProd(p,len);
for (i=0;i<len;i++)
{
if (i==len-1)
printf("%d",p->arr[i]);
else
printf("%d+",p->arr[i]);
}
printf("\n max_step=%I64d\n",prod);
}
void GetSequence(SEQUENCE *p,int totalLen,int currLen,int newNum,int remain)
{
int i,len;
UINT64 prod;
if (currLen+1==totalLen)
{
p->arr[currLen]=newNum;
len=currLen+1;
prod=calcProd(p,len);
if (prod>g_r.prod)
{
g_r.n=p->n;
g_r.prod=prod;
g_r.len=len;
for (i=0;i<len;i++)
g_r.arr[i]=p->arr[i];
}
return;
}
p->arr[currLen]=newNum;
remain-=newNum;
currLen++;
newNum++;
while(1)
{
if ( currLen==totalLen-1)
{
newNum=remain;
GetSequence(p,totalLen,currLen,newNum,remain);
break;
}
else
{
if ( (newNum+newNum+totalLen-currLen-1)*(totalLen-currLen)/2>remain )
break;
GetSequence(p,totalLen,currLen,newNum,remain);
newNum++;
}
}
}
void MonkeyDance(const int n,int *maxStep)
{
int i,len;
DWORD num;
SEQUENCE s;
g_r.n=n;
if (n<7)
{
switch(n)
{
case 1: case 2: case 3:
case 4: case 6:
g_r.len=1;
g_r.arr[0]=n;
break;
case 5:
g_r.len=2;
g_r.arr[0]=(n/2);
g_r.arr[1]=(n/2)+1;
break;
}
*maxStep=1;
for (g_r.prod=1,i=0;i<g_r.len;i++)
{
(*maxStep)*=g_r.arr[i];
}
#ifdef OUTPUT_DETAIL
print(&g_r,g_r.len);
#endif
return;
}
if ((n&1)==0) //偶数//
g_r.arr[0]=(n/2)-1;
else //奇数
g_r.arr[0]=(n/2);
g_r.arr[1]=(n/2)+1;
g_r.len=2;
g_r.prod=g_r.arr[0] * g_r.arr[1];
len=3; s.n=n;
while( (2+ 2+len-1)*len/2<=n)
{
num=2;
while ( (num+num+len-1)*len/2<=n )
{
GetSequence(&s,len,0,num,n);
num++;
}
len++;
}
#ifdef OUTPUT_DETAIL
print(&g_r,g_r.len);
#endif
*maxStep= g_r.prod % 10000;
}
int main(int argc, char* argv[])
{
int i,max;
for (i=1;i<=100;i++)
{
MonkeyDance(i,&max);
printf("n=%d,max=%d\n",i,max);
}
return 0;
}
8 楼
ccpp [专家分：9360] 发布于 2006-08-13 17:48:00
/*
基本思想是用一系列质数来拆整数 n,
质数的乘积和最后剩余的数(有可能是出现过的质数)，
求出它们的最小公倍数 即为所得。此算法未经严格证明！
*/
#define MAXSIZE 100
int prime[MAXSIZE];
//产生一系列质数，并保存到 prime
void GenPrime(int nmax)
{
static int gap = 2;
static int count = 2;
static int may_be_prime = 5;
int i, is_prime;
enum {YES = 1,NO = 0};
prime[0] = 2;
prime[1] = 3;
prime[2] = 5;
while (prime[count] < nmax) {
may_be_prime += gap;
gap = 6 - gap;
is_prime = YES;
for (i = 0; prime[i]*prime[i] <= may_be_prime && is_prime; i++)
{
if (may_be_prime % prime[i] == 0)
{
is_prime = NO;
}
}
if (is_prime)
prime[++count] = may_be_prime;
}
}
//求最大公约数
int Gcd(int x,int y)
{
int t;
//if (x==0||y==0) return 0;
while((t = x%y)!=0)
{
x = y;
y = t;
}
return y;
}
void MonkeyDance(const int n, int* maxStep)
{
int i, j, temp;
int result ,maxnum = n, x;
GenPrime(n);//使用了static,每次调用，质数连续产生
for(i = 0; prime[i] < n; i++)
{
for(temp = n,result = 1,j = i; (temp - prime[j]) > 1;j++)
{
result *= prime[j];
temp -= prime[j];
}
x = temp / Gcd(temp,result) * result;
if(maxnum < x)
maxnum = x;
}
maxnum %= 10000;
i = 0;
while(maxnum)
{
maxStep[i++] = maxnum%10;
maxnum /= 10;
}
}
9 楼
xyhx [专家分：0] 发布于 2006-08-13 18:00:00
#include<stdio.h>
int num=0;
int max=0;
int temp=0,mid;
int mcn(int a,int b);
void Comm(int pre);
void MonkeyDance(const int n, int* maxStep)
{
num=n;
max=1;temp=0;mid=1;
Comm(2);
*maxStep=max%10000;
}
void Comm(int pre)
{
int i,gg=1;
for(i=pre;i<=num-temp;i++)
{
temp+=i;
gg=mcn(mid,i);
mid=mid*i/gg;
if(temp==num&&mid>max)
max=mid;
else
Comm(i+1);
temp-=i;
mid=mid*gg/i;
}
}
int mcn(int a,int b)
{
if (a%b==0) return b;
return mcn(b,a%b);
}
10 楼
ccpp [专家分：9360] 发布于 2006-08-13 18:34:00
#define MAXSIZE 100
//MAXSIZE 为连续质数序列（2，3，5，7，11...）中质数的个数
//为了处理更大的数 请增加 MAXSIZE 的值
[em15]突然决得自己的算法有问题，呵呵
我来回复
您所在位置：