Дополнительные задачи, 8 набор
  • Эти задачи можно делать до 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:

  • Если совсем непонятно, о чем вообще речь - подождите вторника, мы разберем д.з. и, может быть, станет понятнее.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License