Тоже пятничная задачка :о)

← →
default © (2007-05-04 20:15) [40]

Внук © (04.05.07 20:12) [39]
многие бы за вычисление факториала через рекурсию сняли бы с собеседования враз...

← →
Внук © (2007-05-04 20:16) [41]

>>default © (04.05.07 20:15) [40]
У каждого свои комплексы

← →
Sha © (2007-05-04 20:16) [42]

program InverseEven; {$APPTYPE CONSOLE} uses SysUtils; var s, t: string; begin while true do begin ReadLn(s); if s="" then break; if (StrToIntDef(s,1) and 1)=0 then t:=s + #13#10 + t; end; Write(t); ReadLn; end.

← →
default © (2007-05-04 20:18) [43]

Внук © (04.05.07 20:16) [41]
когда считается факториал через рекурсию кушается много памяти в стеке
что совсем неоправдано ибо очевидный итеративный вариант память не кушает

← →
Alx2 © (2007-05-04 20:20) [44]

Понеслось :)
#pragma comment(linker, "/stack:0x8000000")
#include <iostream>
void main()
{
if (!std::cin.eof())
{ int n;
std::cin>>n;
main();
if (!(n&1))
std::cout<<n<<" ";
}
}

← →
Зюзя (2007-05-04 20:20) [45]

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

Это еще почему это?

← →
Внук © (2007-05-04 20:21) [46]

>>default © (04.05.07 20:18) [43]
Так я и не говорил, что нужно считать факториал через рекурсию в реальных программах.

← →
default © (2007-05-04 20:23) [47]

Внук © (04.05.07 20:21) [46]

> Я вообще не вижу разницы :) Это лишь вопрос того, где кушать
> память - в массиве, списке или стеке вызовов.

вот это как-то угрожающе звучит...

← →
Sha © (2007-05-04 20:25) [48]

На строчку короче:
program InverseEven; {$APPTYPE CONSOLE} uses SysUtils; var s, t: string; begin repeat ReadLn(s); if (StrToIntDef(s,1) and 1)=0 then t:=s + #13#10 + t; until s=""; Write(t); ReadLn; end.

← →
Зюзя (2007-05-04 20:38) [49]

Факториал - очень быстро растущая функция. То есть, для того, чтобы произошло переполнение разряда даже при использовании int64, нужно взять факториал чего-то около 65. При использовании integer - и подавно. Переполнения стека при 65 рекурсивных вызовах не произойдет. Так все же, почему не стоит считать факториал с использованием рекурсивных алгоритмов?

← →
Alx2 © (2007-05-04 20:41) [50]

>Зюзя (04.05.07 20:38)

Потому-что незачем хранить в памяти кучу значений предыдущих факториалов. Можно обойтись одной переменной-аккумулятором.

А насчет переполнения - есть асимптотики. Формула Стирлинга, например. Тогда вообще все считается без циклов и => по времени независимо от аргумента.

← →
Alx2 © (2007-05-04 20:41) [51]

PS Точность абсолютная не всегда нужна

← →
Sha © (2007-05-04 20:46) [52]

> Зюзя (04.05.07 20:38) [49]
> Так все же, почему не стоит считать факториал
> с использованием рекурсивных алгоритмов?

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

Аналогично, в реальной задаче я никогда не написал бы в цикле
t:=s + #13#10 + t;
а в учебной это совершенно нормально.

← →
Rouse_ © (2007-05-04 20:51) [53]

А я кажется понял в чем фикус. Зотыч щас кодит на яве (этим и обусловлены, по всей видимости, слова о выборе языка), вероятно там есть какой-то хитрозадый метод или класс :) Кто знает яву, отпишитесь плз...

← →
Alx2 © (2007-05-04 20:52) [54]

>Rouse_ © (04.05.07 20:51)

У меня есть подозрения с веткой о функциональных языках. :)

← →
McSimm © (2007-05-04 20:57) [55]

> незачем хранить в памяти кучу значений предыдущих факториалов

А они и не хранятся, возвращаются сразу после вычисления.

Извиняюсь, но подобные "снятия с собеседования" - обычное "пальцегнутие", разве что задача поставлена корректно, с требованием экономить соответсвующие ресурсы

← →
McSimm © (2007-05-04 20:59) [56]

> Rouse_ © (04.05.07 19:27) [30]
> Да и кода там реально 38 асмовских строк :) Если считать
> только код с джампами :)

Скажи спасибо, что я инклюд не считал :)

← →
Rouse_ © (2007-05-04 21:00) [57]

> Alx2 © (04.05.07 20:52) [54]
> >Rouse_ © (04.05.07 20:51)
>
> У меня есть подозрения с веткой о функциональных языках.
> :)

Дай линк, я не в теме, пропустил видать :)

← →
Rouse_ © (2007-05-04 21:01) [58]

> Скажи спасибо, что я инклюд не считал :)

Эээ Максим, если я чичас начну юзесы считать, которые нужны для компиляции всего вышеприведенного, то... :)

← →
Alx2 © (2007-05-04 21:05) [59]

>Rouse_ © (04.05.07 21:00)
http://delphimaster.net/view/15-1178220488/

>McSimm © (04.05.07 20:57)
К сожалению, в рекурсии они сидят.

← →
McSimm © (2007-05-04 21:08) [60]

> >McSimm © (04.05.07 20:57)
> К сожалению, в рекурсии они сидят.

нет :)

← →
McSimm © (2007-05-04 21:09) [61]

факториал вычисляется при обратном движении по стеку, а на стеке хранятся параметры.

← →
Alx2 © (2007-05-04 21:10) [62]

>McSimm © (04.05.07 21:08)

Э... Виноват :)
Адреса возврата сидят
для этого, во всяком случае :)
function f(n:integer):integer;
begin
if n=0 then result := 1
else
result := n*f(n-1);
end;

← →
Alx2 © (2007-05-04 21:11) [63]

>McSimm © (04.05.07 21:09)

Да, и параметры.
Сорри.

Но опять таки зачем излишество?

← →
Внук © (2007-05-04 21:12) [64]

>>Alx2 © (04.05.07 20:52) [54]
Ууу. Помнится, я на прологе факториал считал...

← →
McSimm © (2007-05-04 21:14) [65]

> Но опять таки зачем излишество?

Иногда - незачем, а иногда это не важно.
Например, на собеседовании :)

Опять же, если не уточнить заранее.

← →
Alx2 © (2007-05-04 21:18) [66]

>McSimm © (04.05.07 21:14)

>Например, на собеседовании :)

Эх... Если еще бы и программерское вероисповедание отгадать :)

>Внук © (04.05.07 21:12)

мне запомнился подсчет минимума (максимума)
Программа пишется буквально:
минимум - элемент, меньше которого в списке не существует. :)

← →
Alx2 © (2007-05-04 21:21) [67]

Эх, треклятое косноязычие...
Вот чего бы стоило не называть то, что в стеке факториалами? Ничего :)

← →
Rouse_ © (2007-05-04 21:28) [68]

> Alx2 © (04.05.07 21:05) [59]

Псиб...

ЗЫ: Кстати в тени постановки задачи особенно в связи с фразой "в то же время максимально понятную" ИМХО самым рациональным будет все-же ассемблер (знай себе - читай инструкции, не вникая в особенности), ибо "языки программирования" бывают разные и тащут за собой столько дряни порой что пользователю тошно становиться (не говоря уже о программах на перле или дотнете, которым нужем сам перл или фреймворк) :)
Ввиду того что языков и ответвлений море, а асм един - только он может удовлетворить всем условиям задачи в полной мере :)

> Rouse_ © (04.05.07 21:28) [68]

я твою программу ни скомпилировать ни запустить не мог, а свою прямо в консоли набирал, без редактора :)

> и в то же время максимально понятную

Преследовал эту цель :)

program Project1; {$APPTYPE CONSOLE} uses SysUtils, Contnrs; type TStackForEvenNumbers = class(TStack); procedure PrintStack(Stack: TStack); begin while Stack.Count <> 0 do WriteLn(Integer(Stack.Pop)); end; var Stack: TStackForEvenNumbers; Value: Integer; begin { TODO oUser cConsole Main : Insert code here } Stack := TStackForEvenNumbers.Create; try repeat ReadLn(Value); if not Odd(Value) then Stack.Push(Pointer(Value)) until Value = 0; PrintStack(Stack); ReadLn; finally Stack.Free; end; end.

> McSimm © (04.05.07 21:37) [69]
>
> > Rouse_ © (04.05.07 21:28) [68]
>
> я твою программу ни скомпилировать ни запустить не мог,
> а свою прямо в консоли набирал, без редактора :)

Чтобы скомпилировать FASM нужен, чтобы запустить - клавиатура и винда, а твоя даже в консоли не запустилась :)

После подсказки от const (c) работы с потоками вот так получается:
#include <iostream>
void main()
{
int n;
if (std::cin>>n)
{
main();
if (!(n%2)) std::cout<<n<<" ";
}
}

кстати вот цитата из "Совершенный код" Макконелла по теме рекурсии
"Не используйте рекурсию для факториалов и чисел Фибоначчи

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

#!/usr/bin/ruby puts gets.gsub(/\d?(?:1|3|5|7|9)/, "").split(" ").reverse.join(" ")

Где мой пирожок? :)

> Не считая медленного выполнения и непредсказуемого использования
> памяти, рекурсивный вариант функции трудней для понимания,
> чем итеративный вариант:...
> Из этого примера можно усвоить три урока.

Из этого фрагмента я бы сделал свой вывод... "автор ездит по ушам" :)

Рекурсивный вариант функции трудней чем итеративный для понимания чего? Понимания вычисления факториала ????

Неужели во всех книгах этот пример используется именно для того, чтобы научить факториал вычислять ?

Или все же для понимания принципа использования рекурсивных алгоритмов ?
Так для этого итеративный вариант похоже подходит весьма слабо :)

А вот как раз чтобы понять работу рекурсии пример F(N) = N * F(N-1) подходит как нельзя лучше.

#!/usr/bin/ruby puts gets.chomp.gsub(/(|\d+)(1|3|5|7|9)( |$)/, "").split(" ").reverse.join(" ")

Вот так, вроде, корректно.

McSimm © (05.05.07 00:02) [76]
Вы не верите что если неопытному в программировании студенту показать итеративный вариант и рекурсивный вариант ему не будет понятнее итеративный?
автор не ездит по ушам, а лишь говорит, что в книгах такой мощной инструмент в борьбе со сложностью как рекурсия используется неэффективно и не выявляет всей мощи рекурсии вводя в некоторое заблуждение

> Вы не верите что если неопытному в программировании студенту
> показать итеративный вариант и рекурсивный вариант ему не
> будет понятнее итеративный?

Понятнее что ?

Тоже пятничная задачка :о) Найти похожие ветки