開発blog?とりあえず何でもやってみる人。試した結果などの記録的な何か(笑)。参考にでもなれば嬉しい。利用制限はありません。[edit]前回、漸化式を使っての組合せの数を求めたが、別の解法として「パスカルの三角形」を利用して組合せを求める方法もある。パスカルの三角形とは「二項係数」とか「二項定理」とも呼ばれ、高校数学でやった二項式を展開するときの係数に合致しているが、他にも色々利用できる性質がある。簡単に作り方を覚えてしまおう。非常に単純なので一度聞いたら忘れることもないだろう。作り方は以下のようになる。1.頂点(一番上)に「1」を書き、ここをスタート地点とする。2.スタート地点から左右(矢印の方向:斜め下)に向かって進んでいく。その際、交差する地点はその1つ前の値を合計する。これは道に例えると「網の目のように必ず2つの分岐点がある道を進むとき、その地点に最短で辿り着く方法は何通りあるか?」という数になる。通りあるという単純なものである。この値は、以下のように組合せを求める式の答えとも合致している。このパスカルの三角形を作ることをシミュレーションすれば、組合せの数も簡単に求めることができるというわけだ。上記の作り方をそのままコーディングしてみよう。<p>パスカルの三角形を斜めに傾けた配列を作成。左上が(0,0)で右下に拡がる感じになる。//パスカルの三角形パスカルの三角形を下の図のように斜め45度傾けて配列に入れたと考えれば簡単だろう。組合せの数を求めたいなら、この表を作って、値を取得すれば良いということになる。「5個のものから3個取り出す組合せ」の数になる。なり、配列の縦横を入れ替えても同じとなる。関数として作って置きたいなら、以下のような感じにすれば良い。パスカルの三角形から求める。大きすぎるとオーバーフローするので注意。r][r];}漸化式での組合せ[O(n)]と比べたメリットは、計算が単純な加算しかしていないため、オーバフローが少しばかりしにくい所だろうか。1900回演算で、計算量が少なくなるので速い)。単体で計算するなら、毎回配列を作る[O(n2)]ので、実行速度は遅くなるので注意しよう。ここで試しに練習問題をやってみよう。これはどちらかというとプログラミング問題というより数学の問題だ。ないの?」と思った人は気をつけよう。それは前回の「コイン4枚のうち2枚が表の確率」同様、ただ単に思い込みをしているだけだ。合計になり、それぞれ3手あるので3倍になる。ちなみに、この問題はわざわざパスカルの三角形を使った解法で試してみたが、「n人でじゃんけんを1回するとき、あいこになる確率」を一般化すると、となるので、一発計算で求めることもできる。2人~20人でじゃんけんをしたとき、あいこになる確率を計算してみよう。超えるので、もはや勝負がつかなくなる。人数が増えたとき、あいこが延々と続くようになるのはこういうことだ(笑)。人数が多いとき、4人以下で分割してじゃんけんした方が効率が良いことも理にかなっている。パスカルの三角形の作り方のコードを見て、アルゴリズマーな人なら(笑)、「あれ?このコード見たことあるな...」と思ったかもしれない。P.176~177)に載っている「動的計画法」のコードと同じだったりする。まで最短で移動する方法は何通りあるか?というような問いである。この格子状の経路は先のパスカルの三角形を斜めに倒した表と一致するので、全く同じコードになるわけだ。この格子状の経路を数え上げる問題は組合せの問題と本質的に同じになる。漸化式での方法でも一発で求めることができることになる。この格子状の道に通行止めがあった場合を考えよう。なると単純な組合せの計算一発では求められなくなる。その場合は、パスカルの三角形の作り方を改造すれば意外と簡単に求められるのだ。0)」を挿入してしまえば良い。計算量はかかってしまうので、非常に重くなる。起こすこともあるので気をつけよう。組合せの数と経路数の数え上げのロジックが繋がっていることを覚えておくと、利用価値があるかもしれない。考察してみると良いだろう。エースター)アルゴリズムでやったので、ついでに「15パズル」を解いてみよう。Scriptパズル自体の解き方は言わば「全パターン総当り方式(全探索)」である。15パズルになると、単純な全探索では、答えの手数が大きいときにフリーズしたような状態になってしまい、いずれキューのバッファオーバーフローでプログラムが停止してしまう。ような枝刈りアルゴリズムが必須になる。エースター)アルゴリズムで迷路を探索する」で簡単な考え方を解説している。「推定値」の使い方だけ覚えれば十分だろう。}}rrdllldruuurdllddrurrd答えとなる移動経路の文字列は空白の移動のものなので、人の指で数字パネルを動かす方向(スライド)は逆となる(空白が右に動くということは、数字パネルは左に動く)。スライド方向で表示したいときは上下左右を反転するメソッドでも付け加えると良いだろう。推定値は「各パネルが正しい並び(位置)に移動するのに必要な距離の総和+手数」になっている。指で数字パネルをスライドできる方向は4方向なので、移動コスト(距離)は「マンハッタン距離」になる。