Экзамен

Двоичный поиск

Реализуйте двоичный поиск.

Коллекции

Создать список List<String> из чисел от 1 до 100. Здесь и везде реализуйте функцию, которая решает задачу. В main методе вызовите ее для проверки.
Дан список, верните новый список, в котором все элементы идут в обратном порядке. Сделайте две версии задачи: чистую функцию и функцию, которая меняет заданный список.
Сделайте по две версии следующих трех функций: чистую функцию и функцию, которая меняет заданный список.
- Дан List<String>, удалите в нем все элементы с четным индексом.
- Дан List<String>, удалить в нем все элементы, которые являются четными числами
- Дан List<Integer>, удалить в нем все элементы, которые являются четными числами
Взять текстовый файл, желательно большой на русском. Прочитать из него все слова, каждое слово привести к нижнему регистру и сохранить в множестве HashSet. Вывести все слова.
- Повторите аналогичные действия для TreeSet, LinkedHashSet. Т.е. Ваша программа должна читать текстовый файл три раза. Убедитесь, что вы не дублируете код, и не скопировали программу три раза для каждого из видов множества.

Ассоциативные массивы

Дана строка. Посчитать каждый символ, сколько раз он встретился. Например, строка “banana” должна выдать массив Map<Character, Integer>:
```
     'b' -> 1
     'a' -> 3
     'n' -> 2
```
Аналогично предыдущему, но выдать Map<Character, List<Integer>> со списком индексов, где встретился символ:
```
     b -> [0]
     a -> [1, 3, 5]
     n -> [2, 4]
```
Частотный словарь слов из файла. Т.е. нужно прочитать слова из файла и посчитать, сколько раз они встретились. Приводите слова к нижнему регистру перед подсчетом. Желательно использовать большой текст на русском, например, возьмите его на http://lib.ru. Используйте Scanner.useDelimiter(), чтобы указать сканеру, какие символы считать разделителями слов.
- Сначала используйте HashMap
- Потом исправьте программу так, чтобы она использовала все три вида массивов: HashMap, TreeMap, LinkedHashMap. Соответственно, выведите ответ три раза. Не дублируйте код.
- Выведите слова в порядке уменьшения частот. Вам потребуется отсортировать список List<Map.Entry<String, Integer»

Потоки (Streams)

Следующая функция возвращает бесконечный поток случайных целых чисел от 0 до max - 1. Попробуйте понять, как она работает.

    public static IntStream randomStream(int max) {
        Random r = new Random();
        return IntStream.generate(() -> r.nextInt(max));
    }

Следующая функция возвращает бесконечный поток натуральных чисел 1, 2, 3 и т.д. Попробуйте понять, как она работает

    public static IntStream integersStream() {
        return IntStream.iterate(1, x -> x + 1);
    }

Следующая функция возвращает поток слов из файла. Попробуйте примерно понять, как она работает:

    public static Stream wordsStream(File f) {
        try {
            byte[] fileAsBytes = Files.readAllBytes(f.toPath());
            String fileAsText = new String(fileAsBytes, "UTF-8");
            return Arrays.stream(fileAsText.split("\\s+"));
        } catch (Exception e) {
            System.out.println("Failed to read file " + f);
            return Stream.of();
        }
    }

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

Дано n. Посчитайте сумму
1. чисел от 1 до n
2. квадратов чисел от 1 до n
3. кубов чисел от 1 до n
4. обратных чисел от 1 до n
Дан список чисел. Верните новый список, в котором удалены все четные числа.
Дан файл. Посчитайте среднюю длину слов в этом файле. А еще максимальные и минимальные длины слов. Используйте подходящий Collector.
1. Найдите самое длинное слово в файле. Получится сделать это за один проход по потоку?
Бросьте монетку 100 раз, сколько раз выпал орёл, а сколько решка?
Еще будут

Объекты

Класс Rational

Сделаем класс Rational, это рациональные числа, для которых хранится их числитель и знаменатель. С рациональными числами можно совершать арифметические операции.

Создайте класс и добавьте поля n и d (numerator, denominator - числитель, знаменатель). Убедитесь, что поля приватные.
Класс должен иметь конструкторы вида Rational(3, 2) и Rational(3).
Добавьте метод public String toString(), который возвращает естественное представление числа в виде строки, например, 5/7. Если знаменатель равен 1, его не нужно писать. Если числитель ноль, то “0”, а не “0/2” и т.п.
Добавьте метод double toDouble(), который возвращает значение в виде double.
Добавьте сокращение дроби в конструктор: поделить числитель и знаменатель на НОД, убедиться, что знаменатель положительный.
Арифметические функции. add, sub, mul, div:
```
 Rational r1 = r2.add(r3); // создает новое число
 r2.addInPlace(r3); // добавляет к r2 и изменяет его
```
Протестируйте! Проверьте, например, что \(\frac16 + \frac13 = \frac12\), и проверьте другие аналогичные равенства для других арифметических операций.
Создайте функцию не в Rational, которая по n считает \(1 + \frac12 + \frac13 + \frac14 + \frac15 + … + \frac1n\) Проверьте, что f(1) = 1, f(2) = 1.5, f(3) = 1.833333333333333
Чему равно f(20)? Почему оно равно тому, чему равно? Как исправить?
Добавьте get- методы для числителя и знаменателя. Чтобы Rational стал совсем неизменяемым, закомментируйте методы *InPlace().
Создайте статические константы ONE и ZERO типа Rational, хранящие элементы 0, 1 в виде рациональных чисел.
Сделайте статическим метод поиска НОД (или сокращения)
Создайте статические версии арифметических операций: static Rational add(Rational r1, Rational r2) и т.п. Эти операции создают новое число, вы можете переиспользовать старые арифметические операции.

Класс Drawing

Класс Drawing (изображение) хранит изображение в виде массива символов char[][]. Например,

    .........
    .........
    ....x....
    .........

Создайте конструктор, в котором указывается размер (сколько строк и столбцов) и символ, которым изначально все заполнить. Например, new Drawing(20, 30, ‘.’)
Создайте метод print(), он печатает на экране изображение
Метод setPoint(x, y, char) рисует один символ в изображении. Методу нужно указать, где и какой символ поставить.
Методы drawVerticalLine(...), drawHorizontalLine(...) рисуют вертикальную или горизонтальную линию от заданной точки до заданной. Определите сами параметры для методов, они должны определять расположение линии и символ, которым линию рисовать.
Метод drawRectangle() рисует прямоугольник по двум противоположным углам, стороны прямоугольника вертикальны и горизонтальны. Используйте методы, реализованные ранее.
Необязательно: Рисование произвольной линии (см. необязательную задачу за прошлый семестр)
Рисование круга (или окружности — необязательно). Пользователь указывает центр и радиус, программа должна пройтись по всем точкам поля и, если они лежат в круге, зарисовать их указанным символом.
Реализуйте метод draw(x, y, Drawing d) нарисовать одно изображение на другом. При вызове метода указывается, где и какое изображение рисовать.
(Необязательная задача). Сделайте Drawing неизменяемым: все функции рисования возвращают новый Drawing и не меняют текущий.
Используйте все реализованные вами ранее методы, чтобы нарисовать домик.

Интерфейсы, лямбда выражения и анонимные классы

Создайте интерфейс Printable с одним методом void print(), этот метод означает что объект печатает что-то на экране. Сделайте так, что класс Drawing реализует этот интерфейс. Проверьте, что получилось.
Создайте класс PrintableLetter, реализующий интерфейс Printable. Пользоваться классом нужно так:
```
   PrintableLetter pl = new PrintableLetter("x", 10);
   pl.print(); //печатает букву x 10 раз
```
Создайте класс PrintableString, реализующий интерфейс Printable, этот класс хранит строку, пользоваться им нужно так:
```
   PrintableString ps = new PrintableString("asdf");
   ps.print(); //печатает asdf
```
Создайте массив типа Printable[], заполните его 1) Drawing 2) PrintableLetter 3) PrintableString 4) анонимным классом 5) лямбда выражением. В цикле попросите всех что-нибудь напечатать.

Результаты

Таблица результатов