题解：SP13838 M_SEQ - Mosty! Find Gn

1.题目大意

f(n) = 8 + \frac{(n-2)^2}{n^2} f(n-2), \quad f(1) = f(2) = 8.

以及

g(n) = \sqrt{ f(n) - \frac{(n-1)^2}{n^2} f(n-1) + \frac{1}{n^2} }.

求

g(n)

的通项

2.化简 $f(n)$

递推只关联

f(n)

与

f(n-2)

，

分

n

为奇数和偶数讨论。

设

h(n) = f(n) - 8

，则

h(n) = \frac{(n-2)^2}{n^2} h(n-2) + \frac{(n-2)^2}{n^2} \cdot 8.

偶数情况 $n = 2k$

初始

f(2) = 8

，所以

h(2) = 0

。

h(2k) = \frac{(k-1)^2}{k^2} h(2k-2) + 8 \cdot \frac{(k-1)^2}{k^2}.

令

a_k = h(2k)

，则

a_1 = 0

，

a_k = \frac{(k-1)^2}{k^2} a_{k-1} + 8 \cdot \frac{(k-1)^2}{k^2}.

两边乘以

k^2

：

k^2 a_k = (k-1)^2 a_{k-1} + 8 (k-1)^2.

令

b_k = k^2 a_k

，

则

b_1 = 1^2 \cdot a_1 = 0

，

b_k = b_{k-1} + 8(k-1)^2.

所以

b_k = 8 \sum_{j=1}^{k-1} j^2 = 8 \cdot \frac{(k-1)k(2k-1)}{6}.

所以

a_k = \frac{b_k}{k^2} = \frac{8(k-1)k(2k-1)}{6 k^2} = \frac{4(k-1)(2k-1)}{3k}.

所以

f(2k) = 8 + \frac{4(k-1)(2k-1)}{3k} = \frac{24k + 4(k-1)(2k-1)}{3k} = \frac{4(2k+1)(k+1)}{3k}.

奇数情况 $n = 2k+1$

初始

f(1) = 8

，所以

h(1) = 0

。

h(2k+1) = \frac{(2k-1)^2}{(2k+1)^2} h(2k-1) + 8 \cdot \frac{(2k-1)^2}{(2k+1)^2}.

令

c_k = h(2k+1)

，

c_0 = h(1) = 0

，

c_k = \frac{(2k-1)^2}{(2k+1)^2} c_{k-1} + 8 \cdot \frac{(2k-1)^2}{(2k+1)^2}.

两边乘以

(2k+1)^2

：

(2k+1)^2 c_k = (2k-1)^2 c_{k-1} + 8 (2k-1)^2.

令

d_k = (2k+1)^2 c_k

，则

d_0 = 1^2 \cdot c_0 = 0

，

d_k = d_{k-1} + 8 (2k-1)^2.

于是

d_k = 8 \sum_{j=1}^{k} (2j-1)^2.

已知

\sum_{j=1}^k (2j-1)^2 = \frac{k(4k^2 - 1)}{3}

，

所以

d_k = 8 \cdot \frac{k(4k^2 - 1)}{3}.

所以

c_k = \frac{d_k}{(2k+1)^2} = \frac{8k(4k^2 - 1)}{3 (2k+1)^2}.

所以

f(2k+1) = 8 + c_k = 8 + \frac{8k(4k^2 - 1)}{3 (2k+1)^2}.

因此

f(2k+1) = \frac{8(k+1)(2k+3)}{3(2k+1)}.

总结：

f(n) = \begin{cases} \dfrac{4(2k+1)(k+1)}{3k}, & n=2k, \\ \dfrac{8(k+1)(2k+3)}{3(2k+1)}, & n=2k+1. \end{cases}

3.计算 $g(n)$

g(n) = \sqrt{ f(n) - \frac{(n-1)^2}{n^2} f(n-1) + \frac{1}{n^2} }.

$n=2k$ 情况

f(2k) = \frac{4(2k+1)(k+1)}{3k}

，

f(2k-1) = \frac{8k(2k+1)}{3(2k-1)}

f(2k) - \frac{(2k-1)^2}{(2k)^2} f(2k-1) = \frac{4(2k+1)(k+1)}{3k} - \frac{(2k-1)^2}{4k^2} \cdot \frac{8k(2k+1)}{3(2k-1)}.

于是

f(2k) - \frac{(2k-1)^2}{(2k)^2} f(2k-1) = \frac{2(2k+1)}{k}.

因此

g(2k) = \sqrt{ \frac{2(2k+1)}{k} + \frac{1}{4k^2} }.

$n=2k+1$ 情况

f(2k+1) = \frac{8(k+1)(2k+3)}{3(2k+1)}

，

f(2k) = \frac{4(2k+1)(k+1)}{3k}

。

f(2k+1) - \frac{(2k)^2}{(2k+1)^2} f(2k) = \frac{8(k+1)(2k+3)}{3(2k+1)} - \frac{4k^2}{(2k+1)^2} \cdot \frac{4(2k+1)(k+1)}{3k}.

于是

g(2k+1) = \sqrt{ \frac{8(k+1)}{2k+1} + \frac{1}{(2k+1)^2} }.

4. $g(n)$ 公式

偶数

n=2k

：

g(2k) = \sqrt{ \frac{2(2k+1)}{k} + \frac{1}{4k^2} }.

奇数

n=2k+1

：

g(2k+1) = \sqrt{ \frac{8(k+1)}{2k+1} + \frac{1}{(2k+1)^2} }.

用

n

表示：

若 $n$ 偶， $k = n/2$ ： $g(n) = \sqrt{ \frac{2(n+1)}{n/2} + \frac{1}{n^2} } = \sqrt{ \frac{4(n+1)}{n} + \frac{1}{n^2} }.$
若 $n$ 奇， $n=2k+1$ ， $k=(n-1)/2$ ： $g(n) = \sqrt{ \frac{8\left(\frac{n-1}{2}+1\right)}{n} + \frac{1}{n^2} } = \sqrt{ \frac{8\cdot \frac{n+1}{2}}{n} + \frac{1}{n^2} } = \sqrt{ \frac{4(n+1)}{n} + \frac{1}{n^2} }.$

奇偶情况一致

g(n) = \sqrt{ \frac{4(n+1)}{n} + \frac{1}{n^2} } = 2 + \frac{1}{n}.

5.代码

很简单了

CPP

#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
int T, n;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while(T --) {
        cin >> n;
        cout << fixed << setprecision(8) << (2.0 + 1.0 / (double) n); 
    } 
	return 0;
}

题解：SP13838 M_SEQ - Mosty! Find Gn

文章操作

1.题目大意

2.化简 $f(n)$

偶数情况 $n = 2k$

奇数情况 $n = 2k+1$

3.计算 $g(n)$

$n=2k$ 情况

$n=2k+1$ 情况

4. $g(n)$ 公式

5.代码

相关推荐

评论

题解：SP13838 M_SEQ - Mosty! Find Gn

文章操作

1.题目大意

2.化简 f(n)f(n)f(n)

偶数情况 n=2kn = 2kn=2k

奇数情况 n=2k+1n = 2k+1n=2k+1

3.计算 g(n)g(n)g(n)

n=2kn=2kn=2k 情况

n=2k+1n=2k+1n=2k+1 情况

4. g(n)g(n)g(n) 公式

5.代码

相关推荐

评论

2.化简 $f(n)$

偶数情况 $n = 2k$

奇数情况 $n = 2k+1$

3.计算 $g(n)$

$n=2k$ 情况

$n=2k+1$ 情况

4. $g(n)$ 公式