免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 递推算法,没看出递推

本帖最后由 realnumber 于 2019-8-26 18:35 编辑

极值问题
时间限制: 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
提示:递推算法
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

本帖最后由 hejoseph 于 2019-8-26 15:00 编辑

其实就是一个 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$ 是任意正整数。由此就能写出递归公式了。

TOP

题目中
$(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}
\]

TOP

那不是斐波那契数列的性质么?可以考虑构造斐波那契数列

TOP

是线性递归关系,但不是 Fibonacci 数列那种

TOP

由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)
有没其他途径得到这个关系或其它关系等

TOP

回复 6# realnumber


    应该没有了,数论中的基础

TOP

本帖最后由 realnumber 于 2019-8-30 07:54 编辑

https://baike.baidu.com/item/%E4 ... 11029962?fr=aladdin
$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}$).

TOP

4楼  说得对
可以用数学归纳法证明,斐波那契数列连续两项符合1楼递推关系
假设m,n(m<n)可以,则n,m+n也符合

反过来 可以用无穷递降法证明,符合递推关系,就是斐波那契数列数列中连续两项.
若m,n(m<n)可以,则n-m,m也一定符合,直至为0,1

TOP

返回列表 回复 发帖