遞推算法 遞推問題求解過程 確定狀態 確定遞推關系和邊界條件 程序實現 例1 計算系數 NOIP2011day2 題目描述 給定一個多項式 ax by k 請求出多項式展開后xnym項的系數 輸入 共一行 包含5個整數 分別為a b k n m 每兩個整數之間用一個空格隔開 輸出 輸出共1行 包含一個整數 表示所求的系數 這個系數可能很大 輸出對10007取模后的結果 輸入輸出樣例 factor infactor out113123 數據范圍 對于30 的數據 有0 k 10 對于50 的數據 有a 1 b 1 對于100 的數據 有0 k 1 000 0 n m k 且n m k 0 a b 1 000 000 方法一 根據二項式定理可知 ax by k 取i n xnym的系數為其中an和bm可以用快速冪來計算 在lg n lg m 內完成 計算可以用遞推來求解 狀態 f i j 表示從i個數中選j個數的方案數 f k n 就是答案 根據第i數選還是不選來進行分析 1 選擇第i個數 此情況的方案數等價于從i 1個數中選擇j 1個數的方案數即f i 1 j 1 2 不選第i個數 此情況的方案數等價于從i 1個數中選擇j個數的方案數即f i 1 j 所以f i j f i 1 j 1 f i 1 j 邊界條件 f i 0 1 f i i 1 時間復雜度為O n k 方法二 當k達到106的時候 方法一會超時 由于10007是素數 在計算C k n mod10007時可以采用擴展GCD來解決 時間復雜度為O k 參考代碼 include includeusingnamespacestd ifstreamfin factor in ofstreamfout factor out constintMAXN 1005 intdp MAXN MAXN a b k n m ans intmain fin a b k n m dp 1 1 dp 1 2 1 for inti 2 i k i for intj 1 j i 1 j dp i j dp i 1 j dp i 1 j 1 10007 ans dp k m 1 for inti 1 i n i ans ans 10007 a 10007 10007 for inti 1 i m i ans ans 10007 b 10007 10007 fout ans endl return0 例2 B光滑數 問題描述 B為一個正整數 如果一個自然數N的質因子分解式中沒有大于B的因子 我們就稱N是一個B光滑數 請你編一個程序 求出某個區間中所有的B光滑數的個數 輸入 輸入文件名為bnum in 僅有一行 包含三個用空格隔開的整數N M B 其中1 N 2 000 000 000 1 M 100 000 000 1 B 1 000 000 輸出 輸出文件名為bnum out 僅一行 一個整數 表示區間 N N M 之間的B光滑數的個數 樣例輸入 30105 樣例輸出 4 參考題解 首先我們定義一個表pri max pri i 表示第i個質數 第一個質數為2 設數組max 其中max i 記錄i的最大質因子 定義f b x1 x2 表示區間 x1 x2 之間不包括大于第b個質數的質因子的所有正整數 則有如下遞歸關系 F b x1 x2 f b 1 x1 x2 f b x1 1 divpri b 1 x2divpri b 該遞歸式的邊界條件為 F 0 x1 x2F x2 x1 1x2 pri b 可直接驗證x1 x2F trunc log2 x2 trunc log2 x1 b 1 例3 出棧序列統計 問題描述 棧是常用的一種數據結構 有n個元素在棧頂端一側等待進棧 棧頂端另一側是出棧序列 你已經知道棧的操作有兩種 push和pop 前者是將一個元素進棧 后者是將棧頂元素彈出 現在要使用這兩種操作 由一個操作序列可以得到一系列的輸出序列 請你編程求出對于給定的n 計算并輸出由操作數序列1 2 n 經過一系列操作可能得到的輸出序列總數 輸入 輸出 就一個數n 1 n 1000 一個數 即可能輸出序列的總數目 樣例 stack instack out35 算法分析 我們通過回溯的方法計算并輸出不同的出棧序列 這里只要求輸出不同的出棧序列總數目 所以我們希望能找出相應的遞推公式進行處理 從排列組合的數學知識可以對此類問題加以解決 我們先對n個元素在出棧前可能的位置進行分析 它們有n個等待進棧的位置 全部進棧后在棧里也占n個位置 也就是說n個元素在出棧前最多可能分布在2 n位置上 出棧序列其實是從這2n個位置上選擇n個位置進行組合 根據組合的原理 從2n個位置選n個 有C 2n n 個 但是這里不同的是有許多情況是重復的 每次始終有n個連續的空位置 n個連續的空位置在2n個位置里有n 1種 所以重復了n 1次 所以出棧序列的種類數目為 算法分析 C 2n n n 1 2n 2n 1 2n 2 n 1 n n 1 2n 2n 1 2n 2 n 2 n 考慮到這個數據可能比較大 所以用高精度運算來計算這個結果 本題實際是一個經典的Catalan數模型 有關Catalan數的詳細解釋請參考 組合數學 等書 參考程序 include includeusingnamespacestd typedeflonglonglld lldi n ans lldh 1000 intmain freopen stack in r stdin freopen stack out w stdout h 2 1 cin n n n 2 for lldi 3 i n i for lldk 2 k i k h i h i h k h i k 1 cout h n endl return0 思考與提高 我們知道 在某個狀態下 所能做的操作 移動方法 無非有兩種 1 將右方的等待進棧的第一個元素進棧 2 將棧頂的元素出棧 進入左邊的出棧序列 設此時右方 棧 左方的元素個數分別為a b c 我們就能用 a b c 表示出當前的狀態 顯然n a b c 則c n a b 即已知a和b c就被確定 所以我們可以用 a b 來作為狀態的表示方法 則起始狀態為 n 0 目標狀態為 0 0 又由上面的兩種移動方法 我們可類似的得到兩種狀態轉移方式 思考與提高 思考與提高 再設f a b 為從狀態 a b 通過移動火車變為狀態 0 0 的所有移動方法 類似于動態規劃的狀態轉移方程 我們可寫出以下遞歸式 邊界值 f 0 0 1 有了這個遞歸公式后 再寫程序就比較簡單了 例4 骨牌覆蓋問題 有2行n列的長方形方格 要求用n個1 2的骨牌鋪滿 有多少種鋪法 如n 3時有以下3種覆蓋方法 方法一 狀態 f i 表示鋪滿2 i的長方形的方案數找規律 手工或搜索求出i 1 2 3 4 5的方案數分別為1 2 3 5 8 容易發現f i f i 1 f i 2 i 3 邊界條件 f 1 1 f 2 2遞推關系式1i 1f i 2i 2f i 1 f i 2 i 3答案為f n 時間復雜度為O n 方法二 對于i 3 分析第一列的兩個格子覆蓋情況 有兩種情況 1 用1 2的骨牌豎著覆蓋第一列 這種情況的方案數等于后面2 i 1 的長方形的覆蓋方案數 即f i 1 2 用兩個1 2的骨牌橫著覆蓋 這種情況的方案數等于后面2 i 2 的長方形的覆蓋方案數 即f i 2 所以f i f i 1 f i 2 方法三 分析用1 2的骨牌覆蓋列的位置來計算方案數1 如果i為偶數 覆蓋方案分為兩類 1 沒有豎立覆蓋其中一列的情況 全部用橫向覆蓋的方案 方案數為1 2 有豎立覆蓋的情況 為了避免重復 考慮第一次豎立覆蓋的位置在x列 x必須是奇數 而且前1到x 1列覆蓋方法唯一 全部采用橫向覆蓋 方案數等于后面i x列的覆蓋情況 即f i x 所以當i為偶數時 f i 1 f 1 f 3 f i 3 f i 1 2 如果i是奇數 一定有豎立覆蓋的情況 f i 1 f 2 f 4 f i 3 f i 1 如何證明該遞推關系式等價于f i f i 1 f i 2 試著用橫向覆蓋的來分析遞推關系式 方法四 分治 一分為二來考慮 左邊為ndiv2列 右邊為n ndiv2列 如果左右獨立則方案數為f ndiv2 f n ndiv2 如果有橫向覆蓋第ndiv2列和第ndiv2 1列 則方案數為f ndiv2 1 f n ndiv2 1 所以f n f ndiv2 f n ndiv2 f ndiv2