人気ブログランキング |

ハノイの塔を拡張する

古い記事にたんぽぽさんからコメントをいただきました。https://kinshati.exblog.jp/20602142/

Commented by たんぽぽ at 2019-07-23 23:53 x
差分方程式
a(n+1) = 2a(n) + 1, a(1) = 1
を解けばよい


さてここからが本題です。関数a(n)を求めたいんだけど、ふつうのハノイの塔の場合は「(2^n)-1」と判明しています。たんぽぽさんのコメントでは初期値をa(1)=1としていますが、それを2にしたらどうなるか、さらに一般化してa(1)=mにしたらどうか? を考えます。


ふつうのハノイの塔の数列の下に、a(1)を変えた数列を、数表にして書きだしてみます。


さて、この数表を横に見ても僕にはルールが分かりませんでした(涙)が、縦に見るとごくふつうの等差数列です。


d0164691_12443116.png

*ミスタッチがあったので訂正しました。一番下の「縦に見るとごくふつうの等差数列です。」が訂正前は「縦に見るとごくふつうの階差数列です。」になっていました。

訂正前のスクショです↓

d0164691_07182148.png

by tomoarrow | 2019-07-29 07:00 | モチーフについて | Comments(12)
Commented by たんぽぽ at 2019-07-29 23:51 x
おおお、わたしのコメントから、
エントリを書いてくださったのですね。

>この数表を横に見ても

階差数列が等比数列になっています。
Commented by tomoarrow at 2019-07-30 07:42
コメントありがとうございます、たんぽぽさんのおかげで記事が書けました。

等比数列は気がつかなかった。
Commented by たんぽぽ at 2019-07-30 23:41 x
こちらこそ、わたしのコメントに
関心を持ってくれてありがとうです。


階差数列が等比数列であることは、
差分方程式を解かなくてもわかります。

b(n) = a(n) - a(n-1)
とおいて
b(n+1) / b(n)
を計算すればいいです。
Commented by tomoarrow at 2019-08-05 08:02
階差数列が等比数列ならば、各行の一般項の漸化式が書ける?

そして各行の初項はmだから、こっちの経路からも数表の一般項が記述できるかな。
Commented by たんぽぽ at 2019-08-06 23:08 x
b(n+1) / b(n) = 2
になります。
nやa(1)と無関係の定数です。


a(n)の一般項は、これでいいのでは?
http://lacrima09.web.fc2.com/fig7/hanoi.html
Commented by tomoarrow at 2019-08-08 07:37
階差数列の公比はやはり2ですよね(答え合わせしてもらってすいません)。

>a(n)の一般項は、これでいいのでは?
>http://lacrima09.web.fc2.com/fig7/hanoi.html

拝見しました。わざわざ作ってくれたんですか? なんかすいません・・僕の結果は↓です。
https://kinshati.exblog.jp/27705096/

僕は初項をmで一般的にとっていますが、同じ結果ですね。

ちなみに行の階差数列から数表の一般項を求める試みはすでに予約稿済みで8/11、8/12にアップされる予定なのです。いくつもテーマをいただいてありがとうございます。
Commented by たんぽぽ at 2019-08-10 09:22 x
>階差数列の公比はやはり2ですよね

そうです。

>拝見しました。わざわざ作ってくれたんですか?

いえいえ、お気になさらずに。
タイプできないので、コメント欄に
直接書けなくて、別途作ったしだいです。


一般的な解法は、特性方程式を使うことだと思います。
a(n+1) = pa(n) + q
に対して、
x = px + q
という方程式を作る解きかたです。
(a(n+1)とa(n)を両方xで置き換える。)

a(n+1) = 2a(n) + 1
の場合、特性方程式は
x = 2x + 1
でその根は、x = -1。
もとの差分方程式の両辺からxを引くと
a(n+1) + 1 = 2(a(n) + 1)
となって、
c(n) = a(n)+1
なる数列が公比2の等比数列になります。


>https://kinshati.exblog.jp/27705096/
>僕は初項をmで一般的にとっていますが、同じ結果ですね。

拝見しました。
同じになっているのを確認しました。


>いくつもテーマをいただいてありがとうございます

こちらこそ、わたしのつたないコメントから、
話題を発展させてくださってありがとうです。
Commented by tomoarrow at 2019-08-10 16:15
詳細な解説をありがとうございます。もう一点おしえてください。

>a(n+1) + 1 = 2(a(n) + 1)
>となって、
>c(n) = a(n)+1
>なる数列が公比2の等比数列になります。

ここがよくわからないのです。c(n)はどこから出てくるのですか?
Commented by たんぽぽ at 2019-08-11 12:19 x
>c(n)はどこから出てくるのですか?

c(n) は a(n)から、
特性方程式の根を引いたものです。

この問題の場合、特性方程式は
x = 2x + 1
で根は-1なので
c(n) = a(n) - (-1) = a(n) + 1
になります。

これをもとのa(n)の差分方程式に代入すると、
c(n)は公比が2の等比数列
c(n+1) = 2c(n)
になります。


一般の定係数の差分方程式
a(n+1) = pa(n) + q
でも、特性方程式
x = px + q
の根xをa(n)から引いた
c(n) = a(n) - x
は、公比がpの等比数列
c(n+1) = pc(n)
になります。
Commented by tomoarrow at 2019-08-14 16:24
a(n+1) = 2a(n) + 1
のa(n+1)とa(n)を両方xで置き換えると、下になりますよね。
x=2x+1
そして両辺から(-1)を引くと
a(n+1) + 1 = 2(a(n) + 1)・・(式1)
左辺は0になるので
0=2(a(n) + 1)
0=a(n) + 1
これをc(n)とするのかしら?
c(n)=a(n) + 1・・(式2)

[1]
代入する「もとの差分方程式」とは、7/23たんぽぽさんのコメント中にある「a(n+1) = 2a(n) + 1, a(1) = 1」ですよね。
2a(n)+1=2(a(n)+1)-1=2c(n)-1
両辺から-1を引くと
2(a(n)+1)=2c(n)
2で割って
a(n)+1=c(n)

[2]
また(式2)にn+1を代入すると、(式1)から
c(n+1)=a(n+1)+1=2(a(n)+1)=2c(n)
これも[2(a(n)+1)=2c(n)]の部分の両辺を割ると
a(n)+1=c(n)

特性方程式がよくわかっていないので、(式2)の導き方の理解があっているのか自信がありませんが、それ以降の式変形はわかりました。
Commented by たんぽぽ at 2019-08-16 07:16 x
>代入する「もとの差分方程式」とは、
>7/23たんぽぽさんのコメント中にある
>「a(n+1) = 2a(n) + 1, a(1) = 1」ですよね。

そうです。


a(n)+1=c(n) (式2)を導いているけれど、
意味ないです。
それはc(n)を定義する式だからです。

等比数列を得るために、
a(n)+1=c(n)と変数変換するのであり、
変換のために導入した定義式を
導いているだけです。
Commented by tomoarrow at 2019-08-16 22:12
>a(n)+1=c(n) (式2)を導いているけれど、意味ないです。

僕も、この式は循環していると思いました。いろいろと付き合ってくれてありがとうございますね。