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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 43, средняя оценка - 4.77
HOBI4EK
1 / 1 / 0
Регистрация: 14.04.2011
Сообщений: 4
#1

Дано n различных чисел, напечатать все возможные перестановки этих чисел - C++

14.04.2011, 20:31. Просмотров 5432. Ответов 13
Метки нет (Все метки)

Помогите пожалуйста решить задачу через рекурсию:
Дано n различных чисел, напечатать все возможные перестановки этих чисел.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.04.2011, 20:31     Дано n различных чисел, напечатать все возможные перестановки этих чисел
Посмотрите здесь:

C++ возможные комбинации перестановки n чисел
C++ Все возможные варианты перестановки символов строки
Все возможные комбинации 5 чисел C++
Найти все возможные значения чисел C++
Дано 12 чисел. Напечатать сначала вс отрицательные из них, а затем все остальные. C++
Дано n различных натуральных чисел (n=5). Напечатать все перестановки этих чисел C++
C++ Все возможные перестановки элементов заданного массива
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
14.04.2011, 23:22     Дано n различных чисел, напечатать все возможные перестановки этих чисел #2
это ж как определитель матрицы...
HOBI4EK
1 / 1 / 0
Регистрация: 14.04.2011
Сообщений: 4
16.04.2011, 20:55  [ТС]     Дано n различных чисел, напечатать все возможные перестановки этих чисел #3
Что не кто не знает как это сделать ?
Препод просит что бы в задачи был рекурсивный спуск и рекурсивный подъем, а я не представляю как это сделать (
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
16.04.2011, 23:46     Дано n различных чисел, напечатать все возможные перестановки этих чисел #4
ща сделаю.

Добавлено через 1 час 26 минут
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<cstdio>
#include<cstdlib>
 
int askNumberOfElements()
{
    int ret;
    do
    {
        printf( "Vvedite k-vo elementov v masive: " );
        scanf_s("%d", &ret);
    }
    while(ret <= 0);
    return ret;
}
int* packArray(int elements)
{
    int* ret = (int*) malloc(elements * sizeof(int));
    for(int i = elements; i; --i)
    {
        printf( "Vvedite %d element massiva: ", elements - i + 1 );
        scanf_s("%d", ret + elements - i);
    }
    return ret;
}
 
bool isContain(int* array, int countOfElements, int requiredElement)
//функция поиска элемента в массиве
{
    for(int i = 0; i < countOfElements; ++i)
        if(array[i] == requiredElement)
            return true;
    return false;
}
void nextElement(int* usedElements, int countOfUsedElements, int& currentElement)
//функция перехода к следующему элементу.
{
    while(isContain(usedElements, countOfUsedElements, ++currentElement)) {   }
}
int firstElement(int* usedElements, int countOfUsedElements)
//Определяет, с какого элемента нацинать итерирование цикла.
{
    int currentElement = 0;
    while(isContain(usedElements, countOfUsedElements, currentElement))
        ++currentElement;
 
    return currentElement;  
}
void recursionPrintAllCombinationOfElemens(int* array, int elements, int countOfUsedElements = 0)
{
    /*
    вообще алгоритм мой тупорыл и состоит в следующем: заводится массив usedElements куда
    записывается номер элемента, который уже был включён в собираемый порядок следования.
    она объявлен как static, это значит что объявлен он будет только первый раз а не при
    каждом рекурсивном вызове функции. Далее если колличество записанных в массив использованных
    элементов не равно количеству элементов выводимого масива то входим в цикл по перебору
    всех неиспользованных элементов, каждый записывается в массив использованных элементов,
    после этого для него вызывается рекурсия.
    если число элементов в массиве использованных элементов равно числу элементов выводимого
    масива, т. е. достиднуто дно рекурсии(или пик, как привычнее) то вызывается цикл по
    выводу элементов исходного массива в соответствии с порядком, указанным в массиве использованных
    элементов. Если ваш препод - толстый троль, он может обратить внимание на то что вывод
    происходит не на этапе выхода из рекурсии а в отдельном цикле. Скажите ему что это вызвано
    спецификой моего алгоритма. и вообще если такой вопрос возникнет, знайте что вопрос этот
    сам по себе тупой, так как для реализации вывода на этапе выхода из рекурсии необходимо,
    так или иначе, вывести все собранные на верхних этажаэ элементы, а для этго всёравно
    нужен отдельный цикл.
    Недостаток алгоритма в том, что заводится дополнительный массив и по нему постоянно идёт
    пойск. Для учебной задачи такой недостаток не так уж и ужасен и кроме того, я пробовал
    гуглить на эту тему и альтернативных решений не нашел. вообще задача решается наилучшим
    образом не с помощью рекурсии а используя циклический подход. что, в целом, логично.
 
    Реализовано всё на чистом си, единственное - не уверен по поводу static. если его ваш
    препод не вытерпет(в нём нет ничего плохого, просто он может выходить за рамки преподаваемого
    материалла) то вынисите объявление usedElements или в глобальное пространство или в main
    */
    static int* usedElements = (int*) malloc(elements * sizeof(int));
    if(countOfUsedElements != elements)
        for(int i = firstElement(usedElements, countOfUsedElements); i < elements; nextElement(usedElements, countOfUsedElements, i))
        {
            usedElements[countOfUsedElements] = i;
            recursionPrintAllCombinationOfElemens(array, elements, countOfUsedElements + 1);
        }
    else
    {
        for(int i = 0; i < elements; ++i)
            printf("%d\t", array[usedElements[i]]);
        printf("\n");
    }
}
 
void main()
{
    int n = askNumberOfElements(),
      * m = packArray(n);
 
    printf("Vse vozmojnie kombinacii elementov:\n");
    recursionPrintAllCombinationOfElemens(m, n);
 
    free(m);
}
HOBI4EK
1 / 1 / 0
Регистрация: 14.04.2011
Сообщений: 4
16.04.2011, 23:58  [ТС]     Дано n различных чисел, напечатать все возможные перестановки этих чисел #5
Спасибо тебе большое, за помощь. Очень благодарен за то что откликнулся.Буду пытаться сдать твой код.
Препод у меня не толстый тролль, а худенькая девушка ))
Ей главное что бы мы научились делать рекурсию, и применили ее к своей задачи(но я от этого далек).
Подскажи пожалуйста где тут рекурсивный спуск и подъем, а то она просит что бы мы пальцем тыкнули и показали ей.
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
17.04.2011, 03:17     Дано n различных чисел, напечатать все возможные перестановки этих чисел #6
когда я учился были углубление в рекурсию и выход из неё. углубление это когда функция вызвала себя а выход это когда вызванная своим верхним экземпляром функция завершила свою работу. Судя по всему получается что спуск это вызов функции, то есть
C
1
recursionPrintAllCombinationOfElemens(array, elements, countOfUsedElements + 1);
а подъёмом можно назвать ту часть функции которая выполняется после того как сработало условие достижения дна рекурсиии. это вывод
C
1
2
3
4
5
6
        else
        {
                for(int i = 0; i < elements; ++i)
                        printf("%d\t", array[usedElements[i]]);
                printf("\n");
        }
и непосредственно завершение работы функций.
NightmareZ
 Аватар для NightmareZ
1339 / 562 / 37
Регистрация: 31.03.2009
Сообщений: 1,907
17.04.2011, 03:33     Дано n различных чисел, напечатать все возможные перестановки этих чисел #7
Цитата Сообщение от HOBI4EK Посмотреть сообщение
Помогите пожалуйста решить задачу через рекурсию:
Дано n различных чисел, напечатать все возможные перестановки этих чисел.
Рекурсия (во всяком случае в явном виде) никоим боком тут не упёрлась. Правильно эту задачу решать так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <algorithm>
 
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    size_t len = sizeof(arr) / sizeof(int);
 
    do
    {
        for (int i = 0; i < len; i++)
            std::cout << arr[i] << " ";
        std::cout << std::endl;
    } while (std::next_permutation (arr, arr + len));
 
    return 0;
}
Цитата Сообщение от HOBI4EK Посмотреть сообщение
Препод просит что бы в задачи был рекурсивный спуск и рекурсивный подъем, а я не представляю как это сделать (
Печально, что у нас большинство преподов настолько калечные, что не способны придумать адекватные задачи на рекурсию.
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
17.04.2011, 03:49     Дано n различных чисел, напечатать все возможные перестановки этих чисел #8
+3!)))
HOBI4EK
1 / 1 / 0
Регистрация: 14.04.2011
Сообщений: 4
14.05.2011, 13:08  [ТС]     Дано n различных чисел, напечатать все возможные перестановки этих чисел #9
Спасибо большое за помошь, препод сказала что программу можно было сделать в 2 раза меньше.(но вроди притензий по правильности не было)
Кто-нибуть знает как сделать схему стека (просит ее нарисовать).

Добавлено через 6 минут
Точнее: Модель рекурсивного вызова

Добавлено через 4 часа 50 минут
Все спасибо ничего не надо )) Так договорился )
teebee91
0 / 0 / 0
Регистрация: 15.07.2011
Сообщений: 15
29.09.2013, 00:00     Дано n различных чисел, напечатать все возможные перестановки этих чисел #10
Здравствуйте, уважаемые программисты и сисадмины
Просмотрел коды в форуме но ничего касательно с++ не нашел
Пожалуйста помогите
У меня та же задача но нужно обязательно использовать рекурсию
Дано n различных чисел, напечатать все возможные перестановки этих чисел (на С++)
Спасибо заранее
teebee91
0 / 0 / 0
Регистрация: 15.07.2011
Сообщений: 15
05.10.2013, 23:52     Дано n различных чисел, напечатать все возможные перестановки этих чисел #11
Прошу помощи.....
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
06.10.2013, 00:03     Дано n различных чисел, напечатать все возможные перестановки этих чисел #12
так требуется код написанный выше переписать в объектно-ориентированном стиле?
teebee91
0 / 0 / 0
Регистрация: 15.07.2011
Сообщений: 15
06.10.2013, 20:12     Дано n различных чисел, напечатать все возможные перестановки этих чисел #13
Нет, не в Ооп стиле. Структурно на С++ если можно.
И препод просит с рекурсией (((... Просто я пересмотрел выше код и он слишком громоздкий чтоб понять его, а встроенные функции перебора не прокатят... ((
Плизз
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.10.2013, 20:16     Дано n различных чисел, напечатать все возможные перестановки этих чисел
Еще ссылки по теме:

Сделать масивом.Дано 5 действительных чисел. Вычислить сумму квадратных корней модулей этих чисел C++
дано натуральное число n и вещественные числа a1 a2 aN. определить среднеарифметическое этих чисел C++
C++ Вывести все возможные перестановки слов в предложении
Задан массив K(m) попарно различных целых чисел. Получить все перестановки целых чисел C++
Из заданного интервала натуральных чисел выбрать и напечатать все пары дружественных чисел C++

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

Или воспользуйтесь поиском по форуму:
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
06.10.2013, 20:16     Дано n различных чисел, напечатать все возможные перестановки этих чисел #14
ну блин. Всё-равно не понимаю. Если это слишком громоздкий, чтобы его понять, то надо бороться с ленью наверно...
Yandex
Объявления
06.10.2013, 20:16     Дано n различных чисел, напечатать все возможные перестановки этих чисел
Ответ Создать тему
Опции темы

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