Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.141.30.162] |
|
Сообщ.
#1
,
|
|
|
Всем хай! Сходу к делу!
Вот условие задачи: описать 2 рекурсивные функции (линейную и каскадную), которые проверяют, что в одномерном массиве нет элементов, больших заданного числа. с линейной рекурсией сложностей не возникло (Паскаль): 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-го раза. И, честно говоря, что-то я не выкупаю, как эту каскадную рекурсию можно применить для поставленной задачи. Там элементики вектора перебираются последовательно, один за другим, т е чисто линейный вариант возникает... К чему стремится то? |
Сообщ.
#2
,
|
|
|
Реализуй тупо деление пополам.
|
Сообщ.
#3
,
|
|
|
Цитата Akina @ Реализуй тупо деление пополам. хм...вроде понял у меня были какие-то мысли, направить движение проверки элементов друг навстречу друга, но там вроде была линейность с твоим вариантом (дихотомия вроде) получилось так (Паскаль): // 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; я правильно понял или вообще не то сделал? |
Сообщ.
#4
,
|
|
|
Правильно, правильно.
Если отрезок состоит из одного элемента проверяешь его на величину. Иначе разбиваешь отрезок на две части, получаешь ответ для каждой из них и объединяешь результат. По-моему начать программу лучше было с if(pl = pr) then // сузился подмассив до 1 элемента IsCascade := pv[pl] <Б= px else И я бы для надёжности добавил случай, когда pr < pl, вернув true. |
Сообщ.
#5
,
|
|
|
amk, ясно, спс
|
Сообщ.
#6
,
|
|
|
Еще хотел уточнить по каскадной рекурсии на другом примере!
Условие такое: для заданного одномерного массива из n элементов найти значение максимального по модулю элемента массива. С трудом написал линейную рекурсию (вроде работает даже, Паскаль): // нахождение наибольшего по модулю элемента вектора 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 элемента, то он сам и возвращается или вообще все не так нужно... |
Сообщ.
#7
,
|
|
|
Цитата FasterHarder @ только сужать нужно НЕ ДО ОДНОГО элемента, а до ДВУХ и возвращать наибольшее по модулю из них? Если отрезок из 1 элемента, то он сам и возвращается или вообще все не так нужно... Это одно и то же. Просто экономится один уровень рекурсии. Хотя обычно рекурсию сравнения завершают на ТРЁХ элементах - сортировка выбором для трёх быстрее ещё одного уровня рекурсии. |
Сообщ.
#8
,
|
|
|
Цитата Akina @ Хотя обычно рекурсию сравнения завершают на ТРЁХ элементах хм...понятно, интересно Написал каскадную рекурсию для последней задачи, вроде работает (мне фартануло, что она вроде получилась, т к на 100% этот код не понимаю) //=========================================================== // нахождение наибольшего по модулю элемента вектора //=========================================================== 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-ом этапе кажется простой! Если копнуть рекурсию, то там возникают лютые (нет, даже лютейшие) сложности, на определенном этапе... |
Сообщ.
#9
,
|
|
|
Цитата FasterHarder @ любую задачу можно решить, используя лин.рекурсию? Стопудово нет. Цитата FasterHarder @ любую задачу, которую можно решить лин.рекурсией, всегда можно переписать на использование каскадной рекурсии? Попробуй простейший факториал перепиши на каскад... |
Сообщ.
#10
,
|
|
|
Цитата FasterHarder @ 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 элементов: if(pright - pleft < 2) then begin if(abs(pv[pleft]) > abs(pv[pright])) then CascadeMaxABS := pv[pleft] else CascadeMaxABS := pv[pright]; end или вообще if(pright - pleft < 2) then CascadeMaxABS := (pv[pleft] + pv[pright] + ABS(pv[pleft] - pv[pright])) / 2; |
Сообщ.
#11
,
|
|
|
Цитата Akina @ Попробуй простейший факториал перепиши на каскад... нет, не получается) я не знаю, там может как-то извратиться все-таки можно, вычисляя в одной команде f(n - 1) * f(n - 2), а потом менять счетчики, но там какой-то бред будет по факту, конечно... все-таки я хотел еще раз окончательно выяснить правдивость этой фразы: Цитата FasterHarder @ Т е как я понял, главный признак каскадной рекурсии в том, что в одной команде она вызывается БОЛЬШЕ 1-го раза. в моей последней ф-ции НЕТ такой ни одной команды , т е и каскада нет? а, если так написать? //=========================================================== // нахождение наибольшего по модулю элемента вектора //=========================================================== 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; //=========================================================== каскад есть , но что-то мне кажется это не то... |
Сообщ.
#12
,
|
|
|
Цитата FasterHarder @ в моей последней ф-ции НЕТ такой ни одной команды А это тогда что: Цитата FasterHarder @ x := CascadeMaxABS(pv, pleft, center); y := CascadeMaxABS(pv, center + 1, pright); Признак каскадной рекурсии - хотя бы один раз, хотя бы на одном уровне рекурсии, выполняется не менее двух обращений к рекурсии следующего уровня. Ну то есть хотя бы в одной точке дерево вызовов раздвояется. А в одном операторе или в разных - глубоко сиренево. |
Сообщ.
#13
,
|
|
|
Цитата Akina @ Иногда даже на большем количестве. Но в данном случае речь идёт о принципе, а поиск максимального элемента итерацией на любом количестве элементов оказывается быстрее рекурсии, если только не используется функциональный язык и распараллеливание. Так что здесь имеет смысл довести рекурсию до предела.Хотя обычно рекурсию сравнения завершают на ТРЁХ элементах - сортировка выбором для трёх быстрее ещё одного уровня рекурсии. Цитата Akina @ Тем не менее практически любую итерационную задачу можно свести к рекурсии, быть может написав для этого пару-другую вспомогательных функций.Стопудово нет. Цитата Akina @ На самом деле как раз факторила переписывается на каскадную рекурсию несложно, Для этого достаточно написать дополнительную функцию. Основная функция не будет рекурсивной, а вспомогательная будет иметь другую сигнатуру и быть каскадно-рекурсивной.Попробуй простейший факториал перепиши на каскад... Один из вариантов дополнительной функции - функция, возвращающая произведение всех целых из интервала. Её можно рекурсивно представить как произведение двух произведений половин этого интервала. По поводу границы рекурсии, итерация всегда быстрее не распараллеленной рекурсии. |
Сообщ.
#14
,
|
|
|
Цитата Akina @ Признак каскадной рекурсии - хотя бы один раз, хотя бы на одном уровне рекурсии, выполняется не менее двух обращений к рекурсии следующего уровня. Ну то есть хотя бы в одной точке дерево вызовов раздвояется. вот! теперь я понял, что такое каскадная рекурсия еще глубже. Что же раньше об этом не написал, я бы поумнел быстрее, еще в начале темы) ведь еще в 1-ом посте я был не точен относительно ее... Цитата amk @ Тем не менее практически любую итерационную задачу можно свести к рекурсии я правильно понимаю, что, если задача НЕ ИТЕРАТИВНАЯ, то ее практически нельзя свести к рекурсии, да? А, если обход бинарного дерева. Или всегда можно написать изврат бессмысленный и все сделать через рекурсию? также приведи, плиз, пример, когда итерационную задачу НЕЛЬЗЯ записать через рекурсию. Цитата amk @ На самом деле как раз факторила переписывается на каскадную рекурсию несложно, Для этого достаточно написать дополнительную функцию. не будет ли это означать, что прямого алгоритма переноса на каскадную рекурсию не существует? ведь ты планируешь ввести ДОПОЛНИТЕЛЬНУЮ ф-цию, которая как бы делает не "чистый" перенос, т е облегчает перенос на каскадный вариант... |
Сообщ.
#15
,
|
|
|
Цитата FasterHarder @ я правильно понимаю, что, если задача НЕ ИТЕРАТИВНАЯ, то ее практически нельзя свести к рекурсии, да? Наоборот. Если задача не реализуется линейной рекурсией, то она не итеративна. Цитата FasterHarder @ пример, когда итерационную задачу НЕЛЬЗЯ записать через рекурсию. Итерация всегда может быть преобразована в рекурсию. Несмотря на то, что в 99% случаев это откровенно глупо. Добавлено Цитата amk @ факторила переписывается на каскадную рекурсию несложно, Для этого достаточно написать дополнительную функцию. Основная функция не будет рекурсивной, а вспомогательная будет иметь другую сигнатуру и быть каскадно-рекурсивной. Это потребует искажения понятия факториала. Точнее, форма реализации не будет соответствовать физике смысла - а именно последовательному домножению в прямом или обратном порядке. Соответственно - хоть функция и вычисляет факториал, вычислением факториала не является... и так бывает, чо... |
Сообщ.
#16
,
|
|
|
Цитата Akina @ Это зависит от того, как определить факториал. Если применять рекурсивное определение n!=n*(n-1)!, то да, не является.Соответственно - хоть функция и вычисляет факториал, вычислением факториала не является... Но есть и другое определение, которое к тому же является основным: факториал числа n, есть произведение натуральных чисел от 1 до n. А уже это определение, слегка обобщённое, вполне соответствует предложенному мной варианту. Причём обобщение вполне естественное. Факториал ведь равен числу перестановок из n элементов. А обобщение вычисляет число укороченных перестановок. |
Сообщ.
#17
,
|
|
|
в общем понятно про каскадную рекурсию приблизительно и пр.
всем спс за помощь! |