БлогNot. Представить натуральное число N в виде комбинации K натуральных чисел

Представить натуральное число N в виде комбинации K натуральных чисел

В показанном ниже консольном листинге Visual Studio функция binomialCoeff на основе расчёта биномиальных коэффициентов определяет количество всех возможных решений как перестановок, то есть, для N = 5 и K = 3 имеем 6 вариантов - ( 1, 1, 3 ), ( 1, 3, 1 ), ( 3, 1, 1 ), ( 1, 2, 2 ), ( 2, 2, 1 ) и ( 2, 1, 2 ). Рекурсивная функция output, которая тоже могла бы быть пооптимальней, выводит только комбинации чисел из решений, то есть, получится ( 1, 1, 3 ), ( 1, 2, 2 ).

Поэтому будем рассматривать программу как набросок, а не стопроцентное решение :)

 #include <iostream>
#include <string> /* нужен C++11 из-за to_string */
#include <algorithm>
 using namespace std;

 int** allocate(int n, int m) { //Выделение памяти под матрицу n x m
  int **a = NULL;
  a = new int * [n];
  if (!a) return NULL;
  for (int i = 0; i < n; i++) {
   a[i] = new int [m];
   if (!a[i]) return NULL;
  }
  return a;
 }

 int binomialCoeff (int **C, int n, int k) { //Матрица биномиальных коэффициентов C(n,k)
  int i, j;
  for (i = 0; i <= n; i++) {
   for (j = 0; j <= min(i, k); j++) {
    if (j == 0 || j == i) C[i][j] = 1;
    else C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
   }
  }
  return C[n][k];
 }

 void output(string rs, int k, int s, int in, int n, int kmax) { //Вывод комбинаций
  if (k < kmax) {
   for (int j = in; j <= n-k; j++) {
    output (rs+"+"+to_string(j), k + 1, s + j, j, n, kmax);
   }
  } 
  else if (s == n) cout << rs << endl;
 }
 
 
int main() {
 int n = 10, k = 5;
 int **a = allocate (n,k);
 if (!a) {
  cout << "No memory!";
 }
 else {
  cout << "There are " << binomialCoeff(a, n - 1, k - 1) << " variant(s), here is it:" << endl;
  string s(""); 
  output(s, 0, 0, 1, n, k);
 }
 cin.get();
 return 0;
}

Ссылки по теме: Разбиение числа на Javascript, Варианты получения суммы из комбинации заданных слагаемых.


теги: числа алгоритм c++

05.12.2019, 17:12; рейтинг: 250