Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Dark2012
0 / 0 / 0
Регистрация: 03.12.2011
Сообщений: 43
#1

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

31.07.2012, 21:31. Просмотров 470. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.07.2012, 21:31
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсия: нахождение биномиальных коэффициентов (C++):

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

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

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

Напечатать треугольник Паскаля — таблицу биномиальных коэффициентов - C++
дано целое неотрицательное число K. Напечатать треугольник Паскаля - таблицу биномиальных коэффициентов (C из m по n) для всех возможных...

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

Рекурсия, нахождение минимума в массиве - C++
В общем, в названии темы само задание. int min(int a,int n) { int minim=a; if(minim>a) {minim=a; return min(a,n-1);} else...

4
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
31.07.2012, 21:57 #2
Что-то я не понял. Можно разъяснить определение «биноминальных коэффициентов последовательности»? Потому что если это «все варианты выбора k элементов из n с точностью до перестановки», то где 124, 125, 135 во втором примере?
0
Dark2012
0 / 0 / 0
Регистрация: 03.12.2011
Сообщений: 43
31.07.2012, 22:05  [ТС] #3
Да да натупил во если k = 3 то 123, 124, 125, 134, 145, 234, 235, 245, 345
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 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
Миниатюры
Рекурсия: нахождение биномиальных коэффициентов  
01.08.2012, 12:31
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.08.2012, 12:31
Привет! Вот еще темы с ответами:

Рекурсия: нахождение минимального элемента массива - C++
Определить рекурсивную функцию,возвращающую минимальный элемент массива.Использовать её для одномерного массива,содержащего n целых...

Рекурсия: нахождение чисел Фибоначчи (нужны комментарии) - C++
это функция нахождения чисел фибоначи. немогу понять как она работает можите написат как это происходит в программе. отладка много не...

Ввод коэффициентов в уравнение - C++
Здраствуйте. Собственно я не програмист даже близко, но сейчас встала задача написания решения уравнения методом Ньютона. Саму программу...

Пересчет коэффициентов массива - C++
Допустим имеем массив float matr = { { 0, 0, 15, 2, 3 }, { 0, 4, 5, 6, 4 }, { 2, 8, 7, 11, 9 }, { 6, 3, 8, 13, 10 }, ...


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

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

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