Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
stochanskuo
0 / 0 / 0
Регистрация: 05.11.2018
Сообщений: 2
1

Вывод всех возможных вариантов перестановки элементов массива (рекурсия)

05.11.2018, 01:38. Просмотров 233. Ответов 19
Метки нет (Все метки)

Никак не могу создать алгоритм для вывода всех возможных вариантов перестановки элементов массива через рекурсию. Входные данные: массив элементов. Подскажите пожалуйста как это реализовать.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2018, 01:38
Ответы с готовыми решениями:

Перебор и вывод всех возможных сочетаний
Итак,здравствуйте форумчане. Привела меня к вам интересная задачка. Вводится слово,заранее не...

Перестановка букв в слове и вывод всех возможных перестановок
Написал программу для перестановки букв в слове и выводе всех возможных перестановок. Но при вводе...

Вывод элемента массива, значение которого меньше всего отличается от арифметической средней всех элементов массива
Всем доброго дня! Работаю над заданием. Только не сделал его до конца. Помогите пожалуйста...

Алгоритм перестановки элементов массива
Кто-нибудь знает как сделать перестановку элементов таким образом 1 2 3 4 5 6 7 8 9 10 11 12 13 14...

Рекурсия для нахождения всех делителей массива чисел
Привет всем! Прошу о помощи. Нужно исправить ошибку. Пишу рекурсию для нахождения всех делителей...

19
stake-k26
539 / 412 / 323
Регистрация: 25.04.2016
Сообщений: 1,194
05.11.2018, 01:54 2
1. если количество перестановок < рассчитанного заранее максимума:
1.а. перемешал массив
1.б. если такого массива еще нет в базе, записал полученный вариант в базу (а заодно и вывел на экран при желании)
1.в иначе уменьшил количество перестановок на 1
2. повторил шаг 1

элементарно.

Добавлено через 54 секунды
но в коде я это писать не буду.
0
stochanskuo
0 / 0 / 0
Регистрация: 05.11.2018
Сообщений: 2
05.11.2018, 02:00  [ТС] 3
Можна код пж. Не могу понять как ето написать

Добавлено через 2 минуты
Какого максимума??
0
ft4l
Невнимательный
252 / 215 / 91
Регистрация: 08.02.2013
Сообщений: 641
Записей в блоге: 1
05.11.2018, 02:06 4
Где-то здесь есть ответ на похожее post
1
Байт
Эксперт C
20038 / 12660 / 2662
Регистрация: 24.12.2010
Сообщений: 26,362
05.11.2018, 11:04 5
Цитата Сообщение от stake-k26 Посмотреть сообщение
если такого массива еще нет в базе
А если есть?
Вообще, предложенный алгоритм похож на первоапрельскую шутку. Готовитесь заранее?
stochanskuo, смотрите в сторону "Генерация перестановок". На форум встречалось много раз.

Добавлено через 3 минуты
ft4l, да, по вашей ссылке есть и с рекурсией и без.
0
gng
846 / 582 / 179
Регистрация: 08.09.2013
Сообщений: 1,567
05.11.2018, 14:51 6
По ссылке одинаковые элементы не отлавливаются, но там и условие этого не требовало.
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
#include <stdio.h>
#include <stdlib.h>
#define N 8 
 
void move (int *a, int n) {
  static int count=0;
  if (n == N-1) {
    printf ("%d:\t", ++count);
    for (int j=0; j<N; j++) printf ("%d ", a[j]);
    printf ("\n");
    return;
  }
  for (int i= n; i<N; i++) {
    for (int j=n; j<i; j++) if (a[j] == a[i]) goto next;
    int *a_ = malloc (N*sizeof(int));
    for (int j=0; j<N; j++) {
      if (j == n) a_[j] = a[i];
      else if (j == i) a_[j] = a[n];
      else a_[j]= a[j];
    }
    move (a_, n+1);
    free (a_);
next: ;
  }
}
 
int main() {
  int a[N];
  for (int i=0; i<N; i++) a[i]= rand()%12;
 
  move (a,0);
  return 0;
}
1
Байт
Эксперт C
20038 / 12660 / 2662
Регистрация: 24.12.2010
Сообщений: 26,362
05.11.2018, 20:26 7
Код с "goto" смотреть не буду. Не потому что я его такой уже рьяный противник. На его использование свидетельствует о недостаточной дисциплине ума.
1
gng
846 / 582 / 179
Регистрация: 08.09.2013
Сообщений: 1,567
05.11.2018, 21:37 8
Цитата Сообщение от Байт Посмотреть сообщение
Код с "goto" смотреть не буду. Не потому что я его такой уже рьяный противник. На его использование свидетельствует о недостаточной дисциплине ума.
Это один из немногих случаев, где использование goto оправдано, поскольку любое обходное решение усложняет логику и читабельность программы. Здесь в холиварах этот вопрос "шумно" обсуждался.
Чтобы кто-то прочел, упрощу программу, предположив, что переставляем символы в строке.
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define SWAP(a,b) if ((a)!=(b)) {a^=b; b^=a; a^=b;}
 
void move (char *a, int n) 
{
  static int count=0;
  int N = strlen(a);
 
  if (n == N-1) printf ("%d:\t%s\n", ++count, a);
  else for (int i= n; i<N; i++) {
    for (int j=n; j<i; j++) if (a[j] == a[i]) goto next;
 
    SWAP (a[i], a[n]);
    move (a, n+1);
    SWAP (a[i], a[n]);
next: ;
  }
}
 
int main() {
  char a[] = "012310";
  move (a, 0);
  return 0;
}
2
Байт
Эксперт C
20038 / 12660 / 2662
Регистрация: 24.12.2010
Сообщений: 26,362
05.11.2018, 22:07 9
Цитата Сообщение от gng Посмотреть сообщение
for (int j=n; j<i; j++) if (a[j] == a[i]) goto next;
Неужели так уж трудно написать тут вместо goto сontinue или break Али вы этого не проходили?
Вообще вопросов много. Как ни стараюсь, никак не могу ничего не понять. Давайте так. Вы этот код запускали? Ну и что? Работает? Поверю на слово. Но только тогда буду разбираться. Кажется бредом. Возможно, я чего-то не понимаю.
0
gng
846 / 582 / 179
Регистрация: 08.09.2013
Сообщений: 1,567
05.11.2018, 22:13 10
Цитата Сообщение от Байт Посмотреть сообщение
Неужели так уж трудно написать тут вместо goto сontinue или break
Тогда уж и break и continue и повторение условий. Внутренний цикл прерываем, во внешнем переходим к следующей итерации.
Цитата Сообщение от Байт Посмотреть сообщение
Работает?
На простых примерах с повторениями символов ошибок не обнаружил.
При отсутствии повторений выдает n! вариантов.
0
Байт
Эксперт C
20038 / 12660 / 2662
Регистрация: 24.12.2010
Сообщений: 26,362
06.11.2018, 09:18 11
gng, похоже, что все у вас правильно. И я зря ворчал.
0
stake-k26
539 / 412 / 323
Регистрация: 25.04.2016
Сообщений: 1,194
06.11.2018, 13:52 12
Цитата Сообщение от Байт Посмотреть сообщение
А если есть?
Цитата Сообщение от stake-k26 Посмотреть сообщение
1.в иначе уменьшил количество перестановок на 1
А это для кого написано?

Добавлено через 3 минуты

Не по теме:

псевдокод разжевывать.. - как-то это уже перебор, не находите? :)

0
Байт
Эксперт C
20038 / 12660 / 2662
Регистрация: 24.12.2010
Сообщений: 26,362
06.11.2018, 14:57 13
stake-k26, разжевывать псевдокод, конечно, не надо. Тем более, что идея его просто чудовищная.
Попробуйте решить такую задачку по терверу. Есть N целей. Ведется случайная стрельба по этим целям. Каково матожидание количества выстрелов для поражения всех целей?
В полученную формулу подставьте N = 120 (для 5-ти перестановок) 720 (для 6-ти) и так далее.
И не говорите, пожалуйста, что эта математика не имеет отношения к вашему алгоритму. Имеет. И самое прямое.
(Если вам сложно подсчитать матожидание для произвольного N, подсчитайте для N = 6. И вы будете просто поражены чудовищной неэффективности вашего алгоритма. Я уж не говорю о том, что имеется ненулевая вероятность не получить все перестановки НИКОГДА. И об объеме "базы" тоже не говорю.
0
stake-k26
539 / 412 / 323
Регистрация: 25.04.2016
Сообщений: 1,194
06.11.2018, 15:13 14
Цитата Сообщение от Байт Посмотреть сообщение
вы будете просто поражены чудовищной неэффективности вашего алгоритма
Вот уж вряд ли. меня сложно впечатлить моим же кодом. Байт, в каком месте я сказал, что этот алгоритм эффективен? Он работает, и только, однако про эффективность речь не шла ни разу.

Если я где-то ошибся, и где-то упомянул, что это высокоэффективный.. или просто эффективный алгоритм, можете смело кинуть в меня цитатой.

Цитата Сообщение от Байт Посмотреть сообщение
имеется ненулевая вероятность не получить все перестановки НИКОГДА
.. имеется, но учитывая мощности современного железа, она стремится к 0, вопрос лишь во времени, которое железяка потратит на выполнение кода.

Не по теме:

я уж как бы промолчу, что рекурсия - это само по себе плохой вариант для любого решения. Можно запросто упереться в стек.

0
Catstail
Модератор
24154 / 12143 / 2178
Регистрация: 12.02.2012
Сообщений: 19,721
06.11.2018, 16:51 15
Цитата Сообщение от stake-k26 Посмотреть сообщение
рекурсия - это само по себе плохой вариант для любого решения.
- рекурсию нужно применять с умом. Бывают случаи, когда рекурсивный вариант великолепен, а нерекурсивный - откровенно уродлив. Например, попробуйте реализовать без рекурсии "ханойскую башню". Общее правило: рекурсия хороша, когда рекурсивна структура данных.

Добавлено через 2 минуты
stake-k26, да, Ваш алгоритм одобрить не могу... Каждую перестановку придется "хранить в базе"... Это какой же объем понадобится? А Вы о стеке беспокоитесь..
0
stake-k26
539 / 412 / 323
Регистрация: 25.04.2016
Сообщений: 1,194
06.11.2018, 18:00 16
Цитата Сообщение от Catstail Посмотреть сообщение
А Вы о стеке беспокоитесь
ошибаетесь.
Цитата Сообщение от stake-k26 Посмотреть сообщение
но в коде я это писать не буду.
Если найдется достаточно отважный человек для реализации этого алгоритма на практике, то это буду точно не я, так что мне глубоко до фонаря, что там не так и какие бока могут вылезти.
0
Catstail
Модератор
24154 / 12143 / 2178
Регистрация: 12.02.2012
Сообщений: 19,721
06.11.2018, 18:51 17
Цитата Сообщение от stake-k26 Посмотреть сообщение
ошибаетесь.
- в чем же? Вы писали - "...плохой вариант для любого решения. Можно запросто упереться в стек"
0
stake-k26
539 / 412 / 323
Регистрация: 25.04.2016
Сообщений: 1,194
06.11.2018, 19:10 18
Цитата Сообщение от Catstail Посмотреть сообщение
в чем же?
а не скажу..

Сначала уважаемый Байт словно с луны свалился. Я уж думал, что на сегодня все, но нет, следом вы.. Вот скажите, Catstail, а для кого, позвольте-с спросить, там цитирование стоит, которое прямо указывает на строку, которой адресован ответ? Для котейкина на вашей аватарке?
0
Байт
Эксперт C
20038 / 12660 / 2662
Регистрация: 24.12.2010
Сообщений: 26,362
06.11.2018, 20:20 19
stake-k26, Ладно. Не хотите ничего слушать - не надо. Пусть предложенный вами "алгоритм" останется на вашей совести. Я только хотел предупредить возможных читателей этого топика о его полной непригодности, даже бредовости. Дискутировать на эту тему дальше - смысла не вижу.
Тем более, что задача уже решена. И здесь, и в ссылках.
Всего наилучшего!
0
stake-k26
539 / 412 / 323
Регистрация: 25.04.2016
Сообщений: 1,194
07.11.2018, 01:19 20
Цитата Сообщение от Байт Посмотреть сообщение
Я только хотел предупредить возможных читателей этого топика о его полной непригодности
и все это время вы писали мне... каким местом я похож на возможного читателя этого топика?

Байт, давайте так, если вы хотите обратиться к широкой аудитории из возможно недалекого будущего, и указать на существующие недостатки предложенного кем-то алгоритма (о которых автор алгоритма вполне возможно осведомлен никак не хуже вас), так и пишите этой самой аудитории, хорошо?

Т.е. буквально: "Ахтунг, товарисчи! Предложенный вот тем-то редиской алгоритм плох вот тем и этим, и так делать не стоит".. А то выглядит это примерно так:

- Вот ты написал книгу. А ты знаешь с какой стороны ее правильно открывать?
- ???
- Справа- налево..
- Спасибо, КЭП, что б я без тебя делал?

Выглядит как-то не очень, не находите?
0
07.11.2018, 01:19
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2018, 01:19

Перестановки Рекурсия.
подскажите, пожалуйста, в чем ошибка)) #include &lt;stdio.h&gt; #include &lt;malloc.h&gt; void...

Рекурсия: напечатать всевозможные перестановки заданных чисел
Тему рекурсия понимаю понимаю, а вот сделать это задание вообще не получается:( : Дано n различных...

Вычисление по формуле. X - сумма всех элементов массива; Y - произведение положительных элементов массива
Составить программу для вычисления по формуле X - сумма всех элементов массива; Y -...


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

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

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