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

    Если это счётчик в массиве, то вызов с отрицательным индексом (дошли до первого элемента (индекс 0), увеличили его до предела, попытались вызвать функцию для более левого элемента)
      Еще хотел уточнить такой момент: на каком-то форуме тоже была тема про размещения и там "кинули" готовый код спрашиваемому и в этом коде была рекурсия + какая-то вспомогательная функция, которая вызывалась из рекурсивной, но сама она была простой функцией.

      Поэтому хочу сразу понять, можно ли написать ОДНУ рекурсивную функцию, которая будет размещать как надо или это невозможно?
        >ожно ли написать ОДНУ рекурсивную функцию

        А зачем больше рекурсивных функций ???
          Цитата MBo @
          А зачем больше рекурсивных функций ???

          так я и интересуюсь, т к не знаю :wall: просто в том коде была какая-то вспомогательная функция! :yes:

          Цитата MBo @
          Если это счётчик в массиве, то вызов с отрицательным индексом (дошли до первого элемента (индекс 0), увеличили его до предела, попытались вызвать функцию для более левого элемента)

          так, понял вроде

          нужно попытаться составить заголовок рекурсивной функции (все параметры прокомментированы):
          ExpandedWrap disabled
            //----------------------------------------------------
            // Получение размещений с повторениями
            // pv - последовательность размещаемых объектов/цифр
            // pi - индекс переставляемого объекта/цифры (отсчет по правилам массивов С++)
            // pmaxValue - максимальное значение, принимаемое объектом/цифрой
            // pID - номер текущей последовательности (нужно для вывода на экран)
            //----------------------------------------------------
            void Deployment(int *pv, int pi, int pmaxValue, int pID)
            {
            }
            //----------------------------------------------------


          из функции main() первый раз вызывается так:
          ExpandedWrap disabled
            Deployment(v, count - 1, maxValue, ID);


          тут все норм. или что-то не учтено, что пригодится?
            В итоге чертовщина какая-то получилась, т к до конца еще не разобрался с этим алгоритмом:
            ExpandedWrap disabled
              //----------------------------------------------------
              // Получение размещений с повторениями
              // pv - последовательность размещаемых объектов/цифр
              // pi - индекс переставляемого объекта/цифры (отсчет по правилам массивов С++)
              // pmaxValue - максимальное значение, принимаемое объектом/цифрой
              // pID - номер текущей последовательности (нужно для вывода на экран)
              // pcount - количество объектов/цифр в последовательности
              //----------------------------------------------------
              void Deployment(int *pv, int pi, int pmaxValue, int pID, int pcount)
              {
                  if(pi >= 0) // когда pi = -1, то процедура закончена!
                  {
                      PrintSequence(pv, pcount, pID);
                      if(pv[pi] < pmaxValue)
                      {
                          pv[pi]++;
                          Deployment(pv, pi, pmaxValue, ++pID, pcount);
                      }
                      else
                      {
                          pv[pi - 1]++;
                          pv[pi] = 1;
                          Deployment(pv, pi - 1, pmaxValue, ++pID, pcount);
                      }
                  }
              }
              //----------------------------------------------------


            Есть следующие вопросы:
            ExpandedWrap disabled
              1. Если рекурсия на спуске, то получаем в возрастающем лексикографическом порядке, а, если на возврате, то в убывающем, да?
              2. В теле рекурсивной функции не должно быть никаких циклов? Вообще рек.функция должна выполнять действия: либо увеличение на 1 нужной цифры,
              либо переход на следующий разряд, стоящий слева от текущего и увеличение его на 1, и выставление какого-то разряда в 1?
              3. Есть что-то общее в этой рек.функции с рек.функциями, которые используют в сильноветвящихся деревьях?


            Допустим, дано 4 объекта, которые принимают значения {1, 2}
            1: 1111
            2: 1112
            3: 1121
            4: 1122
            5: 1211
            ...
            Вот мне абсолютно непонятно по цепочке 1211, на каких копиях рекурсивных функциях будут выставлены 1 и 1 в двух правых цифрах.

            P.S. Бинарные деревья поиска и то были более понятными...
              Если неприменно нужна рекурсия, вот:

              ExpandedWrap disabled
                Const N As Long = 3, M As Long = 2
                Dim Ar(N - 1) As Long
                 
                Sub Main()
                  Dim i As Long
                 
                  For i = 0 To N - 1
                    Ar(i) = 1
                  Next i
                  NextVal
                End Sub
                 
                Sub NextVal()
                  Dim i As Long
                 
                  PrintAr
                  i = N - 1
                  While i >= 0
                    Ar(i) = Ar(i) + 1
                    If Ar(i) > M Then
                      Ar(i) = 1
                      i = i - 1
                    Else
                      NextVal
                      Exit Sub
                    End If
                  Wend
                End Sub
                 
                Sub PrintAr()
                  Dim i As Long
                 
                  For i = 0 To N - 1
                    Debug.Print Ar(i);
                  Next i
                  Debug.Print
                End Sub
                ExpandedWrap disabled
                  sub recurse(currentvariant, currentlevel)
                  if currentlevel = 0 then
                      print currentvariant
                  else
                      for i = 1 to statescount
                          call recurse(currentvariant & states(i), currentlevel - 1)
                      next i
                  end if
                  end sub ' recurse
                   
                  public const statescount = someinteger
                  public states(1 to statescount) as sometype
                   
                  sub Main
                  for i = 1 to statescount
                      states(i) = somevalue
                  next i
                  call recurse(empty, levelsneeded)
                  end sub ' Main
                  for i in 1 to C
                  GENERATE_Random_Pemutation


                  вот весь код
                  С = максимальное количество пермутаций * логарифм от максимального количества пермутаций умножить на 10

                  Алгоритм вероятностный
                  0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                  0 пользователей:


                  Рейтинг@Mail.ru
                  [ Script execution time: 0,0293 ]   [ 16 queries used ]   [ Generated: 29.03.24, 07:53 GMT ]