Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1] 2 3  Все   Вниз
  Печать  
Автор Тема: Заметки о рекурсии  (Прочитано 89511 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Dimyan
Гость
« : 25-04-2004 06:01 » 

Alf, спасибо
Статья великолепная, и я говорю это обьективно, потому что пока ты ее готовил я успел кое что уже почитать Улыбаюсь
И заявляю, что все что я нашел о рекурсии по сравнению с твоей статьей просто отжимается  :twisted:
Конкретно мне понравился стиль изложения и обилие примеров .
Не могу сказать что узнал прекрасный метод программирования - рекурсию, я ее знал, НО я ее понял наконец то! В купе с кодом по загрузке дерева, который как ты и рекомендовал я прошел по шагам в дебагере я могу с уверенностью заявить что теперь я знаю что такое рекурсия и могу применять ее на практике!
Еще я понял чего действительно не хватает для понимания рекурсии, нужно просто представить ее в обьеме, пройти по шагам не в дебагере а в голове, вот тогда после прояснения картины, она как родная становится Улыбаюсь
Записан
Dimyan
Гость
« Ответ #1 : 25-04-2004 06:03 » 

Да, и еще: Ага
Я нахожу тему интересной и с ОГРОМНЫМ удовольствием узнал бы побольше о рекурсии  Вот такой я вот
Записан
Alf
Гость
« Ответ #2 : 25-04-2004 10:37 » 

Dimyan, молодчина, что не пожалел сил и разобрался!  Улыбаюсь

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

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

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

Если хочешь поупражняться в рекурсии, вот тебе несколько задач (я думаю привести их в качестве примеров к последующим статьям; если решишь их достаточно быстро, опубликуем твое решение, если не получится - сверимся, что именно вызвало затруднения).

1) Задача о восьми ферзях.
Имеется шахматная доска 8*8 клеток и 8 ферзей. Нужно расставить ферзей таким образом, чтобы ни один из них не мог побить другого. (Заимствовано у Вирта из книги "Алгоритмы + структуры данных = программы").

2) Сравнение строки с шаблоном.
Задана произвольная текстовая строка и шаблон, который помимо символов может содержать метасимволы "?" (заменяет любой символ) и "*" (заменяет любую, в том числе пустую, последовательность символов), подобно шаблонам имен файлов. Нужно определить, соответствует ли строка шаблону.
Например,
"dfgjr" и "d*kc" не соответствуют, а
"dgjryseaerdt" и "dg*er?t" - соответствуют.
(Задача взята из реальной жизни, когда несколько лет назад мои знакомые делали собственную поисковую систему. Человек, считавший себя гуру С++, заключил со мной пари на ящик импортного пива, что напишет более компактную и корректную программу, но неумение работать с рекурсией привело его к проигрышу).

3) Раскраска географической карты.
Дана плоская географическая карта. Нужно раскрасить ее таким образом, чтобы никакие два региона, имеющие общую границу, не были окрашены одним цветом (как обычно и красятся карты). Необходимо при этом использовать минимальное количество красок.
Есть теорема (доказанная относительно недавно), что ЛЮБУЮ карту можно покрасить всего четырьмя красками. Проверь ее в деле! (Заимствовано из книги Ч. Уэзерелла "Этюды для программистов").
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #3 : 25-04-2004 12:22 » 

Цитата

доказанная относительно недавно


а я не видел доказательства - где можно посмотреть?
(те книги, где я встречал эту теорему, она была ещё в статусе - "не имеет доказательств, но работает")
Записан

Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #4 : 25-04-2004 13:10 » 

Alf, сбрось мне на мыло пожалуйста функцию сравнения которую ты писал по рекурсии - дабы время сэкономить - началось у меня опять - поджимает немного!
Вот это!!!
Цитата
2) Сравнение строки с шаблоном.
Записан

А птичку нашу прошу не обижать!!!
Alf
Гость
« Ответ #5 : 25-04-2004 16:57 » 

Цитата: Гром
Alf, сбрось мне на мыло пожалуйста функцию сравнения которую ты писал по рекурсии - дабы время сэкономить - началось у меня опять - поджимает немного!
Вот это!!!
Цитата
2) Сравнение строки с шаблоном.
Гром, это было почти 10 лет назад, где-то в 1995-м, на Borland C++ 3.1 под DOS... Само собой, с тех пор очень мало что уцелело, даже дискеты тогдашние 5.25 дюйма уже не читаются...  Жаль
Но надеюсь, что программировать с тех пор не разучился  Ага
Если тебе нужно для дела, то с этой задачи как раз и начну.
Записан
Alf
Гость
« Ответ #6 : 25-04-2004 17:42 » 

Цитата: Алексей1153
Цитата

доказанная относительно недавно


а я не видел доказательства - где можно посмотреть?
(те книги, где я встречал эту теорему, она была ещё в статусе - "не имеет доказательств, но работает")
Вот первое упоминание доказательства, которое мне удалось найти: Steen L.A. Solution of the Four Color Problems. Mathematics Magazine, 49, 4, September 1976.
Должен сказать, что доказательство не из тех ,которые поражают изяществом: вначале было доказано, что все возможные конфигурации сводятся к 1936 случаям, а затем было проверено при помощи компьютера, что каждый из этих случаев может быть раскрашен 4-мя красками.
Чтобы не быть голословным, цитирую самих авторов, Аппеля и Хакена: "Читатель должен разобраться в 50 страницах текста и диаграмм, 85 страницах с почти 2500 дополнительными диаграммами, 400 страницами микрофишей, содержащими еще диаграммы, а также тысячи отдельных проверок утверждений, сделанных в 24 леммах основного текста. Вдобавок читатель узнает, что проверка некоторых фактов потребовала 1200 часов компьютерного времени, а при проверке вручную потребовалось бы гораздо больше. Статьи устрашающи по стилю и длине, и немногие математики прочли их сколько-нибудь подробно".
Записан
Dimyan
Гость
« Ответ #7 : 26-04-2004 03:40 » 

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

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

P.S.: Повспоминал свои старые программы написанные на C++ Builder и ужаснулся над моим придумыванием велосипеда, ведь сколько было гемороя (реально помню две таких программки, ох и помучался я с ними), а все могло решится элегантной рекурсией
Записан
Never
Команда клуба

ua
Offline Offline
Пол: Женский

« Ответ #8 : 26-04-2004 07:48 » 

Добралась, наконец реально прочитать твою статью. Альф- нет слов: просто здорово написал. Я, конечно, в тебе и не сомневалась, Ага  но все-таки - статья вышла просто СУПЕР!!!
Дальше? Конечно- надо!
Записан

не умеете летать- не мучайте метлу!
Alf
Гость
« Ответ #9 : 26-04-2004 08:32 » 

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

Dimyan, давай сделаем так: поскольку Грому решение задачи по сопоставлению строкии шаблона нужно прямо сейчас, то я сегодня вечером напишу его по памяти и отправлю ему, но обнародовать не буду, чтобы не навязывать тебе свой подход. Когда твое решение будет готово, мы их сопоставим. Уверен, ты будешь просто изумлен красотой и компактностью функции.
Кстати, если найдется кто-то желающий представить итеративное решение этой или остальных задач, милости просим. Думаю, сравнение этих двух подходов будет весьма познавательным.

Всем: если у кого есть интересные задачи и вы подозреваете, что рекурсия подходит для их решения, - присылайте, попробуем решить их вместе. Чтобы продолжение статей о рекурси не заглохло, нужны интересные и полезные на практике примеры.
Записан
Dimyan
Гость
« Ответ #10 : 26-04-2004 10:22 » 

Alf, у меня уже кое что получилось (точнее все работает), но зашел в тупик с алгоритмом сравнения при введенной звездочке (*), с этим пока никак  Так больше нельзя...
Записан
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #11 : 26-04-2004 10:23 » 

Alf, я в принципе могу и сам написать - но если по ходу пойдет то очень даже было бы не плохо поиметь функцию в которую введя две строки с * ? получить ответ равны или нет...
Заранее Спасибо.

А за статьи твои не просто спасибо, а ОГРОМНОЕ спасибо.
Мне очень приятно сознавать, что такие люди как ты здесь!!!
Записан

А птичку нашу прошу не обижать!!!
Alf
Гость
« Ответ #12 : 26-04-2004 10:55 » 

Dimyan, покажи, что уже получилось.
А "звездочка"-то и есть изюминка в этой программе. Если бы не она, то и без рекурсии бы превосходно обошлись, просто шли по строкам и посимвольно сравнивали. Чуть сложнее стандартной strcmp.

Гром, если есть идеи, как писать такую функцию, поделись. Интересно сравнить разные подходы. А вечером я тебе свой вариант вышлю.
Записан
Dimyan
Гость
« Ответ #13 : 26-04-2004 11:35 » 

Только вот это Жаль
Код:
private void Comparison(int Length)
{
if((Length+1)<= textBox1.Text.Length)
{
if(((textBox1.Text[Length] == textBox2.Text[Length])||(textBox2.Text[Length]=='?')))
{
Length++;
Comparison(Length);
}
else
{
MessageBox.Show("Строки не равны");
}

}
else MessageBox.Show("Строки равны");

}
« Последнее редактирование: 25-11-2007 17:45 от Алексей1153++ » Записан
Alf
Гость
« Ответ #14 : 26-04-2004 12:06 » 

Dimyan, мне не понравилось...  Жаль

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

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

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

Вот тебе небольшая наводка, как делал я.
Представь строку в виде "первый символ" + "хвост". То же самое сделай и с шаблоном. А потом рассмотри, при каких условиях строка соответствует шаблону при таком подходе. Там всего-то несколько вариантов получается, и все либо простые, либо очень простые.
Записан
Dimyan
Гость
« Ответ #15 : 26-04-2004 12:24 » 

Хорошо попробую
Записан
Alf
Гость
« Ответ #16 : 26-04-2004 22:53 » 

Dimyan, Гром, набросал вчера функцию сопоставления строки и шаблона. Вот что у меня получилось:
Код:
const char asterisk = '*';
const char question = '?';
const char endofline = '\0';

bool PattCmp(const char *s, const char *p)
{
  if (!*s && !*p)
    return true;
  else if (!*p)
    return false;
  else if (!*s)
    return ((asterisk == *p++) && (endofline == *p));
  else if (asterisk == *p)
  {
    if (endofline == *++p)
      return true;
    else
    {
      bool f;
      do
        f = PattCmp(s++, p);
      while (!f && *s);
      return f;
    }
  }
  else if (question == *p)
    return PattCmp(++s, ++p);
  else
    return (*p == *s) ? PattCmp(++s, ++p) : false;
}
Набросал по-быстрому, поэтому мог ошибиться. Если кто найдет входные данные, которые неправильно обрабатываются, сообщите мне, буду благодарен, т.к. функция пойдет примером в следующую статью о рекурсии.
Напоминаю, что в шаблоне помимо обычных символов могут быть два метасимвола: "?" заменяет любой символ, "*" - любую последовательность символов (в том числе пустую).
« Последнее редактирование: 25-11-2007 17:47 от Алексей1153++ » Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #17 : 27-04-2004 06:54 » 

Красиво!  Получил большое удовольствие, разбираясь в твоей функции.

В POSIX есть аналогичная функция fnmatch, заточенная под сравнение имён файлов.  Но у меня нет под руками сорсов glibc, чтобы сравнить.
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Alf
Гость
« Ответ #18 : 27-04-2004 07:25 » 

Цитата: npak
Красиво!  Получил большое удовольствие, разбираясь в твоей функции.

Рекурсия, примененная к месту, всегда чертовски красива  Улыбаюсь
Особенно это заметно, если сравнить эту функцию с ее итеративным собратом (который к тому же садился в калошу на некоторых сложных шаблонах).
Цитата
В POSIX есть аналогичная функция fnmatch, заточенная под сравнение имён файлов.  Но у меня нет под руками сорсов glibc, чтобы сравнить.

Интересно было бы сравнить. Мне попадались подобные функции для имен файлов, но они имели ограничения на вид шаблона (например, не более одной звездочки и т.п.)
Записан
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #19 : 27-04-2004 08:13 » 

Alf, я проверю, мне как раз это будет надоть!!!!
Записан

А птичку нашу прошу не обижать!!!
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #20 : 27-04-2004 08:53 » 

Цитата: Alf
Рекурсия, примененная к месту, всегда чертовски красива


 Я шокирован!  

"To iterate is human, to recurse divine" L. Peter Deutsch
("Итерация свойственна человеку, рекурсия - божественна")

А ты говоришь... "чертовски" Ага
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Alf
Гость
« Ответ #21 : 27-04-2004 09:04 » 

Джон, поскольку рекурсия мне тоже некоторым образом свойственна (чему есть многочисленные свидетели), не мог же я сказать, что она "божественно красива". Окружающие сочтут это нескромным, мол, сам себе скрытый комплимент делаю  Ага
А так вроде нейтрально получилось, даже учтиво по отношению к коллеге из преисподней  Улыбаюсь
Записан
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #22 : 27-04-2004 10:42 » 

Alf,  Отлично
Записан

А птичку нашу прошу не обижать!!!
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #23 : 27-04-2004 11:36 » 

Понимаю - единство и борьба противоположностей - Отлично  Отлично
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
ysv_
Помогающий

ua
Offline Offline

« Ответ #24 : 28-04-2004 07:45 » 

Цитата

Набросал по-быстрому, поэтому мог ошибиться. Если кто найдет входные данные, которые неправильно обрабатываются, сообщите мне, буду благодарен, т.к. функция пойдет примером в следующую статью о рекурсии.

Alf, при следующих данных твоя функция возвращает неправильный результат: PattCmp("", "**");
Записан
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #25 : 28-04-2004 07:59 » 

ysv_, добавь проверку - if (strlen(first_str) == 0) return false;
Записан

А птичку нашу прошу не обижать!!!
ysv_
Помогающий

ua
Offline Offline

« Ответ #26 : 28-04-2004 08:10 » 

Цитата

ysv_, добавь проверку - if (strlen(first_str) == 0) return false;

ГРОМ, Так она и возвращает false, а должна true.
Записан
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #27 : 28-04-2004 08:12 » 

Неа - строка не содержащая ничего не должна возвращать что равна содержащей строке - тут ты не прав!

Если я проверяю ввденный параметр на наличие двух букв - с пустой строкой - как они могут быть равны???
Записан

А птичку нашу прошу не обижать!!!
ysv_
Помогающий

ua
Offline Offline

« Ответ #28 : 28-04-2004 08:33 » 

* - обозночает любое количество букв, в том числе - н_у_л_е_в_о_е. О!
Записан
Alf
Гость
« Ответ #29 : 28-04-2004 08:37 » 

Гром, формально ysv_ прав - звездочка может означать пустую строку, и любое количество звездочек подряд - тоже.

ysv_, спасибо за тест, придется подлатать 3-й return.

Гром, вопрос к тебе, как к потенциальному потребителю функции: где она будет применена и имеет ли смысл в этом приложении сравнивать пустую строку с шаблоном? Можешь привести реальный пример?
Записан
Страниц: [1] 2 3  Все   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines