Trouvez le terme général de la séquence de Fibonacci étendue (séquence k-Bonatch: somme des k termes immédiatement précédents) en utilisant l'algèbre linéaire et Python

(Il semble que la formule ne puisse pas être affichée à partir d'un smartphone, donc dans ce cas, veuillez la voir à partir d'un PC, etc. Je suis désolé.)

Qu'est-ce qu'une séquence de Fibonacci étendue?

La séquence de Fibonacci est une séquence qui ajoute les deux termes précédents pour créer le terme suivant. Exprimé comme une expression

\begin{cases}
\begin{align}
a_{n+2} &= a_{n+1} + a_{n}\\ 
a_0 &= 0\\
a_1 &= 1
\end{align}
\end{cases}

Ce sera. La séquence de Fibonacci étendue est l'extension de celle-ci au terme suivant, qui est la somme des termes $ k $ précédents. J'ai cherché le nom, mais je ne l'ai pas trouvé, alors je l'appellerai $ k $ -Bonatch sequence. Exprimé comme une expression

\begin{cases}
\begin{align}
a_{n+k} &= a_{n+k-1}+a_{n+k-2}+\dots+a_{n}\\
&=\displaystyle \sum_{i=n}^{n+k-1}a_i
\\ a_0 &= a_1 = \dots = a_{k-2} = 0\\a_{k-1} &= 1
\end{align}
\end{cases}

Ce sera. Dans l'article précédent (Trouver les termes généraux d'une séquence tribonatch avec algèbre linéaire et Python), nous avons traité une séquence tribonatch avec $ k = 3 $. Cette fois, nous allons l'étendre.

Préparation

(C'est presque la même chose que Calculer le terme général de la séquence Tribonacci avec l'algèbre linéaire et Python, vous pouvez donc l'ignorer.)

Soit $ V $ l'espace formé par une suite de nombres réels qui satisfont l'expression graduelle. Étant donné le premier $ k $ terme $ a_0, a_1, \ dots, a_ {k-1} $ dans la séquence $ \ {a_n } $, la séquence $ \ {a_n \ in $ n \ geq k $ } $ Est déterminé de manière unique.

\begin{align}
\boldsymbol{v_0}&=\{\overbrace{1,0,0,\dots,0}^{k pièces},1,\dots \}\\ 
\boldsymbol{v_1}&=\{0,1,0,\dots,0,1,\dots \}\\
& \vdots \\
\boldsymbol{v_{k-1}}&=\{0,0,0,\dots,1,1,\dots\}
\end{align}

ça ira. Pour $ c_0, c_1, \ dots, c_ {k-1} \ in \ mathbb {C} $, $ c_0 \ boldsymbol {v_0} + c_1 \ boldsymbol {v_1} + \ dots + c_ {k-1} Si \ boldsymbol {v_ {k-1}} = \ boldsymbol {0} $ tient,

c_0\{1,0,0,\dots \}+c_1\{0,1,0,\dots \}+\dots+c_{k-1}\{0,\dots,1,\dots \}\\=\{c_0,c_1,\dots,c_{k-1},\dots \}=\{0,0,\dots,0,\dots \}

Par conséquent, $ c_0 = c_1 = \ dots = c_ {k-1} = 0 $. Par conséquent, $ \ boldsymbol {v_0}, \ boldsymbol {v_1}, \ dots, \ boldsymbol {v_ {k-1}} $ sont connus pour être linéairement indépendants.

prochain,

\boldsymbol{a}= \{ a_0,a_1,\dots,a_{k-1},\dots \}

Est une source arbitraire de $ V $

\begin{align}
\boldsymbol{a}&=\{ a_0,0,0,\dots \}+\{0,a_1,0,\dots \} +\dots+\{0,\dots,0,a_{k-1},\dots \}  \\
 &=a_0\{1,0,0,\dots \}+a_1\{0,1,0,\dots \}+\dots+a_{k-1}\{0,\dots,0,1,\dots \}  \\
&=a_0\boldsymbol{v_0}+a_1\boldsymbol{v_1}+\dots+a_{k-1}\boldsymbol{v_{k-1}}
\end{align}

Il peut être représenté par une combinaison linéaire de $ \ boldsymbol {v_0}, \ boldsymbol {v_1}, \ dots, \ boldsymbol {v_ {k-1}} $. Ainsi $ \ boldsymbol {v_0}, \ boldsymbol {v_1}, \ dots, \ boldsymbol {v_ {k-1}} $ générera $ V $.

D'après ce qui précède, $ \ boldsymbol {v_0}, \ boldsymbol {v_1}, \ dots, \ boldsymbol {v_ {k-1}} $ est linéairement indépendant et génère $ V $, donc c'est la base de $ V $.

Maintenant, map $ f: V \ rightarrow V $

f(\{ a_n\}_{n=0}^{\infty})=\{ a_n\}_{n=1}^{\infty}

ça ira. $ \ boldsymbol {a} = \ {a_0, a_1, a_2, \ dots } \ in V $, $ f (\ boldsymbol {a}) = \ {a_1, a_2, a_3, \ dots } $ Il satisfait l'expression graduelle, donc c'est $ f (\ boldsymbol {a}) \ in V $.

\boldsymbol{a}=\{ a_n\}_{n=0}^{\infty}\in V \\
\boldsymbol{b}=\{ b_n\}_{n=0}^{\infty}\in V \\
c\in \mathbb{C}

Puis

f(\boldsymbol{a}+\boldsymbol{b})=f(\{ a_n+b_n\}_{n=0}^{\infty})=\{ a_n+b_n\}_{n=1}^{\infty}=\{ a_n\}_{n=1}^{\infty}+\{ b_n\}_{n=1}^{\infty}=f(\boldsymbol{a})+f(\boldsymbol{b})\\
f(c\boldsymbol{a})=f(c\{ a_n\}_{n=0}^{\infty})=c\{ a_n\}_{n=1}^{\infty}=cf(\boldsymbol{a})

Est vrai, donc $ f $ est une transformation linéaire de $ V $.

Représenter l'expression graduelle sous forme de matrice

Concernant $ \ boldsymbol {v_0}, \ boldsymbol {v_1}, \ dots, \ boldsymbol {v_ {k-1}} $

\begin{align}
f(\boldsymbol{v_0})&=\{0,0,\dots,0,1,\dots \}=\boldsymbol{v_{k-1}}\\
f(\boldsymbol{v_1})&=\{1,0,\dots,0,1,\dots \}=\boldsymbol{v_0}+\boldsymbol{v_{k-1}}\\
f(\boldsymbol{v_2})&=\{0,1,\dots,0,1,\dots \}=\boldsymbol{v_1}+\boldsymbol{v_{k-1}}\\
\vdots \\
f(\boldsymbol{v_{k-1}})&=\{0,0,\dots,1,1,\dots \}=\boldsymbol{v_{k-2}}+\boldsymbol{v_{k-1}}
\end{align}

Alors

[f(\boldsymbol{v_0})\quad f(\boldsymbol{v_1})\quad f(\boldsymbol{v_2}) \quad \cdots \quad f(\boldsymbol{v_{k-1}})]=
[\boldsymbol{v_0}\ \boldsymbol{v_1}\ \boldsymbol{v_2} \cdots \boldsymbol{v_{k-1}}]
\begin{bmatrix}
0 & 1 & 0 & 0 & \cdots & 0\\
0 & 0 & 1 & 0 & \cdots & 0\\
0 & 0 & 0 & 1 & \cdots & 0\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & 0 & \cdots & 1\\
1 & 1 & 1 & 1 & \cdots & 1
\end{bmatrix}

Peut être exprimé comme. Par conséquent, la matrice de représentation pour la base $ \ boldsymbol {v_0}, \ boldsymbol {v_1}, \ dots, \ boldsymbol {v_ {k-1}} $ de $ f $ est

\overbrace{
\begin{bmatrix}
0 & 1 & 0 & 0 & \cdots & 0\\
0 & 0 & 1 & 0 & \cdots & 0\\
0 & 0 & 0 & 1 & \cdots & 0\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & 0 & \cdots & 1\\
1 & 1 & 1 & 1 & \cdots & 1
\end{bmatrix}
}^{k lignes k colonnes}

est. Soit cette matrice de représentation $ A $.

Relation entre valeur propre et rapport commun

(C'est la même chose que Calculer le terme général de la séquence Tribonacci avec l'algèbre linéaire et Python, vous pouvez donc l'ignorer.)

\boldsymbol{p}=\{ r^{n} \}_{n=0}^{\infty}=\{1,r,r^2,\dots \}

Appartient à $ V $

f(\boldsymbol{p})=f(\{ r^{n} \}_{n=0}^{\infty})=\{ r^{n} \}_{n=1}^{\infty}=\{ r^{n+1} \}_{n=0}^{\infty}=r\{ r^{n} \}_{n=0}^{\infty}=r\boldsymbol{p}

Par conséquent, $ \ boldsymbol {p} $ devient un vecteur propre avec une valeur propre de $ r $. Inversement, à partir de l'équation ci-dessus, on peut voir que le vecteur propre de la valeur propre $ r $ de $ f $ est une séquence de rapport égal du rapport commun $ r $. Par conséquent, nous savons que le rapport commun et la valeur propre sont égaux.

Trouvez la valeur unique

Trouvez la valeur unique de $ f $. La polynésie propre de $ A $ utilise $ I $ comme matrice unitaire.

\begin{align}
\varphi_k(\lambda)&=|A-\lambda I|\\
&=\begin{vmatrix}
-\lambda & 1 & 0 & 0 & \cdots & 0\\
0 & -\lambda & 1 & 0 & \cdots & 0\\
0 & 0 & -\lambda & 1 & \cdots & 0\\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & 0 & \cdots & 1\\
1 & 1 & 1 & 1 & \cdots & 1-\lambda
\end{vmatrix}
\end{align}

Extension des cofacteurs le long de la première colonne

\begin{align}
\varphi_k&=(-1)^{1+1}(-\lambda) \begin{vmatrix}
-\lambda & 1 & 0 & \cdots & 0\\
0 & -\lambda & 1 & \cdots & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \cdots & 1\\
1 & 1 & 1 & \cdots & 1-\lambda
\end{vmatrix} + (-1)^{k+1}\cdot 1 \begin{vmatrix}
1 & 0 & 0 & \cdots & 0\\
-\lambda & 1 & 0 & \cdots & 0\\
0 & -\lambda & 1 & \cdots & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \cdots & 1\\
\end{vmatrix} \\
&=-\lambda \varphi_{k-1} - (-1)^{k}\cdot 1\cdot 1\\
&=-\lambda \varphi_{k-1} - (-1)^{k}
\end{align}

Peut être exprimé comme une expression graduelle. Diviser les deux côtés par $ (-1) ^ k $

\begin{align}
\frac{\varphi_k}{(-1)^k} &= -\lambda \frac{\varphi_{k-1}}{(-1)^k} - 1\\
&=\lambda \frac{\varphi_{k-1}}{(-1)^{k-1}} - 1
\end{align}

Si vous définissez $ b_k = \ displaystyle \ frac {\ varphi_k} {(-1) ^ k} $,

\begin{align}
b_k &= \lambda b_{k-1} - 1\\
b_k - \frac{1}{\lambda - 1} &= \lambda \left(b_{k-1} - \frac{1}{\lambda - 1}\right)\\
&=\cdots \\
&= \lambda^{k-2}\left(b_{2} - \frac{1}{\lambda - 1}\right)
\end{align}

Et le premier terme est

\begin{align}
b_2- \frac{1}{\lambda - 1} &= \displaystyle \frac{\varphi_2}{(-1)^2} - \frac{1}{\lambda - 1}\\
&=\varphi_2 - \frac{1}{\lambda - 1}\\
&=\begin{vmatrix}
-\lambda & 1 \\
1 & 1-\lambda
\end{vmatrix}- \frac{1}{\lambda - 1}\\
&=\lambda^2 - \lambda - 1- \frac{1}{\lambda - 1}\\
&=\frac{\lambda^3-2\lambda^2}{\lambda-1}
\end{align}

est. Donc,

\begin{align}
b_k &- \frac{1}{\lambda - 1}= \lambda^{k-2} \frac{\lambda^3-2\lambda^2}{\lambda-1}\\
b_k &= \frac{\lambda^{k+1}-2\lambda^k}{\lambda-1} + \frac{1}{\lambda - 1} \\
&= \frac{\lambda^{k+1}-2\lambda^k+1}{\lambda-1}\\
&=\lambda^k - \lambda^{k-1} - \lambda^{k-2} - \dots - \lambda^2 - \lambda - 1\quad (\parce que la méthode d'assemblage)
\end{align}

A été dérivée. Vous pouvez voir que l'équation $ \ varphi_k (\ lambda) = (-1) ^ k b_k = 0 $ équivaut à $ b_k = 0 $.

Cependant, $ b_k = 0 $ ne peut pas être résolu facilement. Dans un chapitre ultérieur, nous utiliserons un ordinateur pour le calculer numériquement.

Si $ k $ des solutions sont $ \ lambda_0, \ lambda_1, \ dots, \ lambda_ {k-1} $, alors les vecteurs propres correspondant à chaque solution sont

\boldsymbol{u_0}=\{ \lambda_0^{n} \}_{n=0}^{\infty}\\
 \boldsymbol{u_1}=\{ \lambda_1^{n} \}_{n=0}^{\infty}\\
\vdots \\
 \boldsymbol{u_{k-1}}=\{ \lambda_{k-1}^{n} \}_{n=0}^{\infty}

Appartient à $ V $. Ceux-ci sont linéairement indépendants car ce sont des vecteurs propres correspondant à différentes valeurs propres de $ f $, en supposant que $ \ lambda_0, \ lambda_1, \ dots, \ lambda_ {k-1} $ sont tous différents. De plus, $ \ dim V = k $. Par conséquent, $ \ boldsymbol {u_0}, \ boldsymbol {u_1}, \ dots, \ boldsymbol {u_ {k-1}} $ est la base de $ V $.

Déterminer le coefficient

De ce qui précède, il y a un certain $ c_0, c_1, \ dots, c_ {k-1} $,

\boldsymbol{a_n}=c_0\boldsymbol{u_0}+c_1\boldsymbol{u_1}+\dots+c_{k-1}\boldsymbol{u_{k-1}}

Parce qu'il peut être exprimé comme

\begin{align}
\boldsymbol{a_n}&=c_0\boldsymbol{u_0}+c_1\boldsymbol{u_1}+\dots+c_{k-1}\boldsymbol{u_{k-1}}\\
\Leftrightarrow \{a_0,a_1,\dots,a_{k-1},\dots \}&=c_0\{ \lambda_0^{n} \}_{n=0}^{\infty}+c_1\{ \lambda_1^{n} \}_{n=0}^{\infty}+\dots+c_{k-1}\{ \lambda_{k-1}^{n} \}_{n=0}^{\infty}\\
\Leftrightarrow \{0,0,\dots,1,\dots \}&=c_0\{ 1,\lambda_0,\dots,\lambda_0^{k-1},\dots \}+c_1\{1,\lambda_1,\dots,\lambda_1^{k-1},\dots \}+\dots+c_{k-1}\{ 1,\lambda_{k-1},\dots,\lambda_{k-1}^{k-1},\dots\} \\
\Leftrightarrow \{0,0,\dots,1,\dots \}&=\{ c_0+c_1+\dots+c_{k-1},\ c_0\lambda_0+c_1\lambda_1+\dots+c_{k-1}\lambda_{k-1},\dots, c_0\lambda_0^{k-1}+c_1\lambda^{k-1}+\dots+c_{k-1}\lambda^{k-1}, \dots\}
\end{align}

Exprimant cela sous forme de matrice,

\begin{bmatrix}
1 & 1 & 1 & \cdots & 1\\
\lambda_0 & \lambda_1 & \lambda_2 & \cdots & \lambda_{k-1} \\
\lambda_0^2 & \lambda_1^2 & \lambda_2^2 & \cdots & \lambda_{k-1}^2\\
\vdots & \vdots & \vdots & \ddots & \vdots  \\
\lambda_0^{k-1} & \lambda_1^{k-1} & \lambda_2^{k-1} & \cdots & \lambda_{k-1}^{k-1}
\end{bmatrix}
\begin{bmatrix}
c_1 \\ c_2 \\ c_3 \\ \vdots \\ c_{k-1}
\end{bmatrix}
=
\begin{bmatrix}
0 \\ 0 \\ 0 \\ \vdots \\ 1
\end{bmatrix}

est. L'expression de matrice pour la matrice de gauche est l'expression de matrice de Van der Monde $ V_k $,

V_k = \begin{vmatrix}
1 & 1 & 1 & \cdots & 1\\
\lambda_0 & \lambda_1 & \lambda_2 & \cdots & \lambda_{k-1} \\
\lambda_0^2 & \lambda_1^2 & \lambda_2^2 & \cdots & \lambda_{k-1}^2\\
\vdots & \vdots & \vdots & \ddots & \vdots  \\
\lambda_0^{k-1} & \lambda_1^{k-1} & \lambda_2^{k-1} & \cdots & \lambda_{k-1}^{k-1}
\end{vmatrix}
 =\prod_{0\leq i < j \leq k-1}\big(\lambda_j - \lambda_i\big)

Est connu comme. En utilisant la formule de Cramel, pour $ 0 \ leq m \ leq k-1 $

\begin{align}
c_m &= \frac{\begin{vmatrix}
1 & 1 & \cdots & 1 & 0 & 1 & \cdots & 1\\
\lambda_0 & \lambda_1 & \cdots & \lambda_{m-1} & 0 & \lambda_{m+1} & \cdots & \lambda_{k-1} \\
\lambda_0^2 & \lambda_1^2 & \cdots & \lambda_{m-1}^2 & 0 & \lambda_{m+1}^2 & \cdots & \lambda_{k-1}^2\\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots  \\
\lambda_0^{k-1} & \lambda_1^{k-1} & \cdots & \lambda_{m-1}^{k-1} & 1 & \lambda_{m+1}^{k-1} & \cdots & \lambda_{k-1}^{k-1}
\end{vmatrix}}{V_k}\\
&=\frac{(-1)^{m}\begin{vmatrix}
0 & 1 & 1 & \cdots & 1 & 1 & \cdots & 1\\
0 & \lambda_0 & \lambda_1 & \cdots & \lambda_{m-1}  & \lambda_{m+1} & \cdots & \lambda_{k-1} \\
0 & \lambda_0^2 & \lambda_1^2 & \cdots & \lambda_{m-1}^2  & \lambda_{m+1}^2 & \cdots & \lambda_{k-1}^2\\
0 & \vdots & \vdots & \vdots & \vdots  & \vdots & \ddots & \vdots  \\
1 & \lambda_0^{k-1} & \lambda_1^{k-1} & \cdots & \lambda_{m-1}^{k-1}  & \lambda_{m+1}^{k-1} & \cdots & \lambda_{k-1}^{k-1}
\end{vmatrix}}{V_k}\quad (\car la colonne est échangée m fois)\\
&=\frac{(-1)^{m+k-1}\begin{vmatrix}
1 & \lambda_0^{k-1} & \lambda_1^{k-1} & \cdots & \lambda_{m-1}^{k-1}  & \lambda_{m+1}^{k-1} & \cdots & \lambda_{k-1}^{k-1}\\
0 & 1 & 1 & \cdots & 1 & 1 & \cdots & 1\\
0 & \lambda_0 & \lambda_1 & \cdots & \lambda_{m-1}  & \lambda_{m+1} & \cdots & \lambda_{k-1} \\
0 & \lambda_0^2 & \lambda_1^2 & \cdots & \lambda_{m-1}^2  & \lambda_{m+1}^2 & \cdots & \lambda_{k-1}^2\\
0 & \vdots & \vdots & \vdots & \vdots  & \vdots & \ddots & \vdots  \\
0 & \lambda_0^{k-2} & \lambda_1^{k-2} & \cdots & \lambda_{m-1}^{k-2}  & \lambda_{m+1}^{k-2} & \cdots & \lambda_{k-1}^{k-2}
\end{vmatrix}}{V_k}\quad (\parce que la ligne k-Échange une fois)\\
&=\frac{(-1)^{m+k-1}\begin{vmatrix}
1 & 1 & \cdots & 1 & 1 & \cdots & 1\\
\lambda_0 & \lambda_1 & \cdots & \lambda_{m-1}  & \lambda_{m+1} & \cdots & \lambda_{k-1} \\
\lambda_0^2 & \lambda_1^2 & \cdots & \lambda_{m-1}^2  & \lambda_{m+1}^2 & \cdots & \lambda_{k-1}^2\\
\vdots & \vdots & \vdots & \vdots  & \vdots & \ddots & \vdots  \\
\lambda_0^{k-2} & \lambda_1^{k-2} & \cdots & \lambda_{m-1}^{k-2}  & \lambda_{m+1}^{k-2} & \cdots & \lambda_{k-1}^{k-2}
\end{vmatrix}}{V_k}\\
&=\frac{(-1)^{m+k-1}\displaystyle \prod_{0\leq i < j \leq k-1 et i\neq m et j\neq m}\big(\lambda_j - \lambda_i\big)}{\displaystyle \prod_{0\leq i < j \leq k-1}\big(\lambda_j - \lambda_i\big)}\quad (\parce que la formule matricielle de Van der Monde)\\
&=\frac{(-1)^{m+k-1}}{\displaystyle \prod_{0\leq i < j \leq k-1 et(i=m ou j=m)}\big(\lambda_j - \lambda_i\big)}\\
&=\frac{(-1)^{m+k-1}}{\displaystyle \prod_{0\leq i < m}\big(\lambda_m - \lambda_i\big)\prod_{m < j \leq k-1}\big(\lambda_j - \lambda_m\big)}\\
&=\frac{(-1)^{m+k-1}}{\displaystyle \prod_{0\leq i < m}\big(\lambda_m - \lambda_i\big)\prod_{m < j \leq k-1}(-1)\big(\lambda_m - \lambda_j\big)}\\
&=\frac{(-1)^{m+k-1}}{\displaystyle \prod_{0\leq i < m}\big(\lambda_m - \lambda_i\big)(-1)^{k-m-1}\prod_{m < j \leq k-1}\big(\lambda_m - \lambda_j\big)}\\
&=\frac{(-1)^{(m+k-1)-(k-m-1)}}{\displaystyle \prod_{0\leq i < m}\big(\lambda_m - \lambda_i\big)\prod_{m < j \leq k-1}\big(\lambda_m - \lambda_j\big)}\\
&=\frac{(-1)^{2m}}{\displaystyle \prod_{0\leq i < m}\big(\lambda_m - \lambda_i\big)\prod_{m < j \leq k-1}\big(\lambda_m - \lambda_j\big)}\\
&=\frac{1}{\displaystyle \prod_{0\leq i <m,m<i\leq k-1}\big(\lambda_m - \lambda_i\big)}
\end{align}

Est requis.

De ce qui précède,

\begin{align}
\boldsymbol{a_n} &= c_0 \boldsymbol{u_0} + c_1 \boldsymbol{u_1} +\dots+ c_{k-1} \boldsymbol{u_{k-1}}\\
&=\left\{ \frac{\lambda_0^n}{\displaystyle \prod_{1\leq i \leq k-1}\big(\lambda_0 - \lambda_i\big)} + \frac{\lambda_1^n}{\displaystyle \prod_{0\leq i <1,1 <j\leq k-1}\big(\lambda_1 - \lambda_i\big)} +\dots+ \frac{\lambda_{k-1}^n}{\displaystyle \prod_{0\leq i \leq k-2}\big(\lambda_{k-1} - \lambda_i\big)}\right\}_{n=0}^{\infty}\\
&=\left\{\sum_{i=0}^{k-1}\frac{\lambda_i^n}{\displaystyle \prod_{0\leq j <i, i< j\leq k-1}\big(\lambda_i - \lambda_j\big)}\right\}_{n=0}^{\infty}
\end{align}

Alors

a_n = \sum_{i=0}^{k-1}\frac{\lambda_i^n}{\displaystyle \prod_{0\leq j <i, i< j\leq k-1}\big(\lambda_i - \lambda_j\big)}

A été conduit.

Exemple de mise en œuvre et comparaison des montants de calcul

Jusqu'à présent, nous connaissons la forme du terme général, mais nous ne connaissons pas les valeurs spécifiques de $ \ lambda_0, \ lambda_1, \ dots, \ lambda_ {k-1} $. Il n'y a pas toujours de solution algébrique pour les équations de degré 5 ou plus, alors trouvez une solution numérique. Cette fois également, il est calculé à l'aide de la bibliothèque numpy de Python. Considérez les problèmes suivants.

Étant donné les nombres naturels $ K, N $. $ K $ -Imprimez le terme $ N $ de la séquence Bonatch.

Exemple de mise en œuvre 1: calculer comme défini

teigi.py

k, n = map(int, input().split())

a = [0] * max(n+1,k)
a[k-1] = 1

for i in range(k,n+1):
    for j in range(1,k+1):
        a[i] += a[i-j]

print(a[n])

Si vous calculez selon la définition, vous devez ajouter $ K $ fois pour chaque $ i (K \ leq i \ leq N) $, donc $ O (K (NK)) = O (KN) $. Je vais.

Exemple de mise en œuvre 2: utiliser des termes généraux

ippankou.py

import numpy as np
import warnings 
warnings.filterwarnings('ignore')       #Un avertissement se produit lors du calcul de nombres complexes, supprimez-le.

k, n = map(int, input().split())

equation = [1]
for i in range(k):
    equation.append(-1)     # equation = [1, -1, -1, ... , -1] = lambda^k - lambda^{k-1} - ... - lambda -1 = 0

lam = np.roots(equation)     # lambda_i

a = 0

for i in range(k):
    prod = 1
    for j in range(k):
        if j != i:
            prod *= lam[i] - lam[j]
    a += np.power(lam[i],n) / prod
    
        

print(int(round(a)))

Calculé en termes généraux, chaque $ i (0 \ leq i \ leq K) $ est multiplié par chaque $ j (0 \ leq j <i, i <j \ leq K) $ et $ N $ Puisque $ O (\ log N) $ est nécessaire pour le calcul de la multiplication, $ O (K (K + \ log N)) = O (K ^ 2 + K \ log N) $. Il semble que cette méthode ait une erreur d'environ 1/10 ^ {14} $ de la valeur numérique due au nombre à virgule flottante, comme dans le cas du précédent $ k = 3 $.

Exemple d'implémentation 3: Utilisez l'expression graduelle suivante (enregistrez la somme des termes k et n'échangez que le début et la fin)

\begin{align}
a_{n+k} &= \sum_{i=n}^{n+k-1}a_i\\
a_{n+k+1} &= \sum_{i=n+1}^{n+k}a_i \\
&= a_{n+k}+\sum_{i=n}^{n+k-1}a_i-a_n\\
&= a_{n+k}+a_{n+k}-a_n\\
&= 2a_{n+k} - a_n
\end{align}

zenkashiki.py

k, n = map(int, input().split())

a = [0] * max(n+1,k)
a[k-1] = 1
a[k] = 1

for i in range(0,n-k):
    a[i+k+1] = 2 * a[i+k] - a[i] 

print(a[n])

De cette façon, si vous pensez à un algorithme tel que la somme cumulée qui stocke la somme des termes $ k $ sans trouver le terme général, vous pouvez le trouver avec le montant du calcul $ O (N) $.

Exemple d'exécution

2 5
5

3 50
3122171529233

4 25
1055026

10 50  
1082392024832

50 30
0

100 150
1125899906842618

1000 1010
1024

Comparaison du montant de calcul

En comparant la quantité de calcul entre l'implémentation 2 et l'implémentation 3, il est préférable de comparer $ N $ et $ K ^ 2 + K \ log N $ et de considérer laquelle est la plus rapide.

Comparaison du temps d'exécution

measure_time.py

import time
import numpy as np
import warnings 
warnings.filterwarnings('ignore')       #Un avertissement se produit lors du calcul de nombres complexes, supprimez-le.

k, n = map(int, input().split())
m = 100        # loop count

"""
#Mise en œuvre 1
start = time.time()
for loop in range(m):

    a = [0] * max(n+1,k)
    a[k-1] = 1

    for i in range(k,n+1):
        for j in range(1,k+1):
            a[i] += a[i-j]

elapsed_time = time.time() - start
elapsed_time /= m
print ("Mise en œuvre 1: {0}".format(elapsed_time) + "[sec]")
"""


#Mise en œuvre 2
start = time.time()
for loop in range(m):

    equation = [1]
    for i in range(k):
        equation.append(-1)     # equation = [1, -1, -1, ... , -1] = lambda^k - lambda^{k-1} - ... - lambda -1 = 0

    lam = np.roots(equation)     # lambda_i

    a = 0

    for i in range(k):
        prod = 1
        for j in range(k):
            if j != i:
                prod *= lam[i] - lam[j]
        a += np.power(lam[i],n) / prod

elapsed_time = time.time() - start
elapsed_time /= m
print ("Mise en œuvre 2: {0}".format(elapsed_time) + "[sec]")


#Mise en œuvre 3
start = time.time()
for loop in range(m):

    a = [0] * max(n+1,k)
    a[k-1] = 1
    a[k] = 1

    for i in range(0,n-k):
        a[i+k+1] = 2 * a[i+k] - a[i] 

elapsed_time = time.time() - start
elapsed_time /= m
print ("Mise en œuvre 3: {0}".format(elapsed_time) + "[sec]")

Exemple de résultat de mesure

# N ~ K^2+Klog N
10 500 
Mise en œuvre 2: 0.00041536092758178713[sec]
Mise en œuvre 3: 0.0003914594650268555[sec]

# N > K^2+Klog N
3 10000
Mise en œuvre 2: 0.0002478790283203125[sec]
Mise en œuvre 3: 0.012493629455566407[sec]

# N < K^2+Klog N
100 500
Mise en œuvre 2: 0.01716961145401001[sec]
Mise en œuvre 3: 0.0002404618263244629[sec]

Comme je le pensais dans la comparaison des montants de calcul, il est confirmé que la mise en œuvre 2 est rapide lorsque $ N> K ^ 2 + K \ log N $ et que la mise en œuvre 3 est rapide lorsque $ N <K ^ 2 + K \ log N $. Je vais.