再帰のお勉強 ― 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) ); }
}
コメントをどうぞ
※メールアドレスとURLの入力は必須ではありません。 入力されたメールアドレスは記事に反映されず、ブログの管理者のみが参照できます。
※なお、送られたコメントはブログの管理者が確認するまで公開されません。
※投稿には管理者が設定した質問に答える必要があります。