看到论坛好冷清啊。想认识论坛的高手。都冒出来吧。

特地找了几个数学题目大家来一起交流哈

题目：一个人需要上到一个n级的楼梯顶端。
         现在他单次可以踏上一级或者两级。
         
   1.请求出他到达顶端的可行方案总数。
   2.请穷举出他到达顶端的所有可行方案。
   3.若他单词可以踏上1 2 3...k级。求2。
   4.若他单次可以踏上m m+1 m+2...k级。求2。
   5.若单次可以踏上a b c ...这些值由用户输入。求2。
  
附上第3问我写出来的，呵呵。

上楼梯2.0.zip (35.27 KB)

[ 本帖最后由 q7408695 于 2011-8-9 17:36 编辑 ]

自己顶一下。

[ 本帖最后由 q7408695 于 2011-8-9 17:34 编辑 ]

第一问  斐波那契数列只不过 f(1) = 1 f(2) = 2

#include<stdio.h>
#define MAX 65
__int64 mem[MAX] = {0};
int main()
{
    int n = 0;
    mem[1] = 1;mem[2] = 2;
    for(int i = 3;i<MAX;i++)
    {
        mem[i] = mem[i-1]+mem[i-2];
    }
    while(EOF != scanf("%d",&n))
    {
        printf("%I64d\n",mem[n]);
    }
}

敢问楼主第二问要怎么穷举呢  如果n很大 它的解空间将会是一颗非常庞大的二叉树

只要从根开始累加到大于n的都将是一条可行的递归路径  已经写出来了  回溯法加剪枝


[ 本帖最后由 laoyang103 于 2011-8-9 18:11 编辑 ]

嘿嘿，先热身呗。

#include<stdio.h>
#define MAX 65
void fun(int d,int sum,int mem[],int depth,int n)//走几步 只有1 2，当前走的总步数，存储步数，递归深度,走几层
{
    if(sum > n)//剪枝
        return ;
    if(sum == n)
    {
        for(int i = 0;i<depth;i++)
            printf("%d ",mem[i]);
        printf("\n");
        return ;
    }
    mem[depth] = 1;
    fun(1,sum+1,mem,depth+1,n);
    mem[depth] = 2;
    fun(2,sum+2,mem,depth+1,n);
}
int main()
{
    int i,j,n;
    while(EOF != scanf("%d",&n))
    {
        int mem[64] = {0};
        fun(0,0,mem,0,n);
    }
}

第三问  就是把第二问的2改成n可以了

#include<stdio.h>
#define MAX 65
int step = 0;
void fun(int d,int sum,int mem[],int depth,int n)//走几步 只有1 2，当前走的总步数，存储步数，递归深度,走几层
{
    if(sum > n)//剪枝
        return ;
    if(sum == n)
    {
        for(int i = 0;i<depth;i++)
            printf("%d ",mem[i]);
        printf("\n");
        return ;
    }
    for(int i = 1;i<=step;i++)
    {
        mem[depth] = i;
        fun(i,sum+i,mem,depth+1,n);
    }
}
int main()
{
    int i,j,n;
    while(EOF != scanf("%d %d",&n,&step))
    {
        int mem[64] = {0};
        fun(0,0,mem,0,n);
    }
}

下面的都差不多  只要改下面的这个for循环递归九可以了
第四问:
for(int i = m;i<=m+k;i++)
    {
        mem[depth] = i;
        fun(i,sum+i,mem,depth+1,n);
    }
第五问:
先用数组把那些可行的步数保存  int sets[1000] = {0}; int n;//有多少中迈步法
for(int i = 0;i<n;i++)
    {
        mem[depth] = sets[i];
        fun(sets[i],sum+sets[i],mem,depth+1,n);
    }

高手。这么速度就解决了。

我是菜鸟

这叫菜鸟啊？？？ 哭了  ！   我要怎么才能到这种境界啊？？