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

Рекурсия - C++

Восстановить пароль Регистрация
 
Dark2012
0 / 0 / 0
Регистрация: 03.12.2011
Сообщений: 43
31.07.2012, 21:31     Рекурсия #1
В общем нужно вывести биноминальные коэффициенты последовательности....

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

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

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

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

Прога должна работать рекурсивно!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
31.07.2012, 21:57     Рекурсия #2
Что-то я не понял. Можно разъяснить определение «биноминальных коэффициентов последовательности»? Потому что если это «все варианты выбора k элементов из n с точностью до перестановки», то где 124, 125, 135 во втором примере?
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
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 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 лучше получается удалять с конца. Можно точно так же брать первый элемент и удалять с начала.)
-=ЮрА=-
Заблокирован
Автор 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
Миниатюры
Рекурсия  
Yandex
Объявления
01.08.2012, 12:31     Рекурсия
Ответ Создать тему
Опции темы

Текущее время: 01:14. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru