FC2ブログ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

アルゴリズム勉強記⑭~再帰編1 順列~

今回から何回かに渡って、本の「再帰」の章をやっていきます。
まずは、再帰を使って順列を生成するプログラムです。

とりあえず、本を見ないでテーマに沿って書いてみたものです。
アルゴリズムは、

再帰関数makenPr()内で、深さdepthの時に、1~Nの値について
ary[0]からary[depth - 1]までを調べ、登場していない場合に
ary[depth]に値を格納し、makenPr()を呼び出す。
depth = Nのときにary[]の内容を出力する。

というものです。
まあ、明らかにいちいちある値がそれまで登場しているかを調べる部分が無駄ですね。
けどまあ、私の頭ではこういう単純なのしか思いつかないので、勘弁してくだしあ。。

↓コード

#include<iostream>
using namespace std;
#define N 5

int ary[N];

void makenPr(int depth)
{
int i;
if(depth == N)
{
for(i = 0; i < depth; i++)
{
cout << ary[i] << " ";
}
cout << endl;
return;
}
int j;
int f = 0;
for(i = 1; i <= N; i++)
{
for(j = 0; j < depth; j++)
{
if(ary[j] == i) f = 1;
}
if(!f)
{
ary[depth] = i;
makenPr(depth + 1);
}
f = 0;
}
}

int main()
{
int i;
makenPr(0);


return 0;
}


で、次は本を読んで書いたプログラムです。
こっちのアルゴリズムは、

n個の順列は、1~nを先頭にするn - 1個の順列に分解でき、さらにそのそれぞれはその先頭とn - 2個の順列に……と、そんな感じで問題を分解する方法です。
具体的な方法は、

・depth = Nのときにary[]を出力する
・ary[N]に1~Nの値を格納しておく
・深さdepthのときに、ary[depth]とary[depth]~ary[N - 1]のそれぞれを交換する
・makenPr()を呼び出す
・交換したary[]を元に戻す

という形です。
ary[depth]をそれ以降と交換していくという部分が、先頭を決める部分に対応していますね。
depthより前の部分は、既に決定されているとみなされるので、変更の必要はありません。
これなら、無駄な比較がないので、私のよりは効率が良いはずです。

以下コード


#include<iostream>
using namespace std;

#define swap(x, y) do{int t = x; x = y; y = t;}while(0)
#define N 3

int ary[N];

void makenPr(int depth)
{
int i;
if(depth == N)
{
for(i = 0; i < N; i++)
{
cout << ary[i] << " " << endl;
}
cout << endl;
return;
}

//ary[depth]を、ary[depth]以降の要素と交換
for(i = depth; i < N; i++)
{
swap(ary[depth], ary[i]);
makenPr(depth + 1);
swap(ary[depth], ary[i]);
}
}

int main()
{

int i;
for(i = 0; i < N; i++)
{
ary[i] = i + 1;
}

makenPr(0);

return 0;
}


ミソは順列を小さい順列の問題に分解するというところですね。

あと、総当たり系の再帰で引っかかりやすいのが、ある深さで変更した値を、再帰呼び出し後に戻し忘れていること。これ、結構引っかかったことあります。
たとえば、前の騎士巡回問題とか。これはある深さでボードのフラグを立てて、その後に再帰呼び出しをし、全ての呼び出しが終わったらフラグを元に戻しています。

再帰王に、俺はなる!
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメント

Secret

プロフィール

PON4416

Author:PON4416
職業: 高校生

プログラミング歴: 2年弱

絵描き歴: '09年11月ごろから

趣味: プログラミング(C, C++)、お絵かき、漫画、アニメ、ゲーム

好きなもの: ジョジョ(2=3>1=4=7>5=6)、東方、うみねこ、ガンダム00、イカ娘

妖夢
嫁です(キリッ


Wilesの趣味的な人格。
最近PHPを始めたらしい。→やめたらしい

メール: yoshihiro[dot]hozumi[at]gmail[dot]com
skype: wiles4416

主にpixivで活動しています。
マイピクとか常に大募集してますw
プロフィールはこちらから



にほんブログ村 イラストブログ イラスト練習へ

最新記事
ひとりごと
最新コメント
月別アーカイブ
カテゴリ
ブロとも一覧

Weak's Smaller
割れ厨撲滅
検索フォーム
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。