雲の亀日記

ついつい、現実逃避をして再帰関数で遊んでいます。たまたま見つけた、再帰表現法という書籍に説明のあった、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) );
 }

}