Загадочная "сумма сумм" и задача о разбиении множества
Почти в каждом поколении школьников, а то и вполне себе взрослых людей, кто-нибудь обязательно открывает этот "волшебный факт":
Случайно открыл такое свойство чисел: допустим есть число 12345.
Сложим все цифры по нумерологическому принципу: 1+2+3+4+5=15, 1+5=6.
Теперь сложим те же цифры, разбив число по-другому, например, 12 + 35 = 47, 47 + 4 (четверку ещё не использовали) = 51, 5 + 1 = 6.
Можно как угодно разбивать, например, 15 (6) + 32 (5) + 4 = 15 и снова 1+5 = 6 и т.д.
Чем это можно объяснить или это открытие?!
На самом деле люди в данном случае заново "открывают" признак делимости на 9.
Число даёт при делении на 9 тот же остаток, что и его сумма цифр.
И для самого числа, и для всех его разбиений, остаток от деления на 9 будет одним и тем же, так как состав цифр остаётся прежним (например, 123%9 = 6, 12%9 (=3) + 3%9 (=3) = 6, 1%9 (=1) + 23%9 (=5) = 6 и т.д.)
При замене чисел на сумму цифр это свойство также сохраняется. Тот же самый остаток от деления получается при любых группировках и суммированиях.
На этом свойстве основано много самых разных задач и олимпиадного, и практического типа, меня же сейчас "сумма сумм" навела на мысль проверить для какого-нибудь числа все возможные варианты разбиения числа на группы цифр с последующим их сложением.
Задача о разбиении множества часто встаёт перед нами на практике, с ней связана куча всяких вычислительных проблем.
Здесь мы просто хотим получить все разбиения множества элементов (чисел), причём, исходные элементы могут повторяться, а порядок элементов в группе не имеет значения, например, для {1, 1, 2, 2} имеем при этих условиях разбиения
{ {1}, {1}, {2}, {2} }, { {1}, {1}, {2, 2} }, { {1}, {1, 2}, {2} }, { {1}, {1, 2, 2} }, { {1, 1}, {2}, {2} }, { {1, 1}, {2, 2} }, { {1, 1, 2}, {2} }, { {1, 1, 2, 2 }, { {1, 2}, {1, 2} }
или всего 9 разбиений. Не правда ли, похоже на нашу проблему? Просто найдём суммы цифр в каждом подмножестве и сложим потом эти суммы.
Увы, количество возможных разбиений числа на группы цифр будет быстро расти с увеличением его разрядности, число Белла никто не отменял, но для относительно небольших числовых значений вполне можно написать программку.
Запускалась она в консоли Visual Studio 2019, но должна сработать и в версиях помладше, к вычислительной эффективности алгоритма я в данном случае не стремился, просто нужен был работающий код.
#include <iostream> #include <vector> #include <set> #include <algorithm> #include <numeric> using namespace std; vector <int> integerToArray(int x) { //Целое в массив цифр vector <int> resultArray; while (true) { resultArray.insert(resultArray.begin(), x % 10); x /= 10; if (x == 0) return resultArray; } } template <typename T> T sumOfArray(vector <T> &v) { //Сумма элементов массива T sum = std::accumulate(v.begin(), v.end(), (T)0); return sum; } void allPossibleSubset(vector <int> arr) { //Печать всех подмножеств множества, она тут просто так, жалко стирать :) int n = arr.size(); int count = pow(2, n); for (int i = 0; i < count; i++) { for (int j = 0; j < n; j++) { if ((i & (1 << j)) > 0) cout << arr.at(j) << " "; } cout << endl; } } void solve (set<vector<vector<int>>>& solution, vector<int> inputSet, vector<vector<int>>& partitions, vector<int> partition, int n, int i) { int numberOfElements = 0; for (int i = 0; i < partitions.size(); i++) { numberOfElements += partitions[i].size(); } if (numberOfElements == n) { vector<vector<int>> newPartitions = partitions; for (int i = 0; i < newPartitions.size(); i++) { sort(newPartitions[i].begin(), newPartitions[i].end()); } sort(newPartitions.begin(), newPartitions.end()); solution.insert(newPartitions); return; } for (int j = i; j < n; j++) { partition.push_back (inputSet[j]); partitions.push_back (partition); vector<int> partitionNew; solve (solution, inputSet, partitions, partitionNew, n, j + 1); partitions.pop_back(); } } void permute (set<vector<vector<int>>>& solution, vector<int>& inputSet, int i, int n) { if (i == n) { vector<int> partition; vector<vector<int>> partitions; solve (solution, inputSet, partitions, partition, inputSet.size(), 0); return; } for (int j = i; j <= n; j++) { swap (inputSet[i], inputSet[j]); permute (solution, inputSet, i + 1, n); swap (inputSet[i], inputSet[j]); } } int main() { int n = 1288; //Тестовое число; учтите, что количество разбиений растёт быстро! //Сделали из числа вектор цифр: vector <int> inputSet = integerToArray(n); //Напечатали его: cout << "Set: " << endl; for (auto const& element : inputSet) cout << element << " "; cout << endl; //И сумму: cout << "Sum=" << sumOfArray(inputSet) << endl; //Теперь ищем разбиения: vector <int> partition; int counter = 1; //это их счётчик //Вспомогательные данные: set<vector<vector<int>>> partitions; set<vector<vector<int>>>::iterator it; //Счёт: permute (partitions, inputSet, 0, inputSet.size() - 1); //Вывод: int sum, sum0; for (it = partitions.begin(); it != partitions.end(); it++) { cout << "Partition # " << counter++ << ": " << endl; sum = 0; for (int i = 0; i < (*it).size(); i++) { sum0 = 0; for (int j = 0; j < (*it)[i].size(); j++) { cout << (*it)[i][j] << " "; sum0 += (*it)[i][j]; } cout << " = " << sum0 << endl; sum += sum0; } cout << "Total sum = " << sum << endl; } cin.get(); return 0; }
Вот вывод тестового прогона:
Set: 1 2 8 8 Sum=19 Partition # 1: 1 = 1 2 = 2 8 = 8 8 = 8 Total sum = 19 Partition # 2: 1 = 1 2 = 2 8 8 = 16 Total sum = 19 Partition # 3: 1 = 1 2 8 = 10 8 = 8 Total sum = 19 Partition # 4: 1 = 1 2 8 8 = 18 Total sum = 19 Partition # 5: 1 2 = 3 8 = 8 8 = 8 Total sum = 19 Partition # 6: 1 2 = 3 8 8 = 16 Total sum = 19 Partition # 7: 1 2 8 = 11 8 = 8 Total sum = 19 Partition # 8: 1 2 8 8 = 19 Total sum = 19 Partition # 9: 1 8 = 9 2 = 2 8 = 8 Total sum = 19 Partition # 10: 1 8 = 9 2 8 = 10 Total sum = 19 Partition # 11: 1 8 8 = 17 2 = 2 Total sum = 19
07.01.2020, 00:02 [1631 просмотр]