Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 14.07.2010, 12:46
Новичок

Отправить личное сообщение для PackBear Посмотреть профиль Найти все сообщения от PackBear
 
Регистрация: 14.07.2010
Сообщений: 4

Усовершенствованный перебор
День добрый. Мне хотелось бы разобраться со следущей задачкой.

Имеется массив X от 1 до 4. в каждом элементе может быть записано число от 1 до 7. То есть количество переборных комбинаций 7^4=2401. Так же есть некий массив размером Y от 1 до 4, с неким набором готовых значений. (к примеру Y(4,1,6,3)). Как найти все значения массива X, удовлетворяющие условию: Различия наборов массивов должно равняться некому K.
Пример:
если K =1 (знаком "&" - рассматривать любое число от 1 до 7, кроме указанного в массиве Y)
Y (4,1,6,3)
значения массива X подходящие под условие
Х (4,1,6,&) (6 чисел, то есть кроме 3)
Х (4,1,&,3) (6 чисел, то есть кроме 6)
Х (4,&,6,3) (6 чисел, то есть кроме 1)
Х (&,1,6,3) (6 чисел, то есть кроме 6)
всего 24 таких значений

если K =2
Y (4,1,6,3)
значения массива X подходящие под условие
Х (4,1,&,&) (36 чисел, 6*6, перебор наборо 3го разряда и 4го, кроме цифры 6 в 3ем и 3 в 4ом)
Х (4,&,6,&) (36 чисел, аналогично)
Х (&,1,6,&) (36 чисел, аналогично)
Х (4,&,&,3) (36 чисел, аналогично)
Х (&,1,&,3) (36 чисел, аналогично)
Х (&,&,6,3) (36 чисел, аналогично)
всего 36*6=216 таких значений
и так далее

спешу уверить, что эта задача путем полного перебора мной решена (опять же благодаря теоретическому материалу сайта, за что огромное отдельное спасибо!!!!) я пробовал "прикрутить" алгоритм перебора с отходом назад, у меня не получилось .
Буду очень признателен, если подскажите как решить эту задачку
  #2  
Старый 15.07.2010, 14:09
гость

 
Сообщений: n/a

Ответ
Можно условие сформулировать в более строгой форме. Непонятно, что требуется подать на выход.
  #3  
Старый 15.07.2010, 15:48
Новичок

Отправить личное сообщение для PackBear Посмотреть профиль Найти все сообщения от PackBear
 
Регистрация: 14.07.2010
Сообщений: 4

Постараюсь на сколько это возможно. Есть массив Y (в котором забит строгий набор цифр) в массиве X перебираются возможные варианты наборов цифр. Далее находит насходжение массивов Х и Y, которое определеятся как "расхождение=количество не совпадающих (различных) цифр в соответствующих разрядах". если "расхождение" не превышает(или равно) заданному К, то это вариант массива Х попадает в коллекцию нужных вариантов.

найти все нужные варианты.

PS если опять что-то не так, подскажите плиз. поправлю!
  #4  
Старый 21.07.2010, 03:15
Пользователь

Отправить личное сообщение для maxal Посмотреть профиль Найти все сообщения от maxal
 
Регистрация: 28.11.2006
Сообщений: 68

Количество искомых массивов равно C(L,K)*(M-1)^K, где L=4 - длина массива, M=7 - вехняя грань элементов массиво.
  #5  
Старый 26.07.2010, 14:26
Новичок

Отправить личное сообщение для PackBear Посмотреть профиль Найти все сообщения от PackBear
 
Регистрация: 14.07.2010
Сообщений: 4

Не спорю. Формула судя по всему верна, за что тоже огромное спасибо!!!
Но вопрос актуален: как получить все значенния массива для соответствующего K?
  #6  
Старый 30.07.2010, 10:13
Новичок

Отправить личное сообщение для deosis Посмотреть профиль Найти все сообщения от deosis
 
Регистрация: 30.07.2010
Сообщений: 8

Т.е. тебе надо найти все вектора отличающиеся от заданного в К позициях.
Для этого достаточно сгенерировать все перестановки из 0 и 1, а потом использовать аналог бинарного счетчика по соответствующим позициям.
В результате получишь все возможные комбинации в виде C(n,k) отсортированных массивов.
При этом если не важен порядок комбинаций, то хранить понадобится только 2 вектора: 1 - для определения позиций, 2 - для бинарного счетчика
  #7  
Старый 30.07.2010, 12:11
Новичок

Отправить личное сообщение для PackBear Посмотреть профиль Найти все сообщения от PackBear
 
Регистрация: 14.07.2010
Сообщений: 4

Спасибо. Буду разбираться!
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Перебор комбинаций слов timugatu Математические алгоритмы (другое) 4 29.11.2009 18:55
Перебор всех возможных вариантов RuZk Реализация, исходники, языки 1 06.05.2009 18:41
Рекурсивный перебор гость Математические алгоритмы (другое) 1 20.07.2008 03:43
(С++)Перебор купюр с повторениями indolent Математические алгоритмы (другое) 24 06.03.2008 20:56
перебор незарегистрированный Математические алгоритмы 1 17.12.2006 21:17