evol128[Blog]

I am the bone of my code

不同层次的程序员是如何解决问题的

本文仅供娱乐,切莫当真 

感谢grant, liu, molly。 没有你们的帮忙我不可能完成这篇文章,谢谢大家

 

原题:5个水手在岛上发现一堆椰子, 夜晚睡觉后,第一名水手把椰子分为等量的5堆,还剩下一个给了猴子,自己藏起一堆。第二个水手把剩下的4堆混合后重新分为 等量的5堆,剩下一个给了猴子;自己藏起一堆。第三第四第五位水手依此办理。天亮以后,大家把剩下的椰子分为等量的5堆,剩下一个给了猴子。问原来这堆椰子最少为多少个。

 

for(i=0;i<=10000;i++){
    check(i);
}

 

printf("Please enter the number of pirates\n");
scanf("%d",&x);
for(i=0;i<=1000000;i++){  
    check(i,x);
}

 

#define NUM 5
//i是最后一次剩下的椰子个数
for(i=NUM-1;i<=INT_MAX;i+=NUM-1){
    check(i,NUM);
}

 

#define NUM_PIRATE 5
#define NUM_MONKEY 1

LARGEINT a,b,c,x,y;

//from last pirate to first, recursively solve (n-1)x=ny+1
a=NUM_PIRATE-1;
b=-NUM_PIRATE;
c=NUM_MONKEY;
for(i=0;i<NUM_PIRATES;i++){
//this function solves ax+by=c by extended-euclid algorithm
    extended_euclid(a, b, c, &x, &y); 
    b=b*NUM_PIRATE;
    c=NUM_MONKEY+NUM_PIRATE*x;
}
return NUM_PIRATE*x+NUM_MONKEY;

 

数学家

他们不写程序,他们发现椰子的数量是下面这个方程的正整数解:

(N-1)^N*x-N^{N+1}+(N-1)^{N+1}=N^{N+1}*y

接着他们手算欧几里得算法来解这个方程

 

#define NUM_PIRATE 5
#define NUM_MONKEY 1

LARGEINT a,b,c,x,y;

//这式子是不是很眼熟?
a=pow(NUM_PIRATE-1,NUM_PIRATE);
b=-pow(NUM_PIRATE,NUM_PIRATE+1);
c=(-b-a*(NUM_PIRATE-1))*NUM_MONKEY;
extended_euclid(a,b,c,&x,&y);
return x;

 

echo 15621

 

 

P.S. 本文的代码简化了很多细节,譬如说求解ax+by=c的时候,欧几里得算法只应用于c=gcd(a,b)的情况,但本题中c=k*gcd(a,b)。而且,我们需要求的是最小正整数解,而不是任意一组解。还有一个就是LARGEINT必须实现高效率乘除法,这个细节就不在这里讨论了,呵呵