求教这个算法题的缩短时间的方法

    游戏规则是这样的：n个人站成一个圆圈，其中的一个人手里拿着一个球，当裁判吹哨子时开始传球，每个人可以把球传给自己左右的两个人中的一个（左右任意），当裁判再次吹哨子时，传球停止，此时，拿着球没传出去的那个人就是败者，要给大家表演一个节目。

    有人提出一个有趣的问题：有多少种不同的传球方法可以使得从他手里开始传的球，传了m次以后，又回到他手里。两种传球的方法被视作不同的方法，当且仅当这两种方法中，接到球的人按接球顺序组成的序列是不同的。比如有3个人，1号、2号、3号，并假设这个人为1号，球传了3次回到这个人手里的方式有1->2->3->1和1->3->2->1，共2种。

Input
 输入共一行，有两个用空格隔开的整数n，m（3<=n<=30，1<=m<=30）。 

Output
 输出共一行，有一个整数，表示符合题意的方法数。 

#include <iostream>

using namespace std;

int Ways(int,int,int);

int main ()
{
    int n,m;

    cin>>n>>m;

    cout<<Ways(m,1,n)<<endl;

    return 0;
}

int Ways (int a,int pos,int n)
{
    if(pos==0)pos=n;
    if(pos==n+1)pos=1;
    //if(pos==a+1&&pos<n/2)return 1;
    //if(pos>a+1&&pos<n/2)return 0;
    //if(pos>(n/2+1)&&pos==n-a+1)return 1;
    //if(pos>(n/2+1)&&pos<n-a+1)return 0;
    if(a==1)
    {
        if(pos==2||pos==n)return 1;
        else return 0;
    }else{
    return (Ways(a-1,pos-1,n)+Ways(a-1,pos+1,n));}
} 

 
希望论坛的牛人们能帮忙看看，我的程序超时了，怎么缩短时间？还有编程风格等方面的建议，希望不吝赐教。

------------------
Best Regards
 
施炜炜
Mason Archer
 
国立中山大学
信息科学与技术学院
Sun Yat-sen University
School of Information Science and Technology
Tel: [phone](643974)
Email Address: [e-mail]
Wei Bo: weibo.com/zixiaojun

3 个解决方案

#1

尽量不用递归，你现在是指数复杂度，当然会超时。
给你个思路：首先结果肯定是偶数，因为对称。所以可以假设第一次始终是1->2.如果7个人，传6次，最远走到4（即：m/2+1），（如前述，只考虑单方向）。而且是不重复的，只有一种。而最近的到2，也只有一种。而如果最远到3呢？因为必须的步骤是4步，多出来2步，可以在任意阶段（在3处只能右传）左右传，就是4*2+1.
就是先把范围定下来，然后中间的把必须步数减去，然后在把剩下的往返步数算出就可以了。

#2

动态规划。dp[i][j]表示第i步传到j的方法有多少种。

#3

假如规定顺时针为正方向，那么小球最终走的“位移”（传过去再反方向传回来相等的距离视为0）必然是n的整数倍，（即可能相对这个人不动（0），或相对这个人刚好顺（逆）时针传了k圈）
枚举所有可能的k值（满足|k|*n<=m && (m-|k|*n)%2==0 ）
我举个例子，n=3，m=9，k=1(本例|k|可以等于1,3)，那么简单计算可得，9次传球中必然6次是顺时针，3次是逆时针（类似鸡兔同笼），则对于这个k值，方法有 c（3,9）种，（组合数下边是9上边是3，相当于在9次传球中确定顺时针的3次的序号，剩下的序号对应的必然逆时针传，则一种传球方式可确定）
再把对所有k值求得的解相加。
对于给的例子，m==3，n==3 k为+1或-1；
对于每个k 解得个数是c（3,3）==1 所以共2个解
这是大概思路，具体实现成程序就可以了，有什么不对的地方我们再讨论~