Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / перебор комбинаций m по 2, m по 3, ...., m по m / 6 сообщений из 6, страница 1 из 1
15.03.2006, 15:13
    #33602644
V17
V17
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
перебор комбинаций m по 2, m по 3, ...., m по m
Может кто подскажет алгоритм перебора всех комбинаций по 2, по 3 , ... по N.
N по 2 - это два цикла (2-вложенный).
Код: plaintext
1.
2.
3.
for i= 1  to N- 1 
  for j=i+ 1  to N
  Next j
Next i
N по 3 - соответственно 3 цикла.
...
Но как сделать N по N (и вообще все комбинации по k , где k = 2, ..., N) ?
...
Рейтинг: 0 / 0
15.03.2006, 17:57
    #33603310
madgol
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
перебор комбинаций m по 2, m по 3, ...., m по m
Рекурсия
...
Рейтинг: 0 / 0
15.03.2006, 23:14
    #33603753
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
перебор комбинаций m по 2, m по 3, ...., m по m
madgolРекурсия
Я бы не советовал. А если точнее, для алгоритмических языков крайне не советовал бы для чего-то серьезнее практикума в школе.

V17 Может кто подскажет алгоритм перебора всех комбинаций по 2, по 3 , ... по N. ....... Но как сделать N по N (и вообще все комбинации по k , где k = 2, ..., N) ?
Назову два стандартных подхода. Во-первых, в ряде случаев легко можно построить отображение требуемого множества на подмножество множества натуральных чисел. Например, если нужно перебрать все возможные сочетания N чисел (или N любых элементов), это то же самое, что пройти цикл от 0 до 2^N-1, рассматривая переменную цикла как набор из N битовых флагов. Другой подход - определить понятия "текущее состояние" и "переход к следующему состоянию". Например, если требуется перебрать все сочетания из N по K, достаточно сделать массив из K элементов, инициированных 1, 2, 3, ... K и сделать код перехода к следующему состоянию наподобие прибавления единицы "столбиком": увеличиваем последнее значение, если оно стало больше N, увеличиваем предпоследнее, а последнее сбрасываем в "предпоследнее плюс один" итп.
...
Рейтинг: 0 / 0
16.03.2006, 13:21
    #33605151
V17
V17
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
перебор комбинаций m по 2, m по 3, ...., m по m
Первый подход абсолютно верен!
Второй подход - это то же что описал я - лишь одина группа вложенных циклов из N групп. Вопрос был как организовать N групп циклов - ведь я не могу динамически в проге создавать вложенность из N циклов.

Впрочем задача уже решена, т.к. хватило групп 7 циклов (написал их последовательно - вначале 1, потом 2 вложенных цикла, потом 3, ... 7 вложенных циклов). Дальше по задаче смысла нет..
...
Рейтинг: 0 / 0
16.03.2006, 14:08
    #33605372
AL_KIR
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
перебор комбинаций m по 2, m по 3, ...., m по m
V17...- ведь я не могу динамически в проге создавать вложенность из N циклов...

-- вам ответили -- рекурсия, используется для перебора иерархических (древовидных) данных,

но для вашего случая скорее подойдет описанный выше softwarer
способ
...
Рейтинг: 0 / 0
16.03.2006, 19:11
    #33606452
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
перебор комбинаций m по 2, m по 3, ...., m по m
V17Первый подход абсолютно верен!
Спасибо на добром слове.

V17Второй подход - это то же что описал я
Нет, не то же.

V17Впрочем задача уже решена, т.к. хватило групп 7 циклов
В хорошей книге Йодана в приложениях давалась подобная задача.. и был комментарий, что некоторые из программистов решали ее с помощью 48 вложенных циклов.
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / перебор комбинаций m по 2, m по 3, ...., m по m / 6 сообщений из 6, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]