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

SCOOTER "GUEST LIST"

'Pon the mic I'm the teacher!
Spread my words like a preacher!
Yiiihhaaaa!!!!

SCOOTER "WEEKEND"
Реализуй тупо деление пополам.
Есть претензии ко мне как к модератору? читайте Правила, разделы 5 и 6, и действуйте соответственно.
Есть претензии ко мне как к участнику? да ради бога.
Не нравятся мои ответы? не читайте их.
В общем, берегите себя. Нервные клетки не восстанавливаются.
Цитата 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;

я правильно понял или вообще не то сделал?
I originate
You must appreciate, all the others imitate

SCOOTER "GUEST LIST"

'Pon the mic I'm the teacher!
Spread my words like a preacher!
Yiiihhaaaa!!!!

SCOOTER "WEEKEND"
Правильно, правильно.

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

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

И я бы для надёжности добавил случай, когда pr < pl, вернув true.
Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
amk, ясно, спс
I originate
You must appreciate, all the others imitate

SCOOTER "GUEST LIST"

'Pon the mic I'm the teacher!
Spread my words like a preacher!
Yiiihhaaaa!!!!

SCOOTER "WEEKEND"
Еще хотел уточнить по каскадной рекурсии на другом примере!
Условие такое: для заданного одномерного массива из 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 элемента, то он сам и возвращается
или вообще все не так нужно...
I originate
You must appreciate, all the others imitate

SCOOTER "GUEST LIST"

'Pon the mic I'm the teacher!
Spread my words like a preacher!
Yiiihhaaaa!!!!

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

Это одно и то же. Просто экономится один уровень рекурсии.
Хотя обычно рекурсию сравнения завершают на ТРЁХ элементах - сортировка выбором для трёх быстрее ещё одного уровня рекурсии.
Есть претензии ко мне как к модератору? читайте Правила, разделы 5 и 6, и действуйте соответственно.
Есть претензии ко мне как к участнику? да ради бога.
Не нравятся мои ответы? не читайте их.
В общем, берегите себя. Нервные клетки не восстанавливаются.
Цитата 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 -
I originate
You must appreciate, all the others imitate

SCOOTER "GUEST LIST"

'Pon the mic I'm the teacher!
Spread my words like a preacher!
Yiiihhaaaa!!!!

SCOOTER "WEEKEND"
Цитата FasterHarder @
любую задачу можно решить, используя лин.рекурсию?

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

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

Попробуй простейший факториал перепиши на каскад...
Есть претензии ко мне как к модератору? читайте Правила, разделы 5 и 6, и действуйте соответственно.
Есть претензии ко мне как к участнику? да ради бога.
Не нравятся мои ответы? не читайте их.
В общем, берегите себя. Нервные клетки не восстанавливаются.
Цитата 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;
Есть претензии ко мне как к модератору? читайте Правила, разделы 5 и 6, и действуйте соответственно.
Есть претензии ко мне как к участнику? да ради бога.
Не нравятся мои ответы? не читайте их.
В общем, берегите себя. Нервные клетки не восстанавливаются.
Цитата 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: , но что-то мне кажется это не то...
I originate
You must appreciate, all the others imitate

SCOOTER "GUEST LIST"

'Pon the mic I'm the teacher!
Spread my words like a preacher!
Yiiihhaaaa!!!!

SCOOTER "WEEKEND"
Цитата FasterHarder @
в моей последней ф-ции НЕТ такой ни одной команды

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


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

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

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

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

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

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

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

не будет ли это означать, что прямого алгоритма переноса на каскадную рекурсию не существует? ведь ты планируешь ввести ДОПОЛНИТЕЛЬНУЮ ф-цию, которая как бы делает не "чистый" перенос, т е облегчает перенос на каскадный вариант...
I originate
You must appreciate, all the others imitate

SCOOTER "GUEST LIST"

'Pon the mic I'm the teacher!
Spread my words like a preacher!
Yiiihhaaaa!!!!

SCOOTER "WEEKEND"
Цитата FasterHarder @
я правильно понимаю, что, если задача НЕ ИТЕРАТИВНАЯ, то ее практически нельзя свести к рекурсии, да?

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

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

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

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

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


Рейтинг@Mail.ru
[ Script Execution time: 0,1786 ]   [ 19 queries used ]   [ Generated: 25.04.18, 18:28 GMT ]