递推算法,没看出递推
[i=s] 本帖最后由 realnumber 于 2019-8-26 18:35 编辑 [/i]极值问题
时间限制: 1 Sec 内存限制: 128 MB
题目描述
已知m,n为整数,且满足下列两个条件:
①m,n∈{1,2, …,k},即1≤m,n≤k;
②$(n^2-m*n-m^2)^2=1$.
编程输入正整数k($1≤k≤10^9$),求一组满足上述两个条件的m,n,并且使$m^2+n^2$的值最大。(p163)
输入:
正整数k。
输出:
满足上述两个条件的m,n。
样例输入
1995
样例输出
m=987
n=1597
提示:递推算法 [i=s] 本帖最后由 hejoseph 于 2019-8-26 15:00 编辑 [/i]
其实就是一个 Pell 方程的求解问题:$n^2-mn-m^2=\pm 1$,即 $(2n-m)^2-5m^2=\pm 4$。$m$ 是偶数,方程变为 $(n-m_1)^2-5m_1^2=\pm 1$,其中 $m=2m_1$,这是一般的 Pell 方程。若 $m$ 是奇数,则 $2n-m$ 和 $m$ 必定互素。
设 $D$ 是非完全平方数的正整数,则
Pell 方程 $x^2-Dy^2=1$ 的通解是 $x+\sqrt Dy=\left(x+\sqrt Dy_0\right)^k$,其中 $(x_0,y_0)$ 是满足 $x_0>0$,$y_0>0$ 的最小解,$k$ 是任意正整数。
Pell 方程 $x^2-Dy^2=-1$ 的通解是 $x+\sqrt Dy=\left(x+\sqrt Dy_0\right)^{2k-1}$,其中 $(x_0,y_0)$ 是满足 $x_0>0$,$y_0>0$ 的最小解,$k$ 是任意正整数。
Pell 方程 $Ax^2-By^2=4$($A$、$B$ 是正整数,且不同时为完全平方数)满足$x>0$,$y>0$,$x$、$y$ 互素的通解是
\[
\frac{\sqrt Ax+\sqrt By}{2}=\left(\frac{\sqrt Ax_0+\sqrt By_0}{2}\right)^{6k-5}
\]
其中 $(x_0,y_0)$ 是满足 $x_0>0$,$y_0>0$ 的最小解,$k$ 是任意正整数。由此就能写出递归公式了。 题目中
$(n-m_1)^2-5m_1^2=1$ 的通解是
\[
n-m_1+\sqrt 5m_1=\left(9+4\sqrt 5\right)^k
\]
$(n-m_1)^2-5m_1^2=-1$ 的通解是
\[
n-m_1+\sqrt 5m_1=\left(2+\sqrt 5\right)^{2k-1}
\]
$(2n-m)^2-5m^2=4$ 的通解是
\[
\frac{2n-m+\sqrt 5m}{2}=\left(\frac{3+\sqrt 5}{2}\right)^{6k-5}
\]
$(2n-m)^2-5m^2=-4$ 的通解是
\[
\frac{2n-m+\sqrt 5m}{2}=\left(\frac{1+\sqrt 5}{2}\right)^{6k-5}
\] 那不是斐波那契数列的性质么?可以考虑构造斐波那契数列 是线性递归关系,但不是 Fibonacci 数列那种 由3楼
$(n-m)^2-5m^2=1$ 的通解是
\[n-m+\sqrt 5m=\left(9+4\sqrt 5\right)^k\]
k,k-1对应的解为$(n_1,m_1),(n_2,m_2),$则由上面通解得
$n_1=13n_2+16m_2,m_1=4n_2+5m_2$
检验了(1,0)到(13,4)
有没其他途径得到这个关系或其它关系等 [b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=33546&ptid=6521]6#[/url] [i]realnumber[/i] [/b]
应该没有了,数论中的基础 [i=s] 本帖最后由 realnumber 于 2019-8-30 07:54 编辑 [/i]
[url]https://baike.baidu.com/item/%E4%BD%A9%E5%B0%94%E6%96%B9%E7%A8%8B/11029962?fr=aladdin[/url]
$x_n=2x_1x_{n-1}-x_{n-2}$
$y_n=2x_1y_{n-1}-y_{n-2}$
其中$(x_1,y_1)$是$x^2-Dy^2=1$的最小正整数解.
按上面思路编程就很“数学”了,耗时近于O($log_{x_1}k$).
另:可以按
for n=k downto 1 do { m,n关系写为一元二次方程求根公式,m为整数 },直接搜索,找到就是$m^2+n^2$最大,猜是也能通过或大部分通过,耗时最差O($x_{n+1}-x_{n}$). 4楼 说得对
可以用数学归纳法证明,斐波那契数列连续两项符合1楼递推关系
假设m,n(m<n)可以,则n,m+n也符合
反过来 可以用无穷递降法证明,符合递推关系,就是斐波那契数列数列中连续两项.
若m,n(m<n)可以,则n-m,m也一定符合,直至为0,1
页:
[1]