# 排列球以使相邻球为不同类型的方式

2021年4月4日19:04:10 发表评论 649 次浏览

## 本文概述

``````Input  : p = 1, q = 1, r = 0
Output : 2
There are only two arrangements PQ and QP

Input  : p = 1, q = 1, r = 1
Output : 6
There are only six arrangements PQR, QPR, QRP, RQP, PRQ and RPQ

Input  : p = 2, q = 1, r = 1
Output : 6
There are only six arrangements PQRP, QPRP, PRQP, RPQP, PRPQ and PQPR``````

1)最后要放置的球是P型

2)最后要放置的球是Q型

3)最后要放置的球是R型

## C ++

``````// C++ program to count number of ways to arrange three
// types of balls such that no two balls of same color
// are adjacent to each other
#include<bits/stdc++.h>
using namespace std;

// Returns count of arrangements where last placed ball is
// 'last'.  'last' is 0 for 'p', 1 for 'q' and 2 for 'r'
int countWays( int p, int q, int r, int last)
{
// if number of balls of any color becomes less
// than 0 the number of ways arrangements is 0.
if (p<0 || q<0 || r<0)
return 0;

// If last ball required is of type P and the number
// of balls of P type is 1 while number of balls of
// other color is 0 the number of ways is 1.
if (p==1 && q==0 && r==0 && last==0)
return 1;

// Same case as above for 'q' and 'r'
if (p==0 && q==1 && r==0 && last==1)
return 1;
if (p==0 && q==0 && r==1 && last==2)
return 1;

// if last ball required is P and the number of ways is
// the sum of number of ways to form sequence with 'p-1' P
// balls, q Q Balls and r R balls ending with Q and R.
if (last==0)
return countWays(p-1, q, r, 1) + countWays(p-1, q, r, 2);

// Same as above case for 'q' and 'r'
if (last==1)
return countWays(p, q-1, r, 0) + countWays(p, q-1, r, 2);
if (last==2)
return countWays(p, q, r-1, 0) + countWays(p, q, r-1, 1);
}

// Returns count of required arrangements
int countUtil( int p, int q, int r)
{
// Three cases arise:
return countWays(p, q, r, 0) +  // Last required balls is type P
countWays(p, q, r, 1) +  // Last required balls is type Q
countWays(p, q, r, 2); // Last required balls is type R
}

// Driver code to test above
int main()
{
int p = 1, q = 1, r = 1;
printf ( "%d" , countUtil(p, q, r));
return 0;
}``````

## Java

``````// Java program to count number
// of ways to arrange three types of
// balls such that no two balls of
// same color are adjacent to each other
class GFG {

// Returns count of arrangements
// where last placed ball is
// 'last'. 'last' is 0 for 'p', // 1 for 'q' and 2 for 'r'
static int countWays( int p, int q, int r, int last)
{
// if number of balls of any
// color becomes less than 0
// the number of ways arrangements is 0.
if (p < 0 || q < 0 || r < 0 )
return 0 ;

// If last ball required is
// of type P and the number
// of balls of P type is 1
// while number of balls of
// other color is 0 the number
// of ways is 1.
if (p == 1 && q == 0 && r == 0 && last == 0 )
return 1 ;

// Same case as above for 'q' and 'r'
if (p == 0 && q == 1 && r == 0 && last == 1 )
return 1 ;
if (p == 0 && q == 0 && r == 1 && last == 2 )
return 1 ;

// if last ball required is P
// and the number of ways is
// the sum of number of ways
// to form sequence with 'p-1' P
// balls, q Q Balls and r R balls
// ending with Q and R.
if (last == 0 )
return countWays(p - 1 , q, r, 1 ) +
countWays(p - 1 , q, r, 2 );

// Same as above case for 'q' and 'r'
if (last == 1 )
return countWays(p, q - 1 , r, 0 ) +
countWays(p, q - 1 , r, 2 );

if (last == 2 )
return countWays(p, q, r - 1 , 0 ) +
countWays(p, q, r - 1 , 1 );

return 0 ;
}

// Returns count of required arrangements
static int countUtil( int p, int q, int r) {
// Three cases arise:
return countWays(p, q, r, 0 ) + // Last required balls is type P
countWays(p, q, r, 1 ) + // Last required balls is type Q
countWays(p, q, r, 2 );  // Last required balls is type R
}

// Driver code
public static void main(String[] args)
{
int p = 1 , q = 1 , r = 1 ;
System.out.print(countUtil(p, q, r));
}
}

// This code is contributed by Anant Agarwal.``````

## Python3

``````# Python3 program to count
# number of ways to arrange
# three types of balls such
# that no two balls of same
# color are adjacent to each
# other

# Returns count of arrangements
# where last placed ball is
# 'last'. 'last' is 0 for 'p', # 1 for 'q' and 2 for 'r'
def countWays(p, q, r, last):

# if number of balls of
# any color becomes less
# than 0 the number of
# ways arrangements is 0.
if (p < 0 or q < 0 or r < 0 ):
return 0 ;

# If last ball required is
# of type P and the number
# of balls of P type is 1
# while number of balls of
# other color is 0 the number
# of ways is 1.
if (p = = 1 and q = = 0 and
r = = 0 and last = = 0 ):
return 1 ;

# Same case as above
# for 'q' and 'r'
if (p = = 0 and q = = 1 and
r = = 0 and last = = 1 ):
return 1 ;

if (p = = 0 and q = = 0 and
r = = 1 and last = = 2 ):
return 1 ;

# if last ball required is P
# and the number of ways is
# the sum of number of ways
# to form sequence with 'p-1' P
# balls, q Q Balls and r R
# balls ending with Q and R.
if (last = = 0 ):
return (countWays(p - 1 , q, r, 1 ) +
countWays(p - 1 , q, r, 2 ));

# Same as above case
# for 'q' and 'r'
if (last = = 1 ):
return (countWays(p, q - 1 , r, 0 ) +
countWays(p, q - 1 , r, 2 ));
if (last = = 2 ):
return (countWays(p, q, r - 1 , 0 ) +
countWays(p, q, r - 1 , 1 ));

# Returns count of
# required arrangements
def countUtil(p, q, r):

# Three cases arise:
# Last required balls is type P
# Last required balls is type Q
# Last required balls is type R
return (countWays(p, q, r, 0 ) +
countWays(p, q, r, 1 ) +
countWays(p, q, r, 2 ));

# Driver Code
p = 1 ;
q = 1 ;
r = 1 ;
print (countUtil(p, q, r));

# This code is contributed by mits``````

## C#

``````// C# program to count number
// of ways to arrange three types of
// balls such that no two balls of
// same color are adjacent to each other
using System;

class GFG {

// Returns count of arrangements
// where last placed ball is
// 'last'. 'last' is 0 for 'p', // 1 for 'q' and 2 for 'r'
static int countWays( int p, int q, int r, int last)
{

// if number of balls of any
// color becomes less than 0
// the number of ways
// arrangements is 0.
if (p < 0 || q < 0 || r < 0)
return 0;

// If last ball required is
// of type P and the number
// of balls of P type is 1
// while number of balls of
// other color is 0 the number
// of ways is 1.
if (p == 1 && q == 0 && r == 0
&& last == 0)
return 1;

// Same case as above for 'q' and 'r'
if (p == 0 && q == 1 && r == 0
&& last == 1)
return 1;
if (p == 0 && q == 0 && r == 1
&& last == 2)
return 1;

// if last ball required is P
// and the number of ways is
// the sum of number of ways
// to form sequence with 'p-1' P
// balls, q Q Balls and r R balls
// ending with Q and R.
if (last == 0)
return countWays(p - 1, q, r, 1) +
countWays(p - 1, q, r, 2);

// Same as above case for 'q' and 'r'
if (last == 1)
return countWays(p, q - 1, r, 0) +
countWays(p, q - 1, r, 2);

if (last == 2)
return countWays(p, q, r - 1, 0) +
countWays(p, q, r - 1, 1);

return 0;
}

// Returns count of required arrangements
static int countUtil( int p, int q, int r)
{

// Three cases arise:
// 1. Last required balls is type P
// 2. Last required balls is type Q
// 3. Last required balls is type R
return countWays(p, q, r, 0) +
countWays(p, q, r, 1) +
countWays(p, q, r, 2);
}

// Driver code
public static void Main()
{
int p = 1, q = 1, r = 1;

Console.Write(countUtil(p, q, r));
}
}

// This code is contributed by nitin mittal.``````

## 的PHP

``````<?php
// PHP program to count number
// of ways to arrange three
// types of balls such that
// no two balls of same color
// are adjacent to each other

// Returns count of arrangements
// where last placed ball is
// 'last'. 'last' is 0 for 'p', // 1 for 'q' and 2 for 'r'
function countWays( \$p , \$q , \$r , \$last )
{

// if number of balls of
// any color becomes less
// than 0 the number of
// ways arrangements is 0.
if ( \$p < 0 || \$q
< 0 || \$r < 0)
return 0;

// If last ball required is
// of type P and the number
// of balls of P type is 1
// while number of balls of
// other color is 0 the number
// of ways is 1.
if ( \$p == 1 && \$q == 0 &&
\$r == 0 && \$last == 0)
return 1;

// Same case as above
// for 'q' and 'r'
if ( \$p == 0 && \$q == 1 &&
\$r == 0 && \$last == 1)
return 1;

if ( \$p == 0 && \$q == 0 &&
\$r == 1 && \$last == 2)
return 1;

// if last ball required is P
// and the number of ways is
// the sum of number of ways
// to form sequence with 'p-1' P
// balls, q Q Balls and r R
// balls ending with Q and R.
if ( \$last == 0)
return countWays( \$p - 1, \$q , \$r , 1) +
countWays( \$p - 1, \$q , \$r , 2);

// Same as above case
// for 'q' and 'r'
if ( \$last == 1)
return countWays( \$p , \$q - 1, \$r , 0) +
countWays( \$p , \$q - 1, \$r , 2);
if ( \$last == 2)
return countWays( \$p , \$q , \$r - 1, 0) +
countWays( \$p , \$q , \$r - 1, 1);
}

// Returns count of
// required arrangements
function countUtil( \$p , \$q , \$r )
{

// Three cases arise:
// Last required balls is type P
// Last required balls is type Q
// Last required balls is type R
return countWays( \$p , \$q , \$r , 0) +
countWays( \$p , \$q , \$r , 1) +
countWays( \$p , \$q , \$r , 2);
}

// Driver Code
\$p = 1;
\$q = 1;
\$r = 1;
echo (countUtil( \$p , \$q , \$r ));

// This code is contributed by nitin mittal.
?>``````

``6``

## C ++

``````// C++ program to count number of ways to arrange three
// types of balls such that no two balls of same color
// are adjacent to each other
#include<bits/stdc++.h>
using namespace std;
#define MAX 100

// table to store to store results of subproblems
int dp[MAX][MAX][MAX][3];

// Returns count of arrangements where last placed ball is
// 'last'.  'last' is 0 for 'p', 1 for 'q' and 2 for 'r'
int countWays( int p, int q, int r, int last)
{
// if number of balls of any color becomes less
// than 0 the number of ways arrangements is 0.
if (p<0 || q<0 || r<0)
return 0;

// If last ball required is of type P and the number
// of balls of P type is 1 while number of balls of
// other color is 0 the number of ways is 1.
if (p==1 && q==0 && r==0 && last==0)
return 1;

// Same case as above for 'q' and 'r'
if (p==0 && q==1 && r==0 && last==1)
return 1;
if (p==0 && q==0 && r==1 && last==2)
return 1;

// If this subproblem is already evaluated
if (dp[q][r][last] != -1)
return dp[q][r][last];

// if last ball required is P and the number of ways is
// the sum of number of ways to form sequence with 'p-1' P
// balls, q Q Balls and r R balls ending with Q and R.
if (last==0)
dp[q][r][last] = countWays(p-1, q, r, 1) + countWays(p-1, q, r, 2);

// Same as above case for 'q' and 'r'
else if (last==1)
dp[q][r][last] = countWays(p, q-1, r, 0) + countWays(p, q-1, r, 2);
else //(last==2)
dp[q][r][last] =  countWays(p, q, r-1, 0) + countWays(p, q, r-1, 1);

return dp``````[q][r][last];
}

// Returns count of required arrangements
int countUtil( int p, int q, int r)
{
// Initialize 'dp' array
memset (dp, -1, sizeof (dp));

// Three cases arise:
return countWays(p, q, r, 0) +  // Last required balls is type P
countWays(p, q, r, 1) +  // Last required balls is type Q
countWays(p, q, r, 2); // Last required balls is type R
}

// Driver code to test above
int main()
{
int p = 1, q = 1, r = 1;
printf ( "%d" , countUtil(p, q, r));
return 0;
}``````

## Java

``````// Java program to count number
// of ways to arrange three
// types of balls such that no
// two balls of same color
// are adjacent to each other
import java.util.Arrays;

class GFG
{

static final int MAX = 100 ;

// table to store to store results of subproblems
static int dp[][][][] = new int [MAX][MAX][MAX][ 3 ];

// Returns count of arrangements
// where last placed ball is
// 'last'. 'last' is 0 for 'p', // 1 for 'q' and 2 for 'r'
static int countWays( int p, int q, int r, int last)
{
// if number of balls of any
// color becomes less than 0
// the number of ways arrangements is 0.
if (p < 0 || q < 0 || r < 0 )
return 0 ;

// If last ball required is
// of type P and the number
// of balls of P type is 1
// while number of balls of
// other color is 0 the number
// of ways is 1.
if (p == 1 && q == 0 && r == 0 && last == 0 )
return 1 ;

// Same case as above for 'q' and 'r'
if (p == 0 && q == 1 && r == 0 && last == 1 )
return 1 ;

if (p == 0 && q == 0 && r == 1 && last == 2 )
return 1 ;

// If this subproblem is already evaluated
if (dp[q][r][last] != - 1 )
return dp[q][r][last];

// if last ball required is P and
// the number of ways is the sum
// of number of ways to form sequence
// with 'p-1' P balls, q Q balss and
// r R balls ending with Q and R.
if (last == 0 )
dp[q][r][last] = countWays(p - 1 , q, r, 1 ) +
countWays(p - 1 , q, r, 2 );

// Same as above case for 'q' and 'r'
else if (last == 1 )
dp[q][r][last] = countWays(p, q - 1 , r, 0 ) +
countWays(p, q - 1 , r, 2 );
//(last==2)
else
dp[q][r][last] = countWays(p, q, r - 1 , 0 ) +
countWays(p, q, r - 1 , 1 );

return dp``````[q][r][last];
}

// Returns count of required arrangements
static int countUtil( int p, int q, int r)
{
// Initialize 'dp' array
for ( int [][][] row : dp)
{
for ( int [][] innerRow : row)
{
for ( int [] innerInnerRow : innerRow)
{
Arrays.fill(innerInnerRow, - 1 );
}
}
};

// Three cases arise:
return countWays(p, q, r, 0 ) + // Last required balls is type P
countWays(p, q, r, 1 ) +    // Last required balls is type Q
countWays(p, q, r, 2 );       // Last required balls is type R
}

// Driver code
public static void main(String[] args)
{
int p = 1 , q = 1 , r = 1 ;
System.out.print(countUtil(p, q, r));
}
}

// This code is contributed by Anant Agarwal.``````

## C#

``````// C# program to count number
// of ways to arrange three
// types of balls such that no
// two balls of same color
// are adjacent to each other
using System;

class GFG
{

static int MAX = 101;

// table to store to store results of subproblems
static int [, , , ] dp = new int [MAX, MAX, MAX, 4];

// Returns count of arrangements
// where last placed ball is
// 'last'. 'last' is 0 for 'p', // 1 for 'q' and 2 for 'r'
static int countWays( int p, int q, int r, int last)
{
// if number of balls of any
// color becomes less than 0
// the number of ways arrangements is 0.
if (p < 0 || q < 0 || r < 0)
return 0;

// If last ball required is
// of type P and the number
// of balls of P type is 1
// while number of balls of
// other color is 0 the number
// of ways is 1.
if (p == 1 && q == 0 && r == 0 && last == 0)
return 1;

// Same case as above for 'q' and 'r'
if (p == 0 && q == 1 && r == 0 && last == 1)
return 1;

if (p == 0 && q == 0 && r == 1 && last == 2)
return 1;

// If this subproblem is already evaluated
if (dp != -1)
return dp;

// if last ball required is P and
// the number of ways is the sum
// of number of ways to form sequence
// with 'p-1' P balls, q Q balss and
// r R balls ending with Q and R.
if (last == 0)
dp = countWays(p - 1, q, r, 1) +
countWays(p - 1, q, r, 2);

// Same as above case for 'q' and 'r'
else if (last == 1)
dp = countWays(p, q - 1, r, 0) +
countWays(p, q - 1, r, 2);
//(last==2)
else
dp = countWays(p, q, r - 1, 0) +
countWays(p, q, r - 1, 1);

return dp``````;
}

// Returns count of required arrangements
static int countUtil( int p, int q, int r)
{
// Initialize 'dp' array
for ( int i = 0; i < MAX; i++)
for ( int j = 0; j < MAX; j++)
for ( int k = 0; k < MAX; k++)
for ( int l = 0; l < 4; l++)
dp[i, j, k, l] = -1;

// Three cases arise:
return countWays(p, q, r, 0) + // Last required balls is type P
countWays(p, q, r, 1) + // Last required balls is type Q
countWays(p, q, r, 2); // Last required balls is type R
}

// Driver code
static void Main()
{
int p = 1, q = 1, r = 1;
Console.WriteLine(countUtil(p, q, r));
}
}

// This code is contributed by mits.``````

## Python3

``````# Python3 program to count number of ways to
# arrange three types of balls such that no
# two balls of same color are adjacent to each other
MAX = 100 ;

# table to store to store results of subproblems
dp = [[[[ - 1 ] * 4 for i in range ( MAX )]
for j in range ( MAX )]
for k in range ( MAX )];

# Returns count of arrangements where last
# placed ball is 'last'. 'last' is 0 for 'p', # 1 for 'q' and 2 for 'r'
def countWays(p, q, r, last):

# if number of balls of any color becomes less
# than 0 the number of ways arrangements is 0.
if (p < 0 or q < 0 or r < 0 ):
return 0 ;

# If last ball required is of type P and the
# number of balls of P type is 1 while number
# of balls of other color is 0 the number of
# ways is 1.
if (p = = 1 and q = = 0 and
r = = 0 and last = = 0 ):
return 1 ;

# Same case as above for 'q' and 'r'
if (p = = 0 and q = = 1 and
r = = 0 and last = = 1 ):
return 1 ;
if (p = = 0 and q = = 0 and
r = = 1 and last = = 2 ):
return 1 ;

# If this subproblem is already evaluated
if (dp[q][r][last] ! = - 1 ):
return dp

(adsbygoogle = window.adsbygoogle || []).push({});

[q][r][last];

# if last ball required is P and the number
# of ways is the sum of number of ways to
# form sequence with 'p-1' P balls, q Q Balls
# and r R balls ending with Q and R.
if (last = = 0 ):
dp[q][r][last] = (countWays(p - 1 , q, r, 1 ) +
countWays(p - 1 , q, r, 2 ));

# Same as above case for 'q' and 'r'
elif (last = = 1 ):
dp[q][r][last] = (countWays(p, q - 1 , r, 0 ) +
countWays(p, q - 1 , r, 2 ));
else :

#(last==2)
dp[q][r][last] = (countWays(p, q, r - 1 , 0 ) +
countWays(p, q, r - 1 , 1 ));

return dp``````[q][r][last];

# Returns count of required arrangements
def countUtil(p, q, r):

# Three cases arise:
# Last required balls is type P
# Last required balls is type Q
# Last required balls is type R
return (countWays(p, q, r, 0 ) +
countWays(p, q, r, 1 ) +
countWays(p, q, r, 2 ));

# Driver Code
p, q, r = 1 , 1 , 1 ;
print (countUtil(p, q, r));

# This code is contributed by mits``````

## 的PHP

``````<?php
// PHP program to count number of ways to
// arrange three types of balls such that
// no two balls of same color are adjacent
// to each other
\$MAX = 100;

// table to store to store results of subproblems
\$dp = array_fill (0, \$MAX , array_fill (0, \$MAX , array_fill (0, \$MAX , array_fill (0, 3, -1))));

// Returns count of arrangements where last
// placed ball is 'last'. 'last' is 0 for 'p', // 1 for 'q' and 2 for 'r'
function countWays( \$p , \$q , \$r , \$last )
{
global \$dp ;

// if number of balls of any color becomes less
// than 0 the number of ways arrangements is 0.
if ( \$p < 0 || \$q < 0 || \$r < 0)
return 0;

// If last ball required is of type P and the
// number of balls of P type is 1 while number
// of balls of other color is 0 the number of
// ways is 1.
if ( \$p == 1 && \$q == 0 && \$r == 0 && \$last == 0)
return 1;

// Same case as above for 'q' and 'r'
if ( \$p == 0 && \$q == 1 && \$r == 0 && \$last == 1)
return 1;
if ( \$p == 0 && \$q == 0 && \$r == 1 && \$last == 2)
return 1;

// If this subproblem is already evaluated
if ( \$dp [ \$p ][ \$q ][ \$r ][ \$last ] != -1)
return \$dp [ \$p ][ \$q ][ \$r ][ \$last ];

// if last ball required is P and the number of
// ways is the sum of number of ways to form
// sequence with 'p-1' P balls, q Q Balls and r
// R balls ending with Q and R.
if ( \$last == 0)
\$dp [ \$p ][ \$q ][ \$r ][ \$last ] = countWays( \$p - 1, \$q , \$r , 1) +
countWays( \$p - 1, \$q , \$r , 2);

// Same as above case for 'q' and 'r'
else if ( \$last == 1)
\$dp [ \$p ][ \$q ][ \$r ][ \$last ] = countWays( \$p , \$q - 1, \$r , 0) +
countWays( \$p , \$q - 1, \$r , 2);
else //(last==2)
\$dp [ \$p ][ \$q ][ \$r ][ \$last ] = countWays( \$p , \$q , \$r - 1, 0) +
countWays( \$p , \$q , \$r - 1, 1);

return \$dp [ \$p ][ \$q ][ \$r ][ \$last ];
}

// Returns count of required arrangements
function countUtil( \$p , \$q , \$r )
{

// Three cases arise:
return countWays( \$p , \$q , \$r , 0) + // Last required balls is type P
countWays( \$p , \$q , \$r , 1) + // Last required balls is type Q
countWays( \$p , \$q , \$r , 2); // Last required balls is type R
}

// Driver code
\$p = 1;
\$q = 1;
\$r = 1;
print (countUtil( \$p , \$q , \$r ));

// This code is contributed by mits
?>``````

``6``