2013蓝桥杯预选---第39级台阶

    小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级!
    站在台阶前,他突然又想着一个问题:
    如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,也就是说一共要走偶数步。那么,上完39级台阶,有多少种不同的上法呢?
    请你利用计算机的优势,帮助小明寻找答案。

要求提交的是一个整数。
注意:不要提交解答过程,或其它的辅助说明文字。

首先是Water用py给了一个思路,翻译成C#,9.8s

import time
t = 0
def f(i, j, k, s):
    global t
    if j > 0:   
        j -= i
        k += 1
        s += str(i) + ','
        if j == 0:
            f(0, j, k, s)
        else:
            f(1, j, k, s)
            f(2, j, k, s)
    elif j == 0:
        if k % 2 == 1:
            return
        t += 1
        #print('t=%d k=%s %s' % (t, k, s))
        return
    else:
        return
        
if __name__ == '__main__':
    start = time.time()
    n = 39
    f(1, n, 0, '')
    f(2, n, 0, '')
    c = time.time() - start
    print('t=%d used time %0.3f' % (t,c))

然后参考了网上的算法,翻译成C#,11.5s

#include <stdio.h>  
#include <iostream>  
#include <string.h>  
#include <algorithm>  
#include <math.h>  
using namespace std;  
int ans = 0;  
void dfs(int sum,int step)  
{  
    if(sum<0)  
    return ;  
    if(step%2 == 0 && sum == 0)  
    {  
    ans++;  
    return ;  
    }  
    for(int i = 1;i<=2;i++)  
    dfs(sum-i,step+1);  
}  
int main()  
{  
    dfs(39,0);  
    cout << ans << endl;  
    system("pause");   
    return 0;  
}  

最后是自己复习的好像叫回溯法,还是C#的,大概5.6s的样子

int n = 39;
int[] m = new int[n];
int p = 0, c = 0, s = 0;
while (true)
{
    while (s < n)
    {
        m[p] = 1; s++; p++;
    }
    if ((s == n) && ((p % 2) == 0))
        c++;
    do
    {
        p--;
        if (p < 0)
            break;
        s -= m[p];
    } while (m[p] > 1);
    if (p < 0)
        break;
    else
    {
        m[p] = 2; s += 2; p++;
    }
}

结果都是一样的:51167078

帖吧卧虎藏龙,发现二楼加入了一些自己的算法,翻译过来仅仅需要0.3s
http://tieba.baidu.com/p/3318932820

说一下我的算法思想:
(1)定性分析:由于每次我要走两步,所以一大步(两小步)可以走上2阶(1种)、3阶(2种)、4阶(2种)。那么如果我知道上到n阶、n+1阶、n+2阶的上法分别为f(n)、f(n+1)、f(n+2),则可以推出上到n+4阶的上法f(n+4)。
(2)定量分析:由(1)可得公式f(n+4)=2*f(n)+2*f(n+1)+f(n+2)。但是由于在计算f(n+2)时已经出现了一倍的f(n),所以如果使用上述公式会使得计算f(n+4)中出现重复走法,并且重复的个数为f(n),所以最后整理得到真正的公式为f(n+4)=f(n)+2*f(n+1)+f(n+2)
(3)初始条件:不难用列举法求得1阶、2阶、3阶、4阶的上法分别为0、1、2、2。
(4)代码编程:
int zoufa(int n)
{
    switch (n)
    {
        case 1: return 0;
        case 2: return 1;
        case 3: return 2;
        case 4: return 2;
        default: return zoufa(n - 4) + 2 * zoufa(n - 3) + zoufa(n - 2);
    }
}

有了前人总结的规律,这次毫秒都没了

int Miku(int n)
{
    int[] m = new int[n];
    m[0] = 0; m[1] = 1; m[2] = 2; m[3] = 2;
    if (n > 4)
        for (int i = 4; i < n; i++)
            m[i] = m[i - 4] + 2 * m[i - 3] + m[i - 2];
    return m[n - 1];
}

参考:http://blog.csdn.net/libin56842/article/details/21407503

标签: none

添加新评论