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

← →
Юрий Зотов © (2007-05-04 14:51) [0]

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

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

Писать можно на любом языке.

← →
Rouse_ © (2007-05-04 14:54) [1]

Стандартный stdin-sdtout, СОМ или что именно?

← →
Юрий Зотов © (2007-05-04 14:55) [2]

stdin-stdout

← →
Rouse_ © (2007-05-04 14:56) [3]

Рамер данных определяется заранее, или вывод данных производится по пинку?

← →
Юрий Зотов © (2007-05-04 15:01) [4]

Как угодно.

← →
MBo © (2007-05-04 15:17) [5]

может, какой хитрый прием имеется в виду?
А то с использованием *** пара минут потребовалась...

← →
Юрий Зотов © (2007-05-04 15:20) [6]

Так она за пару минут и пишется. Просто интересно, кто выдаст самый короткий и одновременно самый понятный вариант, подобрав для этого самый подходящий инструмент (язык).

← →
Romkin © (2007-05-04 15:47) [7]

program Project1; {$APPTYPE CONSOLE} procedure PrintEven; var A: integer; begin repeat readln(A); until ((A and 1) = 0); if A <> 26 then PrintEven; writeln(A); end; begin PrintEven; end.

← →
Romkin © (2007-05-04 15:50) [8]

А нафига?

← →
Юрий Зотов © (2007-05-04 16:02) [9]

> Romkin © (04.05.07 15:50) [8]

Хитрый ход, но не понял проверки на 26.

А на фига? Как и все задачки - кто-то мозги разомнет, кто-то поупражняется, кто-то поучится...

← →
Юрий Зотов © (2007-05-04 16:05) [10]

> не понял проверки на 26.

Если имелось в виду ^Z, то проверка должна быть другой.

← →
Romkin © (2007-05-04 16:09) [11]

А чем не нравится проверка? Бодун у меня, поэтому и 26...
Кто Штирлиц - пусть поменяет на 44
Условиям задачи удовлетворяет :-Р

← →
umbra © (2007-05-04 16:25) [12]

не на паскале :)

#!/usr/bin/perl -w use strict; my $line; my @data; while ($line = <STDIN>) { chomp $line; if (!($line =~ /\D/) and $line) { if ($line % 2 == 0) { unshift @data, $line; } } } print "\n\n\n"; foreach my $number (@data) { print $number."\n"; }

← →
clickmaker © (2007-05-04 16:29) [13]

#include <stdio.h> #include <string.h> #include <stdlib.h> void main(void) { char strDigits[512]; gets(strDigits); char* token = strDigits + strlen(strDigits); while (token != strDigits) { if (*token == " ") { int digit = atoi(token); if ((digit % 2) == 0) printf("%d ", digit); *token = 0; } token--; } }

← →
McSimm_ © (2007-05-04 16:43) [14]

@_=(<>);
while ($a = pop @_ ) { print $a unless ($a % 2) }

Наверняка можно короче, подзабыл уже.

← →
Romkin © (2007-05-04 16:56) [15]

clickmaker © (04.05.07 16:29) [13] И опять, млин, дыра переполнения буфера :(

← →
umbra © (2007-05-04 16:59) [16]

2 McSimm_ © (04.05.07 16:43) [14]

будет печатать в обратном порядке все строки (не числа) и четные числа

← →
clickmaker © (2007-05-04 17:11) [17]

> [15] Romkin © (04.05.07 16:56)

я в 2003 студии писал. В 2005 заюзал бы gets_s

← →
McSimm_ © (2007-05-04 17:14) [18]

> будет печатать в обратном порядке все строки (не числа)
> и четные числа

Именно так.
В условии не написано, что программа читает строки и выбирает из них числа :)

Вот еще похожий пример.
<?php array_walk(array_reverse(file("php://STDIN")), create_function("$a","print ($a%2?"":$a);")); ?>

← →
clickmaker © (2007-05-04 17:16) [19]

впрочем, можно fgets(strDigits, sizeof(strDigits), stdin);

← →
McSimm_ © (2007-05-04 17:17) [20]

[14] все же больше удовлетворяет условиям понятности, на мой взгляд :)

← →
McSimm_ © (2007-05-04 17:21) [21]

> umbra © (04.05.07 16:25) [12]
> if (!($line =~ /\D/) and $line) {

Проверка не соответсвует множеству целых чисел :)

← →
begin...end © (2007-05-04 18:13) [22]

var
N: Integer;

begin
with TStack.Create do
try
repeat
ReadLn(N);
if not Odd(N) then Push(Pointer(N))
until N = -1;
while Count <> 0 do
WriteLn(Integer(Pop));
ReadLn
finally
Free
end
end.

← →
Суслик © (2007-05-04 18:18) [23]

хи-хи
юра не может задачу решить?! а мы решай?! :-0

← →
umbra © (2007-05-04 18:22) [24]

да, забыл об отрицательных числах :( Вот как надо:

#!/usr/bin/perl -w use strict; my $line; my @data; while ($line = <STDIN>) { chomp $line; if ($line =~ /^-?\d*/ && $line % 2 == 0) { unshift @data, $line; } } print "\n\n\n"; foreach my $number (@data) { print $number."\n"; }

← →
McSimm_ © (2007-05-04 18:28) [25]

> да, забыл об отрицательных числах

И нуле (в первом варианте)

← →
default © (2007-05-04 18:28) [26]

да наиболее очевидный это вставлять чётные числа в динамический список методом Insert(0, NewEvenNumber) и потом вывод в цикле

← →
Rouse_ © (2007-05-04 18:55) [27]

http://rouse.drkb.ru/yz_test.zip
Там бинарник и исходник. Меньше некуда - все по условиям задачи :)

← →
McSimm_ © (2007-05-04 19:04) [28]

> Rouse_ © (04.05.07 18:55) [27]

Программа на 120 строк, это меньше некуда? :)

← →
Rouse_ © (2007-05-04 19:25) [29]

> Программа на 120 строк, это меньше некуда? :)

Эээ... а при чем тут строки? Я ориентировался на размер скомпиленого кода :) Разве не это нужно было?

← →
Rouse_ © (2007-05-04 19:27) [30]

Да и кода там реально 38 асмовских строк :) Если считать только код с джампами :)

← →
Внук © (2007-05-04 19:54) [31]

Задачка, разумеется, есть стандартная иллюстрация к теме "рекурсия". Либо к теме "стек". А уж кто как извратится, это от степени испорченности зависит :)

← →
default © (2007-05-04 19:57) [32]

рекурсия тут совсем ни к месту
keep it simple, stupid
а если брать стек и подобное, то уж лучше Insert в 0 позицию, что поймёт всяк и каждый

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

>рекурсия тут совсем ни к месту
>а если брать стек и подобное,

Рекурсия ни к месту, а стек - к месту. А рекурсивный стек (стек вызовов) - к месту или ни к месту?

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

Alx2 © (04.05.07 20:03) [33]
разговор совсем не про то...я знаю что рекурсия через стек реализуется...о боже...буквоедство очередное...речь о простоте кода и краткости...

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

>>default © (04.05.07 19:57) [32]
Как не к месту она, например, при вычислении факториала. Тем не менее, классические учебные задачи.

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

>default © (04.05.07 20:05)

Я и не сомневаюсь, что знаешь. Только не возьму в толк чего здесь в рекурсии туманного супротив явного стека?

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

>Внук © (04.05.07 20:05)

Да, в факториале не к месту - там не надо хранить се значения.
А здесь не вижу разницы

← →
default © (2007-05-04 20:12) [38]

Alx2 © (04.05.07 20:06) [36]
просто когда пишешь код полезно предполагать о том, что его будут читать люди достаточно низкой квалификация
это маленькая хитрость заставляющая писать как можно более простой код
в конечном итоге этим самым "низкоквалицифированным" можешь оказать ты сам просматривающий код, например, для целей сопровождения который уже ничерта об этом коде уже не помнит
рекурсия тут проста, но многие люди не очень её понимают, что может вызвать замешательстов даже в таком простом случае рекурсии
Внук © (04.05.07 20:05) [35]
я не отрицаю рекурсию в общем случае:)
я к тому что если можно написать нерекурсивный код не меньшей понятности и краткости чем рекурсивный вариант, то лучше именно его и написать

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

>>Alx2 © (04.05.07 20:08) [37]
Я вообще не вижу разницы :) Это лишь вопрос того, где кушать память - в массиве, списке или стеке вызовов. Думается, кратчайший по количеству строк кода вариант будет при рекурсии.

← →
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]

Псиб...

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

← →
McSimm © (2007-05-04 21:37) [69]

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

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

← →
Kolan © (2007-05-04 22:15) [70]

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

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

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.

← →
Rouse_ © (2007-05-04 22:15) [71]

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

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

← →
Alx2 © (2007-05-04 22:31) [72]

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

← →
default © (2007-05-04 23:38) [73]

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

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

← →
Zeqfreed © (2007-05-04 23:57) [74]

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

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

← →
default © (2007-05-04 23:58) [75]

Zeqfreed © (04.05.07 23:57) [74]
на эйфелевой башне, залезешь - твой

← →
McSimm © (2007-05-05 00:02) [76]

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

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

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

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

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

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

← →
Zeqfreed © (2007-05-05 00:04) [77]

> default © (04.05.07 23:58) [75]

Там кстати неправильный регексп :(
Щас исправить попытаюсь.

← →
Zeqfreed © (2007-05-05 00:07) [78]

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

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

← →
default © (2007-05-05 00:08) [79]

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

← →
McSimm © (2007-05-05 00:09) [80]

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

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

> Если бы программист, работающий у меня, применял рекурсию
> для вычисления факториала, я бы нанял кого-то другого.

Я вот сидел и долго думал, а вот в каком ракусе тогда можно применить рекурсивный алгоритм в плане обучения? Я вот сидел и долго думал, а вот в каком ракусе можно описить "мощность" рекурсионного алгоритма? Я вот сидел и долго думал, а вот сколько у тебя сейчас работает програмистов? :)

Rouse_ © (05.05.07 00:09) [81]
в ракурсе, например, поиска выхода в лабиринте
McSimm © (05.05.07 00:09) [80]
понять как оно работает или хотя бы что оно делает

> ракурсе, например, поиска выхода в лабиринте

Вах как... Занимательно... Вот при таком прямолинейном брутфорсном подходе следует задуматься о квалификации...

> default © (05.05.07 00:11) [82]

совсем не читаете что вам пишут.

Попробую перефразировать.
Как с помощью более понятного итеративного алгоритма объяснить принципы рекурсии ?

Или вы считаете, что в книгах по программированию учат факториалы вычислять?

> рекурсивный вариант функции трудней для понимания (**чего?**),
> чем итеративный вариант:...

вот я и говорю - по ушам проехались.

Rouse_ © (05.05.07 00:13) [83]
хм
у Вас есть сравнивая по понятности итеративная версия обхода лабиринта в поисках выхода?

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

> у Вас есть сравнивая по понятности итеративная версия обхода
> лабиринта в поисках выхода?

Конечно, это-же математическая модель... Зачем рукурсивно бить лбом поле в поисках выхода, если можно рассчитать нормали на основании векторов препятствий?

Rouse_ © (05.05.07 00:21) [88]
и по понятности оно ничем не уступает?
но речь не об конкретике, может пример с лабиринтом и был не совсем удачным, вопрос в том чтобы показывать примеры рекурсии такие в которых без рекурсии было гораздо сложнее, непонятнее и тд

> вопрос в том чтобы показывать примеры рекурсии такие в которых
> без рекурсии было гораздо сложнее

Найти все *.avi на диске С - что может быть конкретней? :)

Rouse_ © (05.05.07 00:27) [90]
вполне вариант, кто ж спорит
вот я спецом открыл щас одну книгу с разделом про рекурсию
там как раз Фибоначчи через рекурсию и итерацию
и сказано лишь, что с рекурсией - лаконичнее
так что Макконелл прав со своими обвинениями пусть и чуть-чуть перегибает

> Макконелл прав со своими обвинениями пусть и чуть-чуть перегибает

Рекурсия это билет в оба конца.

Да кстати, Сань, завязывай называть меня на Вы - чай не первый день на форуме :)

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

И что-б максимально просто и понятно. :)

← →
Зюзя (2007-05-05 04:11) [95]

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

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

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

Во-первых, потому что использование очень даже предсказуемое: для 64-битных вычислений максимальный результат при вычислении 65!, дальше - переполнение, что является ограничением для любого алгоритма (использование сверхбольших чисел и специальных алгоритмов не беру во внимание), а на 65 рекурсивных вызовах ничего непредсказуемого произойти не может.

А во-вторых, с такой позиции, увольнять надо любого, кто вообще для этого хоть какие-то алгоритмы использует, ибо для 65 чисел надо использовать заранее просчитанную табличку. И Range Check. И все. Никаких алгоритмов. И выполнение быстрое, и непредсказуемости никакой.

P.S. И запись в трудовой книжке: "Он не умел считать факториал"...

> для 64-битных вычислений максимальный результат при вычислении
> 65!,

Ни разу не так, обвал произойдет гораздо раньше.

← →
Зюзя (2007-05-05 05:19) [97]

Виндовый калькулятор работает с 8-байтными числами.
И функция факториала в нем есть.
Проверить можно.

<?php class chisla { var $num = array(); /** * Добавляем число * * @param integer $c */ function add( $c ) { if ( !is_float($c) ) { $this->num[] = $c; } } /** * Выводим * */ function show() { foreach ( array_reverse( $this->num ) AS $chislo) { if ( fmod( $chislo, 2) == 0 ) { print $chislo . "<br>"; } } } } $z = new chisla(); /** * Заполняем любыми числами */ $z->add(15); $z->add(5); $z->add(6); $z->add(-5.2); $z->add(7.88888); $z->add(0.9999); $z->add(1); $z->add(0.2); $z->add(-8); /** * Выводим числа по условию */ $z->show(); ?>

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

default © (04.05.07 19:57) [32]
рекурсия тут совсем ни к месту
keep it simple, stupid
а если брать стек и подобное, то уж лучше Insert в 0 позицию, что поймёт всяк и каждый
Зато рекурсия, в отличии от TStack, сохраняет эффективность проги.

Rouse_ c (05.05.07 00:21) [88]

> у Вас есть сравнивая по понятности итеративная версия обхода
> лабиринта в поисках выхода?

Конечно, это-же математическая модель... Зачем рукурсивно бить лбом поле в поисках выхода, если можно рассчитать нормали на основании векторов препятствий?
Вряд ли это будет лучше.

Все зависит от того, что дальше с нормалями делать.

Вариант на PL/1. Прост до безобразия, потому что использует встроенные в сам язык стековые переменные. По той же причине не требует никаких дополнительных модулей, библиотек и т.п.

example: procedure options(main);
dcl I controlled;
on endfile(sysin)
begin
free(I);
goto L2;
end;
L1: allocate(I);
get list(I);
if I and 1 = 1 then free(I);
goto L1;
L2: do while(allocation(I));
put list(I);
free(I);
end;
end example;

Задачка в некоторой степени классическая и, имхо, довольно интересно посмотреть, как она решается разными средствами. Вариант [78] потряс меня своей лаконичностью, но что касается простоты - имхо, без бутылки в нем фиг разберешься.
:о)

> Зюзя (05.05.07 05:19) [97]

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

> GrayFace © (05.05.07 11:20) [99]

Хотя я и знал, что "правильно" через рекурсию, но когда у меня на одном собеседовании возникла и эта задача, то я решил ее без оной. Что я читал не так? Видимо, читая надо видеть и еще что-то кроме фиги?
:)

> Юрий Зотов © (05.05.07 13:42) [101]

Ну, собственно тогда Alx2 в точку пробил о ветке с функязыками - про встроенные в язык средства.

Думкин © (06.05.07 5:05) [102]
Хотя я и знал, что "правильно" через рекурсию, но когда у меня на одном собеседовании возникла и эта задача, то я решил ее без оной.
Видимо на собеседовании была цель решить именно это задачу, а не побыстрее набить код чтоб работало.

> GrayFace © (07.05.07 01:25) [103]

Штука в том, что не факториал в учебниках вычисляют, а на его примере показывают суть рекурсии. Не более. Если это понимать, то проблем никаких не возникает.

> GrayFace © (07.05.07 01:25) [103]

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

Думкин, тут вопрос в том, что вычисление факториала через рекурсию мало что дает. Рекурсию-то он объясняет, но не объясняет ее возможностей и путей применения.
Это годится, как и бассейн с трубами, только для средних классов школы. Но никак не для серьезных учебников.

← →
mrco (2007-05-07 18:20) [108]

Что-то не видно моего любимого языка...

(print (reverse (loop while (numberp (setq r (read))) if (oddp r) collect r ) ) )

Сама задача абсурдная какая-то...
Читай ты данные в массив и выводи их с конца только четные.
А смысл данной задачи - за пределами моих умственных способностей.

> Romkin © (07.05.07 10:48) [106]

Ромкин, если дело ограничивается только факториалом - то другое дело. Но для ввода в понятие рекурсия - факториал вполне нормальный объект. В чем проблема? Я вот не пойму чем таким факториал перебежал дорогу рекурсии?

Тем, что факториал - концевая рекурсия. И легко разворачивается в цикл. И при этом создается впечатление, что рекурсия нафиг не нужна и заменяется циклом.
Почему не дать задачу, алгоритм с рекурсией для которой проще, чем без нее?

> Romkin © (08.05.07 11:35) [112]

А кто-то мешает потом и ее дать? Все-таки не вижу препятствий для иллюстрации ввода в рекурсивное через факториал. Но это уже по кругу.

> Почему не дать задачу, алгоритм с рекурсией для которой
> проще, чем без нее?

Это можно потом.
Наверное это тебе сейчас кажется все тривиальным. Хотя может ты и сразу вник. А я очень живо помню, как постигал рекурсию, как укладывал в своем представлении ее итерации. Это очень трудно в начале. И F(n)=n*F(n-1) мне очень помог, как и ряд других простых примеров, хорошо укладывающихся в воображении.

И ни капельки не помешал. Как только я прочувствовал этот метод (честно говоря я был восхищен им), начал испытывать его для совершенно разнообразных задач. (до сих пор помню свой восторг от простоты получившегося рекурсивного алгоритма решения ханойских башен из любого начального состояния.)

А уже понимание плюсов и минусов на порядок легче дается.

> А кто-то мешает потом и ее дать? Все-таки не вижу препятствий
> для иллюстрации ввода в рекурсивное через факториал. Но
> это уже по кругу.

Дык как правило не дают! :)

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