首页 > 代码库 > POJ-1006 Biorhythms
POJ-1006 Biorhythms
【题目描述】
三个周期时间分别为：23，28和33。分别给定三个周期的某一天（不一定是第一天），和开始计算的日期，输出下一个triple peak。
【思路分析】
如果不了解中国剩余定理，可以通过模拟的方式：从开始日期起，寻找第一次遇到高峰的项目，记录；之后寻找该项目的下一个高峰，测试是否另外两个项目也是高峰。
若用中国剩余定理求解，则求：(n+d)%23=p; (n+d)%28=e; (n+d)%33=i，gcd(23, 28, 33)=1。
记p, e, i分别为a1, a2, a3. 并设M = m1*m2*m3 = 23*28*33 = 21252. Mi = M / mi. 故M1 = 28*33 = 924; M2 = 23*33 = 759; M3 = 23*28 = 644.
则解x = a1t1M1 + a2t2M2 + a3t3M3, 其中tiMi=1(mod mi). 下面将求解ti：
ti 实际上为 Mi 模 mi 的逆。可采用辗转相除法得出，见百度文库：
http://wenku.baidu.com/view/ada3397f2f60ddccdb38a04b.html
http://wenku.baidu.com/view/f0894659be23482fb4da4c51.html
【小结】
复习一下中国剩余定理
【附：完整代码】
#include <iostream>using namespace std;int main(){ int p, e, i, d, caseno = 1; const int CIRCLE[3] = {23,28,33}; while (true) { cin>>p>>e>>i>>d; if (p == -1 && e == -1 && i == -1 && d == -1) break; int testday = d + 1; int largestIndex; int largestDay; // 记录第一次遇到高峰的日期testday，和这个高峰是属于哪个项目 while (true) { if ((testday-p) % CIRCLE[0] == 0) { largestIndex = 0; largestDay = p; break; } else if ((testday-e) % CIRCLE[1] == 0) { largestIndex = 1; largestDay = e; break; } else if ((testday-i) % CIRCLE[2] == 0) { largestIndex = 2; largestDay = i; break; } else { testday++; } } // 寻找三个高峰的日期 while (true) { if ((largestIndex == 0 || (testday-p) % CIRCLE[0] == 0) && (largestIndex == 1 || (testday-e) % CIRCLE[1] == 0) && (largestIndex == 2 || (testday-i) % CIRCLE[2] == 0)) { int resultday = testday - d; cout<<"Case "<<caseno++<<": the next triple peak occurs in "<< resultday <<" days."<<endl; break; } testday += CIRCLE[largestIndex]; } } return 0;}
POJ-1006 Biorhythms
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。