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

    с линейной рекурсией сложностей не возникло (Паскаль):
    ExpandedWrap disabled
      function IsCheckNumbers(pv: TVector; pi: byte; px: byte): boolean;
      begin
      // вышли за правую границу вектора, не встретив элементов, больше заданного
          if(pi > N) then
              IsCheckNumbers := true
          else
      // текущий элемент больше заданного    
              if(pv[pi] > px) then
                  IsCheckNumbers := false
              else
      // именно в этой команде проявляется линейность рекурсии        
                  IsCheckNumbers := IsCheckNumbers(pv, pi + 1, px);
      end;


    я тут не догоняю про КАСКАДНУЮ рекурсию. Почитал про нее, мол это синоним параллельной рекурсии (еще древовидной), например, используется для нахождения чисел Фибоначчи: f(n) = f(n - 1) + f(n - 2).
    Т е как я понял, главный признак каскадной рекурсии в том, что в одной команде она вызывается БОЛЬШЕ 1-го раза.

    И, честно говоря, что-то я не выкупаю, как эту каскадную рекурсию можно применить для поставленной задачи. Там элементики вектора перебираются последовательно, один за другим, т е чисто линейный вариант возникает...
    К чему стремится то?
    Сообщение отредактировано: FasterHarder -
      Реализуй тупо деление пополам.
        Цитата Akina @
        Реализуй тупо деление пополам.

        хм...вроде понял
        у меня были какие-то мысли, направить движение проверки элементов друг навстречу друга, но там вроде была линейность
        с твоим вариантом (дихотомия вроде) получилось так (Паскаль):
        ExpandedWrap disabled
          // true - если все числа вектора НЕ БОЛЬШЕ заданного
          function IsCascade(pv: TVector; pl: byte; pr: byte; px: integer): boolean;
          var
              center: byte;
          begin
              if(pl = pr) then   // сузился подмассив до 1 элемента
                  if (pv[pl] > px) then
                      IsCascade := false
                  else
                      IsCascade := true
              else
              begin
                  center := (pl + pr) div 2;
                  // вот она каскадная рекурсия! вот она!
                  IsCascade := IsCascade(pv, pl, center, px) and IsCascade(pv, center + 1, pr, px);
                  //IsCascade := IsCascade(pv, pl, center, px);
                  //IsCascade := IsCascade(pv, center + 1, pr, px);
              end;
          end;

        я правильно понял или вообще не то сделал?
          Правильно, правильно.

          Если отрезок состоит из одного элемента проверяешь его на величину.
          Иначе разбиваешь отрезок на две части, получаешь ответ для каждой из них и объединяешь результат.

          По-моему начать программу лучше было с
          ExpandedWrap disabled
                if(pl = pr) then   // сузился подмассив до 1 элемента
                    IsCascade := pv[pl] <Б= px
                else

          И я бы для надёжности добавил случай, когда pr < pl, вернув true.
            amk, ясно, спс
              Еще хотел уточнить по каскадной рекурсии на другом примере!
              Условие такое: для заданного одномерного массива из n элементов найти значение максимального по модулю элемента массива.
              С трудом написал линейную рекурсию (вроде работает даже, Паскаль):
              ExpandedWrap disabled
                // нахождение наибольшего по модулю элемента вектора    
                function MaxABS(pv: TVector; pn: integer):integer;
                var
                    curMax: integer;    // макс. по модулю из проверенных
                begin
                    if(pn > 1) then
                    begin
                        curMax := MaxABS(pv, pn - 1);
                        if(abs(pv[pn]) < abs(curMax)) then
                            MaxABS := curMax
                        else
                            MaxABS := pv[pn]
                    end
                    else // элементарный случай рекурсии
                        MaxABS := pv[1]
                end;


              я правильно выкупаю, что для древовидной рекурсии тут тоже можно пойти делением пополам??
              только сужать нужно НЕ ДО ОДНОГО элемента, а до ДВУХ и возвращать наибольшее по модулю из них? Если отрезок из 1 элемента, то он сам и возвращается
              или вообще все не так нужно...
                Цитата FasterHarder @
                только сужать нужно НЕ ДО ОДНОГО элемента, а до ДВУХ и возвращать наибольшее по модулю из них? Если отрезок из 1 элемента, то он сам и возвращается или вообще все не так нужно...

                Это одно и то же. Просто экономится один уровень рекурсии.
                Хотя обычно рекурсию сравнения завершают на ТРЁХ элементах - сортировка выбором для трёх быстрее ещё одного уровня рекурсии.
                  Цитата Akina @
                  Хотя обычно рекурсию сравнения завершают на ТРЁХ элементах

                  хм...понятно, интересно

                  Написал каскадную рекурсию для последней задачи, вроде работает (мне фартануло, что она вроде получилась, т к на 100% этот код не понимаю)
                  ExpandedWrap disabled
                    //===========================================================
                    // нахождение наибольшего по модулю элемента вектора    
                    //===========================================================
                    function CascadeMaxABS(pv: TVector; pleft, pright: integer): integer;
                    var
                        center: integer;
                        x, y: integer;
                    begin
                        if(pleft = pright) then // подмассив из 1-го элемента
                            CascadeMaxABS := pv[pleft] // := pv[pright]
                        else
                            // если отрезок из 2-х элементов, то возвращаем наибольший из них по модулю
                            if(pright = pleft + 1) then
                            begin
                                if(abs(pv[pleft]) > abs(pv[pright])) then
                                    CascadeMaxABS := pv[pleft]
                                else
                                    CascadeMaxABS := pv[pright];
                            end                
                            else    // длина подмассива БОЛЬШЕ 2-х элементов
                            begin
                                center := (pleft + pright) div 2;
                                x := CascadeMaxABS(pv, pleft, center);
                                y := CascadeMaxABS(pv, center + 1, pright);
                                if(abs(x) > abs(y)) then
                                    CascadeMaxABS := x
                                else
                                    CascadeMaxABS := y;
                            end;
                    end;
                    //==========================================================
                  =

                  хотя, конечно, есть такое ощущение, что решать такие задачи рекурсией есть своего рода извращение...

                  Akina, я правильно понимаю, что:
                  1) любую задачу можно решить, используя лин.рекурсию? (вроде в некоторых ЯП нет циклических конструкций, поэтому там только через рекурсию трудятся)
                  2) любую задачу, которую можно решить лин.рекурсией, всегда можно переписать на использование каскадной рекурсии?

                  P.S. ИМХО, рекурсия - сложная тема, хотя на 1-ом этапе кажется простой! Если копнуть рекурсию, то там возникают лютые (нет, даже лютейшие) сложности, на определенном этапе...
                  Сообщение отредактировано: FasterHarder -
                    Цитата FasterHarder @
                    любую задачу можно решить, используя лин.рекурсию?

                    Стопудово нет.

                    Цитата FasterHarder @
                    любую задачу, которую можно решить лин.рекурсией, всегда можно переписать на использование каскадной рекурсии?

                    Попробуй простейший факториал перепиши на каскад...
                      Цитата FasterHarder @
                      ExpandedWrap disabled
                            if(pleft = pright) then // подмассив из 1-го элемента
                                CascadeMaxABS := pv[pleft] // := pv[pright]
                            else
                                // если отрезок из 2-х элементов, то возвращаем наибольший из них по модулю
                                if(pright = pleft + 1) then
                                begin
                                    if(abs(pv[pleft]) > abs(pv[pright])) then
                                        CascadeMaxABS := pv[pleft]
                                    else
                                        CascadeMaxABS := pv[pright];
                                end                


                      Нет смысла разделять для 1 и 2 элементов:
                      ExpandedWrap disabled
                            if(pright - pleft < 2) then
                                begin
                                    if(abs(pv[pleft]) > abs(pv[pright])) then
                                        CascadeMaxABS := pv[pleft]
                                    else
                                        CascadeMaxABS := pv[pright];
                                end                

                      или вообще
                      ExpandedWrap disabled
                        if(pright - pleft < 2) then
                           CascadeMaxABS := (pv[pleft] + pv[pright] + ABS(pv[pleft] - pv[pright])) / 2;
                        Цитата Akina @
                        Попробуй простейший факториал перепиши на каскад...

                        нет, не получается)
                        я не знаю, там может как-то извратиться все-таки можно, вычисляя в одной команде f(n - 1) * f(n - 2), а потом менять счетчики, но там какой-то бред будет по факту, конечно...

                        все-таки я хотел еще раз окончательно выяснить правдивость этой фразы:
                        Цитата FasterHarder @
                        Т е как я понял, главный признак каскадной рекурсии в том, что в одной команде она вызывается БОЛЬШЕ 1-го раза.

                        в моей последней ф-ции НЕТ такой ни одной команды :( , т е и каскада нет?

                        а, если так написать?
                        ExpandedWrap disabled
                          //===========================================================
                          // нахождение наибольшего по модулю элемента вектора    
                          //===========================================================
                          function CascadeMaxABS(pv: TVector; pleft, pright: integer): integer;
                          var
                              center: integer;
                              //x, y: integer;
                          begin
                              //if(pleft = pright) then // подмассив из 1-го элемента
                                  //CascadeMaxABS := pv[pleft] // := pv[pright]
                              //else
                                  // если отрезок не более 2-х элементов, то возвращаем наибольший из них по модулю
                              if(pright - pleft < 2) then
                              begin
                                  if(abs(pv[pleft]) > abs(pv[pright])) then
                                      CascadeMaxABS := pv[pleft]
                                  else
                                      CascadeMaxABS := pv[pright];
                              end                
                              else    // длина подмассива БОЛЬШЕ 2-х элементов
                              begin
                                  center := (pleft + pright) div 2;
                                  if(abs(CascadeMaxABS(pv, pleft, center)) > abs(CascadeMaxABS(pv, center + 1, pright))) then
                                      CascadeMaxABS := CascadeMaxABS(pv, pleft, center)
                                  else
                                      CascadeMaxABS := CascadeMaxABS(pv, center + 1, pright);
                                  //x := CascadeMaxABS(pv, pleft, center);
                                  //y := CascadeMaxABS(pv, center + 1, pright);
                                  //if(abs(x) > abs(y)) then
                                      //CascadeMaxABS := x
                                  //else
                                      //CascadeMaxABS := y;
                              end;
                          end;
                          //===========================================================

                        каскад есть :yes: , но что-то мне кажется это не то...
                          Цитата FasterHarder @
                          в моей последней ф-ции НЕТ такой ни одной команды

                          А это тогда что:
                          Цитата FasterHarder @
                          ExpandedWrap disabled
                                        x := CascadeMaxABS(pv, pleft, center);
                                        y := CascadeMaxABS(pv, center + 1, pright);


                          Признак каскадной рекурсии - хотя бы один раз, хотя бы на одном уровне рекурсии, выполняется не менее двух обращений к рекурсии следующего уровня. Ну то есть хотя бы в одной точке дерево вызовов раздвояется.
                          А в одном операторе или в разных - глубоко сиренево.
                            Цитата Akina @
                            Хотя обычно рекурсию сравнения завершают на ТРЁХ элементах - сортировка выбором для трёх быстрее ещё одного уровня рекурсии.
                            Иногда даже на большем количестве. Но в данном случае речь идёт о принципе, а поиск максимального элемента итерацией на любом количестве элементов оказывается быстрее рекурсии, если только не используется функциональный язык и распараллеливание. Так что здесь имеет смысл довести рекурсию до предела.

                            Цитата Akina @
                            Стопудово нет.
                            Тем не менее практически любую итерационную задачу можно свести к рекурсии, быть может написав для этого пару-другую вспомогательных функций.

                            Цитата Akina @
                            Попробуй простейший факториал перепиши на каскад...
                            На самом деле как раз факторила переписывается на каскадную рекурсию несложно, Для этого достаточно написать дополнительную функцию. Основная функция не будет рекурсивной, а вспомогательная будет иметь другую сигнатуру и быть каскадно-рекурсивной.
                            Один из вариантов дополнительной функции - функция, возвращающая произведение всех целых из интервала. Её можно рекурсивно представить как произведение двух произведений половин этого интервала.

                            По поводу границы рекурсии, итерация всегда быстрее не распараллеленной рекурсии.
                              Цитата Akina @
                              Признак каскадной рекурсии - хотя бы один раз, хотя бы на одном уровне рекурсии, выполняется не менее двух обращений к рекурсии следующего уровня. Ну то есть хотя бы в одной точке дерево вызовов раздвояется.

                              вот! теперь я понял, что такое каскадная рекурсия еще глубже. Что же раньше об этом не написал, я бы поумнел быстрее, еще в начале темы) ведь еще в 1-ом посте я был не точен относительно ее...

                              Цитата amk @
                              Тем не менее практически любую итерационную задачу можно свести к рекурсии

                              я правильно понимаю, что, если задача НЕ ИТЕРАТИВНАЯ, то ее практически нельзя свести к рекурсии, да? А, если обход бинарного дерева. Или всегда можно написать изврат бессмысленный и все сделать через рекурсию?
                              также приведи, плиз, пример, когда итерационную задачу НЕЛЬЗЯ записать через рекурсию.
                              Цитата amk @
                              На самом деле как раз факторила переписывается на каскадную рекурсию несложно, Для этого достаточно написать дополнительную функцию.

                              не будет ли это означать, что прямого алгоритма переноса на каскадную рекурсию не существует? ведь ты планируешь ввести ДОПОЛНИТЕЛЬНУЮ ф-цию, которая как бы делает не "чистый" перенос, т е облегчает перенос на каскадный вариант...
                                Цитата FasterHarder @
                                я правильно понимаю, что, если задача НЕ ИТЕРАТИВНАЯ, то ее практически нельзя свести к рекурсии, да?

                                Наоборот. Если задача не реализуется линейной рекурсией, то она не итеративна.

                                Цитата FasterHarder @
                                пример, когда итерационную задачу НЕЛЬЗЯ записать через рекурсию.

                                Итерация всегда может быть преобразована в рекурсию. Несмотря на то, что в 99% случаев это откровенно глупо.

                                Добавлено
                                Цитата amk @
                                факторила переписывается на каскадную рекурсию несложно, Для этого достаточно написать дополнительную функцию. Основная функция не будет рекурсивной, а вспомогательная будет иметь другую сигнатуру и быть каскадно-рекурсивной.

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


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0476 ]   [ 16 queries used ]   [ Generated: 28.03.24, 10:31 GMT ]