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

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

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

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

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

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

Дано n различных натуральных чисел (n=5). Напечатать все перестановки этих чисел - C++
Дано n различных натуральных чисел (n=5). Напечатать все перестановки этих чисел.

Задан массив K(m) попарно различных целых чисел. Получить все перестановки целых чисел - C++
Помогите пожалуйста с программой. Задан массив K(m) попарно различных целых чисел. Получить все перестановки целых чисел

возможные комбинации перестановки n чисел - C++
Нужно вывести на экран все возможные комбинации перестановки из n заданных чисел подскажите как это эффективнее реализуати если n=3 то...

Сделать масивом.Дано 5 действительных чисел. Вычислить сумму квадратных корней модулей этих чисел - C++
Дано 5 действительных чисел. Вычислить сумму квадратных корней модулей этих чисел

Дано 12 чисел. Напечатать сначала вс отрицательные из них, а затем все остальные. - C++
1)Дано 12 чисел. Напечатать сначала вс отрицательные из них, а затем все остальные. 2)Если в заданный текст вхлдит каждая из букв слова...

Из заданного интервала натуральных чисел выбрать и напечатать все пары дружественных чисел - C++
Напишите пожалуйста простой код на с++ вот условие Из заданного интервала натуральных чисел выбрать и напечатать все пары дружественных...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
CEBEP
106 / 106 / 9
Регистрация: 21.03.2010
Сообщений: 440
14.04.2011, 23:22 #2
это ж как определитель матрицы...
0
HOBI4EK
1 / 1 / 0
Регистрация: 14.04.2011
Сообщений: 4
16.04.2011, 20:55  [ТС] #3
Что не кто не знает как это сделать ?
Препод просит что бы в задачи был рекурсивный спуск и рекурсивный подъем, а я не представляю как это сделать (
0
CEBEP
106 / 106 / 9
Регистрация: 21.03.2010
Сообщений: 440
16.04.2011, 23:46 #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);
}
1
HOBI4EK
1 / 1 / 0
Регистрация: 14.04.2011
Сообщений: 4
16.04.2011, 23:58  [ТС] #5
Спасибо тебе большое, за помощь. Очень благодарен за то что откликнулся.Буду пытаться сдать твой код.
Препод у меня не толстый тролль, а худенькая девушка ))
Ей главное что бы мы научились делать рекурсию, и применили ее к своей задачи(но я от этого далек).
Подскажи пожалуйста где тут рекурсивный спуск и подъем, а то она просит что бы мы пальцем тыкнули и показали ей.
1
CEBEP
106 / 106 / 9
Регистрация: 21.03.2010
Сообщений: 440
17.04.2011, 03:17 #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");
        }
и непосредственно завершение работы функций.
0
NightmareZ
1340 / 563 / 37
Регистрация: 31.03.2009
Сообщений: 1,919
17.04.2011, 03:33 #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 Посмотреть сообщение
Препод просит что бы в задачи был рекурсивный спуск и рекурсивный подъем, а я не представляю как это сделать (
Печально, что у нас большинство преподов настолько калечные, что не способны придумать адекватные задачи на рекурсию.
1
CEBEP
106 / 106 / 9
Регистрация: 21.03.2010
Сообщений: 440
17.04.2011, 03:49 #8
+3!)))
1
HOBI4EK
1 / 1 / 0
Регистрация: 14.04.2011
Сообщений: 4
14.05.2011, 13:08  [ТС] #9
Спасибо большое за помошь, препод сказала что программу можно было сделать в 2 раза меньше.(но вроди притензий по правильности не было)
Кто-нибуть знает как сделать схему стека (просит ее нарисовать).

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

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

Все возможные комбинации 5 чисел - C++
В общем задача такая: Нужно, чтобы программа выдавала все возможные комбнации 5 чисел: 1 число от 1 до 32 2 число от 2 до 33, но...

дано натуральное число n и вещественные числа a1 a2 aN. определить среднеарифметическое этих чисел - C++
дано натуральное число n и вещественные числа a1 a2 aN,определить среднеарифметическое этих чисел

Найти все возможные значения чисел - C++
задано количество разрядов числа диапазона unsigned long, имеющих значение L. Найти все возможные значения чисел.

Все возможные варианты перестановки символов строки - C++
Дана строка s, состоящая из n символ (n меньше 6) составить все возможные варианты перестановки этих символов (язык C)


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
06.10.2013, 20:16
Ответ Создать тему
Опции темы

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