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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Программы pascal переписать под c++ http://www.cyberforum.ru/cpp-beginners/thread631358.html
Доброго времени суток. вот последняя программа которую нужно сделать под c++ Я знаю парни я вам надоел уже :) Больше не буду вас мучать) Задание: В одномерном массиве, состоящем из n...
C++ Подскажите, как сделать сдвиг массива вправо для вставки нового элемента? // После каждого четного числа добавить число 0. const int n=10; int ar,k=n,t; for(int i=0;i<n;i++){ ar=rand()%10+1; cout<<ar<<"\t"; } cout<<endl<<endl; http://www.cyberforum.ru/cpp-beginners/thread631356.html
Проверка на корректность операции C++
Добрый день. Не знаю как лучше задать вопрос. Смысл идеи таков: Есть интерфейс типа данных (IVariable) и наследники от него, например: Number, Complex, Matrix. Необходимо реализовать функцию...
C++ Матрицы. Бесконечный цикл. Проверка ввода
В конструкторе класса матриц пользователю предлагается выбрать ввода с клавиатуры или автоматически. При выборе ручного ввода возникает цикл непонятного характера. Вот фото консоли во вложении. ...
C++ Ссылка на ссылку http://www.cyberforum.ru/cpp-beginners/thread631318.html
Можно ли говорить, что t это ссылка на ссылку? int y=2; int &q=y; int& t = q;
C++ Программы pascal переписать под c++ Всем доброго времени суток помогите переписать программы под c++ Условие Дано натуральное число n, и действительное число x. Вычислить. program laba3_2; uses crt; var x,s:real;... подробнее

Показать сообщение отдельно
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
31.07.2012, 23:07
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
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru