Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/4: Рейтинг темы: голосов - 4, средняя оценка - 5.00
0 / 0 / 1
Регистрация: 03.12.2011
Сообщений: 43
1

Рекурсия: нахождение биномиальных коэффициентов

31.07.2012, 21:31. Просмотров 788. Ответов 4
Метки нет (Все метки)

В общем нужно вывести биноминальные коэффициенты последовательности....

т.е есть последовательность - скажем вектор 12345
n = size = 5
k - пусть равен 2

тогда результатом должны быть все возможные пары

12, 13, 14, 15, 23, 24, 25, 34, 35, 45

если k = 3 то результаты
123, 134, 145, 234, 245, 345

Прога должна работать рекурсивно!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
31.07.2012, 21:31
Ответы с готовыми решениями:

Вывод биномиальных коэффициентов
напишите программу для отображения (без предварительной записи в массив) биномиальных коэффициентов...

Рекурсивное вычисление биномиальных коэффициентов
Привет! Буду рад, если кто то поможет решить: "Рекурсивно описать функцию С(m,n), где...

Рекурсивная процедура вычисления биномиальных коэффициентов
Помогите, пожалуйста! Нужно сдать сегодня. А в рекурсии Си не бум-бум Написать рекурсивную...

Составить программу расчета биномиальных коэффициентов
Добрый день, помогите пожалуйста решить. Задание надо переписывать в тело сообщения!

4
~ Эврика! ~
1253 / 1002 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
31.07.2012, 21:57 2
Что-то я не понял. Можно разъяснить определение «биноминальных коэффициентов последовательности»? Потому что если это «все варианты выбора k элементов из n с точностью до перестановки», то где 124, 125, 135 во втором примере?
0
0 / 0 / 1
Регистрация: 03.12.2011
Сообщений: 43
31.07.2012, 22:05  [ТС] 3
Да да натупил во если k = 3 то 123, 124, 125, 134, 145, 234, 235, 245, 345
0
~ Эврика! ~
1253 / 1002 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
31.07.2012, 23:07 4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <vector>
#include <iostream>
 
using namespace std;
 
template <class T>
vector<vector<T> > perm(vector<T> source, int k)
{
    vector<vector<T> > result;
    if (k == 1) {
        result.reserve(source.size());
        for (int i = 0, len = source.size(); i < len; ++i) {
            vector<T> temp;
            temp.push_back(source[i]);
            result.push_back(temp);
        }
    }
    else if (k == source.size()) {
        result.push_back(source);
    }
    else {
        for (int i = 0, len = source.size() - k + 1; i < len; ++i) {
            T last = source.back();
            source.pop_back();
            vector<vector<T> > temp = perm(source, k - 1);
            for (int j = 0, len = temp.size(); j < len; ++j) {
                temp[j].push_back(last);
                result.push_back(temp[j]);
            }
        }
    }
    return result;
}
 
template <class T>
ostream& operator<<(ostream &stream, vector<T> vec)
{
    stream << "[";
    bool notFirst = false;
    for (typename vector<T>::iterator i = vec.begin();
         i != vec.end();
         ++i)
    {
        if (notFirst) {
            stream << ", ";
        }
        stream << *i;
        if (!notFirst) {
            notFirst = true;
        }
    }
    stream << "]";
    return stream;
}
 
int main()
{
    vector<int> array;
    array.reserve(5);
    for (int i = 1; i <= 5; ++i) {
        array.push_back(i);
    }
    vector<vector<int> > perms = perm(array, 2);
    cout << perms;
    return 0;
}
Вот где-то так вышло. Основано на (очевидных) наблюдениях:
perm([1, 2, 3, 4, 5], 1) = [[1], [2], [3], [4], [5]]

perm([1, 2, 3, 4, 5], 2) = perm([1, 2, 3, 4], 1)|5 + perm([1, 2, 3], 1)|4 + perm([1, 2], 1)|3 + perm([1], 1)|2

perm([1, 2, 3, 4, 5], 3) = perm([1, 2, 3, 4], 2)|5 + perm([1, 2, 3], 2)|4 + perm([1, 2], 2)|3

perm([1, 2, 3, 4, 5], 4) = perm([1, 2, 3, 4], 3)|5 + perm([1, 2, 3], 3)|4

perm([1, 2, 3, 4, 5], 5) = [[1, 2, 3, 4, 5]]
где (на примере):
[1, 2, 3] + [4, 5] = [1, 2, 3, 4, 5]
[[1], [2], [3]]|4 = [[1, 4], [2, 4], [3, 4]]
(Задом наперёд, так как у std::vector лучше получается удалять с конца. Можно точно так же брать первый элемент и удалять с начала.)
0
Заблокирован
Автор FAQ
01.08.2012, 12:31 5
Как то так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cmath>
#include <iostream>
using namespace std;
 
//Ôóíêöèÿ ïîëó÷àåò è ñ÷èòàåò êîë-âî ðàçðÿäîâ ÷èñëà
//åñëè ïîä arr âûäåëåíà ïàìÿòü òî â íåãî çàíîñÿòüñÿ ðàçðÿäû
int * splitDigit(int val, int *arr, int &n);
void rekursBinom(int pos, int *arr, int n, int k);
 
int main()
{
    int val = 0;
    int k   = 0;
    int n   = 0;//Áóäåò ñîäåðæàòü ÷èñëî ðàçðÿäîâ ÷èñëà
    int *arr= 0;//Óêàçàòåëü íà ìàññèâ ñ ðàççðÿäàìè ÷èñëà
    cout<<"Enter value(val): ";cin>>val;
    cout<<"Enter number(k) : ";cin>>k;
    //Óçíàëè ÷èñëî ðàçðÿäîâ
    arr = splitDigit(val, arr, n);
    arr = new int[n];//Âûäåëèëè ïàìÿòü ïîä ìàññèâ
    //Çàïèñàëè ðàçðÿäû â ìàññèâ
    arr = splitDigit(val, arr, n);
    rekursBinom(0, arr, n, k);
    return 0;
}
 
int * splitDigit(int val, int *arr, int &n)
{
    if(val < 0)
        val *= -1;
    n = 1;// ÷èñëå äàæå 0 âñåãäà åñòü 1 öèôðà
    //Ïîäñ÷¸ò êîë-âà öèôð â ÷èñëå val
    //è åñëè arr âàëèäíûé òî çàïîëíåíèå åãî ðàçðàäàìè
    if(arr)
        arr[0] = val % 10;//Çàïèñûâàåì òåêóùèé ðàçðÿä
    while(0 < (val /= 10))
    {
        if(arr)
            arr[n] = val % 10;
        n = n + 1;//Óâåëè÷èâàåì ñ÷¸ò÷èê ðàçðÿäîâ
    }
    return arr;
}
 
void rekursBinom(int pos, int *arr, int n, int k)
{
    int i, j;
    int val = arr[pos];
    for(i = 0; i < n;     i++)
    {
        if(i == pos)
            continue;
        val = arr[pos];
        for(j = 0; j < k - 1; j++)
        {
            val *= 10;
            if(i + j < n)
                val += arr[i +     j];
            else
                val += arr[0 + n - j];  
        }
        cout<<val<<endl;
    }
    while((pos += 1) < n)
        rekursBinom(pos, arr, n, k);
}
Отработка
Enter value(val): 12345
Enter number(k) : 3
543
532
521
511
454
432
421
411
354
343
321
311
254
243
232
211
154
143
132
121
154
143
132
121
254
243
232
211
154
143
132
121
154
143
132
121
354
343
321
311
254
243
232
211
154
143
132
121
154
143
132
121
254
243
232
211
154
143
132
121
154
143
132
121
Press any key to continue
0
Миниатюры
Рекурсия: нахождение биномиальных коэффициентов  
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.08.2012, 12:31

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Составить программу для вычисления биномиальных коэффициентов:
Составить программу для вычисления биномиальных коэффициентов (для заданного M&gt;=i&gt;=j&gt;0 вычислять ...

Напечатать треугольник Паскаля — таблицу биномиальных коэффициентов
дано целое неотрицательное число K. Напечатать треугольник Паскаля - таблицу биномиальных...

Напечатать треугольник Паскаля — таблицу биномиальных коэффициентов по формуле
Дано целое неотрицательное число K. Напечатать треугольник Паскаля - таблицу биномиальных...

Рекурсия: нахождение биномиального коэффициента
Собственно задача поставлена предельно просто, найти биномиальный коэффициент, используя рекурсию....


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

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

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