学步园

代码:[非最优]

//============================================================================
// Name        : 1006.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : 1006 in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int main() {
	int p,e,i,d;
	int j=0;
	int k=0;
	int point=645;
	int result[10000];
	int m=-1,n=-1;
	int temp;
	while(cin>>p>>e>>i>>d)
	{
		j=0;//forget to reset j
		if((p==-1)||(e==-1)||(i==-1)||(d==-1))
		{
			break;
		}
		while(j!=point)
		{
			m=(33*j+i-p)%23;
			n=(33*j+i-e)%28;
			if(m==0&&n==0&&33*j+i-d>0)
				break;
			j++;
		}
		temp=(33*j+i-d)%21252;//can not large than 21252
		if(temp==0)
			result[k++]=21252;
		else
			result[k++]=temp;
	}
	j=0;
	for(;j!=k;j++)
	{
		cout<<"Case "<<j+1<<": the next triple peak occurs in "<<result[j]<<" days."<<endl;
	}
	return 0;
}

思路:

列出三个方程组,

23*x+p=28*y+e=33*z+i=x+d   

控制最大的33(因为循环次数比23 28少.如果是23,最大循环次数是28*33),用z表示x,y

然后控制循环变量j直至找出使方程成立的数.

问题:

1)之前忘记将j重置0,出问题总是没找出来郁闷惨了.

2)应该找比d大的数字,好比输入5 10 15 300.当j=1时就已经成立,但是小于d.

3)控制小于21252.这也是测试出来的.程序总是不对,百度后找到一篇文章,一组数据,暂不详述

测试数据:

0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
5 10 15 300
24 29 34 0
24 29 34 1
24 29 34 2
-1 -1 -1 -1

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.
Case 7: the next triple peak occurs in 20934 days.
Case 8: the next triple peak occurs in 1 days.
Case 9: the next triple peak occurs in 21252 days.
Case 10: the next triple peak occurs in 21251 days.

心得:

本以为很简单的题目,做了很久.

百度后才发现原来这是老祖宗的东西.--中国剩余定理  韩信点兵等.

一篇文章:http://blog.163.com/grass_lh/blog/static/31039454200872795233437/

关于剩余定理,维基上的解释比百度百科好多了.

维基:

http://zh.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E5%89%A9%E4%BD%99%E5%AE%9A%E7%90%86

看来,祖宗的东西丢不得吖......