本文主要是介绍POJ1006 Biorhythms（生理周期，中国剩余定理详述），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
Input
当p = e = i = d = -1时，输入数据结束。
Output
采用以下格式：
Case 1: the next triple peak occurs in 1234 days.
注意：即使结果是1天，也使用复数形式“days”。
Sample Input
0 0 0 0 0 0 0 100 5 20 34 325 4 5 6 7 283 102 23 320 203 301 203 40 -1 -1 -1 -1
Sample Output
Case 1: the next triple peak occurs in 21252 days. Case 2: the next triple peak occurs in 21152 days. Case 3: the next triple peak occurs in 19575 days. Case 4: the next triple peak occurs in 16994 days. Case 5: the next triple peak occurs in 8910 days. Case 6: the next triple peak occurs in 10789 days.
题目：http://poj.org/problem?id=1006
这一题是中国剩余定理，中国剩余定理概念及相关：
http://baike.baidu.com/link?url=oX4jZ9SCVu5lKDwFJQx-Lhwga1KimUyukk3VIAwUoRpK5gY9BTmM0UePXtYBgauGZf_-GLrG6xX5-peyQsnEJwOfnm6OSmB2mVLxbKrrStoop64cirabbXTomITKDUdLVgS4mJj-1iprpvQ8Qcnjpicyt3wxhc_cfMCGakFFopw_NvRy72TG7KRaRdFq6UWbGpEYR3ggWWhWcImUjMNZc_
http://blog.sina.com.cn/s/blog_a6f9a3b60101favb.html
感谢博主。
首先看一下下面的题目，方便引出有关中国剩余定理的解法：
题目：今有物不知其数，三三数之剩二；五五数之剩三；七七数之剩二。问物几何？
解法：凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩十五；一百六以上，以一百零五减之即得；
上面计算方法可以写成如下式子：
70*2+21*3+15*2=233
233-105*2=23
初看解法时真是一头雾水，为什么“则置七十”，“则置二十一”，“则置十五”，解法中并没有说明，而且上网找了很多资料，并没有找到原因，但欣慰的一点是找到了怎么可以算出来这里的“七十”，“二十一”，“十五”，上面的解法中也提到了，不过开始看时不太理解；下面是算法：
下面是对上面题目的详细算法，也是这一类题的通用解法：
这类题就是解一元一次同余式方程组，即已知三个式子中的除数分别为y1,y2,y3, 余数分别为z1,z2,z3,他们的被除数相同，为x，求x。可以写成下面的式子：
x=z1 (mod y1); x÷y1=Z1...z1;
x=z2 (mod y2); 也可以写成 x÷y2=Z2...z2;
x=z3 (mod y3); x÷y3=Z3...z3;
对于上面的题目可以写成：
x=2 (mod 3); x÷3=Z1...2;
x=3 (mod 5); 也可以写成 x÷5=Z2...3;
x=2 (mod 7); x÷7=Z3...2;
1）求出“七十”，“二十一”，“十五”的方法；
i：
for(i=0;;i++)
{//这里既是解得上面的“则置七十”，但不知道为什么if(5*7*i%3==1){a=5*7*i;break;}
}运算后a为70，这里3作为除数，求出直到满足5*7*i%3==1的i为止，则a=5*7*i；
ii：
for(i=0;;i++){//这里既是解得上面的“则置二十一”，但不知道为什么if(3*7*i%5==1){b=3*7*i;break;}}运算后b为21，这里5作为除数，求出直到满足3*7*i%5==1的i为止，则b=3*7*i；
iii：
for(i=0;;i++){//这里既是解得上面的“则置十五”，但不知道为什么if(3*5*i%7==1){c=3*5*i;break;}}运算后c为15，这里7作为除数，求出直到满足3*5*i%7==1的i为止，则c=3*5*i；
2）求出余数的最小公倍数；
一般给出的数字不会很大，手算就能算出来，这里给出一种方法：
int Lcm(int i,int j)
{int a=i,b=j,n;if(i<j){int t=i;i=j;j=t;}do{n=i%j;i=j;j=n;}while(n>0);return a*b/i;
}则3，5，7的最小公倍数即为Lcm(Lcm(3.5.7));
3）求被除数x
x=(a*2+b*3+c*2)%Lcm(3.5.7)
其中2,3,2分别是余数，Lcm(3.5.7)是3,5,7的最小公倍数。
上面这一题代码：
//中国剩余定理得计算方法实验
//------------------------------问题如下-------------------------------//
//“中国剩余定理”是公元5-6世纪、我国南北朝时期的一部著名算术著作《孙子算经》 //
//中的一个“物不知数”的解法问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。 //
//问物几何？答曰：二十三。 //
//-------------------------------------------------------------------//
//----------------------------古人的解法-------------------------------//
//凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一则置十五；一百六以上， //
//以一百零五减之即得。 //
// 依定理译成算式解为： //
// 70×2＋21×3＋15×2＝233 //
// 233－105×2＝23 //
//-------------------------------------------------------------------//import java.util.Scanner;
public class Poj1006_Test {public static void main(String[] agrs){Scanner input=new Scanner(System.in);int a,b,c,i;for(i=0;;i++){//这里既是解得上面的“则置十五”，但不知道为什么if(3*5*i%7==1){a=3*5*i;break;}}for(i=0;;i++){//这里既是解得上面的“则置二十一”，但不知道为什么if(3*7*i%5==1){b=3*7*i;break;}}for(i=0;;i++){//这里既是解得上面的“则置七十”，但不知道为什么if(5*7*i%3==1){c=5*7*i;break;}}System.out.printf("%d %d %d %d\n",a,b,c,(a*2+b*3+c*2)%(3*5*7));//解得a,b,c后按照上面的式子就能解出结果input.close();}}
POJ1006代码如下：
//:Poj1006 Biorhythms
//此题目写成数学表达式即为：(n+d)%23=p;(n+d)%28=e;(n+d)%28=i. 即已知除数和余数，求被除数n+d.
import java.util.Scanner;
public class Poj1006 {int Lcm2(int i,int j){int a=i,b=j,n;if(i<j){int t=i;i=j;j=t;}do{n=i%j;i=j;j=n;}while(n>0);return a*b/i;}int Lcm3(int a,int b,int c){return Lcm2(Lcm2(a,b),c);}public static void main(String[] agrs){int Physical=23,Emotional=28,Intellectual=33;//各个周期int r, a,b,c;for(r=0;;r++)if(Physical*Emotional*r%Intellectual==1){a=Physical*Emotional*r;break;}for(r=0;;r++)if(Physical*Intellectual*r%Emotional==1){b=Physical*Intellectual*r;break;}for(r=0;;r++)if(Emotional*Intellectual*r%Physical==1){c=Emotional*Intellectual*r;break;}
// System.out.println(a+" "+b+" "+c);Scanner input=new Scanner(System.in);int p,e,i,d, n,m=0;while(input.hasNext()){p=input.nextInt();e=input.nextInt();i=input.nextInt();d=input.nextInt();if(p==-1&&e==-1&&i==-1&&d==-1) break;Poj1006 Moth=new Poj1006();
// System.out.println(Moth.Lcm3(Physical,Emotional,Intellectual));n=((a*i+b*e+c*p-d)%(Moth.Lcm3(Physical,Emotional,Intellectual)/*三个除数的最小公倍数*/));if(n>0)System.out.printf("Case %d: the next triple peak occurs in %d days.\n",++m,n);elseSystem.out.printf("Case %d: the next triple peak occurs in %d days.\n",++m,21252-d);}input.close();}
}
简化一点，能事先算出来的就事先算出来：
import java.util.Scanner;
public class Poj1006_简化代码 {public static void main(String[] agrs){Scanner input=new Scanner(System.in);int p,e,i,d, n,m=0;while(input.hasNext()){p=input.nextInt();e=input.nextInt();i=input.nextInt();d=input.nextInt();if(p==-1&&e==-1&&i==-1&&d==-1) break;n=(5544*p+14421*e+1288*i-d)%21252/*三个除数的最小公倍数*/;if(n>0)System.out.printf("Case %d: the next triple peak occurs in %d days.\n",++m,n);elseSystem.out.printf("Case %d: the next triple peak occurs in %d days.\n",++m,21252-d);}input.close();}
}
这篇关于POJ1006 Biorhythms（生理周期，中国剩余定理详述）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
