本文概述

• C ++
• Java
• Python3
• C#
• 的PHP
• C ++
• Java
• C#
• Python3
• 的PHP

有P型的" p"球, Q型的" q"球和R型的" r"球。使用这些球, 我们要创建一条直线, 以使没有两个相同类型的球相邻。
例子 ：

Input: p = 1, q = 1, r = 0 Output : 2 There are only two arrangements PQ and QPInput: p = 1, q = 1, r = 1 Output : 6 There are only six arrangements PQR, QPR, QRP, RQP, PRQ and RPQInput: 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

该解决方案的时间复杂度是指数级的。
我们可以观察到有很多子问题一次又一次被解决, 因此可以使用动态编程(DP)解决该问题。我们可以轻松地为该问题提供记忆解决方案。
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
[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

时间复杂度：O(p * q * r)
辅助空间：O(p * q * r * 3)
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

推荐阅读

• 

  构成职务侵占罪会如何追究责任?
• 

  红梅树修剪时间和方法 刚买的红梅盆栽养殖方法
• 

  佳能单反p档操作 佳能p档怎么使用
• 

  给我查一下一月份哪天日子好 查一下日子
• 

  孤独就像烧开的水壶 孤独水壶是什么意思
• 

  美的随风行 美的随风行移动空调不制冷
• 

  出远门核酸检测提前几天做
• 

  单反相机与数码相机的区别有哪些？ 数码相机和单反相机的区别
• 

  济宁什么情况能带押过户？
• 

  《暗黑破坏神3：夺魂之镰》 圣教军FARM练级实用心得
• 

  新冠疫苗|普通人还有多久能接种新冠疫苗？最新回应来了
• 

  春笋怎么保存一周 春笋保存方法家庭
• 

  专家解读 ：个人医保账户里的钱为何少了？
• 

  上古卷轴5天际怎么玩_玩法大全分享
• 

  慢跑可以练出腹肌吗
• 

  idea是用来干什么的，idea后面加是什么意思
• 

  土豆粉一包多少钱 纯土豆粉条多少钱一斤
• 

  韭菜与鸡肉相克吗
• 

  投稿|营收增长难掩资本市场落寞：腾讯音乐“押宝”元宇宙？
• 

  小耳朵奶茶获得教程 小耳朵奶茶活动什么时候结束

• 为偏斜树着色的方法，以使父级和子级具有不同的颜色
• 使用允许重复的数组元素求和到N的方法
• 分割字符串的方法，以便每个分区以不同的字符开头
• C++标准模板库(STL)中的列表用法详细介绍
• 从二进制字符串中删除一个元素，使XOR变为0的方法
• 萝卜家园系统win732位介绍
• win7纯净版硬盘图解
• 光盘win7 64位图解
• win7原版系统iso介绍