有一段楼梯台阶有15级台阶，以小明的脚力一步最多只能跨3级，请问小明登上这段楼梯有多少种不同的走法?
A. 2345
B. 3261
C. 5768
D. 6843
解法：
http://blog.csdn.net/tengxing007/article/details/54882372
https://www.nowcoder.com/questionTerminal/360069ca7225478380ffdcfb7e4b2a2b
递归思想 与 递归方法
做递归题目遇到这个问题，以为是用递归思想解出来的，原来并不是。只是用递归方法实现计算，套用斐波那契数列公式。网上的很多解法，都是先列举前面几个结果，发现正好符合斐波那契数列规律，然后再套入递归调用，算出结果。
个人认为，这种思想并不好，需要先知道斐波那契数列，才能解这道题。
我以为，比较好的利用递归思想解题，如下汉诺塔的解题思路。
http://blog.csdn.net/computerme/article/details/18080511?locationNum=14&fps=1
设f(n)为将n片圆盘所在塔全部移动到另一塔最少总次数；由递归算法可知：f(1) = 1;当n>1时，f(n) = f(n-1) +1 + f(n-1)。f(n) = 把上面n-1片圆盘移动到中间塔最少总次数f(n-1) + 把第n片圆盘移动到目标塔+把中间盘的n-1片圆盘移动到目标塔最少总次数为f(n-1)。由数学计算可得：f(n)=2^n-1。(n>0)。
汉诺塔的解题过程，先得出递归公式，再穷举，进一步得出最终公式。-- 递归思想
上楼梯问题的解题过程，先穷举，得出公式，用递归实现。 -- 递归方法
我这里本来想自己用递归思想来解题，目前看来不现实，暂无解决方案。
结论：
1、斐波那契数列在生活中由哪些应用？
2、解算法问题时，尝试看看各个数据之间的关系，然后得出公式。
还有一个笨方法，把所有排列组合写出来，选择其中正好为总阶梯数目的组合，统计有多少种组合，就有多少种方法正好走完。以下是代码，当然还有很多可以改进的地方，感觉意义不大，就不继续深究了。
#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时间戳。
return;
}
time (&t2);//获取Unix时间戳。
//lt = localtime (&t);//转为时间结构。
//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);//输出结果
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();//计时
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);
//最慢的方法，一步一步走，就可以结束了
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();//计时
system("pause");
return 0;
}
网友评论