Вопрос 27. Разработка программа обработки числовых последовательностей
Для решения данного вопроса необходимо написать программу для обработки файла, который содержит последовательность чисел. Файл
А содержит количество чисел, которое можно обработать грубым перебором. Для решения файла
В, переборный алгоритм уже не подходит, потому что будет работать долго и получить овтет, за приемлемое для экзамена время, будет практически не возможно. Поэтому, наша цель научиться писать эффективные алгоритмы для решения таких задач.
Для успешного решения данного задания необходимо:
- знать основы комбинаторики;
- знать основы теории чисел;
- знать динамическое программирование.
Последовательность и ее подпоследовательности
Все числа из файла образуют одну последовательность. Подпоследовательность получается из текущей последовательности путем удаления любого числа элементов.
Непрерывная подпоследовательность получается из последовательности путем удаления любого числа элементов либо сначала этой последовательности, либо с конца.
Количество непрерывных подпоследовательностей, которые начинаются с первого элемента, равно числу элементов всей последовательности.
Считывая очередное число последовательности, мы получаем новую подпоследовательность. Сумма элементов новой подпоследовательности вычисляется путем добавления значения нового элемента к сумме элементов предыдущей подпоследовательности. Количество элементов новой подпоследовательности будет на единицу больше количества элементов предыдущей подпоследовательности.
Например, если
s - сумма элементов предыдущей подпоследовательности, а
х следующее число последовательности, то сумма элементов новой подпоследовательности вычисляется таким образом
s = s + x.