オンライントレード

フィボナッチ数列の計算量について

フィボナッチ数列の計算量について
大石ゆかり

【発展】ユークリッドの互除法の計算回数とフィボナッチ数列

$r_$ で割った余りが $r_n$ なので、数列 $\$ はどんどん小さくなっていきます。なので、いつかゼロになります。つまり、次のようになる自然数 N が存在するということですね。\[ r_ = q_ \cdot r_ \]このとき、 N 回目の計算で、「 a と b の最大公約数は $r_N$」とわかることになります。なお、この数列は、$n \gt N$ のときは $r_n = 0$ となります。

一番回数が伸びるケース

ユークリッドの互除法の計算で、一番回数が伸びるケースを考えてみます。上の数列で言うと、 N フィボナッチ数列の計算量について が大きくなるケース、ということですね。

数列 $\$ を考えてみると、\[ r_0 \gt r_1 \gt r_2 \gt \cdots \gt r_N \gt r_= 0 \]となるので、 $r_n$ がなかなか減らないケースを考えればよさそうです。

上の数列の説明で書いた式をもう一度見てみます。\[ r_ = q_ \cdot r_ + r_ \]これで、 $r_n$ がなかなか減らないときというのは、 $q_=1$ のときが考えられます。 $r_ \gt r_$ なので、1回は割れてしまいますが、1回しか割れないなら余りの減少スピードは遅くなります。

つまり、一番計算回数が伸びてしまうケースというのは、\[ r_ = r_+r_ \]のときだろうと、想像がつきます。これをよく見ると、次に紹介するフィボナッチ数列とよく似ていることがわかります。

フィボナッチ数列との比較

上に出てきた式 $r_ = r_+r_$ と比べると、添え字の順番が違うだけで式はよく似ていますね。「一番計算回数が伸びるケースは、フィボナッチ数列と関係がありそう」と書きましたが、それと関連して次のことを証明しましょう($\$ は余りの列、 $\$ はフィボナッチ数列です)。

証明を始める前に、このことから何がわかるのかを考えてみます。「最大公約数を求めよう」としたとき、フィボナッチ数列と比較して、仮に「$b\lt フィボナッチ数列の計算量について F_$」ということが分かったとしましょう。このとき、「最大18回の計算で最大公約数が求められる」ということが分かるんですね。もし19回計算が必要なら、「$b\geqq F_$」にならないといけないよ、と上の命題が教えてくれているわけです。

(1) $r_\gt r_ \gt 0$ であり、ともに自然数なので、$r_\geqq 1=F_2$ と $r_\geqq 2=F_3$が成り立つ。
(2) k を2以上の自然数とする。$n=k$ フィボナッチ数列の計算量について のとき、$r_ \geqq F_$ と $r_ \geqq F_$ が成り立つとする。このとき、
\begin r_ &=& q_ \cdot r_ + r_ \\[5pt] &\geqq& 1 \cdot F_ + F_k \\ &=& F_ \\ \endとなる。よって、$n=k+1$のときも成り立つ。
(1)(フィボナッチ数列の計算量について 2)より、数学的帰納法から命題が成り立つことが示された。
(証明終)

このことから、計算回数を知りたければ、フィボナッチ数列との比較をすればいいということがわかります。しかし、「 b とフィボナッチ数列とを比較する」というのは、少し不便です。もう少しわかりやすい表現ができないか考えてみましょう。

フィボナッチ数列の評価

$\displaystyle \varphi = \frac >$ としたとき、自然数 n について、次が成り立つ。\[ F_ \geqq フィボナッチ数列の計算量について \varphi ^ \quad (※)\]

(1) $n=1$のとき、$F_2=1$で、$\varphi^0=1$なので、(※)が成り立つ。
(2) $n=2$のとき、$F_3=2$である。また、\[ \varphi ^1 フィボナッチ数列の計算量について = \frac > \leqq \frac > = 2 \]なので、(※)が成り立つ。
(3) k を3以上の自然数とし、$F_ \geqq \varphi ^$、$F_ \geqq \varphi ^$が成り立つとする。
$\displaystyle \varphi = \frac >$ を変形して
\begin 2\varphi &=& 1+\sqrt \\ 2\varphi -1 &=& \sqrt \\ 4\varphi^2 -4\varphi +1 &=& 5 \\ \varphi^2 &=& \varphi +1 \\ \endが成り立つことに注意すると、 \begin F_ &=& F_+F_ \\ & \geqq & \varphi ^ +\varphi ^ \\ &=& \varphi ^ (\varphi +1) \\ &=& \varphi ^ \cdot \varphi ^2 \\ &=& \varphi ^k \\ \endが成り立つ。よって、$n=k+1$のときも(※)が成り立つ。
(1)(2)(3)より、すべての自然数 n に対して、(※)が成り立つ。
(証明終)

ちなみに、$\displaystyle \varphi = \frac >$ は「黄金比」と呼ばれているものですね。

既に示した通り、$b\geqq F_$ であり、さらに $F_ \geqq \varphi ^$であることもわかったので、\[ b \geqq \varphi ^ \]が分かりますね。

ユークリッドの互除法の計算回数の評価

$b \geqq \varphi ^$が得られましたが、右辺はまだ少しわかりづらいので、次のように変形してみます。

まず、両辺の常用対数を考えると、
\[ \log_ b \geqq (N-1) \log_ \varphi \]が得られます。ここで、関数電卓などを用いて(例えばGoogle電卓とかで)具体的に計算すると、\[ \log_ \varphi フィボナッチ数列の計算量について フィボナッチ数列の計算量について = \log_ \frac > = 0.2089\cdots \gt \frac \]であることがわかります。よって、
\begin \log_ b & \geqq フィボナッチ数列の計算量について & (N-1) \log_ \varphi \\ \log_ b & \gt & (N-1) \cdot \frac \\ 5 \log_ b & \gt & N-1 \\ \endがわかります。10進数で表したときの b の桁数を m とおけば、$m\gt \log_b \geqq m-1$なので、$5m\gt N-1$が得られます。$m,N$は自然数なので、$5m\geqq N$がわかります。

例えば、「144と89の最大公約数」をユークリッドの互除法で求めるなら、89は2桁なので、10回以下の計算で求められるということですね。実際に計算してみると、次のようになります。
\begin 1:\ & 144 &=& 1 \cdot 89 &+ 55 \\ フィボナッチ数列の計算量について 2:\ & 89 &=& 1 \cdot 55 &+ 34 \\ 3:\ & 55 &=& 1 \cdot 34 &+ 21 \\ 4:\ & 34 &=& 1 \cdot 21 &+ 13 \\ 5:\ & 21 &=& 1 \cdot 13 &+ 8 \\ 6:\ フィボナッチ数列の計算量について フィボナッチ数列の計算量について & 13 &=& 1 \cdot 8 &+ 5 \\ 7:\ & 8 &=& 1 フィボナッチ数列の計算量について フィボナッチ数列の計算量について \cdot 5 &+ 3 \\ 8:\ & 5 &=& 1 \cdot 3 &+ 2 \\ 9:\ & 3 &=& 1 \cdot 2 &+ 1 \\ 10:\ & フィボナッチ数列の計算量について フィボナッチ数列の計算量について 2 &=& 2 \cdot 1 &\\ \endこれはなかなか余りが減っていかないケース、フィボナッチ数列のケースですね。

小さい方から順番に割っていく方法の場合、何も工夫しなければ、最大で $\sqrt$ 回の計算が必要です。 b が数億の場合、数万回の計算が必要になってしまいます。実際には素数だけを考えればいいのですが、1万以下の素数でも1000個以上あるので、千回は計算しないといけません。

整数の公式でフィボナッチ数列を求める

よって、もし \(m = \left(\begin 1 & 1 \\ 1 & 0 \end \right)^n\) なら、 \(bn = m\\) フィボナッチ数列の計算量について になります(Pythonと違って、行列の添え字は通常1が基準になることに注意してください)。 NumPy行列のべき乗が繰り返し二乗法のような振る舞いをすると想定すると、計算量は \(O(\mathrm\ n)\) になります。 さらに、漸化式を解くために、閉じた式を見つける方法もあります。 これにより、次の実数値の公式が導かれます: \(\phi = (1 + フィボナッチ数列の計算量について \sqrt) / 2\) 、 \(\psi = (1 - \sqrt) / 2\) とすると、 \(\mathrm(フィボナッチ数列の計算量について n) = (\phi^ - \psi^) / \sqrt)\) 。 この手法には、任意精度の実数計算を要するという実用上の欠点がありますが、 \(n\) の値が小さければ問題はありません。

任意の数列 \(an\) フィボナッチ数列の計算量について フィボナッチ数列の計算量について フィボナッチ数列の計算量について の母関数は、 \(\Sigman anx^n\) の無限和です。フィボナッチ数列の場合は \(\Sigman \mathrm(n)x^n\) になります。つまり、これは無限に続くべき級数であり、 \(x^n\) の係数は \(フィボナッチ数列の計算量について n\) 番目のフィボナッチ数に相当します。

この式に \(x^\) をかけて \(n\) 全体で和をとると、以下の式が得られます。

\(F(x)\) を \(\mathrm\) の母関数として、それを \(\Sigma_n\mathrm(n)x^n\) と定義すると、上の式は次のように簡略化できます。

\[F(x) - x - 1 = x(F(x) - 1) + x^2F(x)\]

\[F(x) = xF(x) + x^2F(x) + 1\]

これを \(F\) について解くと以下の式が得られます。

整数の公式

まずは、この公式を直感的にとらえるため、 \(10^\) で母関数 \(F\) を評価してみましょう。

興味深いことに、小数展開した部分に \(1, 1, 2, 3, 5, 8, 13, フィボナッチ数列の計算量について 21, 34, 55, 89\) と、フィボナッチ数列が現れています。魔法のような結果に驚いてしまいますが、その理由は次の式から分かります。

\(F(10^) = \mathrm(0) + \mathrm(1)/10^3 + フィボナッチ数列の計算量について フィボナッチ数列の計算量について \mathrm(2)/10^6 + \mathrm(3)/10^9 + \ldots\)

この例では、フィボナッチ数列が次々と \(1/1000\) 倍されて並んでいきます。つまり、その値が一旦1000を超えると、隣り合う数に影響を及ぼし始めるということです。この現象は、上記の \(F(10^)\) の計算で988から確認できます。正しいフィボナッチ数は987ですが、数列の次の数から1だけオーバーフローが発生しています。その結果Off-by-oneエラーが発生し、以降はパターンが崩れてしまうのです。

しかし、いかなる \(n\) の値に対しても、10の負の指数を十分大きく取れば、たとえオーバーフローが発生したとしても、 \(n\) 番目のフィボナッチ数に悪影響が出ることはありません。ここでは、ある \(k\) という値について \(10^\) が妥当な値になると仮定しましょう。この値は後ほど選定します。

さらに整数で計算をしたいので(その方がコーディングしやすいので)、全体を フィボナッチ数列の計算量について \(10^\) 倍して \(n\) 番目のフィボナッチ数が整数の範囲にくるようにして、式を整理します。

この結果を \(10^k\) を法として見ると、 \(n\) 番目のフィボナッチ数が得られます(先ほども書きましたが、 \(k\) には十分大きな値を選んだものと想定しています)。

あとは \(フィボナッチ数列の計算量について フィボナッチ数列の計算量について \mathrm(n+1)\) \(2^k\) になるように、 \(k\) を十分大きく取るだけです。フィボナッチ数列は \(\phi^n\) のように増大して、 \(\phi\) < \(2\) なので、 \(k = n+1\) とすれば安全です。

非反復型で閉じた解が得られたのは興味深いですが、これは全く実用的な手法ではありません。ここではサイズが \( O(n^2) \) ビットの整数を用いて、整数演算を実行しています。でも実際には、最終的にビット単位で論理積を取る前に、最初の \( n \) 個のフィボナッチ数が全て連結した整数値を取得しているのです。

フィボナッチ数列の一般項

式(1)に関しては、$\boldsymbol-\alpha F_n\>>$ をまるごと1つの数列だと考えると、この数列は公比 $\beta$ の等比数列になっていることがわかります。
初項は、$n=1$ とすると
$$ \begin F_2-\alpha F_1 &=& 1- \frac> \cdot 1\\
&=& \frac>\\
&=& \beta \end $$となります。
つまり数列 $\-\alpha F_n\>$ フィボナッチ数列の計算量について フィボナッチ数列の計算量について は初項も公比も $\beta$ だったというわけですね。よって、
$$ F_-\alpha F_n = \beta ^n \tag $$となります。

同様に、式(2)についても見ていきましょう。こちらも $\boldsymbol-\beta F_n\>>$ をまるごと1つの数列だと考えると、この数列は公比 $\alpha$ の等比数列になっていることがわかります。
初項は、$n=1$ とすると
$$ \begin F_2-\beta F_1 &=& 1- \frac> \cdot 1\\
&=& \frac>\\
&=& \alpha \end $$となります。
つまり数列 $\-\beta F_n\>$ の方は初項も公比も $\alpha$ だったとわかります。よって、
$$ F_-\beta F_n = \alpha ^n \tag $$となります。

最初の2項が「1, 1」でない場合

ここまでは、フィボナッチ数列の最初の2項を「1, 1」とする最も一般的な場合のことを考えてきました。
では、最初の2項が「1, 1」ではない場合、どのような一般項になるのしょうか。

前の2項を足すと次の項」というルールは変えません。

漸化式の特性方程式の2解
$$\alpha=\frac> , \ フィボナッチ数列の計算量について \beta=\frac>$$を用いて漸化式を変形すると、
$$ \begin F_-\alpha F_ &=& \beta (F_-\alpha F_n) \tag \\ F_-\beta F_ &=& \alpha (F_-\beta F_n) \tag \end $$となる所までは先ほどと同じです。
ここから最初の2項を変えた影響が出てきます。

式(6)の数列 $\-\alpha F_n\>$ は公比 $\beta$ の等比数列です。
初項は、
$$ F_2-\alpha F_1=b-\alpha a $$となります。よって、
$$ F_-\alpha F_n = ( b-\alpha a )\beta^ \tag $$となることがわかります。
同様に、式(7)からは
$$ F_-\beta F_n = ( b-\beta a )フィボナッチ数列の計算量について \alpha^ \tag $$という関係が得られます。
式(9)-式(8)を計算すると
$$(\alpha-\beta)F_n=( b-\beta a )\alpha^-( b-\alpha a )\beta^$$となります。
この両辺を $\alpha-\beta$ で除すと、
$$ \begin F_n &=& \frac< ( b-\beta a )\alpha^-( b-\alpha a )\beta^ > < \alpha-\beta >\\
&=& \frac> \left\< \left( b-\frac>a \right) \left( \frac> \right)^-\left( b-\frac>a \right) \left( \frac> \right)^ \right\> \end $$となり、これが求める一般項です。

整数の公式でフィボナッチ数列を求める

よって、もし \(m = \left(\begin 1 & 1 \\ 1 & 0 \end \right)^n\) なら、 \(bn = m\\) になります(Pythonと違って、行列の添え字は通常1が基準になることに注意してください)。 NumPy行列のべき乗が繰り返し二乗法のような振る舞いをすると想定すると、計算量は \(O(\mathrm\ n)\) になります。 さらに、漸化式を解くために、閉じた式を見つける方法もあります。 これにより、次の実数値の公式が導かれます: \(\phi = (1 + \sqrt) / 2\) 、 \(\psi = (1 - \sqrt) / 2\) とすると、 \(\mathrm(n) = (\phi^ - \psi^) / \sqrt)\) 。 この手法には、任意精度の実数計算を要するという実用上の欠点がありますが、 \(n\) の値が小さければ問題はありません。

任意の数列 \(an\) の母関数は、 \(\Sigman フィボナッチ数列の計算量について anx^n\) の無限和です。フィボナッチ数列の場合は \(\Sigman \mathrm(n)x^n\) になります。つまり、これは無限に続くべき級数であり、 \(x^n\) の係数は \(n\) 番目のフィボナッチ数に相当します。

この式に \(x^\) をかけて \(n\) 全体で和をとると、以下の式が得られます。

\(F(x)\) を \(\mathrm\) の母関数として、それを \(\Sigma_n\mathrm(n)x^n\) フィボナッチ数列の計算量について と定義すると、上の式は次のように簡略化できます。

\[F(x) - x - 1 = x(F(x) - 1) + x^2F(x)\]

\[F(x) = xF(x) + x^2F(x) + 1\]

これを \(F\) について解くと以下の式が得られます。

整数の公式

まずは、この公式を直感的にとらえるため、 \(10^\) で母関数 \(F\) を評価してみましょう。

興味深いことに、小数展開した部分に \(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89\) と、フィボナッチ数列が現れています。魔法のような結果に驚いてしまいますが、その理由は次の式から分かります。

\(F(10^) = \mathrm(0) + \mathrm(1)/10^3 + \mathrm(2)/10^6 フィボナッチ数列の計算量について フィボナッチ数列の計算量について + \mathrm(3)/10^9 + \ldots\)

この例では、フィボナッチ数列が次々と \(1/1000\) 倍されて並んでいきます。つまり、その値が一旦1000を超えると、隣り合う数に影響を及ぼし始めるということです。この現象は、上記の \(F(10^)\) の計算で988から確認できます。正しいフィボナッチ数は987ですが、数列の次の数から1だけオーバーフローが発生しています。その結果Off-by-oneエラーが発生し、以降はパターンが崩れてしまうのです。

しかし、いかなる \(フィボナッチ数列の計算量について n\) の値に対しても、10の負の指数を十分大きく取れば、たとえオーバーフローが発生したとしても、 \(n\) 番目のフィボナッチ数に悪影響が出ることはありません。ここでは、ある \(k\) という値について \(10^\) が妥当な値になると仮定しましょう。この値は後ほど選定します。

さらに整数で計算をしたいので(その方がコーディングしやすいので)、全体を \(10^\) 倍して \(フィボナッチ数列の計算量について n\) 番目のフィボナッチ数が整数の範囲にくるようにして、式を整理します。

この結果を \(10^k\) を法として見ると、 \(n\) 番目のフィボナッチ数が得られます(先ほども書きましたが、 \(k\) には十分大きな値を選んだものと想定しています)。

あとは \(\mathrm(n+1)\) フィボナッチ数列の計算量について フィボナッチ数列の計算量について \(2^k\) になるように、 \(k\) を十分大きく取るだけです。フィボナッチ数列は \(\phi^n\) のように増大して、 \(\phi\) < \(2\) なので、 \(k = n+1\) とすれば安全です。

非反復型で閉じた解が得られたのは興味深いですが、これは全く実用的な手法ではありません。ここではサイズが \( O(n^2) フィボナッチ数列の計算量について \) ビットの整数を用いて、整数演算を実行しています。でも実際には、最終的にビット単位で論理積を取る前に、最初の \( n \) 個のフィボナッチ数が全て連結した整数値を取得しているのです。

Pythonで再帰的な関数を利用してフィボナッチ数列を実装する方法を現役エンジニアが解説【初心者向け】

田島悠介

大石ゆかり

田島悠介

大石ゆかり

フィボナッチ数列とは

再帰的な関数を利用してフィボナッチ数列を実装してみよう

「スクールは高いから独学で成功する」という気持ちの方は多いと思います。
もちろんその方が金額は低く抑えられるでしょう。
ただ 独学には向き不向きがあり、実はスクールが向いている人も大勢います。

そんな方のために参考として、 テックアカデミー卒業生がスクールを選んだ理由 をご紹介します。

  • ・困って挫折しそうなときに、質問や相談できる相手がいる環境で学んでいきたいなと思った
  • ・わかった気になっているだけだったので、自分を追い込む環境に置いた方がいいと感じた
  • ・スクールのカリキュラムで市場に求められるスキルを学ぶべきと思った

少しでも当てはまる部分があれば、 スクールが向いているかもしれません。
お試しのつもりで、まずは一度 無料相談 に参加してみませんか?

現役エンジニア・デザイナーに何でも気軽に相談できる30分 を すべて無料で できます。
無理な勧誘は一切ない ので、お気軽にご参加ください。

執筆してくれたメンター

得意言語はPython, HTML, CSSで、機械学習やデータ分析、スクレイピングなどが得意。

大石ゆかり

田島悠介

大石ゆかり

初心者・未経験でもできる。まずはテックアカデミーに相談しよう

  • ・調べてもほしい情報が見つからない
  • ・独学のスキルが実際の業務で通用するのか不安
  • ・目標への学習プランがわからず、迷子になりそう

テックアカデミーでは、このような 学習に不安を抱えている方へ、現役エンジニア講師とマンツーマンで相談できる機会を無料で提供 しています。 フィボナッチ数列の計算量について
30分間、オンラインでどんなことでも質問し放題です。

「受けてよかった」と感じていただけるよう 厳しい試験を通過した講師 があなたの相談に真摯に向き合います。

「ただ気になることを相談したい」
「漠然としているがプロの話を聞いてみたい」
こんな気持ちでも大丈夫です。

無理な勧誘は一切ありません ので、まずはお気軽にご参加ください。
※体験用のカリキュラムも無料で配布いたします。(1週間限定)

記事を検索

関連するキーワード

関連する記事

Pythonで出力結果をファイルに保存する方法を現役エンジニアが解説【初心者向け】

Pythonで逆行列を求める方法【初心者向け】

Python2からPython3に切り替える方法を現役エンジニアが解説【初心者向け】

Pythonで音声認識する方法を現役エンジニアが解説【初心者向け】

Pythonのclassにおけるobjectについて現役エンジニアが解説【初心者向け】

Pythonのimportメソッドの使い方【初心者向け】

あわせてよく読まれている記事

JavaScriptで再帰処理を行う方法を現役エンジニアが解説【初心者向け】

JavaScriptで再帰処理を行う方法について、TechAcademyのメンター(現役エンジニア)が実際のコードを使って初心者向けに解説します。 JavaScriptについてそもそもよく分からないという方は、JavaScriptとは何なのか解説した記事をまずご覧ください。 なお本記事は、TechAcademyのオンラインブートキャンプ、JavaScript/jQuery講座の内容をもとにしています。 田島悠介 今回は、JavaScriptに関する内容だね! 大石ゆかり どういう内容でしょうか? 田島悠介 JavaScriptで再帰処理を行う方法について詳しく説明していくね! 大石ゆかり お願いします! 再帰処理とは 再帰処理とは、ある処理について、その処理の中で自身を呼び出すような処理のことを言います。 再帰処理のサンプルと解説 再帰処理のサンプルとしてフィボナッチ数列を取り上げてみます。フィボナッチ数列から引数で指定した位置の数字を取得する関数を考えます。まず、フィボナッチ数列がどのような数列であったかと言うと、 [0, 1, 1, フィボナッチ数列の計算量について 2, 3, 5, 8, 13, 21, 34, 55, . ] JavaScriptの配列に見立てて最初の0を0番目と考えることにします。例えば、6番目の8という値は、4番目の3と5番目の5を足した数になっています。 なので、次のような式が成り立ちます。 F(0) = 0 (フィボナッチ数列の計算量について n = 0) F(1) = 1 (n = 1) F(n) = F(n-2) + F(n-1) (n >= 2) これを、JavaScriptの関数として記述してみます。 const f = n => n < 2 ? n : f(n-2) + f(n-1) 試しにコンソールに出力して確認しましょう。 for (let i = 0 ; i <= 10 ; i++) < console.log(f(i)) >関数fは、その処理の中で自身である関数fを呼び出しています。つまり、この関数は再帰処理をしています。 [PR]

JavaScriptでDOMを再帰的に操作する方法を現役エンジニアが解説【初心者向け】 フィボナッチ数列の計算量について

Pythonのlinspaceメソッドの使い方を現役エンジニアが解説【初心者向け】

Pythonのlinspaceメソッドの使い方について解説します。linspaceを使うことでコード量を減らし読みやすいプログラムを組むことができるようになります。ぜひ参考にしてみてください。 そもそもPythonについてよく分からないという方は、Pythonとは何なのか解説した記事を読むとさらに理解が深まります。 なお本記事は、TechAcademyのオンラインブートキャンプPython講座の内容をもとに紹介しています。 田島悠介 今回は、Pythonに関する内容だね! 大石ゆかり どういう内容でしょうか? 田島悠介 Pythonのlinspaceメソッドの使い方について詳しく説明していくね! 大石ゆかり お願いします! linspace()とは? まず、linspace()フィボナッチ数列の計算量について フィボナッチ数列の計算量について について説明します。 linspace()はPythonのライブラリNumpyの関数で、 数列を作りたいときなどによく使われる便利な関数です。数列を作りたいときというのは、関数のグラフの描画をするときなどが挙げられます。 linspace()で作ることのできる数列には次のようなものがあります。 array([ 0., 3., 6., 9., 12., 15., 18., 21., 24., 27., 30.]) これは、0から始まって30まで3ずつ増えていく数列です。このような数列は同じNumpyライブラリのarange()関数を使って作ることもできます。 しかし、linspace()関数を使うことで少ないコードで書くことできるので、コードを書く方にも読む方にも利点があります。 NumPyのインストール linspace()関数を使う前に、まずはNumpyをインストールしましょう。基本的には、Pythonのパッケージ管理ツールであるpipコマンドを使えば、 pip install numpy を実行するだけでインストールができるはずです。Numpyがインストールできていることを調べます。 pip list を実行すると、これまでにインストールしたパッケージが確認できます。リストの中にnumpyが確認できたら大丈夫です。 [PR] Pythonで挫折しない学習方法を動画で公開中linspace()の使い方 linspace()は、公式のドキュメントで、 numpy.linspace(start, stop, num = 50, endpoint = True, retstep = False, dtype = None) と書かれているように引数は6つありますが、linspace()は基本的に3つの引数を指定して使います。実用上知っておくべきなのは、start, stop, numの3つです。 startは数列の開始点を指定する stopは数列の終了点を指定する フィボナッチ数列の計算量について numは数列の要素の数を指定する ものです。 他の引数については、endpointは数列の終了点を要素に含めるかどうかを、retstepは数列の公差を表示するかどうかを、dtypeは数列の各要素のデータ型を、それぞれ決めるものです。 これらに関しては、ドキュメントにも詳しく説明されているので、必要に応じて目を通しておくと良いでしょう。 linspace()を実行すると数列のndarrayが出力されます。retstepがTrueになっている場合は、数列の公差も出力されます。 linspace()を利用して数列を生成してみよう それでは実際にlinspace()を使ってみましょう。まずは、 import numpy as np を実行してNumpyをインストールします。そして、まずは、00から始まって30まで3ずつ増えていく数列を出力しましょう。 print(np.linsapce(0 ,30, 11)) これを実行すると、 [ 0. 3. 6. 9. 12. 15. 18. 21. 24. 27. 30.] と表示されると思います。retstepをTrueにして、 print(np.linsapce(0 ,30, 11), retstep=True) を実行すると (array([ フィボナッチ数列の計算量について 0.,

Pythonで再帰関数を作る方法【初心者向け】

Pythonで再帰関数を作る方法について解説します。 そもそもPythonについてよく分からないという方は、Pythonとは何なのか解説した記事を読むとさらに理解が深まります。 なお本記事は、TechAcademyのオンラインブートキャンプPython講座の内容をもとに紹介しています。 田島悠介 今回は、Pythonに関する内容だね! 大石ゆかり どういう内容でしょうか? 田島悠介 再帰関数を作る方法について詳しく説明していくね! 大石ゆかり お願いします! 再帰関数とは 再帰関数とはプログラミングの手法の1つで、プログラムの中に自分自身の呼び出しが含まれているものを言います。 フィボナッチ数列の計算量について フィボナッチ数列の計算量について 再帰関数は、繰り返し関数と同様に、同様な処理を複数回行う場合に利用されますが、より複雑な問題を簡単な問題に置き換えて処理できると言われています。再帰関数は以下のような場面で利用されています。 データ処理 複数のデータをソートしたり、繰り返し処理を行う場合、データ構造によっては再帰関数を使うと効率的な場合があります。 再帰データ型 複雑な問題の解決 よく例題としてあげられるのが「ハノイの塔」の問題です。一定のルールに従い、毎回状態が変わる処理に対して、再帰関数を使うと簡単な問題に置き換えて処理することができます。 ハノイの塔 構文解析(自然言語処理) 自然言語処理において、文章を単語に分解する処理を、再帰関数を用いて行う場合があります。自然言語処理については以下の記事も参考にしてください。 自然言語処理とは!仕組みやライブラリを解説 余談ですが、再帰的表現はプログラミングで古くから用いられており、コンピュータ関連の用語にもしばし登場します。例えば「Linux」は「Linux is not unix」の略語であり、自分自身がもととなる文章に含まれています。 再帰的頭字語 フィボナッチ数列の計算量について Pythonで再帰関数を作る方法 Python ではユーザー定義関数を利用して再帰関数を作成することができます。 def myfunc(x): if 終了条件: return x // 何かの処理を行う myfunc(x) 注意点は以下の通りです。 フィボナッチ数列の計算量について 必ず終了条件を入れましょう。終了条件が無いと永久に再帰呼び出しを行い、処理が終わらなくなってしまいます。 再帰呼び出しを行う際の引数に注意しましょう。こちらも状態が変わらないままだと、終了条件の判定が正しく行えません プログラムの内容が複雑だと感じたら、再帰関数以外で実現出来ないか考えてみましょう。再帰関数はシンプルに記述できる反面、処理を追いづらくバグを発見しづらいという面もあります。 [PR] Pythonで挫折しない学習方法を動画で公開中実際に書いてみよう 今回のサンプルプログラムでは、1からnの整数の和を返すプログラムを、再帰関数を使った場合と使わない場合で確認します。はじめに再帰関数を使わない場合です。 def sum(n): ret = 0 for i in range(1, n + 1): ret += i return ret s = sum(100) print("1から100の合計は", s,

Pythonで等差数列を作る方法【初心者向け】

Pythonで等差数列を作る方法について解説します。 そもそもPythonについてよく分からないという方は、Pythonとは何なのか解説した記事を読むとさらに理解が深まります。 なお本記事は、TechAcademyのオンラインブートキャンプPython講座の内容をもとに紹介しています。 田島悠介 今回は、Pythonに関する内容だね! 大石ゆかり どういう内容でしょうか? 田島悠介 Pythonで等差数列を作る方法について詳しく説明していくね! 大石ゆかり お願いします! 等差数列を作る方法 等差数列とは、隣の値(項)との差が同じ数列のことです。例えば以下のような数列です。 フィボナッチ数列の計算量について 10, 20, 30, 40, 50, . Python で等差数列を作成する方法はいくつかあります。 rangeを使う方法 range(開始, 終了, ステップ) 開始から終了-1までの範囲で、ステップの差で数列を作成します。戻り値は range 型となります。 NumPy の arange を使う方法 numpy.arange(開始, 終了, ステップ, dtype) こちらも同様です。開始とステップ、dtypeは省略できます。dtypeは数列の要素の型を指定します。初期値はNone(開始や終了の型に合わせる)です。 NumPy の linspace を使う方法 numpy.linspace(開始, 終了, 分割数, endpoint = True, retstep = False, dtype = フィボナッチ数列の計算量について None) こちらは上記とは考え方が異なり、開始から終了までの範囲を分割数で分割した数列を返します。終了も含みます。開始と終了は必須です。その他のオプションは省略可能です。 オプション 説明 既定値 分割数 出来上がる数列の要素数 50 endpoint 終了を要素に含むか True retstep Trueにすると公差を表示 False dtype 数列の要素の型 None(float型になる) 実際に書いてみよう 今回は上記の3つの方法における等差数列の書き方を確認します。確認しやすいよう、結果は NumPy 配列型で表示することとします。プログラムは Python インタプリタで入力していきます。事前に Python と NumPy ライブラリをインストールする必要があります。はじめに必要なライブラリをインポートしておきましょう。 import numpy フィボナッチ数列の計算量について as np 最初は range を使う方法です。 np.array(range(10, 151, 10)) 実行結果は以下のようになります。 array([ 10, 20, フィボナッチ数列の計算量について 30, 40, 50,

PHPで再帰処理を実装する方法を現役エンジニアが解説【初心者向け】

今回は、PHPで再帰処理を実装する方法について、TechAcademyのメンター(現役エンジニア)が実際のコードを使用して初心者向けに解説します。 PHPについてそもそもよく分からないという方は、PHPとは何なのか解説した記事を読むとさらに理解が深まるでしょう。 なお本記事は、TechAcademyのオンラインブートキャンプPHP/Laravel講座の内容をもとに紹介しています。 田島悠介 今回は、PHPに関する内容だね! 大石ゆかり どういう内容でしょうか? 田島悠介 PHPで再帰処理を実装する方法について詳しく説明していくね! 大石ゆかり お願いします! フィボナッチ数列の計算量について この記事ではPHPで再起処理を実装する方法について解説します。 目次 再帰とは 再帰関数の使い方 再帰処理の例 実際に書いてみよう まとめ 再帰とは 再帰処理とは、関数がメソッドの中で自分自身を呼び出す処理のことです。 再帰処理は自分自身を呼び出すため適切な終了処理をしない限り無限ループになってしまう点に注意する必要があります。 [PR] Pythonで挫折しない学習方法を動画で公開中再帰関数の使い方 再帰関数は関数の中に自分自身を呼び出すことをいいます。ただそのままだと無限に自分自身を呼び出し続けるため終了条件が必要になります。 再帰関数は以下のように書きます。 function 関数名(引数) < if (終了条件) < return 戻り値; >else < 関数名(引数); return 戻り値; >> 自分自身を再度呼ぶ際に同じ引数を設定すると無限ループになるため引数を別の値に変えるようにする必要があります。 再帰処理の例 再帰処理の例として階乗の計算について紹介します。 階乗とは数学の計算方法の1つで4!や5!のように「数字!」と書きます。1から数字までの整数を掛け合わせた値を得ることができます。 6!だと以下のような計算になります。 6! = 1 * 2 * 3 * 4 * 5 * 6; ただこの計算はこのような理解もできます。 6! = 5! * フィボナッチ数列の計算量について 6; 6! = (4! * 5) * 6 6! = ((3! * 4) * 5) *

関連記事

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次
閉じる