首页 > 代码库 > 递推第3题—极值问题

递推第3题—极值问题

[问题描述]已知m,n为整数,且满足下列两个条件:
                 ①m,n∈{1,2,…,k},即1<=m,n<=k

                 ②(n2-mn-m2)2=1

你的任务是:编程由键盘输入正整数k(1<=k<=109),求一组满足上述两个条件的m,n,并且使m2+n2的值最大。例如,我们从键盘输入k=1995,则输出m=987,n=1597。

[问题分析]

典型的数学题……我们可以就条件②出发利用求根公式加上限制条件去解方程,一定能得到正确的解,但是数据范围是109,这种方法只能承受105,用此方法必定超时。

我们可以对这个式子先做一下数学变换:

   (n2-mn-m2)2

=(m2+nm-n2)2

=[(n+m)2-n(n+m)-n2]2

=[(n’)2-m’n’-(m’)2]2

其中n’=m+n,m’=n。虽然从形式上看表达式并没有什么变化,但从上述数学变换式可以看出:如果m和n为一组满足条件的解,那么m’和n‘也是一组满足条件的解,于是可以用迭代法求解。因此我们可以将所有满足条件的m和n按递增顺序排列出来

令m=1,n=1,发现满足条件,即为问题的一组最小解。

我又接着写了一个小程序找了找k=100时的解:

uses math;var m,n:integer;begin  for m:=1 to 100 do     for n:=1 to 100 do       if (n**2-m*n-m**2)**2=1 then writeln(m, ,n);end.

发现输出是这样的:

1 11 22 33 55 88 1313 2121 3434 5555 89

将其按递增顺序排列出来就是1,1,2,3,5,8,……,于是我发现这正是一个Fibonacci数列。

于是一切都变得简单了。

var k,m,n,t:longint;begin  readln(k);  m:=1;n:=1;  repeat    t:=m+n;    if t<=k then begin m:=n;n:=t; end;  until t>k;  writeln(m, ,n);end;

又是一个令人惬意的短代码,这道题重要的不是代码,而是要转化代数式以及联想到Fibonacci数列。

看了看标准程序,和我的也是大同小异,就不再给出。