相關(guān)概念?

遞推方程是指一種遞歸定義，它將問題拆分成更小的子問題，并使用這些子問題的解來計算原問題的解。離散數(shù)學(xué)中，遞推方程通常用于描述數(shù)列、組合問題等。

以下是一些遞推方程相關(guān)的概念和公式：

1. 遞推公式：遞推公式是指將一個問題拆分成更小的子問題，并使用這些子問題的解來計算原問題的解的公式。通常用于描述數(shù)列。

2. 初始條件：遞推公式需要初始條件來確定數(shù)列的起始值。例如，斐波那契數(shù)列的初始條件是前兩個數(shù)為0和1。

3. 遞推關(guān)系式：遞推關(guān)系式是指描述一個問題中相鄰兩項之間的關(guān)系的公式。例如，斐波那契數(shù)列的遞推關(guān)系式為f(n) = f(n-1) + f(n-2)。

4. 通項公式：通項公式是指將遞推公式表示為一個包含n的表達式，直接計算第n項的值。例如，斐波那契數(shù)列的通項公式為

5. 逆向遞推：逆向遞推是指從已知的數(shù)列末項倒推出數(shù)列的初始項。通?？墒褂猛椆交蜻f推公式進行逆向遞推。

6. 生成函數(shù)：生成函數(shù)是一種將一個數(shù)列表示為一個形式冪級數(shù)的函數(shù)?？梢岳蒙珊瘮?shù)求解數(shù)列的各種性質(zhì)和問題。

1.?(程序題)江城子

古詩詞的平仄規(guī)律 平仄,是中國詩詞中用字的聲調(diào)。平指平直,仄指曲折，而蘇軾在寫宋詞的時候?qū)⑵鋭澐譃?種，平，上仄和下仄；而一句詞是有效的當(dāng)且僅當(dāng)這句詞中含有偶數(shù)個“平”；現(xiàn)在讓你計算n位長的詞是有效的話有多少種聲調(diào)？---------“十年生死兩茫茫，不思量，自難忘”！

注意：0是偶數(shù)

Input

輸入數(shù)據(jù)只有1組，一個整數(shù)n(1<=n<=20);

Output

對于輸入的數(shù)據(jù)n,輸出本題答案

Sample Input

2

Sample Output

5

#include <iostream>
#include <cmath>
using namespace std;int main() {int n; // n為指數(shù);cin >> n;long long  sum = pow(3, n); // 調(diào)用pow()函數(shù)求解3的n次方long long result = (1 + sum) / 2;cout << result;return 0;
}

?2.?(程序題)涂格子

一個1*n的方格用紅、藍、綠或橙色四種顏色涂色，如果有偶數(shù)個方格被涂成紅色，還有偶數(shù)個方格被涂成綠色，問有多少種方案？（15分）

Input

輸入數(shù)據(jù)有多組，每組有1個正整數(shù)n(1<=n<=10),代表方格的個數(shù)。

Output

在一行內(nèi)輸出有多少種方案？

Sample Input

1

Sample Output

2

#include <iostream>
#include <cmath>
using namespace std;int main() {int n; // n為指數(shù);while(cin>>n){long long  sum1 = pow(4, n - 1);long long  sum2 = pow(2, n - 1);long long result;if(n == 0)result = 1 ;elseresult = sum1 + sum2 ;cout << result << endl;}return 0;
}

3.?(程序題)?fibonacci數(shù)列

fibonacci數(shù)列定義為 1? ?1? ?2? ?3? ? ?5? ? ?8 ......;

f(n)=f(n-1)+f(n-2);? ?f(0)=1;f(1)=1;

現(xiàn)在請你計算第n個該數(shù)列的長度是多少？（就是求f(n)的位數(shù)）

輸入數(shù)據(jù)只有1組，一個數(shù)n(1<=n<=1000000)

輸出f(n)的位數(shù)即可！

例子輸入；

2

例子輸出

1

#include <iostream>#include <cmath>using namespace std;int main(){int n;double x,sum;cin>>n;x=log10((1+sqrt(5))/2);sum=x*n;cout<<int(sum)+1<<endl;return 0;}

?4.?(程序題)?信息編碼

一個編碼系統(tǒng)用八進制數(shù)字對信息編碼，一個碼字是有效的當(dāng)且僅當(dāng)含有偶數(shù)個7，求n位長的有效碼字有多少個？（10分）

Input

輸入數(shù)據(jù)有多組，每組有1個正整數(shù)n(1<=n<=10),代表編碼的長度。

Output

在一行內(nèi)輸出n位長的有效碼字有多少個？

Sample Input

1

Sample Output

7

#include <iostream>#include <cmath>using namespace std;int main() {int n; // n為指數(shù);while(cin >> n){long long  sum1 = pow(6, n);long long  sum2 = pow(8, n);long long result = (sum1 + sum2) / 2;cout << result<<endl;}return 0;}?