Вычисление значения функции разложением в ряд с точностью N

← →
oldman © (2011-08-02 09:02) [0]

Цикл или рекурсия.
Кто как поступил бы?

← →
TUser © (2011-08-02 09:07) [1]

Конечно, цикл.

← →
Компромисс (2011-08-02 11:06) [2]

Всегда по умолчанию следует использовать цикл. Для того, чтобы использовать рекурсию, должны быть очень веские причины (например, большая сложность циклической реализации). Если на собеседовании реализуют факториал рекурсией, сразу можно указывать соискателю на дверь.

← →
Dennis I. Komarov © (2011-08-02 11:12) [3]

Итерация свойственна человеку, рекурсия божественна. - L. Peter Deutsch

← →
Sha © (2011-08-02 12:08) [4]

Не можешь не сделать не рекурсией - не делай.

← →
Компромисс (2011-08-02 12:20) [5]

Не можешь не сделать не рекурсией - не делай.

Мне кажется, во фразе есть ошибка.
Не можешь не сделать = очень тянет сделать, нет сил терпеть.
Получается, очень тянет сделать нерекурсией - не делай. Неверно, по-моему.

← →
Mystic © (2011-08-02 12:34) [6]

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

← →
Sha © (2011-08-02 13:11) [7]

> Компромисс (02.08.11 12:20) [5]

Советы бывают полезны.

← →
Sha © (2011-08-02 13:17) [8]

> Компромисс (02.08.11 11:06) [2]
> Если на собеседовании реализуют факториал рекурсией,
> сразу можно указывать соискателю на дверь.

А если в книге примером рекурсии служит
вычисление факториала - сжечь книгу.

← →
Компромисс (2011-08-02 13:30) [9]

А если в книге примером рекурсии служит
вычисление факториала - сжечь книгу.

Я учился по хорошей книге, в которой были представлены оба варианта расчета факториала и даже дан сравнительный анализ. Особо было указано, что рекурсивный факториал представляет собой лишь пример, поясняющий суть рекурсивного метода, но не должен использоваться на практике.

← →
Sha © (2011-08-02 13:44) [10]

Вместо факториала куда полезнее рассмотреть быструю сортировку,
а не пудрить мозги детям.

← →
Компромисс (2011-08-02 13:50) [11]

Sha © (02.08.11 13:44) [10]

Быстрая сортировка - это уже advanced/expert level, совсем не для начинающих. Самостоятельно ее не напишут.

← →
Игорь Шевченко © (2011-08-02 13:51) [12]

> Особо было указано, что рекурсивный факториал представляет
> собой лишь пример, поясняющий суть рекурсивного метода,
> но не должен использоваться на практике

если книга про Фортран-66, то да, не должен. В остальных случаях желательно аргументировать заявление

← →
Mystic © (2011-08-02 13:51) [13]

Как минимум в чистых функциональных языках нет изменяемых переменных, поэтому рекурсия это единственно возможный способ реализации факториала. Опять же, хвостовая рекурсия может быть легко оптимизирована компилятором.

← →
Sha © (2011-08-02 13:56) [14]

Я книгу имел в виду. Хотя, думаю,
если человек слышал про быструю сортировку,
он сможет ее написать, пусть и с ошибками.

← →
TUser © (2011-08-02 14:06) [15]

По личным впечатлениям рекурсивные алгоритмы обычно сильно сложнее в отладке.

← →
Компромисс (2011-08-02 14:32) [16]

если книга про Фортран-66, то да, не должен. В остальных случаях желательно аргументировать заявление

Книга действительно была про фортран (правда, 77), но дело не в этом. Есть и более современные варианты. Например, http://www.rulibrary.com/book-101-16.html или https://www.wasm.ru/forum/viewtopic.php?id=27488&p=1

← →
DiamondShark © (2011-08-02 16:00) [17]

> Если на собеседовании реализуют факториал рекурсией, сразу
> можно указывать соискателю на дверь.

Даже если собеседование по Scheme?

← →
DiamondShark © (2011-08-02 16:02) [18]

> А если в книге примером рекурсии служит вычисление факториала
> - сжечь книгу.

Если компилятор не умеет преобразовать хвостовую рекурсию в итерацию -- сжечь компилятор.

← →
DiamondShark © (2011-08-02 16:05) [19]

> В остальных случаях желательно аргументировать заявление

Требование к памяти O(n) там, где положено O(1) -- достаточный аргумент?

← →
Sha © (2011-08-02 16:09) [20]

> DiamondShark © (02.08.11 16:02) [18]
> Если компилятор не умеет преобразовать хвостовую рекурсию в итерацию -- сжечь компилятор.

Т.е. если б Дельфи умела, тебя бы такое чудо устроило бы :)

function MyPosEx(const SubSt, St: AnsiString; From: integer= 1): integer; function MyPosExInternal(Start, Count: integer): integer; begin; if Start>Length(St)+1-Length(SubSt) then Result:=0 else if Count=Length(SubSt) then Result:=Start else if Subst[1+Count]=St[Start+Count] then Result:=MyPosExInternal(Start,Count+1) else Result:=MyPosExInternal(Start+1,0); end; begin; if (Length(SubSt)<=0) then Result:=0 else Result:=MyPosExInternal(From, 0); end; procedure TForm1.Button1Click(Sender: TObject); begin; Edit3.Text:=IntToStr(MyPosEx(Edit1.Text,Edit2.Text)); end;

← →
Компромисс (2011-08-02 16:10) [21]

Если компилятор не умеет преобразовать хвостовую рекурсию в итерацию -- сжечь компилятор.

Основная задача профессионального обучения - вовсе не заставить человека вызубрить команды ассемблера или прерывания с их параметрами. И даже не научить писать драйверы под какую-то систему. Глобальная задача только одна - научить человека алгоритмам и их применению. Поэтому не стоит показывать определенную технику на заведомо для нее неподходящем примере. В лучшем случае читающий посмеется или пойдет на форум искать правду, а в худщем ведь поверит! И получится потом "программист", пишущий экспоненциальный код в надежде на компилятор и быстродействие машины.

https://www.wasm.ru/forum/viewtopic.php?id=27488&p=1

← →
KSergey © (2011-08-02 16:28) [22]

> DiamondShark © (02.08.11 16:00) [17]
> Даже если собеседование по Scheme?

AvtoScheme, я настаиваю!

← →
DiamondShark © (2011-08-02 17:16) [23]

> Sha © (02.08.11 16:09) [20]
> Т.е. если б Дельфи умела, тебя бы такое чудо устроило бы :)

Вполне.
Только вынести наружу инварианты Length(x), и переписать

if Start + Length(SubSt) - 1 > Length(St)

для пущей наглядности.

Если бы символы нумеровались с нуля, было бы ещё нагляднее (исчезли бы лишние +-1).

← →
DiamondShark © (2011-08-02 17:18) [24]

> Компромисс (02.08.11 16:10) [21]

А я не вижу противоречий двух цитат.
Тем более, что под: "Поэтому не стоит показывать определенную технику на заведомо для нее неподходящем примере." -- я подпишусь двумя руками.

← →
Компромисс (2011-08-02 17:23) [25]

DiamondShark © (02.08.11 17:18) [24]

Противоречий, действительно, нет. Компилятор должен быть умным, но программист не должен на это рассчитывать.

← →
Sha © (2011-08-02 17:35) [26]

> DiamondShark © (02.08.11 17:16) [23]

Ну, мне как-то больше по душе что-нибудь вроде
function MyPosEx2(const SubSt, St: AnsiString; From: integer= 1): integer; var Count, Last, Len1: integer; begin; Last:=Length(St); Len1:=Length(SubSt)-1; Last:=Last-Len1; if (Len1<0) or (From<=0) then From:=0 else begin; Count:=0; while true do begin; if Subst[Count+1]=St[Count+From] then if Count>=Len1 then break else inc(Count) else if From<Last then inc(From) else begin; From:=0; break; end; end; end; Result:=From; end;

← →
Игорь Шевченко © (2011-08-02 17:50) [27]

> Ну, мне как-то больше по душе что-нибудь вроде

а что оно делает ?

← →
DiamondShark © (2011-08-02 18:08) [28]

> Sha © (02.08.11 17:35) [26]
> Ну, мне как-то больше по душе что-нибудь вроде

Есть хороший критерий (я его 17 секунд назад придумал): внятно откомментировать каждую строчку.
function MyPosEx(const SubSt, St: AnsiString; From: integer= 1): integer; function MyPosExInternal(Start, Count: integer): integer; begin; if Start>Length(St)+1-Length(SubSt) // граничные условия then Result:=0 // образец длиннее, чем "хвост" строки else if Count=Length(SubSt) // символы образца кончились? then Result:=Start // значит, нашли else if Subst[1+Count]=St[Start+Count] // текущие символы образца и строки равны? then Result:=MyPosExInternal(Start,Count+1) // проверим следующие else Result:=MyPosExInternal(Start+1,0); // неудачка, попробуем перебор образца с другого символа строки end; begin; if (Length(SubSt)<=0) // граничные условия then Result:=0 // пустая строка не содержится ни в какой строке else Result:=MyPosExInternal(From, 0); // ищем посимвольным перебором end;
Попробуете?

Ещё один момент. Код функционального стиля легко читается последовательно.
При чтении второго варианта приходится скакать глазами, да ещё и с запоминанием контекста. Ну, вот, например:
then if Count>=Len1 then break // ой-вэй, это куда?
ага, сюда:
end; Result:=From; // Шыт. А From тут чему равен? end;
не страшно, полистаем назад:
else if From<Last then inc(From) // А-аа, блин, вот он, в другой ветке инкается. else begin; From:=0; break; end;

Вам по душе спагетти? Спасибо, только в столовой.

> DiamondShark © (02.08.11 18:08) [28]
> При чтении второго варианта приходится скакать глазами

Там полная аналогия с первым вариантом, никуда скакать не надо,
все в пределах единственного небольшого цикла.

Плюс скорость работы зависит не от компилятора, а от программиста.

Sha © (02.08.11 19:21) [29]

{ PosEx searches for SubStr in S and returns the index position of SubStr if found and 0 otherwise. If Offset is not given then the result is the same as calling Pos. If Offset is specified and > 1 then the search starts at position Offset within S. If Offset is larger than Length(S) then PosEx returns 0. By default, Offset equals 1. } function PosEx(const SubStr, S: string; Offset: Integer = 1): Integer; overload;

вот тут не возникает вопроса, "что оно делает".

> Игорь Шевченко © (02.08.11 20:05) [31]
> вот тут не возникает вопроса, "что оно делает".

Не у всех. У меня, например, давно есть один вопрос :)

А мне нравится простая такая, "неприметная" книжица - "Вычисление элементарных функций на ЭВМ". Благовещенский, Теслер.
Киев, 1977.

← →
Вариант (2011-08-03 07:47) [34]

> DiamondShark © (02.08.11 18:08) [28]
> Вариант (03.08.11 07:47) [34]

Рекурсивную версию писал, стараясь сделать ее максимально понятной.
Из-за этого она получилась сильно тормознутой. Если избавиться от
повторных вызовов Length(), то получим MyPosEx1 (см. ниже).
Нерекурсивная калька с нее MyPosEx2 почти в 7 раз быстрее и не менее понятна.
Ортимизированная версия MyPosEx3 - в 8 раз быстрее и чуть менее понятна.

function MyPosEx1(const SubSt, St: AnsiString; Start: integer= 1): integer; var SubLen, LastPos: integer; function MyPosExInternal(Start, Count: integer): integer; begin; if Start>LastPos then Result:=0 else if Count=SubLen then Result:=Start else if SubSt[Count+1]=St[Count+Start] then Result:=MyPosExInternal(Start,Count+1) else Result:=MyPosExInternal(Start+1,0); end; begin; SubLen:=Length(SubSt); LastPos:=Length(St)+1-SubLen; if (SubLen<=0) or (Start<=0) then Result:=0 else Result:=MyPosExInternal(Start, 0); end; function MyPosEx2(const SubSt, St: AnsiString; Start: integer= 1): integer; var SubLen, LastPos, Count: integer; begin; SubLen:=Length(SubSt); LastPos:=Length(St)+1-SubLen; Count:=0; if (SubLen>0) and (Start>0) then while (Start<=LastPos) and (Count<SubLen) do if SubSt[Count+1]=St[Count+Start] then inc(Count) else inc(Start); Result:=Start; if Count<SubLen then Result:=0 end; function MyPosEx3(const SubSt, St: AnsiString; Start: integer= 1): integer; var SubLen, LastPos, Count: integer; begin; SubLen:=Length(SubSt); LastPos:=Length(St)+1-SubLen; Count:=0; if (SubLen>0) and (Start>0) then while true do if SubSt[Count+1]<>St[Count+Start] then begin; inc(Start); if Start>LastPos then begin; Start:=0; break; end; end else begin; inc(Count); if Count>=SubLen then break; end else Start:=0; Result:=Start; end; procedure TForm1.Button1Click(Sender: TObject); begin; Edit3.Text:=IntToStr(MyPosEx3(Edit1.Text,Edit2.Text)); end; procedure TForm1.Button2Click(Sender: TObject); const TestCount= 1024*1024; var s1, s2: AnsiString; t0, t1, t2, t3: cardinal; i: integer; begin; s1:="рекурсия"; s2:="ехал грека через реку, видит грека — в реке рак, сунул грека руку в реку, рак за руку греку — цап."; t0:=GetTickCount; for i:=1 to TestCount do MyPosEx1(s1,s2); t1:=GetTickCount; for i:=1 to TestCount do MyPosEx2(s1,s2); t2:=GetTickCount; for i:=1 to TestCount do MyPosEx3(s1,s2); t3:=GetTickCount; Edit3.Text:=Format("%d %d %d",[t1-t0,t2-t1,t3-t2]); // 2156 312 266 end;

> Sha © (02.08.11 16:09) [20]

Автору этого кода надо через год после написания дать его, только где-нибудь в паре мест заменить +1 на -1 или что-нибудь типа того, и попросить отладить. Да, я жесток.

> TUser © (03.08.11 14:11) [36]

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

>Sha
офтоп - SubSt может восприниматься как substitution, и заглавная вторая S не спасает

> Думкин © (03.08.11 14:23) [37]
>
> > TUser © (03.08.11 14:11) [36]
>
> Ну, код для разного пишется. Если такое в черном ящике держать
> в полной уверенности его качества - то пусть там хоть как
> написано будет.
>

Речь не только про конкретный код, а про общую эффективность работы программиста - см. [15], если есть очевидный вариант без рекурсии, то в 99% предпочтителен он.

Вычисление значения функции разложением в ряд с точностью N Найти похожие ветки