Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
不过确实有他的国人之处,也就算拉。第这个算法比较欣赏!In Reply To:0MS 的程序,运用辗转相除法联立方程直接求解,最多一层循环 Posted by:2_080310236 at 2006-03-04 21:58:46 > #include "iostream.h" > #include "math.h" > > void Get_Special_Solution(int a,int b,int N,int x[2]) > { > int x1[2]={0},x2[2]={0},temp,flag1=1,flag2=1; > if(N<0) {a=-a;b=-b;N=-N;} > if(N==0) {x[0]=-b,x[1]=a;return;} > if(abs(a)<abs(b)) {temp=a;a=b;b=temp;} > if(a>0 && b<0) {b=-b;flag2=-1;} > else if(a<0 && b>0) {a=-a;flag1=-1;} > else if(a<0 && b<0) {a=-a;b=-b;} > int m=a,n=b,q1,q2,r1,r2,temp1,temp2; > q1=a/b,r1=a%b;q2=n/r1;r2=b%r1; > m=r1;n=r2; > x1[0]=1, x1[1]=-q1; //r1=a-q1*b; > x2[0]=-q2, x2[1]=q1*q2+1; //r2=b-q2*r1;两个递推式来实现辗转相除法的求解过程 > if(!r2) {x[0]=flag1*x1[0];x[1]=flag2*x1[1];return;} > while(r2!=1) > { > temp1=x1[0];temp2=x1[1]; > x1[0]=x2[0];x1[1]=x2[1]; > q2=m/n;r2=m%n; > x2[0]=-q2*x2[0]+temp1; > x2[1]=-q2*x2[1]+temp2; > m=n;n=r2; > } > x[0]=flag1*x2[0];x[1]=flag2*x2[1]; > x[0]*=N;x[1]*=N; > } > > void Show_Equation_Solve(int a[]) > { > int x[2],y[2],z[2],k1,k2; > Get_Special_Solution(28,-23,a[0]-a[1],x); > while(x[0]>0 && x[1]>0) {x[0]-=23;x[1]-=28;} > while(x[0]<=0||x[1]<=0) {x[0]+=23;x[1]+=28;} > Get_Special_Solution(33,-28,a[1]-a[2],y); > while(y[0]>0 && y[1]>0) {y[0]-=28;y[1]-=33;} > while(y[0]<=0||y[1]<=0) {y[0]+=28;y[1]+=33;} > if(x[0]!=y[1]) Get_Special_Solution(33,-23,x[0]-y[1],z); > while(z[0]>0 && z[1]>0) {z[0]-=23;z[1]-=33;} > while(z[0]<=0||z[1]<=0) {z[0]+=23;z[1]+=33;} > a[0]=28*z[1]+x[1],a[1]=23*z[1]+x[0],a[2]=28*z[0]+y[0]; > } > > void main() > { > int i=0,m,days; > int a[4]; > while(1) > { > cin>>a[0]>>a[1]>>a[2]>>a[3]; > if(a[0]==a[1] && a[1]==a[2] && a[2]==a[3] && a[3]==-1) break; > m=a[0]; > Show_Equation_Solve(a); > cout<<"Case "<<++i<<": the next triple peak occurs in "<<(a[0]*23+21252+m-a[3]-1)%21252+1<<" days."<<endl; > } > } > Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator