刚刚社团里突然有人问我这个问题，其实很简单的，但我看网上竟然没有讲这个的（可能是太简单了吧），反正有空，我也写一下思路吧

1.问题描述

题目描述
上体育课的时候，小蛮的老师经常带着同学们一起做游戏。

这次，老师带着同学们一起做传球游戏。

游戏规则是这样的：

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

闲的没事的小蛮提出一个无聊的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m次以后，又回到小蛮手里。

两种传球的方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。

比如有3个同学1号、2号、3号，并假设小蛮为1号，球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1，共2种。

输入样例
3 3
输出样例
2
复制代码

原题链接-传球问题

2.简单的思路

这个题，递推即可，每一个传球，只有两种可能，一种球在小蛮里，一种球不在小蛮手里

思路：

n个人传m次球
令ball[m][1]表示球在A老师手里的方案数，令ball[n][0]表示球不在A老师手里的方案数，于是
ball[m+1][1]=dp[m][0]
ball[m+1][0]=dp[m][1]*(n-1)+ball[m][0]*(n-2)

因此
我们只要预先初始化前面传的几次后再递推一下就可以了

只传0次的不给予讨论（嫌麻烦）
只穿1次的，很明显，n个人，传不到的次数是 n-1  ，传的到的次数是 0
之后就根据传1次的来递推就可以了
复制代码

3.C语言代码

#include<stdio.h>

void Output( int [][2] , int  ,int); 
void init(int [][2],int n);
void printarr(int arr[][2],int n);

int main()
{
	int n , m ;//n个人，传m次
	
    printf("输入人数\n");
    scanf("%d",&n);
    printf("输入次数\n");
    scanf("%d",&m);

    int ball[50][2];    //c语言好像得先分配好数组的空间才可以
    init(ball,m);   //初始化数组的
    // printarr(sz,m);//打印数组的，m行

    ball[1][0]=n-1; //一个球传一次传不到第一个人的次数
    ball[1][1]=0;   //一个球传一次传到第一个人的次数

    if(n>=2&&m>=2)
    {
        Output(ball,n,m);
    }
    else
    {
        printf("\n开摆了，这部分输出不想写\n");
    }

    printf("次数：%d",ball[m][1]);
    
    getchar();

    return 0 ; 
 } 
 void Output( int arr[50][2] , int n,int m)
 {
 	for(int i = 2;i<=m;i++)
    {
        for(int j= 0;j<2;j++)
        {
            if(j==1)    arr[i][j] = arr[i-1][0];

            if(j==0)    arr[i][j] = arr[i-1][1]*(n-1) + arr[i-1][0]*(n-2);
        }
    }
 }

 void init(int arr[50][2], int n)
 {
     for (int i = 0;i<=n;i++)
        for(int j = 0;j<2;j++)
            arr[i][j] = 0;
 }

 void printarr(int arr[50][2],int n)
 {
      for (int i = 0;i<n;i++)
      {
        putchar('\n');  
        for(int j = 0;j<2;j++)
        {
            printf(" %d ",arr[i][j]);
        }     
      }
 }
复制代码