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

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

07.01.2023, 17:08. Показов 2870. Ответов 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
2356 / 1459 / 526
Регистрация: 07.04.2017
Сообщений: 4,798
08.01.2023, 18:28
yield:
http://pascalabc.net/downloads... uences.pdf
Конкретно сравнивать все отличия никто не будет, но в корне этого же сайта есть литература с которой можно было бы и начинать...
0
-121 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 728
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
-121 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 728
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
-121 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 728
09.01.2023, 11:50  [ТС]
Я и не знал, что в Паскале массив тоже может быть константой.
0
-121 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 728
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
-121 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 728
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
-121 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 728
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
-121 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 728
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
Ответ Создать тему
Новые блоги и статьи
Мир по моей воле
kumehtar 07.08.2026
Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор
Maks 05.08.2026
Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .
У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35".
kumehtar 04.08.2026
С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники).
Hrethgir 04.08.2026
Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .
Термопринтер QR701
Argus19 03.08.2026
Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .
Создание формы заимствованного документа
Maks 03.08.2026
Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .
Задача предоставления скидок покупателям
Maks 03.08.2026
Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .
Почему SEO не начинается с ключевых слов: что проверить до написания текстов
Neotwalker 01.08.2026
Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru