Представить натуральное число 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, Варианты получения суммы из комбинации заданных слагаемых.
05.12.2019, 17:12 [1273 просмотра]