Форум программистов, компьютерный форум, киберфорум
Free Pascal
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.73/11: Рейтинг темы: голосов - 11, средняя оценка - 4.73
-68 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 724

Получить все перестановки натуральных чисел от 1 до N

07.01.2023, 17:08. Показов 2790. Ответов 34
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Даны натуральные числа от 1 до N (они выглядят так: 1 2 3 4 ... N) Надо получить все возможные их перестановки.

Самостоятельно до алгоритма этой программы я бы за 100 лет жизни не додумался. Я прибегнул к помощи теоретической части книги Окулова, которая идет в комплекте с задачником. Там код решения этой задачи приведен в главе про рекурсии. Но разобраться с его работой самостоятельно для меня сложновато. Пожалуйста, объясните принцип работы алгоритма.

Или, возможно, приведите свой код, более простой, и объясните.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
07.01.2023, 17:08
Ответы с готовыми решениями:

Дано n различных натуральных чисел. Напечатать все перестановки этих чисел
Дано n различных натуральных чисел. Напечатать все перестановки этих чисел. Сделать с помощью рекурсивной функции

Дано n различных натуральных чисел. Напечатать все перестановки этих чисел
Дано n различных натуральных чисел (например n=5). Напечатать все перестановки этих чисел. питон 2.7 , базовый пакет есть код...

Дано n натуральных чисел. Определить все возможные перестановки этих чисел
дано n натуральных чисел. определить все возможные перестановки этих чисел C#

34
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7818 / 4637 / 2837
Регистрация: 22.11.2013
Сообщений: 13,159
Записей в блоге: 1
08.01.2023, 18:27
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от Elmar_Velihanov Посмотреть сообщение
Только вот не является ли использование оператора Exit внутри тела функции дурным тоном, подобно использованию оператора Goto?
Перепишите без Exit, в коде выше это тривиально.

Цитата Сообщение от Elmar_Velihanov Посмотреть сообщение
объяснили (расписали) суть алгоритма
В процессе переписывания заодно и разберетесь.

Пока мне непонятно, что вам непонятно. Поясните?
0
 Аватар для Sun Serega
2355 / 1458 / 526
Регистрация: 07.04.2017
Сообщений: 4,798
08.01.2023, 18:28
yield:
http://pascalabc.net/downloads... uences.pdf
Конкретно сравнивать все отличия никто не будет, но в корне этого же сайта есть литература с которой можно было бы и начинать...
0
-68 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 724
08.01.2023, 18:36  [ТС]
Цитата Сообщение от bormant Посмотреть сообщение
Пока мне непонятно, что вам непонятно. Поясните?
Уточните, пожалуйста, в вашем варианте алгоритмов рекурсия нигде не используется?
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7818 / 4637 / 2837
Регистрация: 22.11.2013
Сообщений: 13,159
Записей в блоге: 1
08.01.2023, 18:47
Pascal
17
18
19
  NextPermt:=False;                                           { допустим, следующей перестановки нет }
  i:=High(v)-1; while (i>=0) and (v[i]>=v[i+1]) do Dec(i);  { с конца ищем элемент меньше следующего }
  if i<0 then Exit;                                  { такого нет => последняя перестановка, выходим }
Pascal
20
21
22
23
  k:=High(v); while v[i]>=v[k] do Dec(k);   { с конца ищем k-й элемент, меньший i-го }
  Swap(v[i],v[k]);                          { меняем его с i-м }
  Reverse(v,i+1,High(v));                   { развернём элементы от i+1 до конца }
  NextPermt:=True;                          { есть перестановка }
Добавлено через 1 минуту
Цитата Сообщение от Elmar_Velihanov Посмотреть сообщение
рекурсия нигде не используется?
Если сможете найти вызов процедуры/функции из самой себя -- используется.
Если не смогли, то нет.
Доверьтесь себе.
0
-68 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 724
08.01.2023, 18:52  [ТС]
Цитата Сообщение от bormant Посмотреть сообщение
Если сможете найти вызов процедуры/функции из самой себя -- используется.
Если не смогли, то нет.
Доверьтесь себе.
__________________
Вы можете в таком же стиле откомментировать весь остальной кода алгоритма, который вы представили? Это было бы неплохим объяснением.
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7818 / 4637 / 2837
Регистрация: 22.11.2013
Сообщений: 13,159
Записей в блоге: 1
08.01.2023, 20:31
NextPermt -- следующая перестановка -- это и есть весь алгоритм. Берет текущую перестановку и по ней получает следующую в том же самом массиве. Если перестановка получена, возвращает True, иначе -- False.
Хотя нет, вру, инициализацию начального состояния возрастающими значениями (строка 37), пожалуй, можно тоже считать его частью.
Теперь, вроде, всё.

Добавлено через 1 час 33 минуты
Если вдруг еще и комбинации нужны:
Pascal
1
2
3
4
5
6
7
8
9
function NextCombination(var v: array of Integer; n: Integer): Boolean;
var i, k: Integer;
begin
  NextCombination:=False;
  k:=High(v); while v[k]=n+k-High(v) do Dec(k);
  if k<0 then Exit;
  Inc(v[k]); for i:=k+1 to High(v) do v[i]:=v[k]+i-k;
  NextCombination:=True;
end;
Pascal
1
2
3
4
const a: array [0..2] of Integer = (1, 2, 3);
begin
  repeat vWrite(a) until not NextCombination(a,5);
end.
Это комбинации из n по Length(v).
1
-68 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 724
09.01.2023, 11:50  [ТС]
Я и не знал, что в Паскале массив тоже может быть константой.
0
-68 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 724
14.01.2023, 19:06  [ТС]
bormant, приведенный вами алгоритм генерации перестановок не работает на практике. Пожалуйста, откорректируйте его.
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7818 / 4637 / 2837
Регистрация: 22.11.2013
Сообщений: 13,159
Записей в блоге: 1
14.01.2023, 19:21
Elmar_Velihanov,
на моей практике отлично работает. Поэтому не могу ничего откорректировать, пока не укажете на конкретную проблему.

Добавлено через 7 минут
Например, вот сгенерированные перестановки из 2, 3, 4 элементов:
Code
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
 1 2
 2 1
 
 1 2 3
 1 3 2
 2 1 3
 2 3 1
 3 1 2
 3 2 1
 
 1 2 3 4
 1 2 4 3
 1 3 2 4
 1 3 4 2
 1 4 2 3
 1 4 3 2
 2 1 3 4
 2 1 4 3
 2 3 1 4
 2 3 4 1
 2 4 1 3
 2 4 3 1
 3 1 2 4
 3 1 4 2
 3 2 1 4
 3 2 4 1
 3 4 1 2
 3 4 2 1
 4 1 2 3
 4 1 3 2
 4 2 1 3
 4 2 3 1
 4 3 1 2
 4 3 2 1
Укажите на ошибку, я не вижу.
1
-68 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 724
19.01.2023, 11:48  [ТС]
Цитата Сообщение от bormant Посмотреть сообщение
NextPermt:=False;
  i:=High(v)-1; while (i>=0) and (v[i]>=v[i+1]) do Dec(i);
  if i<0 then Exit;
При первом вызове данной функции она на входе получает массив, упорядоченный по возрастанию, то есть, если N = верхняя грань одномерного массива, то v[N-1]<=v[N] Как же тогда при первой итерации условие этого цикла может стать истинным? Цикл не выполнится ни один раз.
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7818 / 4637 / 2837
Регистрация: 22.11.2013
Сообщений: 13,159
Записей в блоге: 1
19.01.2023, 12:45
Elmar_Velihanov,
1, 2, 3, 4, 5
При первом обращении цикл не выполнится ни разу, так как уже (4>=5) = False. => будет сгенерирована новая перестановка.
А вот после последней перестановки будет
5, 4, 3, 2, 1
цикл while добежит до начала и функция вернёт False.

Повнимательнее.
0
-68 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 724
21.01.2023, 20:00  [ТС]
bormant, я взял ваш код, перенес в свою среду PascalABC.NET и отредактировал так, чтобы он был максимально близким к классическому Паскалю. Давайте я здесь размещу свой вариант кода, а вы укажете на ошибки в нем и откорректируете. Хорошо?
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7818 / 4637 / 2837
Регистрация: 22.11.2013
Сообщений: 13,159
Записей в блоге: 1
21.01.2023, 20:54
Elmar_Velihanov,
этот код был на классическом Паскале.
Можете делать с ним все, что вздумается.
0
-68 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 724
22.01.2023, 11:47  [ТС]
bormant, вы можете привести полный текст программы под ключ, чтобы можно было перенести в редактор без изменений?
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7818 / 4637 / 2837
Регистрация: 22.11.2013
Сообщений: 13,159
Записей в блоге: 1
22.01.2023, 14:14
Цитата Сообщение от Elmar_Velihanov Посмотреть сообщение
можете привести полный текст программы под ключ
... вам не завернуть?
Могу, но не буду, не люблю повторяться.
В этой теме уже есть от меня код "под ключ" для
1) перестановок,
2) комбинаций.

От страховки "угадал все буквы, но не смог прочитать всё слово" даже Поле чудес отказалось, кто я такой, чтобы спорить с трендами.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
22.01.2023, 14:14
Помогаю со студенческими работами здесь

Дано n различных натуральных чисел. Напечатать все перестановки этих чисел
Дано n различных натуральных чисел. Напечатать все перестановки этих чисел

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

Дано n различных натуральных чисел. Напечатать все перестановки этих чисел
Дано n различных натуральных чисел. Напечатать все перестановки этих чисел.

Рекурсия: дано n различных натуральных чисел (n = 5). Напечатать все перестановки этих чисел
Дано n различных натуральных чисел (n = 5). Напечатать все перестановки этих чисел. Очень нужна помощь

Рекурсия: вывести все перестановки натуральных чисел от 1 до n
Доброго дня/ночи HELP ME! Заранее благодарю)) Язык исполнения - АССЕМБЛЕР Опишите рекурсивную функцию и с помощью этой функции...


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

Или воспользуйтесь поиском по форуму:
35
Ответ Создать тему
Новые блоги и статьи
19. здоровье, усталость и психотип работника влияют на производительность предприятия, и наоборот, производительность на здоровье, усталось и психотип
anaschu 28.05.2026
Дискретно-событийная модель рабочего коллектива на AnyLogic: здоровье, выгорание, психотипы и микростимуляция Привет, коллеги. Хочу поделиться итогами нескольких недель работы над симуляционной. . .
"Прокси" для последовательного порта
Eddy_Em 28.05.2026
Эту штуку написал я достаточно давно. Но сейчас вот понадобилось настроить датчик грозы, но при этом не отключать его от "метеодемона". Соответственно, надо запустить этот "прокси": метеодемон будет. . .
Рефакторинг программы уравнивания.
Massaraksh7 26.05.2026
Пример по предыдущей записи в блоге. Но, надо заметить, что, во-первых, там оптимизация не только математики, но и работы с базой данных, и с графами, а во-вторых, это ещё не всё.
Использование TThread в Lazarus для математических вычислений.
Massaraksh7 25.05.2026
Производя рефакторинг своих программ на предмет ускорения их работы, обратил внимание на такой аспект, как сокращение времени матвычислений. Дело в том, что приходится работать с большими матрицами. . .
Модель здравосохранения 18. Чем здоровее работник, тем быстрее выгорает
anaschu 24.05.2026
Имитационная модель корпоративного здравоохранения: что показывает математика Сегодня в модели рабочего коллектива на AnyLogic появились три новые механики — выгорание через накопленную усталость,. . .
Модель здравосохранения 17. Планы на выгорание
anaschu 23.05.2026
Вот конкретная схема реализации: В классе Работник добавить: накопленнаяУсталость — растёт каждый час работы, снижается в перерывы и болезни коэффициентПрезентеизма — снижает продуктивность. . .
Изменение цветов в палитре gif файла aka фавикона
russiannick 23.05.2026
Изменение цветов в палитре gif файла, юзаемого как фавиконка в составе html-файла, помещенная в base64, средствами нативного Java Script, навеянное сном в майский день. Для работы необходим браузер,. . .
Модель здравосохранения 16. Слишком хорошие и здоровые сотрудники уходят, недовольные зарплатой
anaschu 23.05.2026
Отладка увольнений и настройка производительности Сегодня во второй половине дня разобрались с механикой увольнений и настроили коэффициент сложности заданий. Вот что было сделано. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru