母関数の構想で母関数のコードを解釈する

この文章はあなたがすでに母関数に関する数学の知識を見た上で創立して、もし見たことがないならば、hduフォーラムの母関数の授業を見て、ドアを転送することをお勧めします:http://acm.hdu.edu.cn/forum/read.php?tid=3853
最も簡単な例でコードを説明します.
硬貨の額面は1元、5元、10元、25元、50元があって、全部で5種類、1つのお金に対してmoneyを数えて、いくらの中で両替する方法がありますか?
母関数を簡単に構築
G(x) = (x^0 + x^1 + x^2 + …) * (x^0 + x^5 + x^10 + …) * (x^0 + x^10 + x^20 + …)
       * (x^0 + x^25 + x^50 + x^75 + …) * (x^0 + x^50 + x^100 + x^150 + …)
数学の上の構想はこの多項式の因式を分解して、x^moneyの係数がいくらなのかを見てみましょう.だから、プログラミングの鍵はどのように分割を実現するかです.
構想はまず前の2つの因式を分解して、1つの因式を得て、第2の因式に代わります;次に、第3の因式の代わりに、第2の因式(求められた因式)と第3の因式を乗算する.最後の因子式に再帰的に計算し,結果を導いた.
プログラミングが容易なため,G(x)の前に1つの因子(1*x^0+0*x^1+0*x^2+...)を追加し,この因子は1であるため,親関数の値は変更されない.算出された因子の係数を一つの配列aに格納し、現在の因子と次の因子とを乗算した因子の係数を別の配列bに格納する.2つの因式が乗じ終わったら、b配列の中のデータをa配列の中に入れて、b配列を空にして、さっきの手順を繰り返して、最後の因式が乗じて、やっと終わりました.このとき,aデータに格納されるのは,分割された多項式の係数である.
コードは次のとおりです.

#define M 500

int a[M];
int b[M];

void GenerationFunction()
{
    int cent[5] = {1, 5, 10, 25, 50};
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    a[0] = 1; //              (1*x^0 + 0*x^1 + 0*x^2 + … )
    for(int i = 0; i < 5; i ++) // i           （ 0   ）
    {
        for(int j = 0; j < M; j ++)
        {   // j              ，a[j]         j      
            for(int k = 0; j+k < M; k += cent[i])
            {   // k           ，        cent[i]    。
                //   ，   ，    k        1
                
                b[j+k] += a[j]; //    a[j] * x^j * x^k = a[j] * x^(j+k) 
                                //    x^(j+k)     a[j]              b   
            }
        }
        for(int j = 0; j < M; j ++)
        { //     b          a  ，          ；  ，     b
            a[j] = b[j];
            b[j] = 0;
        }
    }
}

明らかに、a配列とbデータはスクロール操作であり、1つの2次元配列で、1つのスクロール変数を加えて簡単な操作を行うことができる.

#define M 500

int ans[M];
int f = 0;

void GenerationFunction()
{
    int cent[5] = {1, 5, 10, 25, 50};
    memset(ans, 0, sizeof(ans));
    ans[0][0] = 1; //            
    for(int i = 0; i < 5; i ++)
    {
        for(int j = 0; j < M; j ++)
        {
            for(int k = 0; j+k < M; k += cent[i])
            {
                ans[1-f][j+k] += ans[f][j];
            }
        }
        memset(ans[f], 0, sizeof(ans[f])); //       ，        
        f = 1 - f; //       
    }
}

2つのコードを見た.リュックサックを見た子供靴は一般的にリュックサックを連想します.
要求されたmoneyについては、リュックの大きさと理解され、各硬貨の額面は貨物の大きさと理解され、a[i]は現在の硬貨を選択し、中にiサイズの貨物を入れる方法数である.タイトルのコインが無限であれば、完全リュックサックですが、制限があれば、修正版の完全リュックサックです.最後に、a[money]は完全部硬貨を選択し、リュックサックにmoneyサイズの貨物を入れる方法数、つまりmoney元を各種硬貨に両替する方法数である.
もちろん,母関数の考え方でコードを理解してもよい.このようにすれば、基本的にhduの授業の中の問題を解決することができ、hdu 2069 Coin Changeを除く.
Coin Changeのテーマには、両替方法ごとに1000個を超えないコインが要求されています.母関数でどうやってこの問題を解決しますか?リュックサックの方法を参考に--1次元を増やします!コードは次のとおりです.

#define M 300

int ans[2][M][101];
int f = 0;

void GenerationFunction()
{
    int cent[5] = {1, 5, 10, 25, 50};
    ans[0][0][0] = 1; //    
    for(int i = 0; i < 5; i ++)
    {
        for(int j = 0; j < M; j ++)
        {
            for(int k = 0; j+k < M; k += cent[i])
            {
                for(int g = 0; g+k/cent[i] < 101; g ++)
                {
                    // ans[][j][g]     j      ，    g     ，    
                    ans[1-f][j+k][g+k/cent[i]] += ans[f][j][g];
                }
            }
        }
        memset(ans[f], 0, sizeof(ans[f]));
        f = 1 - f;
    }
}

いくつかのコードを見て、基本的には、母関数の考え方で叩いたコードとリュックサックで叩いたコードは基本的に同じです.これは母関数の考え方がリュックサックの考え方の一つであることを意味する.もし子供靴がリュックサックに慣れていれば、基本的に母関数のコードをすぐに消化することができますが、もちろん、リュックサックに慣れていないと、私のように母関数の考え方でコードを叩くことができます.効果は同じです.
最後に、hduの授業の最後のページの練習問題をここに貼り付けます:1028、1709、1085、1171、1398、2069、2152.
転載先:https://www.cnblogs.com/lijunle/archive/2010/09/04/1817764.html