Сначала письмо.

Давно читаю Вашу рассылку "Школа программирования: базовый курс" (жаль, не застал того момента, когда все это выходило и можно было переписываться).
Ну ничего, не все потеряно. Я все уроки до этого прошел самостоятельно и никаких проблем не было.
В последнем выпуске прочитал про Лисп (очень понравилась концепция этого языка) и задачи. Заинтриговало сообщение о том, что вторую могут решить 0.1%, а третью - 0.1% от тех 0.1%. Взялся решать... и быстро понял, что все гениальное - просто.
Решение первой задачи не отправляю ввиду его тривиальности. Рассмотрим вторую и третью. Я пишу решение в виде словесного алгоритма, так как мои способности в кодинге сильно отстают от навыка решения головоломок, но благодаря Вашей рассылке это скоро пройдет)
Задача вторая: решение выглядит следующим образом.
1)создаем дерево. Видим первую открывающую скобку
2)если после скобки встретилось число - добавляем к корню лист с записью этого числа
3)если встретилась еще одна открывающая скобка - спускаемся на уровень вниз (добавляем узел)
Повторяем пункты 2 и 3 уже не для корня, а для соответствующего узла, пока не упремся в закрывающую скобку. Возвращаемся на уровень выше.
4)Повторяем пункты 2 и 3, при необходимости спускаясь вниз, пока не упремся в последнюю скобку.
Это рекурсивный алгоритм и ИМХО его не так сложно реализовать. После всех этих манипуляций получаем дерево, соответствующее списку.
После чего берем значение нужного атома и начинаем обходить дерево, записывая путь. Если мы спустились - пишем 1, поднялись - пишем -1. Так и делаем пока не найдем нужный атом. Тогда получаем последовательность обхода в виде длинной цепочки единиц и нулей. Дальше считаем сумму того что вышло: как только стала равна нулю - все что до этого было вычеркиваем и пишем R. И так до конца. Получаем несколько букв R и последовательность 1 и -1. Заменяем единицу на F, после чего повторяем процедуру суммирования и вычеркивания, пока не останутся одни буквы. Получившаюся последовательность из R и F преобразуется в текст на раз-два. Как видно, задача совсем не сложная, ведь то что мы получили - работает, правда очень трудоемко, но ведь компьютеру на что даны его гигагерцы?) Вот если бы была дана задача сделать решение более рациональным чем простой обход, тогда да...
Что касается третьей задачи, то... я ее решил, но я не гений, так как она настолько проста, что ее любой школьник-нераздолбай решит. Она не в тысячу раз сложнее второй, как сказано в задании, напротив - она в 10 раз проще.
Решение такое. Рассмотрим тривиальный список из целых чисел от 1 до 10, и пусть N для определенности равно четырем.
Тогда сколько бы мы ни применяли операции first и rest, атомы от 1 до 3 мы не получим, так как ЛЮБЫЕ наши преобразования затронут лишь часть списка начиная с четвертого атома. То есть мы можем просто отбросить первые 3 атома как недоступные, после чего уменьшить N на 3. Номер каждого элемента уменьшится на 3, в результате операции first и rest будут влиять на ПЕРВЫЕ элементы нового списка. То есть, в общем случае решение такое:
1)атомы с 1 по N-1 включительно недостижимы
2)задача доступа к атомам с N до последнего сводится к получению доступа к нашему списку без первых N атомов при N=1.
Если список нетривиален и состоит из более сложных элементов, от этого ничего не меняется. Обходим первые N ветвей сложного дерева, считая листы. Сколько насчитали - столько и недостижимо, а как попасть к достижимым - смотрим задачу 2.
Единственное, что я не придумал пока, это алгоритм создания и обхода дерево (не силен я в рекурсии), но насколько я знаю они существуют, и их написание выходит за рамки нашей задачи, точно так же как в задачу "сложить а и b и вывести на экран" не входит разработка вывода, достаточно просто набрать cout...
Да, кстати, Вы же ведь наверняка задачу решили, а нам для пущего интереса сказали что не решили, не так ли?)
Red_fox

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

В данном случае действительно не получилось качественно повысить уровень сложности при переходе от Л2 к Л3, в основном потому, что Л3 во многом представляет собой Л2 с настраиваемыми параметрами. Да и сама она была сформулирована недостаточно корректно - если мы задаем N-й элемент на выбор/отбрасывание, то рано или поздно возникнет ситуация, когда в списке будет меньше N элементов и неясно, что делать в таком случае. Один подписчик предложил заменить выбор N на "выбор N или выбор последнего элемента в списке в случае невозможности выбора N". Но это все же техническое усложнение, а не смысловое.

Более наглядной в плане СуперУма :) будет следующая задача.

Имеется некий входной язык программирования, (например, Паскаль), синтаксис которого формально описан набором правил. Существуют специальные нотации, которые позволяют описывать допустимые синтаксические конструкции конкретного языка. Например, форма Бэкуса-Наура.

Имеется также некий выходной язык программирования (например, Си). Этот выходной язык также описан некоторым способом на мета-языке.

Задача для СуперУма. Написать программу, которая будет получать на входе описание входного и выходного языков и правила взаимного преобразования синтаксиса операторов, и станет генерировать исходный текст программы (например, на Дельфи или Лиспе), которая будет переводить программу на заданном входном языке в программу на заданном выходном языке.

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

Например, на вход нашей программы (СУПУМ :) подаем формальное описание синтаксиса языков Си++ и Object Pascal (какие конкретно будут языки, СУПУМ, конечно, не подозревает, ему все равно, для него это просто входные данные, настраиваемые параметры), и правила соответствия операторов одного языка операторам другого языка. СУПУМ работает, несколько часов :) , и выдает исходный код нужного компилятора, написанный например на Дельфи. Далее этот код можно скомпилировать, получить рабочую программу, и далее скармливать ему тексты программ на С++ - они будут преобразованы в Object Pascal.

А в следующий раз СУПУМу можно подать на вход описание Фортрана и Лиспа, и он сгенерирует код на Дельфи, который будет преобразовывать Фортран-тексты в Лисп-тексты.

Кстати, наш гениальный соотечественник Владимир Турчин разработал в 80-х годах язык РЕФАЛ, который хорошо подходит именно для подобных задач. Кому интересно, могут познакомиться в ним тут:
http://www.refal.net
http://offline.computerra.ru/2001/402/10900/

По поводу Л2/Л3. Подписчик Максим прислал код на Дельфи для Л2, а также решение и для Л3! :)

Вот его письмо:

Алгоритм получился вот таким:
1) Ищем в заданной строке заданный атом.
2) Начинаем просматривать строку до закрывающей скобки данного списка, и определяем номер атома в этом списке. Если в данном списке будет вложенный, то мы не должны обращать внимания на скобку закрывающую вложенный список.
3) Генерируем последовательность "(first (rest (rest … ". Число restов – на 1 меньше номера атома в списке.
4) Если данный список вложен в какой-то другой, то делаем шаги 2-3.
5) Генерируем результат
Программировал эту штуку в Делфи. На форме – 3 текстовый окна (Список, Атом, Результат) и одна кнопка.
И еще вопрос:Как в Лиспе проверить правильность решения?

Точно так же, как и в Дельфи :) Запускаем программу и смотрим результат, совпадает ли он с планируемым. Или что-то другое имеется в виду?

Исходный текст программы Максима приведен на сайте в полном варианте выпуска:

http://infiltration.ru/p/b171.html

Новые возможности Лиспа.

Перебирать элементы списка мы научились. Теперь научимся собирать список из кусочков (других списков и атомов). В этом поможет функция CONS. Она получает два аргумента (вторым должен следовать список), и первый из них вставляет в качестве первого элемента второго аргумента-списка.

Например:

   (cons (quote A) (quote (B C)) ) даст (A B C)
   (cons (quote (A B)) (quote (C D)) ) даст ((A B) C D)

В Лиспе существует понятие логических значений. Ложь обозначается атомом NIL, а истина - атомом T (их смысл как логических констант определяется из контекста выражения). В версии newLISP используются более привычные константы true (истина) и false (ложь).

Чтобы проверить, является ли некоторое выражение списком (или атомом), используют функцию ATOM. Ей передается выражение в качестве параметра, и она возвращает T, если это выражение - атом, и NIL в противном случае.
В newLISP она записывается как atom? :

   (atom? A) вернет true
   (atom? (quote (A))) вернет nil
   (atom? (first (quote (A)))) вернет true

Функция EQ сравнивает два своих аргумента (если оба они списки, то ее значение не определено). Она проверяет их на равенство, и если они одинаковы, возвращает T, и NIL в противном случае. В реализации newLISP используются более привычные символы сравнения:

   = != > < >= <=

Примеры:

   (= ' T ' T) вернет T
   (= ' T ' NIL) вернет nil
   (= ' NIL ' NIL) вернет T
   (= ' T ' (T)) вернет nil
   (!= ' T ' (T)) вернет T
   (= ' T (first ' (T))) вернет T

Наконец мы добрались до "логического оператора" Лиспа :) Формально он называется условной функцией COND. Эта функция в общем случае записывается так:

(COND (лв1 в1) (лв2 в2) ...)

где лвN - это выражение Лиспа, возвращающее логическое значение T или NIL, а вN - произвольное выражение.

Функция COND последовательно просматривает каждую такую пару, вычисляя логическое выражение, и если оно НЕ равно NIL, выполняется соответствующее ему обычное выражение (оно вычисляется), после чего работа функции COND заканчивается, и вычисленное значение возвращается в программу. Обычно в качестве последней пары используется список (T T) - если все предыдущие пары проверены и ни одного НЕ-NIL не встретилось, данная пара, очевидно, будет обязательно обработана (так как T не равно NIL :), и функция COND вернет T (истинное значение). Так делают для подстраховки, потому что значение, возвращаемое COND, не определено, если ни одной вычисляемой пары не встретилось.

Например:

   (cond
      ((= ' (A B) ' (A B C)) NIL)
  (true true)
    )

Так как список (A B) не равен списку (A B C), второе значение в паре (NIL) не анализируется и происходит переход к анализу следующей (последней в нашем случае) пары. Ее первый элемент равен T, поэтому и возвращается истинное значение T (второе в последнем списке).

В Лиспе имеются операторы, аналогичные операторам Паскаля и Си (условный, присваивания, цикла), и формально можно писать программу на Лиспе примерно в таком же стиле, как и на Паскале. На эту тему есть интересные письма, и мы в следующие разы рассмотрим принципы создания лисп-программы в классическом стиле Си и Паскаля. Однако все же главный механизм управления вычислительным процессом в Лиспе - не последовательное выполнение операторов, а рекурсия (о ней говорилось в выпуске N 55), вызов функцией самой себя. Доказано, что только с помощью механизма рекурсии можно реализовывать любые алгоритмы, в которых используются последовательно вызываемые операторы условия и цикла.

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

Школа программирования с нуля
Все предыдущие выпуски базового курса всегда тут:
http://www.infiltration.ru/p/

Неофициальный сайт поддержки (со срочными вопросами - сюда):
www.prog-begin.net.ru.

Все эти учебные курсы рассчитаны не только на разработчиков, но и на всех тех, кто хочет стать ИТ-менеджером. Для этого как минимум нужно иметь общее представление о современных технологиях разработки и их истории и владеть соответствующей терминологией. Именно это мои книги и дают.
В учебных курсах описаны десятки технологий, каждой из которых посвящены отдельные книги. Таким образом, купив один учебный курс, вы существенно сэкономите :) В книгах полностью описаны:
- Delphi (версия 2006, полностью совместимая с Delphi 2005/2006/2007 и Turbo Delphi) для обеих платформ - Win32 и .NET;
- C# (новый язык Microsoft, на котором базируется платформа .NET и все новые версии Windows);
- C++ для платформы Win32.
Охвачены также темы работы с файлами на этих платформах, создания файл-серверных, клиент-серверных, распределенных приложений, веб-программ (Indy, ASP.NET, веб-сервисы). Описаны языки SQL и OCL. Немало глав посвящены истории программирования и различных технологий. Особое внимание уделено созданию программ с помощью технологии ECO и языка моделирования UML - программы фактически рисуются, и теперь даже для создания корпоративных приложений и их переноса в Интернет не обязательно знать программирование!
Отдельная часть отведена технологиям организации групповой работы, управления требованиями, контроля версий, локализации и тестирования.
Тут подробнее про книги.

Мои книги, которые пока доступны в продаже:

• Технологии С++Builder. Разработка приложений для бизнеса. Учебный курс
• Технологии С#Builder. Разработка приложений для бизнеса. Учебный курс
• Технологии Delphi. Разработка приложений для бизнеса. Учебный курс
• Технологии Delphi 2006. Новые возможности
• Delphi 7. Учебный курс
• Технологии Пентагона на службе российских программистов