Восстановление исходного массива - Фриланс

кот Бегемот · 18.11.2010, 22:00

Бесплатно эту задачу никто решать не хочет. Или не может. Что ж, я готов заплатить просто потому, что сам пока не могу найти алгоритм.
Итак:

Дан массив из неповторяющихся N натуральных чисел от 1 до N, например, для N=4
a[1]=3 a[2]=4 a[3]=2 a[4]=1.
По значениям элементов этого массива, используя их и как индексы, и как значения, несложно построить массив a[a[i]]:
a[a[1]]=2 a[a[2]]=1 a[a[3]]=4 a[a[4]]=3
это просто. труднее наоборот.

Итак, задача:
по имеющемуся массиву a[a[i]] найти любой вариант исходного массива a[i]
(ну, или сообщить, что такого варианта нет).

PS. Я пробовал решить эту задачу полным перебором перестановок. Решается. Но, только для небольших значений N. В условии N<=20000. Ну, мне и 1000 будет вполне. Может, рекурсивная процедура спасёт?

Условия работы: выполненный exe-шник и вашу цену на мыло zv983@yandex.ru. При согласии сторон, оплата гарантирована на мобилу или другими способами.

frilans · 18.11.2010, 22:40

Выложи код который на малых числах работает....

кот Бегемот · 18.11.2010, 22:50

а зачем он тебе?
алгоритм такой: генератор перестановок перебирает все возможные перестановки чисел и каждую перестановку заносит в массив a[N], массив проверяется на соответствие a[a[i]]. Всё.
PS. Или тебя интересует сам генератор перестановок?

Black Fregat · 18.11.2010, 23:44

Нужно обязательно ВСЕ варианты? Для некоторых видов массивов их может быть ОЧЕНЬ много..

frilans · 18.11.2010, 23:50

Исходный код просил по той причине чтобы посмотреть в итоге у тебя выводился один вариант ответа или несколько т.к. как я понимаю данную задачку вариаций может быть более чем одна

кот Бегемот · 19.11.2010, 00:26

или я писать не умею, или вы читать не умеете:
цитата
найти любой вариант исходного массива

то есть мне нужен только 1 какой-нибудь вариант

ps хотя, как я убедился, с возрастанием N количество вариантов стремится к 1

mss · 19.11.2010, 10:32

icq 169527143

Tronix · 19.11.2010, 12:32

кот Бегемот,
Если кто-нибудь сделает, отпишитесь как решили - перебором, или все-таки нашли некий алгоритм? Заинтересовала просто задачка...

кот Бегемот · 19.11.2010, 13:18

Тема неактуальна.

ps Tronix, отпишусь

Serge_Bliznykov · 19.11.2010, 14:45

_кот Бегемот_, меня тоже заинтересовала задача... Правда, к решению приступить не успел, однако, присоединяюсь к мнению _Tronix_ - сообщите, пожалуйста, каким образом задача решена.

Удачи.

18.11.2010, 22:00	#1
кот Бегемот Новичок Джуниор Регистрация: 15.11.2010 Сообщений: 1	Восстановление исходного массива Бесплатно эту задачу никто решать не хочет. Или не может. Что ж, я готов заплатить просто потому, что сам пока не могу найти алгоритм. Итак: Дан массив из неповторяющихся N натуральных чисел от 1 до N, например, для N=4 a[1]=3 a[2]=4 a[3]=2 a[4]=1. По значениям элементов этого массива, используя их и как индексы, и как значения, несложно построить массив a[a[i]]: a[a[1]]=2 a[a[2]]=1 a[a[3]]=4 a[a[4]]=3 это просто. труднее наоборот. Итак, задача: по имеющемуся массиву a[a[i]] найти любой вариант исходного массива a[i] (ну, или сообщить, что такого варианта нет). PS. Я пробовал решить эту задачу полным перебором перестановок. Решается. Но, только для небольших значений N. В условии N<=20000. Ну, мне и 1000 будет вполне. Может, рекурсивная процедура спасёт? Условия работы: выполненный exe-шник и вашу цену на мыло zv983@yandex.ru. При согласии сторон, оплата гарантирована на мобилу или другими способами. Последний раз редактировалось кот Бегемот; 18.11.2010 в 22:11.

18.11.2010, 22:50	#3
кот Бегемот Новичок Джуниор Регистрация: 15.11.2010 Сообщений: 1	а зачем он тебе? алгоритм такой: генератор перестановок перебирает все возможные перестановки чисел и каждую перестановку заносит в массив a[N], массив проверяется на соответствие a[a[i]]. Всё. PS. Или тебя интересует сам генератор перестановок? Последний раз редактировалось кот Бегемот; 18.11.2010 в 22:53.

19.11.2010, 00:26	#6
кот Бегемот Новичок Джуниор Регистрация: 15.11.2010 Сообщений: 1	или я писать не умею, или вы читать не умеете: цитата найти любой вариант исходного массива то есть мне нужен только 1 какой-нибудь вариант ps хотя, как я убедился, с возрастанием N количество вариантов стремится к 1 Последний раз редактировалось кот Бегемот; 19.11.2010 в 00:35.

19.11.2010, 12:32	#8
Tronix Форумчанин Регистрация: 15.06.2010 Сообщений: 740	кот Бегемот, Если кто-нибудь сделает, отпишитесь как решили - перебором, или все-таки нашли некий алгоритм? Заинтересовала просто задачка... Чтобы понять рекурсию, сперва нужно понять рекурсию.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Анализ исходного кода	heart	Безопасность, Шифрование	7	31.12.2009 08:26
Восстановление исходного кода из .exe файла.	Mutagena	Помощь студентам	3	06.12.2009 15:43
из четных чисел исходного массива сформировать новый массив	sanya006	Помощь студентам	3	11.11.2009 19:14
Поменять местами правую и левую часть исходного массива	антон2	Паскаль, Turbo Pascal, PascalABC.NET	4	07.04.2009 17:36
Два одномерных массива,представляющие собой средние значения строк и столбцов исходного. Делфи 3	<DimonM@n>	Помощь студентам	2	23.11.2008 21:51

18.11.2010, 22:40	#2
frilans Новичок Джуниор Регистрация: 15.06.2010 Сообщений: 0	Выложи код который на малых числах работает....

18.11.2010, 23:44	#4
Black Fregat Программист Участник клуба Регистрация: 23.06.2009 Сообщений: 1,772	Нужно обязательно ВСЕ варианты? Для некоторых видов массивов их может быть ОЧЕНЬ много..

18.11.2010, 23:50	#5
frilans Новичок Джуниор Регистрация: 15.06.2010 Сообщений: 0	Исходный код просил по той причине чтобы посмотреть в итоге у тебя выводился один вариант ответа или несколько т.к. как я понимаю данную задачку вариаций может быть более чем одна

19.11.2010, 10:32	#7
mss Заблокирован Регистрация: 27.05.2010 Сообщений: 1,099	icq 169527143

19.11.2010, 13:18	#9
кот Бегемот Новичок Джуниор Регистрация: 15.11.2010 Сообщений: 1	Тема неактуальна. ps Tronix, отпишусь

19.11.2010, 14:45	#10
Serge_Bliznykov Старожил Регистрация: 09.01.2008 Сообщений: 26,229	_кот Бегемот_, меня тоже заинтересовала задача... Правда, к решению приступить не успел, однако, присоединяюсь к мнению _Tronix_ - сообщите, пожалуйста, каким образом задача решена. Удачи.