遞推求解–高精度計算
實驗題目一：
王老師爬樓梯，他可以每次走1級或者2級或者3級樓梯，輸入樓梯的級數，求不同的走法數。（要求遞推求解）如果N很大，需要高精度計算。
【Accepted】 OJ代碼
#include<iostream>
using namespace std;
int main()
{
int i;
int p, q;
int s = 0;//判斷第一個輸出的數
cin >> i;
int n[1000][100] = { NULL }; //1000行 100列，每列存放五位長的數字
n[0][99] = 1;
n[1][99] = 2;
n[2][99] = 4;
int m;
for (p = 3; p < i; p++)
{
m = n[p - 3][99] + n[p - 2][99] + n[p - 1][99]; //計算最低五位數
n[p][99] = m % 10000; //計算結果取餘最低五位存放在數組中
for (q = 98; q >= 0; q--)
{
m = n[p - 3][q] + n[p - 2][q] + n[p - 1][q] + m / 10000; //計算第q位的五位數字（第q位的計算結果加上第五位的進位）
n[p][q] = m % 10000; //計算結果取餘第五位存放在數組中
}
}
for (int j = 0; j < 100; j++) //循環輸出
{
if (n[i - 1][j] != 0 && s == 0) //第一個輸出的不為0的數，不按照五位輸出
{
cout << n[i - 1][j];
s = 1;
}
else if (n[i - 1][j] != 0 && s == 1) //其他按照五位固定輸出
{
printf("%04d", n[i - 1][j]);
s = 1;
}
}
cout << endl;
system("pause");
return 0;
}
PS：高精度：數組存儲，每列數組存儲五位數。
運作截圖：
實驗題目二：
（請用遞推方式求解）對于一個2行N列的走道。現在用12,22的磚去鋪滿。問有多少種不同的方式。下圖是一個2行17列的走道的某種鋪法。
思考：觀察前n個結果，可以得到遞推式子；如果N很大，需要高精度計算
【Occepted】 OJ代碼
#include<iostream>
using namespace std;
int main()
{
int i;
int p, q;
int s = 0;//判斷第一個輸出的數
cin >> i;
int n[1000][100] = { NULL }; //1000行 100列，每列存放五位長的數字
n[0][99] = 1;
n[1][99] = 3;
n[2][99] = 5;
int m;
for (p = 3; p < i; p++)
{
m = n[p - 2][99] * 2 + n[p - 1][99]; //計算最低五位數
n[p][99] = m % 10000; //計算結果取餘最低五位存放在數組中
for (q = 98; q >= 0; q--)
{
m = n[p - 2][q] * 2 + n[p - 1][q] + m / 10000; //計算第q位的五位數字（第q位的計算結果加上第五位的進位）
n[p][q] = m % 10000; //計算結果取餘第五位存放在數組中
}
}
for (int j = 0; j < 100; j++) //循環輸出
{
if (n[i - 1][j] != 0 && s == 0) //第一個輸出的不為0的數，不按照五位輸出
{
cout << n[i - 1][j];
s = 1;
}
else if(n[i - 1][j] != 0 && s == 1) //其他按照五位固定輸出
{
printf("%04d", n[i - 1][j]);
s = 1;
}
}
cout << endl;
system("pause");
return 0;
}
運作截圖：
實驗題目三
一組n個數，要從中選出其中m個數，使得選出的m個數之間的最小間隔最大。
提示，如果假設間隔為1，然後不斷+1測試，直到最大可能，計算量太大；是以可以采用二分。
【Occepted】 OJ代碼
#include<iostream>
using namespace std;
int a[1000];
int n, m; //輸入的n和m
void selectionsort() //選擇排序
{
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (a[j] < a[i])
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
bool judge(int space) //判斷該間隔是否符合條件
{
int temp, num;
temp = a[0];
num = 1;
for (int i = 1; i < n; i++)
{
if (a[i] - temp >= space) //如果兩數之間的間隔大于現在的間隔
{
num++; //找到數量加一
temp = a[i];
}
}
if (num >= m) //加入數量大于等于查找的m個數
return true;
else
return false; //查找失敗
}
int search()
{
int max, min,half; //max為最大間隔,min為最小間隔
min = 1; //假設最小間隔為1
max = a[n - 1] - a[0]; //最大間隔為數組最大值減去最小值
//二分查找
while ((min != max) && (min + 1 != max))
{
half = (max + min) / 2;
if(judge(half)) //假如中間成功找到，說明還可能有比該間隔更大的間隔
min = half;
else
max=half; //中間間隔未成功，說明這麼大的間隔無法滿足要求
}
if (judge(max)) //此時min=max或min+1=max，判斷其中一個是否符合條件
return max;
else
return min;
}
int main()
{
cin >> n >> m ;
if (n >= m)
{
for (int i = 0; i < n; i++)
{
cin >> a[i];
if (i == n - 1)
break;
}
selectionsort(); //從小到大的順序排好輸入的數組
cout << search()<<endl;
}
system("pause");
return 0;
}
運作截圖：