极值问题（acms）-白红宇

【问题描述】

已知m、n为整数，且满足下列两个条件：

① m、n∈{1，2，…，k}，即1≤m，n≤k，（1≤k≤10⁹）。

②（n²－m*n－m²）²＝1

你的任务是：编程输入正整数k，求一组满足上述两个条件的m、n，并且使m²＋n²的值最大。例如，从键盘输入k=1995，则输出：m=987 n=1597。

【输入样例】

1995

【输出样例】

m=987

n=1597

代码如下：

1     long m,n,k; 2     double delt1,delt2,n1,n2; 3     scanf("%d",&k); 4     for(m=k;m>=1;m--) 5     { 6         delt1=sqrt(5*m*m+4); 7         n1=(m+delt1)/2; 8         n=n1; 9         if(n==n1&&n<=k) break;10 11         delt2=sqrt(5*m*m-4);12         n2=(m+delt2)/2;13         n=n2;14         if(n==n2&&n<=k) break;15     }16     printf("m=%d\nn=%d\n",m,n);

View Code

批注：该算法确实挺好，简洁、高效率，但是有一个问题比较明显，那就是当k的值达到10^9时，for循环内，m从k开始向1遍历。当m的值取10^9时，计算delt的时候，m^2会溢出。而且并非只有当k达到10^9才会有这个问题，当k达到10^5时就会出现这个问题。想要自己写一个函数去实现高精度数的开平方根，似乎也不是这么容易。所以，可以看看下面的递推算法。

标准答案是：

代码如下：

1         int n=1,m=1,k,t; 2     cin>>k; 3     do 4     { 5         t=n+m; 6         if(t<=k) 7         { 8             m=n; 9                 n=t;10         }11     }12     while(t<=k);13     cout<<"m="<
      
       <
       
        <<"n="<

View Code

批注：一开始阅读该算法，实在无法理解为何会是跟斐波那契数列一样的规律。后来查资料，阅读理解，终于看懂。下面做一个记录。