Тест ищется

← →
Romkin © (2009-09-15 14:28) [0]

Ни у кого не найдется вопросов на понимание следующего:
1. Рекурсия
2. Указатели
Не обязательно с вариантами ответов, просто вопросы на Delphi. Которые позволяют понять, а понимает ли человек что такое рекурсия и указатель, в идеале - чем указатель от ссылки отличается.
Сейчас у меня это в виде маленьких заданий, вроде "написать программу, выводящую список файлов указанного каталога и всех его подкаталогов" и "написать модуль, реализующий односвязный список, и процедуру, реализующую его реверсирование (переставляющую узлы в обратном порядке)".
Есть что-нибудь попроще?

← →
palva © (2009-09-15 14:36) [1]

Вычисление факториала, числа Фибоначчи.
Просмотр дерева, любой поиск при помощи построения дерева, напр. задача о 8 ферзях, выход из лабиринта.

Указатели - динамические структуры данных, массив массивов разной длины (без динамических массивов).

← →
Romkin © (2009-09-15 14:43) [2]

> Вычисление факториала, числа Фибоначчи.

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

И мне бы покороче, а не подлиннее :)

← →
clickmaker © (2009-09-15 14:45) [3]

> Надо такое, чтобы без рекурсии никуда.

ну тут дерево вне конкуренции

← →
boa_kaa © (2009-09-15 14:48) [4]

рекурсия без причины - признак... сами понимаете :)

← →
Romkin © (2009-09-15 14:51) [5]

А может, какой-нибудь вопрос на преобразование концевой рекурсии, из практики?

← →
Ega23 © (2009-09-15 14:55) [6]

Рекурсия - сортировка массива бинарным деревом.
Указатели - построение двусвязанного списка, удаление и добавление элементов.

← →
Romkin © (2009-09-15 14:58) [7]

> Рекурсия - сортировка массива бинарным деревом.

Кхе. Такого метода и я не знаю :)

← →
Павел Калугин © (2009-09-15 15:10) [8]

> 1. Рекурсия

Определение длины списка. (на прологе хе)

> 2. Указатели

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

← →
Павел Калугин © (2009-09-15 15:12) [9]

Про преобразование рекурсии в цикл дома есть запросик на сиквеле. Который до сих пор надо размотать в цикл. То есть задача без ответа.

← →
MBo © (2009-09-15 15:16) [10]

>Надо такое, чтобы без рекурсии никуда.
Такого практически нет. Например, функцию Аккермана без рекурсии написать исключительно трудно, а почти все остальное - можно. Разве что подобрать примеры, когда нерекурсивно будет слишком развесисто...

Про деревья уже сказали, можно в готовом заполненном TreeView сумму длин заголовков узлов посчитать.
Комбинаторика - число сочетаний вычислить рекурсивно на основе данной соотв. формулы, или числа Стирлинга первого или второго рода.

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

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

Из математики,если это не испугает - - взятие интеграла cos^n(x) по частям (формулу интегрирования по частям дать)

Реализовать рекурсивную закраску FloodFill - если человек имеет понятие о рекурсии, это займет несколько минут. Более сложно по графике - кривые типа Пеано или снежинки Коха.

← →
jack128_ (2009-09-15 15:44) [11]

> Определение длины списка. (на прологе хе)

да хоть на дельфи ;-) рекурсивный алго определения длины на любом языке одинаков...

← →
jack128_ (2009-09-15 16:01) [12]

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

ну например
procedure WriteString(const S: string); var I: Integer; begin for I := 1 to Length(S) do WriteChar(S[I]) end;
=>
procedure WriteString(const S: string); procedure _WriteString(const S: string; CharIndex: Integer); begin WriteChar(S[CharIndex]); if CharIndex < Length(S) then _WriteString(S, CharIndex + 1); end; begin if Length(S) > 0 then _WriteString(S, 1);

← →
Eraser © (2009-09-15 16:45) [13]

> 1. Рекурсия

перечисление всех файлов в каталоге и вложенных каталогах.

← →
vuk © (2009-09-15 16:45) [14]

>1. Рекурсия
Обход дерева каталогов.

← →
clickmaker © (2009-09-15 16:49) [15]

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

← →
jack128_ (2009-09-15 16:52) [16]

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

рекурсией дерево обойти может и обезьяна.. Это не дает понимания.

← →
vuk © (2009-09-15 16:52) [17]

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

← →
vuk © (2009-09-15 16:55) [18]

Не, конечно, можно еще попросить развернуть рекурсию в итерацию. Ну, например, QuickSort нерекурсивный нписать. Но это жестко. :)

← →
SP (2009-09-15 18:12) [19]

Надо такое, чтобы без рекурсии никуда.

Такого не бывает.

← →
SP (2009-09-15 18:13) [20]

Хм, процитировать забыл

> Romkin © (15.09.09 14:43) [2]
>
> ...
> Надо такое, чтобы без рекурсии никуда.

Вобщем такого не бывает.

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

> Из математики,если это не испугает - - взятие интеграла
> cos^n(x) по частям (формулу интегрирования по частям дать)

Вот это неплохо, спасибо. Хотя и не в тему немного

> Про деревья уже сказали, можно в готовом заполненном TreeView
> сумму длин заголовков узлов посчитать.

А вот это почти в тему...

Стесняюсь спросить: а чем ссылка от указателя отличается? На примере, если можно.

> написать модуль, реализующий односвязный список

Не люблю неясных задач. Непонятно для чего и как реализовать оптимальнее, где можно оптимизировать. И, честно говоря, не совсем понятно что такое односвязный. Это типа указателя на подобную структуру:
PListItem=^TListItem; TListItem = record ItemValue: TItemValue; NextItem: PListItem; end;

У попа была собака,
Он ее любил.
Она съела кусок мяса
Он ее убил.
В землю закопал, надпись написал, что...

Из практики - это не совсем задача. Вот например: есть структура данных, которые грузятся из файла (переменные а, б, в, ...) и потом еще кое что там рассчитывается (переменные a, b, c, ...). Парсер имеется, написан N лет назад. Требуется написать процедуру преобразования этой структуры, которое состоит в том, что меняются значения а, б, в, ... по определенным правилам до тех пор, пока согласно этим правилам изменение не окажется невозможным. Беда в том, что правила опираются на текущие значения a, b, c, ..., которые в свою очередь, есс-но меняются.

Да, можно взять готовый парсер и вызывать у него процедуру "расчитать a, b, c, ...". Если она там есть. А ее там нет, потому что такой задачи N лет назад никто не предвидел. Поэтому и по нек. другим причинам парсер я склонен рассматривать как черный ящик и ничего там не трогать. Отсюда решение:

Каждый раз после пересчета выгружаем а, б, в, ... в стринглист в формате, понимаемом парсером. Уничтожаем предыдущий объект, создаем новый, грузим из стринглиста. Парсим, вызываем процедуру заново. exit.

> И, честно говоря, не совсем понятно что такое односвязный.
> Это типа указателя на подобную структуру:

да. N-й элемент имеет ссылку на N+1-й.
Двусвязнвй - ещё и на N-1-й

Тест ищется Найти похожие ветки