Сумма ИЛИ самых маленьких и самых больших элементов каждого подмножества набора - PullRequest
Новая
       26

Сумма ИЛИ самых маленьких и самых больших элементов каждого подмножества набора

0 голосов
/ 14 мая 2018

По заданному набору S для каждого непустого подмножества найдите самые маленькие и самые большие элементы и возьмите их логическое ИЛИ.Найти сумму этих OR для всех таких подмножеств.

Например: S = {1, 2, 3}, затем подмножества

{1} наименьшее = 1 наибольший = 1 ИЛИ = 1

{2} наименьший = 2 наибольший = 2 ИЛИ = 2

{3} наименьший = 3 наибольший = 3 ИЛИ = 3

{1, 2} наименьший = 1 наибольший= 2 ИЛИ = 3

{2, 3} наименьший = 2 наибольших = 3 ИЛИ = 3

{1, 3} наименьший = 1 наибольший = 3 ИЛИ = 3

{1, 2, 3} наименьший = 1 наибольший = 3 ИЛИ = 3

Ответ - 18.

Я прочитал Как найти сумму различий максимума и минимумавсе возможные подмножества массива , но не могут использовать эту логику здесь.

1 Ответ

0 голосов
/ 14 мая 2018

Алгоритм

  • Сортировка входных данных
  • Цикл от i = 0 to n, где n - длина входа, и j = i to n, поскольку вход отсортирован, input[i] будет наименьшим, а input[j] будет самым большим в диапазоне [i,j]
  • Теперь, когда мы знаем, что input[i] является самым низким, а input[j] является самым большим, мы также знаем, что есть j - i -1 средние элементы массива, комбинации которых приведут к таким же самым низким и самым большим значениям, следовательно, мы умножаем OR низкого и высокого с общим числом возможных перестановок с этими средними числами.
  • Например Для input = [1, 2, 3, 4] и i = 0 и j = 3, т. Е.) lowest = 1 и largest = 4 мы знаем, что элементы [2, 3] могут появляться в подмножествах без изменения самого низкого и самого большого значения. [1, 2, 4], [1, 3, 4], [1, 2, 3, 4] все действительны. Количество возможных комбинаций со средними элементами: 2 ^ (count of middle elements).
  • Повторите это для всей младшей и самой большой пары.

Вот код на C ++. 

#include <iostream>

int main() {
    vector<int> input {3, 2, 1};
    sort(input.begin(), input.end());
    int answer = 0;
    for(int i=0; i < input.size(); ++i)
    {
        for(int j=i; j < input.size(); ++j)
        {
            int elements = (j - i) - 1;
            int multiple = elements > 0 ? pow(2, elements) : 1;
            answer += ((input[i] | input[j]) * multiple);
            cout << input[i] << ' ' << input[j] << ' ' << answer << endl;
        }
        cout << endl;
    }
    cout <<  answer <<endl;
}
...