БлогNot. Загадочная "сумма сумм" и задача о разбиении множества

Загадочная "сумма сумм" и задача о разбиении множества

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

Случайно открыл такое свойство чисел: допустим есть число 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

теги: числа программирование c++ математика

07.01.2020, 00:02; рейтинг: 265