- Эти задачи можно делать до 17 ноября.
1. n ферзей
Написать функцию, которая ищет расстановку n ферзей на первых n вертикалях шахматной доски, так, чтобы они не били друг-друга (n <= 8). Способ представления данных (как хранить информацию о ферзях) придумайте, пожалуйста, сами.
В этой задаче желательно применить 'представление множеств с помощью функций' (видимо, для того, чтобы запоминать, на какие поля еще можно ставить ферзей, а какие уже под боем). За это будет 2 балла. За любое другое решение - 1 балл.
2. Преобразование деревьев в строку и обратно (задача с контрольной, но для конкретного представления дерева)
Пусть у нас есть двоичное дерево, элементы которого – символы. Для простоты давайте считать, что символами могут быть только буквы ‘a’ и 'b'. Написать две функции – одна по дереву строит его представление в виде строки, а вторая функция должна по этой строке восстанавливать исходное дерево.
Причем я xочу хранить дерево в следующем формате:
- Empty кодируется буквой 'e'
- Node x left right кодируется так: сначала буква 'n', потом символ x, потом подряд без разделителей представления для left и right.
Например, дерево Node 'a' Empty (Node 'b' Empty Empty) кодируется строкой "naenbee".
Замечание:
- Tем, кто на контрольной использовал именно такое представление, снова делать задачу не надо, она зачтется автоматически.
3. Представление множеств с помощью функций на C#
Написать на C# функцию, которая для данного массива целых чисел проверяет верно ли, что в нем все элементы разные. При этом функция должна использовать 'представление множеств с помощью функций'. Т.е., другими словами, попробуйте переписать пример с последнего занятия на C#.
Замечания:
- Если хотите, можете решить задачу для List<int> или вообще для IEnumerable<int> - как вам удобнее.
- Можете, если хотите, попробовать решить эту задачу на C++ или Java.
- Вы можете спросить, а зачем такую простую задачу решать так сложно? Да в общем-то просто для интереса:) Ну и для тренировки в работе с лямбда-выражениями и т.д. На практике это, наверное, особо не применимо, честно говоря.
Подсказка: Я бы начал решение этой задачи как-то так:
public static bool allDiff(int[] a)
{
return allDiff1(a, 0, t => true);
}
// allDiff1 - вспомогательная функция
// a - массив, который мы проверяем
// from - с какого места в массиве мы проверяем
// func - функция проверки (которую мы делаем все сложнее и сложнее)
public static bool allDiff1(int[] a, int from, Predicate<int> func)
{
...
Замечание к задачам 1 и 3:
- Если совсем непонятно, о чем вообще речь - подождите вторника, мы разберем д.з. и, может быть, станет понятнее.