Комбинаторные алгоритмы решения школьных задач по информатике

псевдокод:

check(s):

   pointer = 0

   for (i = 1; i <= length(s); i++):

     pointer = (s[i] == '(')? pointer++ : pointer--

     if (pointer < 0)

       return false

   if (pointer == 0)

     return true

   else

     return false

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

Примеры скобочных  последовательностей с несколькими  типами скобок:

•  — верно
•  — неверно

В этом случае для проверки надо будет использовать стек.

Лексикографический порядок  правильных скобочных последовательностей.

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

Примеры лексикографического  порядка для   и  , где   — число открывающихся скобок, а   — число видов скобок

Алгоритм генерации  лексикографического порядка будет  предложен ниже. Количество правильных скобочных последовательностей. Числа Каталана. Количество правильных скобочных последовательностей со скобками одного типа совпадает с числами Каталана.

Определение:

Числа Каталана — последовательность чисел, выражающих: количество не изоморфных упорядоченных бинарных деревьев с корнем и   листьями; количество способов соединения   точек на окружности   не пересекающимися хордами; количество разбиений выпуклого  -угольника на треугольники не пересекающимися диагоналями;

Для чисел Каталана выполняется  выражение:

,

а также они удовлетворяют рекуррентному соотношению:

 — так как существует только одна скобочная последовательность с   открывающихся скобок — пустая

.

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

Алгоритмы генерации

Генерация следующей  скобочной последовательности:

Пусть нам известна строка  , представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то — "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить , заменить ее на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:

 next(s):

   pointer_close = 0

   pointer_open = 0

   for (i = length(s); i > 0; i--)

       if (s[i] == '('):

         pointer_open++

         if (pointer_close > pointer_open)

           break

       else

         pointer_close++

   delete(s, length(s) - pointer_open - pointer_close + 1, pointer_close + l)

   if (s == ""):

     return false

   s = s +')'

   for (j = 1; j <= pointer_open; j++):

     s = s + '('

   for (j = 1; j < pointer_close; j++):

     s = s + ')'

   return true

Если эта функция  после выполнения выводит  , тогда надо напечатать полученную строку  , если  , то следует вывести "No solution".

Получение лексикографического  порядка:

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

 order (n)

   s = "";

   if (n == 0):

     result(s) 

   else

     for (j = 1; j <= n; i++)

       s = s + '(';

     for (j = 1; j <= n; i++)

       s = s + ')';

     result(s);

     t = next(s);

     while (t <> false)

       result(s);

       t = next(s);

   return

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

 

ЗАКЛЮЧЕНИЕ

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

Исследуя тему «Комбинаторные алгоритмы решения школьных задач по информатике» проанализировали научно-методическую литературу, выявили уровень логического мышления основной школы. Так же изучили психологические особенности, изучили методику ознакомления с задачами на комбинаторику.

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

Гипотеза, положенная в  основу исследования подтверждается – качество подготовки выпускников к сдаче ЕГЭ улучшилось при составлении типологии заданий по информатике, и определена логика их изучения в школьном курсе информатики; осуществлен отбор алгоритмов решения задач дискретного анализа с обоснованием их корректности.

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

Для сочетания, перестановки и размещения сформулированы и решены четыре классические задачи. Для перестановок они таковы.

1. Найти алгоритм перечисления всевозможных перестановок из n элементов.
2. Найти отношение порядка на множестве перестановок из n элементов.
3. По порядковому номеру перестановки определить перестановку.
4. По перестановке определить ее порядковый номер.

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

 

ЛИТЕРАТУРА

 

1. Алексеев А. В. Олимпиады школьников по информатике. Задачи и решения. - Красноярск: Красноярское книжное издательство, 1995.
2. Андреева Е. В., Фалина И. Н. Информатика: Системы счисления и компьютерная арифметика. - М.: Лаборатория базовых знаний, 1999.
3. Бадин Н. М., Волченков С. Г., Дашниц Н. Л., Корнилов П. А. Ярославские олимпиады по информатике. - Ярославль: Изд-во ЯрГУ, 1995.
4. Беров В. И., Лапунов А. В., Матюхин В. А., Пономарев А. А. Особенности национальных задач по информатике. - Киров: Триада-С, 2000.
5. Брудно А. П., Каплан Л. И. Московские олимпиады по программированию. - М.: Наука, 1990.
6. Виленкин Н. Я. Комбинаторика. - М.: Наука, 1969.
7. Вирт Н. Алгоритм+структуры даыных=Программы. - М.: Наука, 1989.
8. Гусев В. А., Мордкович А. Г. Математика: справочные материалы. - М.: Просвещение, 1990.
9. Дагене В. А., Григас Г. К., Аугутис К. Ф. 100 задач по программированию. - М.: Просвещение, 1993.
10. Йодан Э. Структурное проектирование и конструирование программ. - М.: Мир, 1979.
11. Касаткин В. Н. Информация. Алгоритмы. ЭВМ. - М.: Просвещение, 1991.
12. Касьянов В. Н., Сабельфельд В. К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986.
13. Кирюхин В. М., Лапунов А. В., Окулов С. М. Задачи по информатике. Международные олимпиады 1989-1996. - М.: «ABF», 1996.
14. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978.
15. Лапунов А. В., Окулов С. М. Задачи международных олимпиад по информатике. - Киров, Изд-во ВятГПУ, 1993.
16. Липский В. Комбинаторика для программистов. - М.: Мир, 1988.
17. Окулов С. М., Пестов А. А. 100 задач по информатике. - Киров: Изд-во ВятГПУ, 2000.
18. Окулов С. М., Пестов А. А., Пестов О. А. Информатика в задачах. - Киров, Изд-во ВятГПУ, 1998.
19. Окулов С. М. Конспекты занятий по информатике (алгоритмы на графах): Учебное пособие. - Киров, Изд-во ВятГПУ, 1996.
20. Окулов С. М. Задачи кировских олимпиад по информатике. - Киров, Изд-во ВятГПУ, 1993.
21. Окулов С. М. Основы программирования. - М.: Лаборатория базовых знаний, 2001.
22. Препарата Ф., Шеймос М. Вычислительная геометрия: введение. - М.: Мир, 1989.
23. Романовский И. В. Дисркетный анализ. – СПб.: БИНОМ, 2002.
24. Савельев Л. Я. Комбинаторика и вероятность. - Новосибирск: Наука, 1975.
25. Усов Б. Б. Комбинаторные задачи// Информатика, 2000, №39.