首页 > 代码库 > 递推第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数列。
看了看标准程序,和我的也是大同小异,就不再给出。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。