Функция вычисления количества сочетаний

@amoteo · Регистрация: 28.10.2017

Код особо ненадо а вот формула что тут n и k умножать вычитать???

@amoteo · 31.12.2018, 17:06 **[ТС]**

888

@DG_ReFLeX · 31.12.2018, 17:33

Конкретную формулу сложно сказать, ибо используется рекурсия. Но вот вам готовое решение.

C++

#include <iostream>
using namespace std;
 
int C(int,int);
int main(){
  int n,k;
  cout << "Enter n:";
  cin >> n;
  cout << "Enter k:";
  cin >> k;
  cout << "C(n,k)= " << C(n,k) << endl; 
  return 0;
}
 
int C(int n, int k){
  if (k == 0 || n == k) return 1;
  else return C(n-1,k-1) + C(n-1,k);
}

Могу объяснить, что есть что, в случае необходимости.

@DG_ReFLeX · 31.12.2018, 17:43

Есть основная формула для нахождения количества сочетаний (см. вложение).
Можно определить, что если k = 0, то C(n,k) = 1.
Также, если k = n, то по формуле C(n,k) = 1.
Поэтому в коде появляется данная строчка:

C++

1	if (k == 0 \|\| n == k) return 1;

Также по условию вам известно C(n,k) = C(n-1,k-1) + C(n-1,k), поэтому в коде появляется строчка №17:

C++

1	else return C(n-1,k-1) + C(n-1,k);

Которая рекурсивным методом будет вызывать саму себя до тех пор, пока k != n или k!=0.

Байт · 01.01.2019, 21:07

DG_ReFLeX, Все это правильно и хорошо. Но в настоящее время лучшим способом считается вычисление C_n^k с помощью подходов Динамического Программирования. Смысл коего в том, что уже вычисленные элементы треугольника Паскаля запоминаются. Да, требуется небольшое количество дополнительной памяти. Но скорость возрастает резко.

Функция вычисления количества сочетаний

Решение

Решение

@amoteo -2 / 0 / 0 Регистрация: 28.10.2017 Сообщений: 33
		1
	Функция вычисления количества сочетаний 31.12.2018, 16:58. Просмотров 1669. Ответов 4 Метки нет (Все метки) Код особо ненадо а вот формула что тут n и k умножать вычитать??? 0

@amoteo -2 / 0 / 0 Регистрация: 28.10.2017 Сообщений: 33
	31.12.2018, 17:06 [ТС]	2
	888 0 Миниатюры

Байт 22101 / 13780 / 2913 Регистрация: 24.12.2010 Сообщений: 29,421
	01.01.2019, 21:07	5
	DG_ReFLeX, Все это правильно и хорошо. Но в настоящее время лучшим способом считается вычисление C_n^k с помощью подходов Динамического Программирования. Смысл коего в том, что уже вычисленные элементы треугольника Паскаля запоминаются. Да, требуется небольшое количество дополнительной памяти. Но скорость возрастает резко. 1

Опции темы