Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
Akella!BLR!
0 / 0 / 0
Регистрация: 01.06.2013
Сообщений: 32
#1

Описать рекурсивную функцию Combin1(N, K)

04.04.2015, 23:56. Просмотров 607. Ответов 3
Метки нет (Все метки)

Описать рекурсивную функцию Combin1(N, K) целого типа, находящую C(N, K) — число сочетаний из N элементов по K — с помощью рекуррентного соотношения:
C(N, 0) = C(N, N) = 1,
C(N, K) = C(N – 1, K) + C(N – 1, K – 1) при 0 < K < N.
Параметры функции — целые числа; N > 0, 0 ≤ K ≤ N. Дано число N и пять различных значений K. Вывести числа C(N, K) вместе с количеством рекурсивных вызовов функции Combin1, потребовавшихся для их нахождения.

Подскажите алгоритм решения. Ну можно код
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.04.2015, 23:56
Ответы с готовыми решениями:

Описать рекурсивную функцию
Описать рекурсивную функцию function nmemb(r: link; b:integer):integer;...

Нужно описать рекурсивную функцию
Помогите описать, и как работает, функция gor2. Код не мой, но хочу понять как...

Описать рекурсивную функцию DigitCount(S)
Описать рекурсивную функцию DigitCount(S) целого типа, которая находит ...

Описать рекурсивную функцию Root(X, K, N)
Описать рекурсивную функцию Root(X, K, N) вещественного типа, находящую...

Описать рекурсивную логическую функцию
Описать рекурсивную логическую функцию Simm(S,l, J), проверяющую, является ли...

3
gunslinger
случайный прохожий
1277 / 809 / 319
Регистрация: 20.07.2013
Сообщений: 2,268
05.04.2015, 03:15 #2
Лучший ответ Сообщение было отмечено Akella!BLR! как решение

Решение

Приблизительно так (основа), если не ошибся с подсчетом вызовов:
C++
1
2
3
4
5
6
7
8
9
10
unsigned __int64 count;
 
unsigned __int64 Combin1(unsigned int n, unsigned int k)
{
  count++;
  if (k == 0 || k == n)
    return 1;
  else
    return Combin1(n-1, k) + Combin1(n-1, k-1);
}
Пример вызова:
C++
1
2
count = 0;  // обнуляем счетчик перед каждым вызовом Combin1
Combin1(10, 5);  // число сочетаний (ЧС)
Чтобы узнать кол-во вызовов (КВ) функции, используй значение переменной count (или count-1 ?).
Для данного примера имеем 252 (ЧС) и 503 (КВ).
1
Akella!BLR!
0 / 0 / 0
Регистрация: 01.06.2013
Сообщений: 32
07.04.2015, 23:38  [ТС] #3
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int Combin1(int n,int k);
int count=0;
int main()
{
    setlocale(0,"");
    int n,k;
    cout<<"Введите натуральное число n ";
    cin>>n;
    cout<<"Введите натуральное число, не больше "<<n<<" ";
    cin>>k;
    cout<<"Число сочетаний из "<<n<<" по "<<k<<": "<<Combin1(n,k)<<"\nКоличество вызовов функции: "<<count<<"\n";
    return 0;
}
int Combin1(int n,int k)
{
    if(k==0 || k==n) return 1;
    return Combin1(n-1,k)+Combin1(n-1,k-1);
    count++;
}
Не работает счётчик, почему?
0
gunslinger
случайный прохожий
1277 / 809 / 319
Регистрация: 20.07.2013
Сообщений: 2,268
08.04.2015, 12:16 #4
Во-первых, ты пропустил else.
Во-вторых, у тебя строка №20 не используется - код после return (в твоем случае) "будет недостижим" (если память мне не изменяет).

Тут та ситуация, когда нужно было просто скопировать код функции:
C++
1
2
3
4
5
  count++;
  if (k == 0 || k == n)
    return 1;
  else
    return Combin1(n-1, k) + Combin1(n-1, k-1);
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.04.2015, 12:16

Описать рекурсивную функцию pow(x,n)
пожалуйста помогите, не могу сообразить как написать такую вот...

Описать рекурсивную функцию stepen (x, n)
Описать рекурсивную функцию stepen (x, n) от вещественного х (х ≠ 0) и целого...

Описать рекурсивную функцию вычисления значения по формуле
Рекурсия


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru