Just the association suddenly someone asked me this question, in fact, very simple, but I see online unexpectedly did not talk about this (may be too simple), anyway free, I also write a train of thought

1. Problem description

During PE class, Xiaoman's teacher often played games with his classmates. This time, the teacher led the students to play passing game. Here's how the game works: N students stand in a circle, one of the students holding a ball, when the teacher blew his whistle to pass, each student can pass the ball around one of the two classmates some (any), when the teacher blew his whistle again, pass the ball to stop, at this time, holding the ball didn't go to the students is the loser, to give you a performance. The idle Man asked a boring question: how many different ways to pass the ball that started from Man's hand, m passes later, will come back to man. The two ways of passing the ball are considered different if and only if the sequence of the students who receive the ball is different in both ways. Such as the3A classmate1Number,2Number,3And assume that Xiaoman is1Number, the ball is passed3There are two ways to get back to Barbarian1->2->3->1and1->3->2->1, a total of2Kind of. Enter the sample3 3The output sample2
Copy the code

Original problem link – Pass problem

2. Simple thinking

For each pass, there are only two possibilities: one ball is in Barbarian and one ball is not in barbarian’s hand

Ideas:

Ball [m][1] = = = = = = = = = = = = = = = = = = =0Teacher A doesn't have the ball1] [1]=dp[m][0]
ball[m+1] [0]=dp[m][1]*(n-1)+ball[m][0]*(n-2) so we just need to pre-initialize the previous pass a few times and then push it again0Second time no discussion (bother) only wear1Times, obviously, n people, n minus times1And the number of times it gets sent is zero0And then according to the passage1I'm just going to recurseCopy the code

C language code

#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 people, m times
	
    printf("Input number \n");
    scanf("%d",&n);
    printf("Input count \n");
    scanf("%d",&m);

    int ball[50] [2];    // C seems to allocate the space of the array first
    init(ball,m);   // Initializes the array
    // printarr(sz,m); // Prints m lines of the array

    ball[1] [0]=n-1; // The number of times a ball can not be passed to the first person
    ball[1] [1] =0;   // The number of times a ball is passed to the first person

    if(n>=2&&m>=2)
    {
        Output(ball,n,m);
    }
    else
    {
        printf("\n open, this part of the output do not want to write \n");
    }

    printf("Times: %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]); }}}Copy the code