読者です 読者をやめる 読者になる 読者になる

C++競プロ学習日記(仮)

( 学習記録であり解説Blogではないです )

再帰と分割統治法|アルゴリズムとデータ構造

アルゴリズムとデータ構造 関数 コード

アルゴリズムとデータ構造 第6章−1「再帰と分割統治法」で階乗コードを書きました。

#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
using namespace std;
int func( int n )
{
    if( n == 1 )
    {
        return 1;
    }
    return n * func( n - 1 ); //自分自信を呼び出し
}
int main()
{    
    int n;
    cin >> n;
    
    REP2( i, 1, n )
    {
        cout << setw( 2 ) << setiosflags( ios::right ) //右桁合わせ
             << i << "! = " << func( i ) << endl;
    }
    return 0;
}

「分割統治法」とは...
1)与えられた問題を部分問題に「分割」する(Divide)
2)部分問題を再帰的に解く(Solve)
3)得られた部分問題を「統合」して元の問題を解く(Conquer)

( 参考:アルゴリズムとデータ構造 P140 )

難しい...(感想)