不同层次的程序员是如何解决问题的
本文仅供娱乐,切莫当真
感谢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;
数学家
他们不写程序,他们发现椰子的数量是下面这个方程的正整数解:
接着他们手算欧几里得算法来解这个方程
#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必须实现高效率乘除法,这个细节就不在这里讨论了,呵呵