【问题描述】
已知m、n为整数,且满足下列两个条件:
① m、n∈{1,2,…,k},即1≤m,n≤k,(1≤k≤109)。
②(n2-m*n-m2)2=1
你的任务是:编程输入正整数k,求一组满足上述两个条件的m、n,并且使m2+n2的值最大。例如,从键盘输入k=1995,则输出:m=987 n=1597。
【输入样例】
1995
【输出样例】
m=987
n=1597
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsISPrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdsATOfd3bkFGazxCMx8VesATMfhHLlN3XnxCMwEzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5SMxYWZ4EzYiZzM1ATYkZDOhRzMkRWYxUWNyUWYwUWM28CX3AzLchDMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjL3M3Lc9CX6MHc0RHaiojIsJye.png)
代码如下:
View Code
批注:该算法确实挺好,简洁、高效率,但是有一个问题比较明显,那就是当k的值达到10^9时,for循环内,m从k开始向1遍历。当m的值取10^9时,计算delt的时候,m^2会溢出。而且并非只有当k达到10^9才会有这个问题,当k达到10^5时就会出现这个问题。想要自己写一个函数去实现高精度数的开平方根,似乎也不是这么容易。所以,可以看看下面的递推算法。
标准答案是:
批注:一开始阅读该算法,实在无法理解为何会是跟斐波那契数列一样的规律。后来查资料,阅读理解,终于看懂。下面做一个记录。