挑战10

rosynirvana

先把问题一般化：
设台阶的数目为n， 走法是f(n)
首先注意到
n = 1，只有一节台阶， 那么f(n) = 1
n = 2，f(n) = 2
n = 3，f(n) = 4 (1, 1, 1) (2, 1) (1, 2) (3) 这四种走法

对于比较大的数字，注意最后一步，可能走了1节，也可能走了2节，也可能走了3节
如果走1节，那么可能性一共有f(n-1)种，如果走2节，可能性一共f(n-2)种，3节就是f(n-3)种
于是得到f(n) = f(n-1) + f(n-2) + f(n-3) (n >= 4)
这是一个斐波那契数列的变形，那么就可以用之前的方法来计算

代码：

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.   int i;
   
6.   long long int step[36+1] = {0, 1, 2, 4};
   
7.   for(i = 4; i!=36+1; ++i)
   
8.     step[i] = step[i-1] + step[i-2] + step[i-3];
   
9.   printf("%lld\n", step[36]);
   
10.   return 0;
    
11. }

复制代码

星辰幻影

#include <stdio.h>
#include <stdlib.h>
int main()
{
        int a,b,c,d,i,j,k;
    a=1;b=2;c=3;d=0;
    for(i=0;i<37;i++)
                for(j=0;j<19;j++)
                        for(k=0;k<13;k++)
                                if(i*a+j*b+k*c==36)
                                        d=d+1;
    printf("%d",d);
        system("pause");
        return 0;
}

看不懂，我是这样做的，结果错了，不知道怎么改。

rosynirvana

星辰幻影 发表于 2014-1-4 18:33
#include
#include
int main()

整个理解错了，没法改，只能重写

星辰幻影

rosynirvana 发表于 2014-1-4 18:55
整个理解错了，没法改，只能重写

理解错了？你上面的解法我看不懂

超神级

星辰幻影 发表于 2014-1-5 12:20
理解错了？你上面的解法我看不懂

http://bbs.ahalei.com/thread-2986-1-1.html这个解法应该容易理解

星辰幻影

超神级 发表于 2014-1-6 18:30
http://bbs.ahalei.com/thread-2986-1-1.html这个解法应该容易理解

谢谢，收藏以后再看

981013

用float做出来是2082876160
检查了算法n遍，还是错
用long long做出来是2082876103（看了这帖我才知道有%lld这回事{:soso_e127:}）对了
差别怎么会这么大！
误差是累积了吗？
可是每步计算都是看似精确的******.000000！（如图）

求解释

rosynirvana

981013 发表于 2014-1-22 15:45
用float做出来是2082876160
检查了算法n遍，还是错
用long long做出来是2082876103（看了这帖我才知道有% ...

float只有6位有效数字，除了最左边6位数字之外都不能保证，而不是精确到小数点后6位
基本上你永远不会需要float的

另外如果使用的libc是微软提供的msvcrt，那么long long的占位符是%I64d，%lld会被当作%ld处理

挑战所有的代码示例都基于clang3.1，我在挑战1里面写过