有一段樓梯臺(tái)階有15級(jí)臺(tái)階，以小明的腳力一步最多只能跨3級(jí)，請(qǐng)問(wèn)小明登上這段樓梯有多少種不同的走法?
A. 2345
B. 3261
C. 5768
D. 6843
解法：
http://blog.csdn.net/tengxing007/article/details/54882372
https://www.nowcoder.com/questionTerminal/360069ca7225478380ffdcfb7e4b2a2b?
遞歸思想 與 遞歸方法
做遞歸題目遇到這個(gè)問(wèn)題，以為是用遞歸思想解出來(lái)的十电，原來(lái)并不是维雇。只是用遞歸方法實(shí)現(xiàn)計(jì)算，套用斐波那契數(shù)列公式翠拣。網(wǎng)上的很多解法，都是先列舉前面幾個(gè)結(jié)果游盲，發(fā)現(xiàn)正好符合斐波那契數(shù)列規(guī)律误墓，然后再套入遞歸調(diào)用，算出結(jié)果益缎。
個(gè)人認(rèn)為谜慌，這種思想并不好，需要先知道斐波那契數(shù)列莺奔，才能解這道題欣范。
我以為，比較好的利用遞歸思想解題，如下漢諾塔的解題思路恼琼。
http://blog.csdn.net/computerme/article/details/18080511?locationNum=14&fps=1?
設(shè)f(n)為將n片圓盤(pán)所在塔全部移動(dòng)到另一塔最少總次數(shù)妨蛹；由遞歸算法可知：f(1) = 1;當(dāng)n>1時(shí)，f(n)? = f(n-1) +1 + f(n-1)晴竞。f(n) = 把上面n-1片圓盤(pán)移動(dòng)到中間塔最少總次數(shù)f(n-1) + 把第n片圓盤(pán)移動(dòng)到目標(biāo)塔+把中間盤(pán)的n-1片圓盤(pán)移動(dòng)到目標(biāo)塔最少總次數(shù)為f(n-1)蛙卤。由數(shù)學(xué)計(jì)算可得：f(n)=2^n-1。(n>0)噩死。
漢諾塔的解題過(guò)程颤难，先得出遞歸公式，再窮舉已维，進(jìn)一步得出最終公式行嗤。-- 遞歸思想
上樓梯問(wèn)題的解題過(guò)程，先窮舉垛耳，得出公式栅屏，用遞歸實(shí)現(xiàn)。 -- 遞歸方法
我這里本來(lái)想自己用遞歸思想來(lái)解題堂鲜，目前看來(lái)不現(xiàn)實(shí)既琴，暫無(wú)解決方案。
結(jié)論：
1泡嘴、斐波那契數(shù)列在生活中由哪些應(yīng)用甫恩？
2、解算法問(wèn)題時(shí)酌予，嘗試看看各個(gè)數(shù)據(jù)之間的關(guān)系磺箕，然后得出公式。
還有一個(gè)笨方法抛虫，把所有排列組合寫(xiě)出來(lái)松靡，選擇其中正好為總階梯數(shù)目的組合，統(tǒng)計(jì)有多少種組合建椰，就有多少種方法正好走完雕欺。以下是代碼，當(dāng)然還有很多可以改進(jìn)的地方棉姐，感覺(jué)意義不大屠列，就不繼續(xù)深究了。
#include "stdafx.h"
#include "stdlib.h"
#include "time.h"
using namespace std;
//#define MAX_TIMES (1073741824)
#define ALL_STAIRS (12)
#define MAX_STEPS (3)
#define MIN_STEPS (1)
void print_time()
{
static time_t t1 = 0,t2 = 0;
struct tm * lt;
if (0 == t1)
{
time (&t1);//獲取Unix時(shí)間戳伞矩。
return;
}
time (&t2);//獲取Unix時(shí)間戳笛洛。
//lt = localtime (&t);//轉(zhuǎn)為時(shí)間結(jié)構(gòu)。
//printf ( "%d/%d/%d %d:%d:%d\n",lt->tm_year+1900, lt->tm_mon, lt->tm_mday, lt->tm_hour, lt->tm_min, lt->tm_sec);//輸出結(jié)果
cout << "spend time = " << t2 - t1 << endl;
return;
}
void print_array(int *array, int size)
{
int i = 0;
while (i < size)
{
cout << array[i] << " , ";
i++;
}
cout << "\r\n" << endl;
return;
}
char calc(int * array, int size)
{
int ret = 0;
int sum = 0;
int i = 0;
int invalid_zero = 0;
while ((i < size))
{
if (0 == array[i])
{
invalid_zero = 1;
break;
}
sum += array[i];
i++;
}
while ((i < size))
{
if ((1 == invalid_zero) && (0 != array[i]))
{
return 0;
}
i++;
}
if (ALL_STAIRS == sum)
{
ret = 1;
}
return ret;
}
int add(int * value)
{
int ret = 0;
if (*value == MAX_STEPS)
{
*value = MIN_STEPS;//最少走一步
ret = 1;
}
else
{
(*value)++;
}
return ret;
}
int fullfill(int *array)
{
int i = 0;
int ret = 0;
while ((i < ALL_STAIRS) && add(&array[i]))
{
i++;
}
if (i >= ALL_STAIRS)
{
ret = 1;
}
return ret;
}
int selective_fill(int *array, int min_size, int max_size)
{
int i = 0;
int ret = 0;
while ((i < ALL_STAIRS) && add(&array[i]))
{
i++;
}
if (i >= ALL_STAIRS)
{
ret = 1;
}
return ret;
}
int _tmain(int argc, _TCHAR* argv[])
{
int array[ALL_STAIRS] = {0};
int array_size = sizeof(array)/sizeof(int);
int sum = 0;
int i = 0;
int max_times = ALL_STAIRS;
int min_times = ALL_STAIRS/MAX_STEPS + 1;
int max_calc_times = pow(double(MAX_STEPS+1),double(ALL_STAIRS));
cout << "max_calc_times = " << max_calc_times << endl;
print_time();//計(jì)時(shí)
while (1)
{
if (fullfill(array))
{
break;
}
//if (selective_fill(array, min_times, max_times))
//{
// break;
//}
print_array(array, array_size);
sum += calc(array, array_size);
//最慢的方法乃坤，一步一步走苛让，就可以結(jié)束了
if (array[max_times-1])
{
break;
}
}
cout << "STEPS = " << MIN_STEPS << " ~ "<< MAX_STEPS << endl;
cout << "ALL_STAIRS = " << ALL_STAIRS << endl;
cout << "sum = " << sum << endl;
print_time();//計(jì)時(shí)
system("pause");
return 0;
}
