Рубрики

Подсчет перестановок, которые дают положительный результат

Учитывая массив цифр длиной n> 1, цифры лежат в диапазоне от 0 до 9. Мы выполняем последовательность из трех операций ниже, пока мы не закончим со всеми цифрами

  1. Выберите начальные две цифры и добавьте (+)
  2. Затем следующая цифра вычитается (-) из результата предыдущего шага.
  3. Результат вышеуказанного шага умножается (X) на следующую цифру.

Вышеуказанную последовательность операций выполняем линейно с оставшимися цифрами.

Задача состоит в том, чтобы найти, сколько перестановок заданного массива дает положительный результат после вышеуказанных операций.

Например, рассмотрим входной номер [] = {1, 2, 3, 4, 5}. Рассмотрим перестановку 21345 для демонстрации последовательности операций.

  1. Добавьте первые две цифры, результат = 2 + 1 = 3
  2. Вычтите следующую цифру, результат = результат-3 = 3-3 = 0
  3. Умножьте следующую цифру, результат = результат * 4 = 0 * 4 = 0
  4. Добавить следующую цифру, результат = результат + 5 = 0 + 5 = 5
  5. результат = 5, что является положительным, так что счетчик приращений на единицу

Примеры:

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 )

Спросил в: Морган Стэнли

Сначала мы генерируем все возможные перестановки заданного массива цифр и последовательно выполняем заданную последовательность операций для каждой перестановки и проверяем, какой результат перестановки является положительным. Ниже код описывает решение проблемы легко.

Примечание. Мы можем сгенерировать все возможные перестановки либо с помощью итеративного метода, см. Эту статью, либо мы можем использовать функцию STL next_permutation () для ее генерации.

C ++

// C ++ программа для поиска количества перестановок, которые производят
// положительный результат.
#include<bits/stdc++.h>

using namespace std;

  
// функция для поиска всех перестановок после выполнения заданного
// последовательность операций и результат которой положителен
// результат> 0) число [] - массив цифр длины n

int countPositivePermutations(int number[], int n)

{

    // Сначала сортируем массив так, чтобы мы получили все перестановки

    // один за другим, используя next_permutation.

    sort(number, number+n);

  

    // Инициализировать результат (количество перестановок с положительным

    // результат)

    int count = 0;

  

    // Итерация для всех возможных перестановок и выполнение операции

    // последовательно в каждой перестановке

    do

    {

        // Сохраняет результат для текущей перестановки. Сначала мы

        // нужно выбрать первые две цифры и добавить их

        int curr_result = number[0] + number[1];

  

        // флаг, который говорит, к какой операции мы собираемся

        // выполнить

        // операция = 0 ---> операция сложения (+)

        // операция = 1 ---> операция вычитания (-)

        // операция = 0 ---> операция умножения (X)

        // сначала сортируем массив цифр, чтобы сгенерировать все

        // перестановка в отсортированном виде

        int operation = 1;

  

        // пройти все цифры

        for (int i=2; i<n; i++)

        {

            // последовательно выполняем операции +, -, X

            switch (operation)

            {

            case 0:

                curr_result += number[i];

                break;

            case 1:

                curr_result -= number[i];

                break;

            case 2:

                curr_result *= number[i];

                break;

            }

  

            // следующая операция (решает случай переключения)

            operation = (operation + 1) % 3;

        }

  

        // результат положительный, затем увеличение на единицу

        if (curr_result > 0)

            count++;

  

    // генерируем следующую большую перестановку, пока она не будет

    // возможно

    } while(next_permutation(number, number+n));

  

    return count;

}

  
// Драйвер программы для проверки кейса

int main()

{

    int number[] = {1, 2, 3};

    int n = sizeof(number)/sizeof(number[0]);

    cout << countPositivePermutations(number, n);

    return 0;

}

Джава

// Java-программа для поиска количества перестановок
// которые дают положительный результат.

import java.util.*;

  

class GFG 

{

  
// функция для поиска всех перестановок после
// выполнение заданной последовательности операций
// и значение результата которого является положительным результатом> 0)
// число [] - массив цифр длины n

static int countPositivePermutations(int number[], 

                                     int n) 

    // Сначала сортируем массив так, чтобы мы получили

    // все перестановки один за другим используя

    // следующая_перестановка.

    Arrays.sort(number); 

  

    // Инициализировать результат (количество перестановок

    // с положительным результатом)

    int count = 0

  

    // Итерация для всех возможных перестановок и

    // делаем операцию последовательно в каждой перестановке

    do

    

        // Сохраняет результат для текущей перестановки.

        // Сначала мы должны выбрать первые две цифры

        // и добавить их

        int curr_result = number[0] + number[1]; 

  

        // флаг, который говорит, к какой операции мы собираемся

        // выполнить

        // операция = 0 ---> операция сложения (+)

        // операция = 1 ---> операция вычитания (-)

        // операция = 0 ---> операция умножения (X)

        // сначала сортируем массив цифр, чтобы сгенерировать все

        // перестановка в отсортированном виде

        int operation = 1

  

        // пройти все цифры

        for (int i = 2; i < n; i++) 

        

            // последовательно выполняем операции +, -, X

            switch (operation) 

            

            case 0

                curr_result += number[i]; 

                break

            case 1

                curr_result -= number[i]; 

                break

            case 2

                curr_result *= number[i]; 

                break

            

  

            // следующая операция (решает случай переключения)

            operation = (operation + 1) % 3

        

  

        // результат положительный, затем увеличение на единицу

        if (curr_result > 0

            count++; 

  

    // генерируем следующую большую перестановку до

    // возможно

    } 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;

}

  
// Код драйвера

public static void main(String[] args)

{

    int number[] = {1, 2, 3}; 

    int n = number.length; 

    System.out.println(countPositivePermutations(number, n)); 

}

  
// Этот код предоставлен PrinciRaj1992

C #

// C # программа для поиска количества перестановок
// которые дают положительный результат.

using System;

  

class GFG

{

      
// функция для поиска всех перестановок после
// выполнение заданной последовательности операций
// и значение результата которого является положительным результатом> 0)
// число [] - массив цифр длины n

static int countPositivePermutations(int []number, 

                                     int n) 

    // Сначала сортируем массив так, чтобы мы получили

    // все перестановки один за другим используя

    // следующая_перестановка.

    Array.Sort(number); 

  

    // Инициализировать результат (количество перестановок

    // с положительным результатом)

    int count = 0; 

  

    // Итерация для всех возможных перестановок и

    // делаем операцию последовательно в каждой перестановке

    do

    

        // Сохраняет результат для текущей перестановки.

        // Сначала мы должны выбрать первые две цифры

        // и добавить их

        int curr_result = number[0] + number[1]; 

  

        // флаг, который говорит, к какой операции мы собираемся

        // выполнить

        // операция = 0 ---> операция сложения (+)

        // операция = 1 ---> операция вычитания (-)

        // операция = 0 ---> операция умножения (X)

        // сначала сортируем массив цифр, чтобы сгенерировать все

        // перестановка в отсортированном виде

        int operation = 1; 

  

        // пройти все цифры

        for (int i = 2; i < n; i++) 

        

            // последовательно выполняем операции +, -, X

            switch (operation) 

            

                case 0: 

                    curr_result += number[i]; 

                    break

                case 1: 

                    curr_result -= number[i]; 

                    break

                case 2: 

                    curr_result *= number[i]; 

                    break

            

  

            // следующая операция (решает случай переключения)

            operation = (operation + 1) % 3; 

        

  

        // результат положительный, затем увеличение на единицу

        if (curr_result > 0) 

            count++; 

  

    // генерируем следующую большую перестановку до

    // возможно

    } 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;

}

  
// Код драйвера

static public void Main ()

{

    int []number = {1, 2, 3}; 

    int n = number.Length; 

    Console.Write(countPositivePermutations(number, n)); 

}

  
// Этот код предоставлен ajit ..

Выход:

4

Если у вас есть лучшее и оптимизированное решение этой проблемы, пожалуйста, поделитесь в комментариях.

Эта статья предоставлена Шашанком Мишрой (Гуллу) и рецензирована командой geeksforgeeks. Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Подсчет перестановок, которые дают положительный результат

0.00 (0%) 0 votes