Задачи

Задачи на repl.it

Динамическое программирование

1. Дан список чисел. Необходимо найти в нем максимальную возврастающую подпоследовательность.
2. Дан список чисел с возможными номиналами монет. Например, даны числа 1, 2, 5, 10, это значит, что в магазине можно расплачиваться монетками таких номиналов. Кроме этого дана сумма в рублях. Например, 42. Как набрать эту сумму монетками, используя минимальное количество монет?
   • Для 42 ответ 10 + 10 + 10 + 10 + 2
   • Для поиска оптимального ответа используйте динамическое программирование
   • А что если пользоваться жадным алгоритмом? Попытайтесь набирать сумму, используя максимально возможную монету. Например, для 42 используйте сразу монету 10, потому что она максимальная из тех, кого можно взять. Продолжайте, пока не наберете сумму. Всегда ли жадный алгоритм дает оптимальный результат?
   • (*) Что если кроме номиналов монет вам дано количество, сколько у вас есть таких монет. Задача усложняется, появляется дополнительное ограничение, монет определенного вида нельзя брать слишком много.
3. (**) Максимальный подпалиндром. Дана строка, найти в ней строку максимальной длины, которая является палиндромом. Размер исходной строки не будет больше, чем 100 символов. Подсказка по требованию.

Список.

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

public class Node {
    private int value;
    private Node next;
    // ...
}

Если узел последний в списке, то поле next содержит null.

Класс IntList - это сам список, он хранит ссылку на первый узел:

public class IntList {
    private Node first;
}

Добавьте в класс IntList методы для

1. добавления элемента в начало списка,
2. для вычисления длины списка
3. опредление значения по индексу
4. удалить элемент по индекску
5. вставить элемент по указанному индексу