Вход | Регистрация


Информационные технологии ::

Метки:

переборные алгоритмы

Я
   Nataly
 
22.02.04 - 07:55
Не могу найти нужную информацию перебора N-элементного множества по M-чисел (без повторений).
Подскажите примерный алгоритм, пожалуйста.
 
 
   GrayT
 
1 - 22.02.04 - 08:20
Не совсем понял что надо - наверное еще не проснулся :)
Попробуй тут поискать http://algolist.manual.ru/
   BorisG
2 - 22.02.04 - 08:25
Д. Кнут Искусство программировани ЭВМ Целочисленные алгоритмы.
RFTM однако...
   fellow
 
3 - 22.02.04 - 08:49
Дональд Э. Кнут, "Искусство программирования" третье издание, том 1 "Основные алгоритмы",изд. Вильямс, 2000г, ISBN 5-8459-0080-8. Глава 1, раздел 1.2.5 "Перестановки и факториалы".
   BorisG
4 - 22.02.04 - 09:17
(3) Спасибо, что поправил, писал спросонья, собрал вместе две книжки...
   Nataly
 
5 - 22.02.04 - 09:26
Спасибо всем, уже ищу Д. Кнута.
Может кто процитирует книжку, если не трудно.
   fellow
 
6 - 22.02.04 - 10:12
Эта книга не содержит рецептов решения частных задач, она даёт крепкое математическое основание для программиста. Поэтому, цитировать её смысла мало, нужно прочитать и понять предыдущие разделы и некоторые последующие. Их немного, всего страниц 75 до и 30 после.

За рецептами можно обратиться к англоязычной on-line книге "Numeric Recipies on C", кажется, так. Она мне попадалась лет 5 тому назад, сейчас, увы, на работе осталась. Попробуйте поискать в Нете.
   fellow
 
7 - 22.02.04 - 10:26
Нашёл всё-таки у себя, "Numeric Recipes in C" называется. Но там более другие вещи, Вашей темы нет. Поэтому, попробуйте что-нибудь другое поискать.
   Nataly
 
8 - 22.02.04 - 16:40
На algolist.manual.ru не нашла моего случая. Есть еще советы? А то нетерпится, или буду ждать понедельника - библиотеки, магазины и т. д. Господа профессионалы - а для вас это трудная задача?
   fellow
 
9 - 22.02.04 - 17:02
Извините, Nataly, но не приходилось с этим сталкиваться. Поэтому, кроме общих мест, и сказать нечего.
   Дмитрий
 
10 - 22.02.04 - 23:01
 
  Рекламное место пустует
   Дмитрий
 
11 - 22.02.04 - 23:03
   Nataly
 
12 - 23.02.04 - 06:14
(10 и 11) Спасибо, Дмитрий, примеры хорошие, но мне надо без повторений (например как в лото 5 из 36).
   Дмитрий
 
13 - 23.02.04 - 10:44
(12) Пардон, полусонный был.
Есть предложение сделать M циклов 1..N, 2..N, .... ,M..N
Индексы сортировать и записывать в строку i1_i2_..._im
Полученные строки заносить в одномерный массив в случае,
если их в этом массиве нет.
   Nataly
 
14 - 25.02.04 - 09:09
Ребята, я до сих пор не могу сообразить. Кое-что делаю, но чувствую, что ход мыслей не тот. Поняла, что надо при сочетании по 5 сначала менять 5-й элемент, затем 4-й сдвинуть по индексу на 1 и далее менять 5-й, пока k(5)< N (конечного элемента) и так далее.
Натолкните на мысль пожалуйста.
   Inside
15 - 28.02.04 - 12:30
Итерация в данном случае не сильно поможет :)
M циклов - это просто прикол :))
Хочу глянуть на код с M > 1000 :)
Рекурсия - вот ваш выход, уважаемая Наталья.
Приблизительно так:

Функция ЕстьЗнач(исхзнач,инд)
   Возврат Найти(исхзнач,Строка(инд));
КонецФункции

Функция НайтиЗначение(исхзнач)
   Для инд=0 по 9 Цикл
       Если ЕстьЗнач(исхзнач,инд)<>0 Тогда
           Продолжить;
       Иначе
           Если СтрДлина(исхзнач)=2 Тогда
               Сообщить(исхзнач+Строка(инд));
               Продолжить;
           Иначе
               НайтиЗначение(исхзнач+Строка(инд));
           КонецЕсли;
       КонецЕсли;
   КонецЦикла;
КонецФункции

Процедура Выполнить()
   НайтиЗначение("");
КонецПроцедуры      


Вариант упрощённвый, но представление о задаче должен дать.
   Inside
16 - 28.02.04 - 12:34
Да, маленькие комментарии про непонятные цифры :)
От 0 до 9 - этакое представление множества значений N.
2 - Это (M-1), длина выборки.
Можно было и в явном виде M, ну да ладно :)

Осудите, ежели чего не так.

PS: А Кнута я не читал...
   Inside
17 - 28.02.04 - 12:56
:) А я-то думал это по 1С вопрос, колбашу на встроенном языке :)

Ежели непонятно, могу переписать на выбранном Вами языке...
Короче всего на Лиспе получится :)
   Nataly
 
18 - 28.02.04 - 16:47
(17) Уважаемый Inside, я, конечно поразбираюсь в вашем тексте, но мне нужно на VB6 или псевдокод, если не трудно.
   Inside
 
19 - 28.02.04 - 17:05
Вот Вам, Наталья, на VB, только если надо выводить
результат в определённое место, избавтесь от MsgBox, а то долго нажимать Акей придётся.

Тут Len(str + CStr(i)) = 3 - длина выборки в явном виде.

Function isexists(str, char)
 isexists = InStr(str, char)
End Function

Sub FindExp(str)
 For i = 0 To 9
   If isexists(str, CStr(i)) <> 0 Then
     GoTo 1
   Else
     If Len(str + CStr(i)) = 3 Then
       MsgBox str + CStr(i)
       GoTo 1
     Else
       FindExp (str + CStr(i))
     End If
   End If
1:
 Next i
End Sub

Sub Run()
 FindExp ("")
End Sub


Успехов!
   Inside
 
20 - 28.02.04 - 17:07
Да, не ругайте за ГоуТу пажалста, не знаю как "Продолжить" или "Continue" в VB :)
   Serpent
 
21 - 28.02.04 - 20:09
Представьте задачу таким образом:
M элементов - это цифры числа, М штук. Например, если М=5, то число из 5 цифр состоит.
Теперь надо пперебирать для каждой цифры 1-N значений.
Проверяем при этом, чтобы в цифрах не было одинаковых.
Начинаем с числа 12345...M.
При такой постановке сразу понятно, что M<N, иначе повторения неизбежны.
   Дмитрий
 
22 - 29.02.04 - 02:53
(15) Вы хотите сказать, что трудоемкость алгоритма при рекурсии меньше, чем при М циклах?
   Inside
 
23 - 01.03.04 - 20:33
(22) Дмитрий! Тродоёмкость алгоритма несравнимо меньше. Для обсуждения я предлагаю Вам привести свой вариант кода при М > 1000. В предложенном мною варианте изменится пара строк в числовых значениях.

(21) Не понял смысла поста, честно :)



Список тем форума
Рекламное место пустует   Рекламное место пустует
Кaк может человек ожидaть, что его мольбaм о снисхождении ответит Тот, кто превыше, когдa сaм он откaзывaет в милосердии тем, кто ниже его? Петр Трубецкой
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Ветка сдана в архив. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.
Рекламное место пустует