Policz permutacje, które dają wynik dodatni
Biorąc pod uwagę tablicę cyfr o długości n > 1, cyfry mieszczą się w przedziale od 0 do 9. Wykonujemy sekwencję poniższych trzech operacji, aż skończymy ze wszystkimi cyframi
- Wybierz dwie początkowe cyfry i dodaj ( + )
- Następnie od wyniku powyższego kroku odejmuje się kolejną cyfrę (-).
- Wynik powyższego kroku jest mnożony (X) przez następną cyfrę.
Powyższą sekwencję operacji wykonujemy liniowo z pozostałymi cyframi.
Zadanie polega na wyznaczeniu, ile permutacji danej tablicy daje wynik dodatni po wykonaniu powyższych operacji.
Na przykład rozważ numer wejściowy [] = {1 2 3 4 5}. Rozważmy permutację 21345, aby zademonstrować sekwencję operacji.
- Dodaj pierwsze dwie cyfry wyniku = 2+1 = 3
- Odejmij następną cyfrę wynik=wynik-3= 3-3 = 0
- Pomnóż następną cyfrę wynik=wynik*4= 0*4 = 0
- Dodaj wynik kolejnej cyfry = wynik+5 = 0+5 = 5
- wynik = 5, który jest dodatni, więc zwiększ liczbę o jeden
Przykłady:
Input : number[]='123' Output: 4 // here we have all permutations // 123 --> 1+2 -> 3-3 -> 0 // 132 --> 1+3 -> 4-2 -> 2 ( positive ) // 213 --> 2+1 -> 3-3 -> 0 // 231 --> 2+3 -> 5-1 -> 4 ( positive ) // 312 --> 3+1 -> 4-2 -> 2 ( positive ) // 321 --> 3+2 -> 5-1 -> 4 ( positive ) // total 4 permutations are giving positive result Input : number[]='112' Output: 2 // here we have all permutations possible // 112 --> 1+1 -> 2-2 -> 0 // 121 --> 1+2 -> 3-1 -> 2 ( positive ) // 211 --> 2+1 -> 3-1 -> 2 ( positive )
Zapytany w: Morgana Stanleya
Najpierw generujemy wszystkie możliwe permutacje danej tablicy cyfr i wykonujemy sekwencyjnie zadaną sekwencję operacji na każdej permutacji i sprawdzamy, dla której permutacji wynik jest dodatni. Poniższy kod w łatwy sposób opisuje rozwiązanie problemu.
Notatka : Możemy wygenerować wszystkie możliwe permutacje za pomocą metody iteracyjnej, patrz Ten artykuł lub możemy użyć funkcji STL następna_permutacja() funkcję jego generowania.
// C++ program to find count of permutations that produce // positive result. #include using namespace std ; // function to find all permutation after executing given // sequence of operations and whose result value is positive // result > 0 ) number[] is array of digits of length of n int countPositivePermutations ( int number [] int n ) { // First sort the array so that we get all permutations // one by one using next_permutation. sort ( number number + n ); // Initialize result (count of permutations with positive // result) int count = 0 ; // Iterate for all permutation possible and do operation // sequentially in each permutation do { // Stores result for current permutation. First we // have to select first two digits and add them int curr_result = number [ 0 ] + number [ 1 ]; // flag that tells what operation we are going to // perform // operation = 0 ---> addition operation ( + ) // operation = 1 ---> subtraction operation ( - ) // operation = 0 ---> multiplication operation ( X ) // first sort the array of digits to generate all // permutation in sorted manner int operation = 1 ; // traverse all digits for ( int i = 2 ; i < n ; i ++ ) { // sequentially perform + - X operation switch ( operation ) { case 0 : curr_result += number [ i ]; break ; case 1 : curr_result -= number [ i ]; break ; case 2 : curr_result *= number [ i ]; break ; } // next operation (decides case of switch) operation = ( operation + 1 ) % 3 ; } // result is positive then increment count by one if ( curr_result > 0 ) count ++ ; // generate next greater permutation until it is // possible } while ( next_permutation ( number number + n )); return count ; } // Driver program to test the case int main () { int number [] = { 1 2 3 }; int n = sizeof ( number ) / sizeof ( number [ 0 ]); cout < < countPositivePermutations ( number n ); return 0 ; }
Java // Java program to find count of permutations // that produce positive result. import java.util.* ; class GFG { // function to find all permutation after // executing given sequence of operations // and whose result value is positive result > 0 ) // number[] is array of digits of length of n static int countPositivePermutations ( int number [] int n ) { // First sort the array so that we get // all permutations one by one using // next_permutation. Arrays . sort ( number ); // Initialize result (count of permutations // with positive result) int count = 0 ; // Iterate for all permutation possible and // do operation sequentially in each permutation do { // Stores result for current permutation. // First we have to select first two digits // and add them int curr_result = number [ 0 ] + number [ 1 ] ; // flag that tells what operation we are going to // perform // operation = 0 ---> addition operation ( + ) // operation = 1 ---> subtraction operation ( - ) // operation = 0 ---> multiplication operation ( X ) // first sort the array of digits to generate all // permutation in sorted manner int operation = 1 ; // traverse all digits for ( int i = 2 ; i < n ; i ++ ) { // sequentially perform + - X operation switch ( operation ) { case 0 : curr_result += number [ i ] ; break ; case 1 : curr_result -= number [ i ] ; break ; case 2 : curr_result *= number [ i ] ; break ; } // next operation (decides case of switch) operation = ( operation + 1 ) % 3 ; } // result is positive then increment count by one if ( curr_result > 0 ) count ++ ; // generate next greater permutation until // it is possible } while ( next_permutation ( number )); return count ; } static boolean next_permutation ( int [] p ) { for ( int a = p . length - 2 ; a >= 0 ; -- a ) if ( p [ a ] < p [ a + 1 ] ) for ( int b = p . length - 1 ;; -- b ) if ( p [ b ] > p [ a ] ) { int t = p [ a ] ; p [ a ] = p [ b ] ; p [ b ] = t ; for ( ++ a b = p . length - 1 ; a < b ; ++ a -- b ) { t = p [ a ] ; p [ a ] = p [ b ] ; p [ b ] = t ; } return true ; } return false ; } // Driver Code public static void main ( String [] args ) { int number [] = { 1 2 3 }; int n = number . length ; System . out . println ( countPositivePermutations ( number n )); } } // This code is contributed by PrinciRaj1992
Python3 # Python3 program to find count of permutations # that produce positive result. # function to find all permutation after # executing given sequence of operations # and whose result value is positive result > 0 ) # number[] is array of digits of length of n def countPositivePermutations ( number n ): # First sort the array so that we get # all permutations one by one using # next_permutation. number . sort () # Initialize result (count of permutations # with positive result) count = 0 ; # Iterate for all permutation possible and # do operation sequentially in each permutation while True : # Stores result for current permutation. # First we have to select first two digits # and add them curr_result = number [ 0 ] + number [ 1 ]; # flag that tells what operation we are going to # perform # operation = 0 ---> addition operation ( + ) # operation = 1 ---> subtraction operation ( - ) # operation = 0 ---> multiplication operation ( X ) # first sort the array of digits to generate all # permutation in sorted manner operation = 1 ; # traverse all digits for i in range ( 2 n ): # sequentially perform + - X operation if operation == 0 : curr_result += number [ i ]; else if operation == 1 : curr_result -= number [ i ]; else if operation == 2 : curr_result *= number [ i ]; # next operation (decides case of switch) operation = ( operation + 1 ) % 3 ; # result is positive then increment count by one if ( curr_result > 0 ): count += 1 # generate next greater permutation until # it is possible if ( not next_permutation ( number )): break return count ; def next_permutation ( p ): for a in range ( len ( p ) - 2 - 1 - 1 ): if ( p [ a ] < p [ a + 1 ]): for b in range ( len ( p ) - 1 - 1000000000 - 1 ): if ( p [ b ] > p [ a ]): t = p [ a ]; p [ a ] = p [ b ]; p [ b ] = t ; a += 1 b = len ( p ) - 1 while ( a < b ): t = p [ a ]; p [ a ] = p [ b ]; p [ b ] = t ; a += 1 b -= 1 return True ; return False ; # Driver Code if __name__ == '__main__' : number = [ 1 2 3 ] n = len ( number ) print ( countPositivePermutations ( number n )); # This code is contributed by rutvik_56.
C# // C# program to find count of permutations // that produce positive result. using System ; class GFG { // function to find all permutation after // executing given sequence of operations // and whose result value is positive result > 0 ) // number[] is array of digits of length of n static int countPositivePermutations ( int [] number int n ) { // First sort the array so that we get // all permutations one by one using // next_permutation. Array . Sort ( number ); // Initialize result (count of permutations // with positive result) int count = 0 ; // Iterate for all permutation possible and // do operation sequentially in each permutation do { // Stores result for current permutation. // First we have to select first two digits // and add them int curr_result = number [ 0 ] + number [ 1 ]; // flag that tells what operation we are going to // perform // operation = 0 ---> addition operation ( + ) // operation = 1 ---> subtraction operation ( - ) // operation = 0 ---> multiplication operation ( X ) // first sort the array of digits to generate all // permutation in sorted manner int operation = 1 ; // traverse all digits for ( int i = 2 ; i < n ; i ++ ) { // sequentially perform + - X operation switch ( operation ) { case 0 : curr_result += number [ i ]; break ; case 1 : curr_result -= number [ i ]; break ; case 2 : curr_result *= number [ i ]; break ; } // next operation (decides case of switch) operation = ( operation + 1 ) % 3 ; } // result is positive then increment count by one if ( curr_result > 0 ) count ++ ; // generate next greater permutation until // it is possible } while ( next_permutation ( number )); return count ; } static bool next_permutation ( int [] p ) { for ( int a = p . Length - 2 ; a >= 0 ; -- a ) if ( p [ a ] < p [ a + 1 ]) for ( int b = p . Length - 1 ;; -- b ) if ( p [ b ] > p [ a ]) { int t = p [ a ]; p [ a ] = p [ b ]; p [ b ] = t ; for ( ++ a b = p . Length - 1 ; a < b ; ++ a -- b ) { t = p [ a ]; p [ a ] = p [ b ]; p [ b ] = t ; } return true ; } return false ; } // Driver Code static public void Main () { int [] number = { 1 2 3 }; int n = number . Length ; Console . Write ( countPositivePermutations ( number n )); } } // This code is contributed by ajit..
JavaScript < script > // Javascript program to find count of permutations // that produce positive result. // function to find all permutation after // executing given sequence of operations // and whose result value is positive result > 0 ) // number[] is array of digits of length of n function countPositivePermutations ( number n ) { // First sort the array so that we get // all permutations one by one using // next_permutation. number . sort ( function ( a b ){ return a - b }); // Initialize result (count of permutations // with positive result) let count = 0 ; // Iterate for all permutation possible and // do operation sequentially in each permutation do { // Stores result for current permutation. // First we have to select first two digits // and add them let curr_result = number [ 0 ] + number [ 1 ]; // flag that tells what operation we are going to // perform // operation = 0 ---> addition operation ( + ) // operation = 1 ---> subtraction operation ( - ) // operation = 0 ---> multiplication operation ( X ) // first sort the array of digits to generate all // permutation in sorted manner let operation = 1 ; // traverse all digits for ( let i = 2 ; i < n ; i ++ ) { // sequentially perform + - X operation switch ( operation ) { case 0 : curr_result += number [ i ]; break ; case 1 : curr_result -= number [ i ]; break ; case 2 : curr_result *= number [ i ]; break ; } // next operation (decides case of switch) operation = ( operation + 1 ) % 3 ; } // result is positive then increment count by one if ( curr_result > 0 ) count ++ ; // generate next greater permutation until // it is possible } while ( next_permutation ( number )); return count ; } function next_permutation ( p ) { for ( let a = p . length - 2 ; a >= 0 ; -- a ) if ( p [ a ] < p [ a + 1 ]) for ( let b = p . length - 1 ;; -- b ) if ( p [ b ] > p [ a ]) { let t = p [ a ]; p [ a ] = p [ b ]; p [ b ] = t ; for ( ++ a b = p . length - 1 ; a < b ; ++ a -- b ) { t = p [ a ]; p [ a ] = p [ b ]; p [ b ] = t ; } return true ; } return false ; } let number = [ 1 2 3 ]; let n = number . length ; document . write ( countPositivePermutations ( number n )); < /script>
Wyjście:
4
Złożoność czasowa: O(n*n!)
Przestrzeń pomocnicza: O(1)
Jeśli masz lepsze i zoptymalizowane rozwiązanie tego problemu, udostępnij je w komentarzach.
