r20 - 11 Jul 2008 - 02:01:52 - Anton OrlovYou are here: TWiki >  Refaldevel Web > UGPSummerSchool2008

Занятия по Рефалу на летней школе в УГП, 2008

Примеры программ на Рефале Плюс

Все примеры могут быть загружены в IDE для Рефала Плюс в виде проекта UGPSummerSchool2008. Для этого:

  1. Должен быть установлен какой-нибудь plug-in для работы с SVN, например Subclipse или Subversive.
  2. Выберите меню File -> New -> Project -> Projects from SVN, Next >
  3. Create a new repository location, Next >
  4. Введите URL: http://svn.botik.ru/refal/applications, Next >
  5. Выберите trunk -> UGPSummerSchool2008, Finish
  6. Finish

Базовые примеры для знакомства с Рефалом

  1. Факториал числа. Обратите внимание на работу с числами произвольной разрядности.
  2. Замена A на B на верхнем уровне выражения. Иллюстрация неоднозначности сопоставления с образцом и пример использования порядка на множестве вариантов сопоставления.
  3. Несколько вариантов функции, переворачивающей (реверсирующей) выражение. Демонстрация конкатенации терма справа, работы с аккумулирующим параметром, функций с несколькими аргументами, чтения стандартного ввода.
  4. Палиндром ли данное выражение?. Образец с повторными переменными, откатные функции, использование ':' для записи сопоставления.
  5. Простейший интерпретатор арифметических выражений.

Более продвинутые примеры

  1. Быстрая сортировка. См. задачу ниже.
  2. Решение задачи о цепочках. См. задачу ниже.
  3. Решение несложной задачки с соревнования по программированию Google Code Jam 08.

Задачи

Теорема о среднем

Докажите, что при любых значениях переменных s1, e2, e3 следующее отождествление выполняется: s1 e2 (e3) : e s (e) e.

Удаление повторных пробелов

Напишите программу, которая удаляет все повторяющиеся пробелы в данной строке литер.

Подстановка

Напишите функцию Subst, которая принимает на вход терм t1, выражение e2 и выражение e3, и подставляет e2 вместо t1
  1. на верхнем уровне выражения e3;
  2. на всех уровнях выражения e3.

Сортировка

  1. Напишите функцию сортировки рефал-термов.
  2. Напишите функцию быстрой сортировки рефал-термов. // Решение.
(Подсказка: воспользуйтесь библиотекой Compare.)

Арифметические выражения

Подсказка: см. пример Int.rf.

  1. Напишите программу, которая считывает последовательность цифр и знаков '+' и '-', интерпретирует её как арифметическое выражение и выдаёт ответ.
  2. Напишите программу, которая считывает последовательность литер и заменяет в ней круглые скобки на рефальские структурные скобки (если скобки в данной последовательности расставлены неправильно, то выдаёт ошибку).
  3. Напишите интерпретатор арифметических выражений, представленных последовательностями из цифр, знаков '+', '-', '*', '/' и скобок.

Нули и единицы

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

  1. равна 3; // Решение в 1 строчку на Рефале-5 приводится у А. Корлюкова.
  2. равна 7;
  3. произвольна.

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

Binary addition

Сколько строчек вам понадобиться, чтобы записать на Рефале программу сложения двух чисел в двоичной системе счисления? // Решение в 3 строчки на Рефале-5 приводится у А. Корлюкова.

Перестановки

Напишите функцию, которая печатает все перестановки чисел от 1 до n. // Решение.

A Sequence Program

Составьте последовательность из трех единичек, трех двоек, ..., трех девяток так, что для каждой цифры i между последовательными вхождениями i в эту последовательность находится ровно i чисел. Пример такой последовательности: 1, 9, 1, 2, 1, 8, 2, 4, 6, 2, 7, 9, 4, 5, 8, 6, 3, 4, 7, 5, 3, 9, 6, 8, 3, 5, 7. // Решение.

Задачи на зачёт

Арифметические выражения.

Дано арифметическое выражение, в котором каждая операция заключена в скобки (см. пример Int.rf).

Например: (((2 '+' 3) '*' 4) '/' (4 '-' 2)).

  1. Напишите программу, которая выдает выражение в префиксной форме (заметим, что скобки в этом случае можно не выдавать).
  2. Считая, что в выражении встречаются только операции сложения и умножения, раскройте все скобки. Например, для выражения ((2 '+' 3) '*' 4) программа должна выдать 2 '*' 4 + 3 '*' 4.
  3. Напишите программу, которая считывает последовательность цифр и знаков '+' и '*', интерпретирует её как арифметическое выражение и выдаёт ответ.
  4. Напишите программу, которая считывает последовательность литер и заменяет в ней круглые скобки на рефальские структурные скобки (если скобки в данной последовательности расставлены неправильно, то выдаёт ошибку).
  5. Напишите интерпретатор арифметических выражений, представленных последовательностями из цифр, знаков '+', '-', '*', '/' и скобок.
Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r20 < r19 < r18 < r17 < r16 | More topic actions
Refaldevel.UGPSummerSchool2008 moved from Refaldevel.Pearls on 10 Jul 2008 - 15:07 by Anton Orlov - put it back
 
R+

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback