再帰のお勉強2007/04/01 22:34

再帰表現法

ついつい、現実逃避をして再帰関数で遊んでいます。たまたま見つけた、再帰表現法という書籍に説明のあった、n 個から m 番目の要素を取り出す方法がやっとわかりました。

わかったついでに、C言語版をC++(STL)版に書き換えてみましたので、参考までに書いておきます。

n個の要素からm番目の要素を取り出す方法(C言語版)

int seekmn( vector<int> &v, int p, int q, int m )

{

 const int r = divide( v, p, q, v[q] );
 swap( v[r], v[q] );
 if( m == r - p + 1 ) return( v[r] );
 if( m <= r - p ){
   return( seekmn(v, p, r - 1, m) );
 }else{
   return( seekmn(v, r + 1, q, m - (r - p + 1)) );
 }

}

int divide( vector<int> &v, int p, int q, int b ) {

 const int max = q;
 for(;;){
   while( q >= p && v[q] >= b ) q--;
   while( p <  q && v[p] <  b ) p++;
   if( !(p <= q) ) break;
   swap( v[p], v[q] );
   p++;
   q--;
 }
 return( min(p, max) );

}

n個の要素からm番目の要素を取り出す方法(C++/STL言語版)

template<typename T>

class Compare3 : public binary_function<T, T, bool>{

public:

 result_type operator()( first_argument_type a, second_argument_type b )
 {
   return( *a >= *b );
 }

};

template<typename BiIter, typename Comp> BiIter divide3( BiIter p, BiIter q, Comp compfn ) {

 // 範囲が、p <= x < q なので、q の範囲を一つ小さくしておく。
 BiIter begin = p + 0;
 BiIter end   = q - 1;
 q--;
 for(;;){
   while( q > begin &&  compfn(q, end) ) q--;
   while( p < end   && !compfn(p, end) ) p++;
   if( !(p <= q) || q == begin || p == end ) break;
   iter_swap( p, q );
   p++;
   q--;
 }
 return( p );

}

template<typename BiIter, typename Comp> BiIter seekmn3( BiIter begin, BiIter end, int m, Comp compfn ) {

 BiIter p = divide3( begin, end, compfn );
 iter_swap( p, end - 1 );
 if( m == distance(begin, p) + 1 ) return( p );
 if( m <= distance(begin, p) ){
   return( seekmn3(begin, p, m, compfn) );
 }else{
   return( seekmn3(p + 1, end, m - (distance(begin, p) + 1), compfn) );
 }

}

再帰22007/04/02 07:00

牧場

今日も、再帰ネタ。今まで、パスワードのブルートフォールスアタックで使用するパスワードをどうやって生成しているのかわからなかったのですが、単純に再帰を使えば良いことに気がつきました。

void comb2( int n ) {

 if( n == 0 ){
   str[pos] = '\0';
   cout << str << endl;
   return;
 }
 
 for( int i = 0; i < 26; i++ ){
   str[pos] = 'a' + i;
   pos++;
   comb2( n - 1 );
   pos--;
 }

}

いや、別に、クラッキングには縁がないのですが、再帰ってこんなに単純なのに意外と?いろいろなことができますね。

またまた再帰(3)2007/04/04 05:40

再帰が連続しますが、この際、ひたすら連続します。今日は、n 個を m個に分割する問題を取り上げます。これは、数学的には、

x0 + x1 +... + xm-1 = n

となる、x0,x1,...xm-1 の組を全て求めることに帰着されます。また、

○○○....○|||...|

という並び(○が n 個、|が m - 1 個)の順列の個数とも言えます。これを再帰を使って求めるというのが本日のお題目です。

void splitnk( const int n, const int k )
{
 if( k == 0 ){
   for( int i = 0; i < pos; i++ ){
     cout << p[i] << " ";
   }
   cout << endl;
   
 }else if( k == 1 ){
   p[pos] = n;
   pos++;
   splitnk( 0, 0 );
   pos--;
 }else{
   for( int i = 0; i <= n; i++ ){
     p[pos] = n - i;
     pos++;
     splitnk( i, k - 1 );
     pos--;
   }
 }
}

なんか見事に解かれてしまってびっくりしました。雲は、いくつ分割の方法があるかを求める方法は高校生の頃から知っていたのですが、これを、アルゴリズムとして解く方法は今の今まで知りませんでした。まだまだ、、、ですね。

C#とC++の相互運用2007/04/04 07:37

今日は、初めて同じ日に二つ書きます。現状、C#の処理速度はどうしてもC++には及びません。また、C/C++には豊富なライブラリがあるため、C#だけでコードを書くことはあまり現実的ではありません。επιστημη三の記事にあるように、やはり、C#は、C/C++と相互運用をしてこそ効果的に利用できると思います。

ということで、現在、επιστημηさんの記事を参考にC#とC/C++の相互運用を試しているところです。うまくいくといいな。


red: ToDo:C#からC++/CLI を呼び出す際に、引数でデータを渡すときの渡し方を調べておくこと。 :red

64bit 整数2007/04/04 21:51

雲は、数値演算プログラムの実行速度を見ていて、ふと気がついた。なんだ、64bit の整数演算部分がとても遅い。__int64 を使っているのですが、信じられないくらいダメダメです。試しに、同じ計算を 32bit の int を使ってあげると、普通の速度で動きます。Microsoft のコンパイラ、Intel のコンパイラ両方試してみたけど、結果は変わらず。

もしかすると、32bit の WindowsXP では、__int64 を使うと処理速度が出ないのかもね。今度、64bit の Windows 上で試してみよう。