[-=TurboRufus=-]

1. Получилось так, что веду лабораторные у второкурсников по дисциплине "Структуры и алгоритмы обработки данных". Группа подобралась хорошая, и хочется дать им задания поинтереснее (ну и посложнее), чем то, что есть в программе.
Вопрос, какие интересные задания можно придумать к темам "Стеки и очереди" и "Бинарные деревья"? Конечно, чтобы не совсем завальные, но не "перевести инфиксную запись в постфиксную".
Пишут они в основном на Delphi. Хотя в выборе языка программирования я их не ограничиваю.

2. Теперь по своей учебе. Задали сделать во Flash некую интерактивную программу, моделирующую магнитное поле Земли и солнечный ветер.
Буду признательна, если подскажете, как к этому всему подступиться (я такого вообще ни разу не делала) или хотя бы, где достать прототип.

@темы: Вопрос

Comments

[Elecktra]

Насчёт "Бинарные деревья"... не знаю, насколько интересная задачка, но мне на втором курсе она оч понравилась.
В общем нужно было сделать семейное древо. А в интерфейсе для конкретного человека из этого древа (выбиралось имя человека) искать любого родственника (выбиралось название родственника).
Например для Ивановой Ольги найти прабабушку.

[-=TurboRufus=-]

Elecktra
Спасибо. Буду иметь в виду =)

[Чайный наркоман]

1. Хм... А насколько сложные нужны? Можно на пару заданий из программы посмотреть чтобы сравнить с тем, что у меня есть?)

2. Так ведь ничего сложного ведь нету, или я ошибаюсь?
Есть какие-то объекты, у них есть масса, нам нужно общитать их взаимодействие через закон всемирного тяготения и периодически прорисовывать.
Для солнечного ветра ещё площадь соприкосновения считать, чтоб силу вычислить. И, наверное, всё. В чём проблема-то?

[-=TurboRufus=-]

Чайный наркоман
1. Примеры заданий

Стеки и очереди

Стеки и очереди:
Проверить, является ли содержимое заданного текстового файла F правильной записью формулы следующего вида:
< формула > ::= < терм > | < терм > + < формула > | < терм > - < формула >
< терм > ::= < имя > | ( < формула > ) | [ < формула > ] | { < формула > }
< имя > ::= x\y\z
Если не является, то указать номер ошибочной позиции.
В решении задачи использовать стек.

В заданном текстовом файле F записано логическое выражение (ЛВ) в следующей форме:
<ЛВ>::= true| false | (!< JIB > ) | ( < ЛВ > ^ < ЛВ > ) | ( < ЛВ > v < ЛВ > )
где знаки !, ^ и v обозначают соответственно отрицание, конъюнкцию и дизъюнкцию. Вычислить (как Boolean) значение этого выражения.
В решении задачи использовать стек

Представьте себе, что четыре железнодорожных вагона находятся на входной стороне пути и перенумерованы соответственно 1, 2, 3, 4. На входе операции над вагонами: вагон N в начало дека; вагон N в конец дека, вагон из начала дека на выход, вагон из конца дека на выход.
Построй программу моделирующую данную ситуацию для N (N < 1000000) вагонов.
В решении задачи использовать дек

Определить, имеет ли заданная в файле F символьная строка сле¬дующую структуру:
aDbDcDd...,
где каждая строка а, b, с, d,..., в свою очередь, имеет вид х1 С х2. Здесь x1 есть строка, состоящая из символов А и В, а х2 - строка, обратная строке x1 (т. е. если x1 = АВАВВ, то х2 - ВВАВА). Таким образом, исходная строка состоит только из символов А, В, С и D. Исходная строка может читаться только последовательно (посимвольно) слева направо.
В решении задачи использовать очередь и/или стек.

вычислить как целое число значение выражения (без переменных), записанного в префиксной форме в заданном текстовом файле prefix; /как выглядят постфиксная, префиксная и инфиксная записи, указано/

Бинарные деревья

Бинарные деревья:
Задано бинарное дерево b типа ВТ с типом элементов Elem. Для введенной пользователем величины Е (var E: Elem) определить число вхождений элемента Е в дерево b.

Для заданного бинарного дерева b типа ВТ с произвольным типом элементов подсчитать число узлов на заданном уровне п дерева b (корень считать узлом 1-го уровня)

Заданы два бинарных дерева b1 и b2 типа ВТ с произвольным типом элементов. Проверить: зеркально подобны ли они (два бинарных дерева зеркально подобны, если они оба пусты либо они оба непусты и для каждого из них левое поддерево одного подобно правому поддереву другого)

С помощью построения дерева-формулы t преобразовать заданную формулу t из инфиксной формы в постфиксную (перечисление в порядке ЛПК)

2.

В чём проблема-то?

- я тупо не знаю, с какой стороны к этому подступиться...
Посоветуйте что ли книги по flash из разряда "для очень начинающих".

[Тигр]

projecteuler.net/

[Чайный наркоман]

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

8. Определите количество узлов на каждом уровне данного бинарного дерева.

9. Определите, есть ли в данном бинарном дереве два одинаковых элемента?
10. Выведите номера уровней данного бинарного дерева, на которых имеются листья.

11. Выведите номера вершин, у которых количество потомков в левом поддереве не равно количеству потомков в правом поддереве.

12. Выведите номера вершин, для которых высота левого поддерева не равна высоте правого поддерева.

13. Выведите номера вершин, у которых количество потомков в левом поддереве отличается от количества потомков в правом поддереве на 1.

14. Найдите высоту дерева H и удалите в нем все вершины на уровне H/2.

15. Найдите минимальный путь между листьями и удалите центральную вершину этого пути.

16. Найдите максимальный путь между вершинами дерева и удалите центральную вершину этого пути.

17. Найдите высоту дерева H и удалите в нем все вершины на глубине H/2, у которых высота левого поддерева равна высоте правого поддерева.

18. Найдите путь максимальной длины и отразите дерево зеркально относительно этого пути.

19. Найдите путь максимальной длины между вершинами с разным числом потомков.

20. Найдите путь максимальной длины между вершинами разной высоты.

21. Найдите пути минимальной длины между корнем и листьями и удалите центральные вершины этих путей.

22. Определите, являются ли два дерева зеркальным отражением друг друга по структуре.

23. Найдите среднюю по значению вершину в дереве.

24. Найдите вершины, у которых высоты поддеревьев равны, а количество потомков в правом и левом поддеревьях не равны.

25. Найдите вершины, у которых высоты поддеревьев не равны, а количество потомков в правом и левом поддеревьях равны.

26. Найдите какую-нибудь вершину в дереве, у которой высоты поддеревьев равны.

27. Удалите все вершины, для которых количество потомков в левом поддереве отличается от количества вершин в правом поддереве на 2 и более.

28. Удалите все вершины, для которых высота левого поддерева отличается от высоты правого поддерева на 2.

Если искать сложнее и много - то это уже по олимпиадным покопаться надо.

2. С точки зрения алгоритма там сложного совсем ничего нету, а вот флэш к сожалению или к счастью не знаю.

[FunTime]

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

[-=TurboRufus=-]

Чайный наркоман, FunTime
Спасибо большое.

Тигр
и Вам спасибо ) Я, правда, не особо хорошо понимаю английский, но посмотрю.