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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 35, средняя оценка - 4.60
Beg1ner
0 / 0 / 0
Регистрация: 28.10.2009
Сообщений: 9
#1

Рекурсия. Комбинаторика. Размещения - C++

04.04.2010, 18:10. Просмотров 4919. Ответов 3
Метки нет (Все метки)

Дана задача: вывести все размещения из n по k, где n - это число элементов конечного множества (например, задаваемого из файла). Комбинации считаются различными, если отличаются либо элементами, либо их порядком. Программа должна работать для любого n. Например:

Пусть множество (1, 2, 3).
Пусть k=2. А n=3.
Размещения тогда:
1 2
1 3
2 1
2 3
3 1
3 2

Пусть множество (1, 2, 3).
Пусть k=3. А n=3.
Размещения тогда:
1 2 3
1 3 2
2 3 1
2 1 3
3 1 2
3 2 1

Помогите написать программу на C++ с использованием рекурсии. Не могу понять алгоритм. Комментарии приветствуются.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.04.2010, 18:10
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсия. Комбинаторика. Размещения (C++):

Рекурсия: размещения из 10 по 3 элемента - C++
Помогите Плз Плз Плз Плз Плз Получить все размещения из 10 элементов 1, 2,..., 10 по 3 в каждом. Размещением называется выборка из п...

Рекурсия: вывести все возможные размещения элементов массива - C++
Дан массив char mas = { a, b, c, d, e, f, g, h, j, k }. Вывести на экран все возможные комбинации букв ( каждая комбинация = 10 символов )

размещения - C++
помогите с задачей ввожу слово например: ab прога должа вывести: a b ab ba может можно эту программу переделать, чтоб...

Комбинаторика - C++
От пользователя требуется ввести n. Результат должен быть таким:

Комбинаторика - C++
Доброго всем времени суток!Помогите пожалуйста с решением такой задачи.Дана последовательность вещественных чисел.Пользователь вводит...

комбинаторика - C++
Здравствуйте! Я решаю задачи по дискретной математике на языке С.В интернете масса примеров задач на тему комбинаторики, но на языке...

3
Beg1ner
0 / 0 / 0
Регистрация: 28.10.2009
Сообщений: 9
12.04.2010, 20:08  [ТС] #2
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
#include <iostream>
#include <sstream>
 
using namespace std;
void Razm(string razm, int place, int n, int k);
 
int main()
{   
    int n;
    int k;
    setlocale (LC_ALL, "Russian_Russia.1251");
    cout << "Введите n и k: " << endl;
    cin >> n >> k;
    cout << "Размещения из " << n << " по " << k << ": " << endl;
    Razm("", 1, n, k);
    cin.get();
    cin.get();
    return 0;
}
 
void Razm(string razm, int place, int n, int k)
{
    if(place > k)
        cout << razm << endl;
    else
        for(int i = 0; i < n; i++)
        {
            ostringstream os;
            os << i + 1;
            Razm(razm + os.str() + " ", place + 1, n, k);
        }
}
Помогите плз сделать так, чтобы выводились размещения без повторений.
0
Alex5
1075 / 739 / 115
Регистрация: 12.04.2010
Сообщений: 1,889
13.04.2010, 23:37 #3
Массив a[] содержит k различных элементов из n возможных FIRST, FIRST+1, FIRST+2, ... FIRST+(n-1)
Функция Next() строит новое размещение и возвращает true.
Или, если все размещения ( из n по k ) перебрали, возвращает false.
Пример. n=3, k=2 a[] : 1 2
вызываем Next() a[] : 1 3 возвращаемое значение : true
вызываем Next() a[] : 2 1 возвращаемое значение : true
вызываем Next() a[] : 2 2 возвращаемое значение : true
вызываем Next() a[] : 3 1 возвращаемое значение : true
вызываем Next() a[] : 3 2 возвращаемое значение : false
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
#define FIRST 1
 
// true : i > 0 and there exists a[i0] == a[i] for  0 <= i0 <= i-1
bool HasCoincidence( int i, int a[] );
 
// create next k-permutation of  n  elements
// true : success;   false : fails, no permutations
bool Next ( int n,  int k, int a[] )
{
    if ( k <= 0 )    return false;
 
    do{
        a[k-1]++;
 
        if ( a[k-1] >= FIRST + n )
        {
            a[k-1] = FIRST;
            if ( ! Next( n, k-1, a ) )    return false;
        
        }
    
    } while( HasCoincidence( k-1, a ) ); 
    // while   a[k-1]   coincides with some of a[0], a[1], ... , a[k-2]
 
 
    return true;
}
1
Beg1ner
0 / 0 / 0
Регистрация: 28.10.2009
Сообщений: 9
14.04.2010, 04:10  [ТС] #4
Спасибо.
0
14.04.2010, 04:10
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.04.2010, 04:10
Привет! Вот еще темы с ответами:

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

Комбинаторика - C++
Здравствуйте все. В данный момент дпополнительно решил заняться комбинаторикой, столкнулся с задачей, и никак не могу её решить.Суть...

Комбинаторика - C++
Помогите написать алгоритм для вычисления количество непустых последовательностей из ряда чисел. Или кинте ссылочку, где почитать. Что я...

Размещения с повторением - C++
Постановка задачи такова: На входе даются два числа &quot;n&quot; и &quot;k&quot;.n-максимальное число в последовательности,а k-длина последовательности ...


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

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

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