Перебор всех возможных вариантов (рекурсивно)

@lufigan · Регистрация: 07.10.2018

Студворк — интернет-сервис помощи студентам

Не буду вникать в суть программы. Предположим у меня есть архивы с точками, мне нужно выбрать минимальную комбинацию, этих архивов что бы они содержали все точки(0-15).

array1 -> 6 {0 6 8 9 10 12}
array2 -> 3 {1 10 11}
array3 -> 5 {2 4 5 11 14}
array4 -> 4 {3 6 7 13}
array5 -> 10 {2 4 5 6 7 9 10 11 13 14}
array6 -> 6 {2 4 5 11 13 14}
array7 -> 9 {0 3 4 6 9 10 11 12 13}
array8 -> 4 {3 4 7 13}
array9 -> 3 {0 8 12}
array10 -> 8 {0 4 6 9 10 11 12 13}
array11 -> 9 {0 1 4 6 9 10 11 12 13}
array12 ->10 {1 2 4 5 6 9 10 11 13 14}
array13 -> 7 {0 6 8 9 10 12 13}
array14 -> 10 {3 4 5 6 7 9 10 11 12 13}
array15 -> 5 {2 4 5 11 14}

Я полагаю, это нужно сделать при помощи рекурсии, задача выглядит простой, но я не могу придумать как это реализовать в коде, помогите пожалуйста.

@FFPowerMan · 23.11.2018, 14:01

Ничего не понял. В чем суть? Это текстовый файл.

Байт · 23.11.2018, 14:03

lufigan, можно так переформулировать задачу. Есть множество из 15 (для данного примера) элементов. И есть набор его подмножеств (случайно - тоже 15), которые вы называете архивами. Эти подмножества покрывают все множество. Нужно найти минимально покрытие. Так?
Я думаю, тут можно использовать метод ветвей и границ. Рекурсивно или итерационно - это уже дело десятое...

@lufigan · 23.11.2018, 14:08 **[ТС]**

FFPowerMan, нуу, если развернуто то вот.
Задача, в каком селе нужно поставить телевышку что бы покрыть все деревни, на входе дано кол-во чисел и R вышки, и координаты деревень, я смог подсчитать до каких деревень дотягивается вышка(указаный авхив), и теперь нужно найти минимально кол-во деревень для установки вышки. Вот картинка, как это выглядит визуально.

Перебор всех возможных вариантов (рекурсивно)

Príklad vstupu: это ввод и Príklad výstupu: вывод

Новые блоги и статьи Все статьи Все блоги /
Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .
Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .

@lufigan 0 / 0 / 0 Регистрация: 07.10.2018 Сообщений: 34

	Перебор всех возможных вариантов (рекурсивно) 23.11.2018, 13:43. Показов 1849. Ответов 3 Метки нет (Все метки) Не буду вникать в суть программы. Предположим у меня есть архивы с точками, мне нужно выбрать минимальную комбинацию, этих архивов что бы они содержали все точки(0-15). array1 -> 6 {0 6 8 9 10 12} array2 -> 3 {1 10 11} array3 -> 5 {2 4 5 11 14} array4 -> 4 {3 6 7 13} array5 -> 10 {2 4 5 6 7 9 10 11 13 14} array6 -> 6 {2 4 5 11 13 14} array7 -> 9 {0 3 4 6 9 10 11 12 13} array8 -> 4 {3 4 7 13} array9 -> 3 {0 8 12} array10 -> 8 {0 4 6 9 10 11 12 13} array11 -> 9 {0 1 4 6 9 10 11 12 13} array12 ->10 {1 2 4 5 6 9 10 11 13 14} array13 -> 7 {0 6 8 9 10 12 13} array14 -> 10 {3 4 5 6 7 9 10 11 12 13} array15 -> 5 {2 4 5 11 14} Я полагаю, это нужно сделать при помощи рекурсии, задача выглядит простой, но я не могу придумать как это реализовать в коде, помогите пожалуйста. 0

@FFPowerMan 2158 / 1238 / 509 Регистрация: 11.10.2018 Сообщений: 6,280
	23.11.2018, 14:01
	Ничего не понял. В чем суть? Это текстовый файл. 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	23.11.2018, 14:03
	lufigan, можно так переформулировать задачу. Есть множество из 15 (для данного примера) элементов. И есть набор его подмножеств (случайно - тоже 15), которые вы называете архивами. Эти подмножества покрывают все множество. Нужно найти минимально покрытие. Так? Я думаю, тут можно использовать метод ветвей и границ. Рекурсивно или итерационно - это уже дело десятое... 0

@lufigan 0 / 0 / 0 Регистрация: 07.10.2018 Сообщений: 34
	23.11.2018, 14:08 [ТС]
	FFPowerMan, нуу, если развернуто то вот. Задача, в каком селе нужно поставить телевышку что бы покрыть все деревни, на входе дано кол-во чисел и R вышки, и координаты деревень, я смог подсчитать до каких деревень дотягивается вышка(указаный авхив), и теперь нужно найти минимально кол-во деревень для установки вышки. Вот картинка, как это выглядит визуально. Príklad vstupu: это ввод и Príklad výstupu: вывод 0