На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: shadeofgray, JoeUser
  
> Алгоритм обхода
    Всем доброго,

    не могу описать алгоритм математически, попробую описать словами и примером. Надо обойти все варианты определенным образом, на выходе надо иметь список всех вариантов. Язык реализации не имеет значения.
    Например есть 4(может быть любым) группы, в каждой группе может быть до 8-и элементов(может быть и больше, но не меньше кол-ва групп), 1-есть, 0-нет. В двух группах не может быть больше одного и того-же элемента как и в каждой группе всегда есть по крайней мере один элемент. В этом примере перебор вариантов будет следующим:

    1.
    00011111
    00100000
    01000000
    10000000
    2.
    00001111
    00110000
    01000000
    10000000
    3.
    00001111
    00010000
    01100000
    10000000
    4.
    00001111
    00010000
    00100000
    11000000
    5.
    00000111
    00111000
    01000000
    10000000
    6.
    00000111
    00011000
    01100000
    10000000
    7.
    00000111
    00011000
    00100000
    11000000
    8.
    00000111
    00001000
    01110000
    10000000
    9.
    00000111
    00001000
    00110000
    11000000
    10.
    00000111
    00001000
    00010000
    11100000
    11.
    00000011
    00111100
    01000000
    10000000
    ...
    Сообщение отредактировано: fenix710 -
      Сложная постановка задачи. Предлагаю переформулировать - нужно собрать число n из k слагаемых. Наборы, отличающиеся порядком слагаемых, считаются разными. В твоём случае n = 8, k = 4, и твоим вариантам соответствуют такие наборы:
      (5, 1, 1, 1), (4, 2, 1, 1), (4, 1, 2, 1) и т.д. По такому набору табличка получается естественным образом. Сами же наборы проще всего генерировать рекурсивно, задавая очередное число в нём в 1, 2 и т.д пока это имеет смысл, т.е. как-то так:
      (1, (список всех наборов с суммой n - 1 и длиной k - 1)), (2, (список всех наборов с суммой n - 2 и длиной k - 1)) ...
      Подпись была включена в связи с окончанием срока наказания
        Данную задачу можно сформулировать попроще: перебрать все варианты распределения М шаров в N корзин .
        В примере ТСа М=4, N=4.
        Сообщение отредактировано: MIF -
        Мои религиозные убеждения не позволяют мне комментировать код.
        Моё мировоззренье таково: в программе комментария ни одного!
          Цитата OpenGL @
          Сами же наборы проще всего генерировать рекурсивно

          Или даже не рекурсивно, а послойно. Пусть a[i, j] это все наборы с суммой i длины j. Тогда a[i, 1] = {i}, и циклом наподобие
          ExpandedWrap disabled
            for j in 2..k:
               for i in 1..n:
                  # заполняешь a[i, j]
          Подпись была включена в связи с окончанием срока наказания
            ExpandedWrap disabled
              Пусть Б от 1 до 1<<К:
               Пусть Л от 1 до 1<<К:  
                Пусть М от 1 до 1<<К:  
                 Пусть Н от 1 до 1<<К:
                  Если (М & Н=0) &&
                       (Л & М=0) && (Л & Н=0) &&    
                       (Б & Л=0) && (Б & М=0) && (Б & Н=0)
                         то выводим(Б, Л, М, Н);
            Сообщение отредактировано: Pavia -
            Правильный обед должен состоять из 5 блюд приготовленных из 33 ингредиентов.
            1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
            0 пользователей:


            Рейтинг@Mail.ru
            [ Script Execution time: 0,0756 ]   [ 14 queries used ]   [ Generated: 17.11.19, 00:18 GMT ]