4.2. Задача «Сумма двух чисел»
Рассмотрим совсем простую задачу.
- Входные данные: Целые числа $a$ и $b$ на одной строке (разделённые пробелом).
- Выходные данные: Сумма $a$ и $b$.
- Ограничения: $0 le a, b le 9$.
- Пример
| Ввод | Вывод |
|---|---|
| 9 7 | 16 |
- Ограничение по времени (с): 1 секунда
- Ограничение по памяти: 512 Mb.
Поскольку задача решается в одно действие, шаг Спроектировать алгоритм мы пропустим и перейдём сразу к псевдокоду.
SumOfTwoDigits(a, b):
return a + b
Так как псевдокод не уточняет ввод $a$ и $b$, ниже мы приводим решения для языков C++, Java и Python3, а также рекомендации по компиляции и реализации. Вы можете скопировать и вставить код в файл, скомпилировать, запустить и протестировать с разными данными, а затем сдать исходный файл в систему проверки. Разумеется, мы рассчитываем, что вы знакомы с основами одного из языков программирования, который используется в нашей системе тестирования: C++, Python3, Java.
C++
#include <iostream>
int sum_of_digits(int first, int second) {
return first + second;
}
int main() {
int a = 0;
int b = 0;
std::cin >> a;
std::cin >> b;
std::cout << sum_of_digits(a, b);
return 0;
}
Java
import java.util.Scanner;
class SumOfTwoDigits {
static int sumOfTwoDigits(int first_digit, int second_digit) {
return first_digit + second_digit;
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int a = s.nextInt();
int b = s.nextInt();
System.out.println(sumOfTwoDigits(a, b));
}
}
Python3
def sum_of_digits(first_digit, second_digit):
return first_digit + second_digit
if __name__ == '__main__':
a, b = map(int, input().split())
print(sum_of_digits(a, b))
Ваша цель — реализовать алгоритм, который дает верный результат с ограничениями по времени и памяти и при любом вводе. Нет необходимости проверять, что входные данные соответствуют ограничениям: например, в задаче Сумма двух чисел вам не нужно следить за тем, чтобы целые числа $a$ и $b$ действительно были однозначными числами (это гарантировано).
Глава прочитана
Задачи
0 / 0 задач выполнено Перейти
Сегодня мы начнём рассматривать алгоритмы обработки
информации в массивах. Достаточно часто встречается ситуация, при которой нам
необходимо сложить элементы массива, рассмотрим задачу. На складе яблоки
хранятся в мешках, известно количество мешков и количество яблок в каждом
мешке. Директор склада попросил нас написать программу, которая вычисляет
количество яблок на складе.
Обозначим через n количество мешков на складе, через i
– номер текущего мешка, а через s – сумму яблок в мешках. Очевидно, что
для решения данной задачи нам удобно будет представить склад в виде массива
целых чисел a, элементами которого будут мешки с яблоками. Значениями
элементов будут количества яблок в мешках.
Составим блок-схему алгоритма решения задачи.
Блок-схема начинается с блока «Начало», далее будет следовать блок ввода
количества мешков на складе – n.
За ним будет следовать цикл «Для i от 1 до n», в котором будет блок ввода i-того
элемента массива. Далее мы должны задать значение суммы яблок в мешках, равной
нулю, так как пока ни одного мешка мы не просмотрели, s =
0.
Потом снова будет следовать цикл «Для i от 1 до n», внутри
которого будет одна команда – присваивания переменной s сумму её
текущего значения и значения количества яблок в i-том мешке, s = s + a[i].
Таким образом, после просмотра всех n мешков, s будет содержать
сумму яблок во всех мешках. Далее будет следовать блок вывода s, блок-схема всегда заканчивается
блоком «Конец».
Блок-схема
алгоритма решения задачи
Начнём написание программы. Запишем служебное слово program. Назовём нашу программу sklad.
В разделе описания переменных var укажем,
что нам нужен массив a,
так как количество мешков в момент написания программы неизвестно, возьмём
размерность массива равной максимально возможному количеству мешков, например 100 элементов типа integer. А также нам понадобится
переменная n,
в которой будет храниться количество мешков на складе, переменная i,
которая будет хранить индекс текущего элемента массива, и переменная s, которая будет хранить значение
суммы яблок в мешках. Так как в данной задаче все величины выражаются в целых
числах, все переменные будут типа integer.
Между
служебными словами begin и end запишем тело программы.
Для начала выведем на экран поясняющее сообщение о том, что это программа
подсчёта яблок на cкладе
с запросом на ввод количества мешков на складе. Затем запишем команду
считывания значения переменной n с переходом на следующую строку. Далее запишем цикл for i:=1
to
n
do,
который будет содержать команду вывода на экран запроса на ввод количества
яблок в i-том мешке и команду считывания с переходом на следующую строку
значения
i-того элемента массива a.
Таким образом, мы ввели количество яблок в мешках.
Теперь
присвоим переменной s значение 0 и запишем цикл for i:=1
to
n
do,
который будет содержать всего одну команду – присваивание переменной «С», суммы
её текущего значения и значения И-того элемента массива «A»,
s:=
s
+ a[i].
Далее будет следовать команда вывода на экран поясняющего сообщения с текстом
«Количество яблок на складе:», а также значения переменной s.
Программа
решения задачи
Запустим программу на выполнение, пусть на складе
будет 4 мешка яблок, в первом мешке будет 100 яблок, во втором – 200, в третьем
– 300, а в четвёртом – 400. Действительно, всего на складе должна быть тысяча
яблок. Программа работает верно.
Пример
работы программы
Ещё раз рассмотрим нахождение суммы элементов массива
на примере нашей программы. В начале для хранения суммы элементов массива
выделяется ячейка памяти, в нашем случае это переменная s, затем ей присваивается значение,
равное 0, после чего для каждого элемента массива этой переменной присваивается
сумма её значения и значения элемента массива.
Теперь мы знаем, как найти сумму элементов массива.
Рассмотрим ещё одну задачу. Написать программу для нахождения суммы цифр целого
положительного числа. Длина числа до девяти цифр.
Обозначим число, которое вводится – k, количество его цифр – n, номер текущей цифры – i,
сумму цифр – s,
а также нам понадобится массив a, элементами которого будут цифры данного числа.
Для
начала составим блок-схему данного алгоритма. Она будет начинаться с блока
«Начало», за которым будет следовать блок ввода числа k, далее нам нужно
проинициализировать переменную i –
она
будет равна нулю, так как массив цифр a пока не содержит ни одной цифры.
Теперь
нам нужно сделать из числа k
массив цифр. Запишем для этого цикл «Пока» с условием k >
0, который
будет содержать команду выделения последней цифры числа k и записи её в
массив a.
Для этого достаточно использовать функцию нахождения остатка от деления,
которая в языке Pascal
называется mod,
так в начале нам нужно определить, в какой элемент массива a мы будем записывать данную цифру.
Для этого к числу i нужно прибавить единицу.
Теперь
i-тому элементу массива a присвоим значение последней цифры числа k, это будет остаток от его деления на
10. Теперь нужно убрать из числа k его последнюю цифру, для этого
достаточно присвоить числу k результат его безостаточного
деления на 10, данная операция записывается в языке Pascal
словом div.
Таким образом, после выполнения указанного цикла действий в массиве a
будут содержаться цифры числа k,
а в переменной i будет содержаться номер элемента массива a, в который была сохранена старшая по
разряду цифра. Он будет совпадать с количеством цифр в числе, поэтому присвоим
переменной n
значение переменной i. А также присвоим
переменной s
значение 0. Далее будет следовать уже знакомый нам цикл вычисления суммы
элементов массива a.
После него будет блок вывода
s
–
суммы цифр числа. Блок-схема будет заканчиваться
блоком «Конец».
Блок-схема
алгоритма решения задачи
Посмотрим, как работает наш алгоритм на примере числа
345. В начале переменной i присваивается значение 0. Так как 345 больше 0 – i увеличится
на 1, после чего первому элементу массива будет присвоено значение остатка от
деления 345 на 10, то есть 5. Само число k будет без остатка поделено на 10, и
станет равным 34. Далее так как 34 больше 0, значение переменной i
снова
увеличится на 1 и станет равным 2. Так i-тому элементу массива
будет присвоен результат остатка от деления 34 на 10, то есть 4. А число k снова будет поделено без остатка на
10 и станет равным 3. Так как 3 больше 0, переменная i станет равной 3, третьему
элементу массива a
будет присвоено значение 3, а число k снова будет поделено без остатка на
10 и станет равным 0. После завершения работы цикла массив a будет
содержать цифры числа k
в порядке, обратном их следованию в числе, а переменная i
будет
содержать номер элемента массива, который хранит цифру числа k с
самым высоким разрядом, это же число будет равно количеству элементов массива,
поэтому присвоим переменной n
значение i.
Теперь остаётся лишь просуммировать элементы массива. И вывести значение суммы
на экран. Она будет равна 12.
Приступим к написанию программы. Назовём нашу
программу sum.
Так как число по условию не длиннее 9 цифр и значение цифры может быть только
целым, раздел описания переменных будет содержать массив a из 9 элементов типа integer, а также переменные i,
n,
s
и k
типа integer.
Тело программы будет начинаться с команды вывода на экран поясняющего сообщения
о том, что пользователь работает с программой нахождения суммы цифр числа, и
запрос на ввод числа. Далее будет следовать команда считывания числа k. Теперь присвоим переменной i
значение ноль и запишем цикл преобразования числа k в массив цифр. Он будет
продолжаться, пока k
больше 0 и будет содержать команду увеличения i на 1, команду
присваивания i-тому элементу массива a значения остатка от деления k на 10 и команду присваивания
переменной k
её значения, поделённого без остатка на 10.
После окончания цикла присвоим переменной n значение переменной i,
а переменной s
– ноль. После чего запишем цикл for i:=1
to
n
do,
который будет содержать команду присваивания переменной s суммы её текущего значения и
значения i-того
элемента массива a.
Далее будет следовать команда вывода на экран поясняющего сообщения «Сумма цифр
числа:», а также значения переменной s.
Исходный
код программы
Запустим программу на выполнение. Введём число 34 964.
Получим ответ. Сумма цифр данного числа будет равна 26. Программа работает
правильно, следовательно, задача решена.
Пример
работы программы
Обратим внимание, что данную задачу можно решать и без
использования массива. Для этого достаточно присвоить переменной s значение 0 в начале программы, и при
выделении каждой цифры числа сразу добавлять её значение к s.
Изменим нашу программу. Уберём из неё цикл нахождения
суммы элементов массива, команду присваивания переменной s значения 0 перенесём сразу после
ввода числа, а также изменим цикл выделения цифр числа. Теперь можно убрать из
раздела описания переменных переменные i и n, а также массив a.
Изменённая
программа
Из-за того, что изменённая программа имеет в своём
составе меньшее количество команд и использует меньшее количество переменных,
то есть потребляет меньше оперативной памяти, она будет работать быстрее. Снова
запустим программу на выполнение и введём то же число, что и в первый раз, 34
964. Как и в первый раз, программа вывела ответ 26. Программа работает верно.
Пример
работы изменённой программы
Важно запомнить:
Алгоритм
нахождения суммы элементов массива состоит из трёх шагов:
1)
Выделения ячейки памяти для хранения
суммы.
2)
Присваивания ей значения 0.
3) Перебора элементов массива с вычислением для каждого суммы
его значения и значения ячейки памяти для хранения суммы и с присваиванием
результата ячейке памяти для хранения суммы.
Мы научились применять алгоритм нахождения суммы
элементов массива при решении задач.
Алгоритм вычисления суммы и произведения
рассмотрим на следующем примере (Рис.
5.2):
Пример.
Дан одномерный массив из N
элементов A[1, N].
Требуется найти сумму положительных
элементов и произведение элементов,
принадлежащих интервалу [B,
C].
Следует оговорить, что предварительно
идентификатору суммы Sum необходимо
присвоить значение Sum =
0, а идентификатору произведения Pr
= 1.
Структура алгоритма, приведенного на
Рис. 5.2:
-
Ввод
количества элементов в массиве. -
Ввод
массива. -
Ввод
границ интервала для вычисления
произведения. -
Подготовка
идентификаторов суммы и произведения. -
Организация
цикла по идентификатору i
от 1 до N с шагом 1. -
Проверка
условия положительности элемента
массива A[i]. -
Увеличение
значения суммы на положительный элемент
массива A[i]. -
Проверка
условия принадлежности элемента массива
A[i] интервалу [B,
C]. -
Формирование
произведения элементов массива. -
Вывод
результирующих значений суммы и
произведения элементов массива.
5.3 Алгоритмы определения экстремального элемента
Задача поиска максимального (минимального)
элемента массива возникает при решении
различных задач при упорядочивании,
анализе данных, масштабировании
информационных массивов и реализовывается
в двух алгоритмах:
-
Поиск
максимального (минимального) элемента
массива. -
Поиск
максимального (минимального) элемента
массива принадлежащего некоторому
интервалу, например [B;
C].
Алгоритм
поиска максимального (не
нарушая общности, данный алгоритм
рассмотрим для случая определения
максимального элемента массива) элемента
в массиве основан на следующей
идее (Рис. 5.3). Идентификатору максимального
элемента присваивается значение первого
элемента массива, идентификатору его
индекса – присваивается 1. Затем в цикле
каждый элемент массива сравнивается с
максимальным, и в случае, если он больше
максимального, выполняется переадресация
с фиксированием номера этого элемента
в массиве.
Алгоритм
поиска минимального элемента в интервале
(Рис. 5.4) основан на том, что проверяется,
принадлежит ли элемент массива заданному
интервалу. Если элемент принадлежит
интервалу, то сначала необходимо
идентификатору минимального значения
присвоить значение первого из элементов
массива, принадлежащих интервалу. Это
выполняется с помощью флажка –
переключателя, которому вначале алгоритма
присваивается фиксированное значение.
Как только найден первый элемент,
принадлежащий заданному интервалу,
идентификатору минимального значения
присваивается это значение, запоминается
его индекс и значение флажка меняется.
Для второго, третьего и т.д. элементов
массива, принадлежащих заданному
интервалу, производится сравнение с
найденным значением минимального
элемента из интервала. Если рассматриваемый
элемент массива меньше минимального,
то идентификатору минимального элемента
присваивается его значение и запоминается
его номер.
Переход на эту ветвь алгоритма
осуществляется по изменившемуся значению
флажка.
Если элемент массива не принадлежит
интервалу или принадлежащий элемент
массива не меньше минимального, то
рассматривается следующий элемент
массива.
По окончании обработки массива проверяется
значение флажка. Если это значение равно
начальному, то в заданном интервале не
оказалось ни одного элемента массива.
Об этом выдается соответствующее
сообщение пользователю, в противном
случае на выдается значение минимального
элемента и его номер в массиве.
Структура алгоритма Рис. 5.4:
-
Ввод
количества и элементов массива А. -
Ввод
интервала значений. -
Первоначальное
значение флажка и счетчика циклов. -
Приращение
счетчика циклов. -
Проверка
условия завершения цикла. -
Проверка
значения флажка. -
Вывод
сообщения об отсутствии элементов в
заданном интервале. -
Вывод
минимального значения и его индекс. -
Проверка
принадлежности элемента массива
заданному интервалу. -
П
роверка
значения флажка. -
Изменение
значения флажка – найден первый элемент
массива, принадлежащий заданному
интервалу. -
Сравнение текущего элемента с минимальным.
-
Переадресация,
определение номера минимального
элемента в массиве.
Отметим, что для упрощения структуры
алгоритма целесообразно ввести
подпрограмму-процедуру, выполняющую
действия, отмеченные пунктирным
прямоугольником на рис. 5.4.
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
Главная
>> Каталог задач
>> Последовательности
>>
Найти максимальную сумму в последовательности
Aвтор:
Дата: 20.04.2004
Просмотров: 132150
реализации(C++: 1шт…)
+добавить
- Вступление
- Задача и простой алгоритм
- Кубический алгоритм (N3 очень медленно!)
- Два квадратичных алгоритма (~N2)
- И второй квадратичный
- Алгоритм «разделяй и властвуй» (~N*LgN)
- And winner is… сканирующий (линейный) алгоритм!
- Подробней про замеры
- История
- Ценные методы, подходы
- Все реализации
Вступление
Одна из самых интересных задач. На ее примере познаются многие, очень полезные подходы для написания быстрых, хороших алгоритмов. К сожалению, данная задача в чистом виде, как выясняется — мало где применяется: а случаи отличные от одномерного — требуют написания алгоритмов намного сложней, и намного менее красивых чем приведенные здесь.
По книге Джона Бентли:
«Жемчужины программирования»
Задача и простой алгоритм
Задача эта появляется при распознавании одномерного шаблона; к ее истории мы обратимся позже. На входе имеется массив X из N вещественных чисел, на выходе должна быть получена максимальная сумма любой непрерывной последовательности элементов массива. Например, если во входном массиве содержатся следующие 10 элементов (рис. 8.1):
— программа должна вернуть сумму х[2..6], то есть 187. Задачу легко решить с положительными числами — максимальная сумма будет равна сумме всех элементов массива. Проблема возникает, когда появляются отрицательные числа: стоит ли включать такой элемент в выбранную последовательность, надеясь, что соседние компенсируют его? Чтобы завершить постановку задачи, скажем, что когда все элементы массива отрицательны, на выходе должна быть сумма элементов пустой последовательности элементов массива, равная нулю.
Кубический алгоритм (N3 очень медленно!)
Первый вариант программы, который приходит в голову, перебирает все пары целых i и j, где 0<=i<=j
maxsofar = 0
for i = 0 to n-1
for j = 0 to n-1
sum = 0
for k = i to j
sum += x[k]
/* sum - сумма всех элементов x[i..j] */
maxsofar = max(maxsofar, sum)
/* на выходе получаем в maxsofar -
максимальную сумму */
Программа короткая, ясная, ее легко понять. К сожалению, она работает медленно. На моем компьютере(прим. ред: в те времена) ей требуется 22 минуты, если n=10 000, и 15 дней, если n=100 000. Вопросы, связанные с временем выполнения, будут детально рассмотрены ниже в разделе про замеры производительности.
Конкретные данные о времени работы программы хорошо приводить в байках, но почувствовать реальную эффективность алгоритма можно, используя оценку эффективности с помощью понятия «О-большое». Внешний цикл выполняется ровно n раз, средний — не более n раз на каждый из проходов внешнего цикла. Перемножив эти величины, получим, что код внутри среднего цикла выполняется О(n2) раз. Внутренний цикл выполняется не более n раз, поэтому его мы тоже записываем как О(n). Перемножив все эти величины, получим, что время работы алгоритма пропорционально n3. Такие алгоритмы называются кубическими.
Этот пример иллюстрирует метод анализа с помощью «О-большого», а также его сильные и слабые стороны. Главный недостаток его в том, что мы все равно не знаем, сколько будет работать программа при конкретных входных данных, а знаем лишь, что количество шагов будет О(n3). Этот недостаток обычно компенсируется двумя сильными сторонами метода: анализ с помощью «О-большого» легко производить (как в примере выше), а информация об асимптотическом поведении алгоритма обычно достаточна для предварительных оценок эффективности.
Далее по тексту асимптотическое время работы алгоритма используется в качестве единственной оценки производительности программы. Более высокая точность анализа для данной задачи разбирается ниже в разделе про замеры. Прежде чем читать дальше, задумайтесь на минуту и попробуйте найти более быстрый алгоритм.
Два квадратичных алгоритма (~N2)
Большинство программистов реагируют на алгоритм 1 одинаково: «есть очевидный способ сделать его намного быстрее». Таких способов на самом деле два, причем конкретному программисту обычно очевиден лишь один из двух. Оба алгоритма обладают квадратичным временем работы — делают О(n2) операций для массива размером n — и в обоих сумма x[i..j] вычисляется за постоянное количество шагов, а не за j-i+1 сложений, как в алгоритме 1. Однако эти два алгоритма используют принципиально различные методы вычисления сумм за конечное число шагов.
Первый квадратичный алгоритм позволяет быстро вычислить сумму благодаря тому, что сумма x[i..j] легко получается из предыдущей: x[i..j-l]. Использование этого свойства позволяет получить алгоритм:
maxsofar = 0
for i = 0 to n-1
sum = 0
for j = i to n-1
sum += x[j]
/* sum - сумма всех элементов x[i..j] */
maxsofar = max(maxsofar, sum)
Операторы внутри внешнего цикла выполняются n раз, а те, что лежат внутри внутреннего, — не более чем n раз, так что время работы алгоритма составляет О(n2).
И второй квадратичный
Альтернативный квадратичный алгоритм вычисляет сумму во внутреннем цикле, обращаясь к структуре данных, которая строится отдельно, до начала первого цикла. Создается массив cumarr, 1-й элемент которого содержит кумулятивную сумму значений х[0..i], поэтому сумму x[i…j] можно получить как разность cumarr[j] -cumarr[i-l]. В итоге получим:
cumarr[-1] = 0
for i = 0 to n-1
cumarr[i] = cumarr[i-1] + x[i]
maxsofar = 0
for i = 0 to n-1
for j = i to n-1
sum = cumarr[j] - cumarr[i-1]
/* sum - сумма всех элементов x[i..j] */
maxsofar = max(maxsofar, sum)
Этот код требует также О(n2) операций; анализ проводится так же, как и для квадратичного алгоритма №1.
Рассмотренные три варианта алгоритмов исследуют все возможные пары начального и конечного индексов, вычисляя сумму элементов последовательности. Поскольку таких последовательностей О(n2), ни один алгоритм, проверяющий их все, не может быть быстрее квадратичного. Можете ли вы придумать способ обойти проблему и получить более быстрый алгоритм?
Алгоритм «разделяй и властвуй» (~N*LgN)
Первый из быстрых алгоритмов, по времени выполнения он линейно-алгорифмичный и при этом достаточно сложен, поэтому если вы запутаетесь в деталях, можете перейти сразу к следующему разделу, вы не слишком много потеряете при этом. Итак, алгоритм основан на следующем правиле:
!Если нужно решить задачу размера n, следует рекурсивно решить 2 подзадачи размера приблизительно n/2, а затем объединить их решение в единое целое!
В данном случае мы имеем дело с массивом размера n, поэтому наиболее естественным способом разделения задачи на 2 подзадачи будет создание 2-х массивов приблизительно одинаковогоразмера. Один из ним мы назовем A, а другой B:
Затем мы рекурсивно найдем подпоследовательности с максимальной суммой элементов в масивах A и B; одну из них назовем ma, а другую — mb:
| ma | mb |
Соблазнительная мысль о том, что мы решили задачу, потому что подпоследовательность всего массива с максимальной суммой должна равняться либо ma, либо mb, оказывается неправильной, потому что эта искомая подпоследовательность может и пересекать границу между A и B. Такую подпоследовательность мы назовем mc, поскольку она пересекает границу.
Итак, наш алгоритм «разделяй и властвуй» должен рекурсивно находить ma и mb, после чего каким-то другим способом находить mc и сравнивать их между собой.
Этого описания почти достаточно для написания программы. Осталось лишь определить способ работы с массивами малого размера и способ вычисления mc. Первое сделать несложно: подпоследовательность с максимальной суммой для массива из одного элемента равна этому элементу, если он положителен, или нулю, если элемент отрицателен, а максимальная подпоследовательность пустого массива равна нулю. Для вычисления mc отметим, что его левая часть представляет собой максимальную подпоследовательность элементов, заканчивающуюся на границе A и B и простирающуюся в A, а правая часть — такую же подпоследовательность, лежащую в B. Собрав все это вместе, получим следующий алгоритм:
function maxsum(l, u)
if l > u
return 0 /* пустой массив */
if l == u /* 1 элемент */
return max(0, x[l])
m = (l + u) / 2
/* поиск макс. последовательности
слева от границы: */
lmax = sum = 0
for i = m downto l
sum += x[i]
lmax = max(lmax, sum)
/* поиск макс. последовательности
СПРАВА от границы: */
rmax = sum = 0
for i = m + 1 to u-1
sum += x[i]
rmax = max(rmax, sum)
return max(lmax+rmax, // =>Mc
maxsum(l, m) // =>Ma
maxsum(m+1, u)) // =>Mb
/* А теперь запуск всего алгоритма */
answer = maxsum(0, n-1)
Код достаточно сложен, в нем легко ошибиться, но он решает задачу за О(n log n) операций. Мы можем доказать это несколькими способами. Неформальное доказательство заключается в том, что алгоритм выполняет работу О(n) на каждом из O(log n) уровней рекурсии. Доказательство можно сделать более строгим, используя рекуррентные соотношения. Если Т(n) обозначает время решения задачи размера n, то Т(1) = О(1) и Т(n) = 2Т(n/2) + О(n).
And winner is… сканирующий (линейный) алгоритм!
Воспользуемся простейшим алгоритмом для работы с массивами. Начинать следует с левого конца массива (элемента х[0]), затем нужно перебрать все элементы и закончить на правом конце (элемент х[n-1]), все время сохраняя информацию о наилучшей на данный момент сумме. Изначально максимальная сумма равна нулю. Предположим, что мы решили задачу для х[0. .i-1], как можно расширить ее решение, добавив в него элемент x[i]? Используем те же соображения, что и для алгоритма «разделяй и властвуй»: подпоследовательность первых i элементов с максимальной суммой может либо целиком лежать в первых i элементах (хранится в maxsofar), либо заканчиваться элементом i (хранится в maxendinghere):
Вычисление maxendinghere каждый раз заново, аналогично алгоритму 3, даст нам в итоге еще один квадратичный алгоритм. Мы можем обойти это, используя тот же метод, который привел нас к алгоритму 2: вместо того, чтобы находить максимальную подпоследовательность, заканчивающуюся элементом i, мы воспользуемся максимальной подпоследовательностью, заканчивавшейся элементом i-1. В итоге получаем алгоритм 4:
maxsofar = 0
maxendinghere = 0
for i = 0 to n-1
/* инвариант: значения maxendinghere и
maxsofar точны для x[0..i-1] */
maxendinghere = max(maxendinghere + x[i], 0)
maxsofar = max(maxendinghere, maxsofar)
Ключ к пониманию этой программы — переменная maxendinghere. Перед первым оператором присваивания в цикле значение переменной равно максимальной сумме подпоследовательностей, заканчивающихся элементом i-1. Оператор присваивания изменяет ее содержимое таким образом, что оно становится равным максимальной сумме подпоследовательностей, заканчивающихся элементом i. Оператор увеличивает это значение добавлением x[i] до тех пор, пока это действие оставляет сумму подпоследовательности положительной; возможные отрицательные значения заменяются нулем, поскольку максимальная по сумме подпоследовательность, заканчивающаяся элементом i, теперь является пустой. Хотя этот код труден для понимания, он прост и быстр, потому что выполняется за О(n) операций. Такие алгоритмы называются линейными.
Подробней про замеры
Пока что мы действовали довольно безответственно, используя «О-большое». Пришло время поговорить о реальных вещах и измерить время выполнения программ. Я реализовал четыре приведенных выше алгоритма на языке С на компьютере Pentium II 400 МГц, измерил скорость их работы и экстраполировал данные, сведя их в табл. 8.1. Время выполнения квадратичного алгоритма №2 обычно отличалось не более чем на 10% от квадратичного алгоритма №1, поэтому я не стал выделять его в отдельный столбец:
Эта таблица дает довольно много разнообразных сведений. Самый главный вывод: выбор правильного алгоритма может очень сильно влиять на время решения задачи. Это особенно подчеркивается в средней части таблицы. Последние две строки показывают, как связаны время решения задачи и ее размер.
Есть еще один важный момент. При сравнении кубического, квадратичного и линейного алгоритмов постоянные множители в выражениях для производительности значат не так уж много. Для быстрорастущих функций постоянные множители значат еще меньше. Чтобы подчеркнуть важность этого момента, я поставил эксперимент, в котором разница в постоянных множителях была максимально возможной. Алгоритм 4 был реализован на компьютере Radio Shack TRS-80 Model III (бытовой компьютер 1980 года выпуска с процессором Z80 на частоте 2.03 МГц). Чтобы еще больше замедлить его работу, я использовал интерпретатор Бейсика, что замедляет программу в 10-100 раз по сравнению с компилированным кодом. Алгоритм 1 был реализован на компьютере Alpha 21164 с частотой 533 МГц. Время выполнения кубического алгоритма росло по формуле 0,58n3 нc, а для линейного алгоритма — 19,5n мс (то есть 19 500 000n наносекунд или 50 элементов в секунду!). В таблице 8.2 показаны результаты экспериментов для различных размеров задачи:
Отношение постоянных множителей в виде 1/33 000 000 — давало некоторое преимущество кубическому алгоритму при малых размерах задачи, но линейный алгоритм неизбежно должен был нагнать кубический при увеличении n. Оба алгоритма решают задачу за одинаковое время при n ~ 5800; при этом обоим компьютерам требовалось около 2 мин:
История
История задачи проливает свет на методы разработки алгоритмов. Наша небольшая задачка возникла в рамках работы по распознаванию образов, которой занимался Ульф Гренандер (Ulf Grenander) в Университете Брауна. Исходная задача была двумерной. При этом подмножество с максимальной суммой элементов отражало наибольшее соответствие между двумя цифровыми изображениями. Поскольку в двумерном варианте решить задачу было слишком тяжело, Гренандер упростил ее и занялся вначале одномерной, чтобы вникнуть в суть дела.
Гренандер решил, что кубический алгоритм выполняется слишком медленно, и придумал алгоритм 2. В 1977 году он рассказал о задаче Майклу Шамосу (Michael Shamos), который в тот же вечер придумал алгоритм 3. Когда Шамос вскоре после этого показал задачу мне, мы решили, что этот вариант алгоритма является лучшим из возможных, потому что незадолго до того исследователи показали, что несколько аналогичных задач могут быть решены только за время, пропорциональное ~ n*log n. Спустя несколько дней Шамос рассказал о задаче и ее истории на семинаре Карнеги Меллона (Carnegie Mellon), где присутствовал статистик Джей Кадан (Jay Kadane), который и набросал алгоритм 4, затратив на это приблизительно минуту. К счастью, мы знаем, что никакой алгоритм не может работать быстрее этого последнего четвертого варианта. Любой правильный алгоритм решения такой задачи потребует О(n) операций.
Хотя одномерная задача была решена полностью, исходная задача Гренандера в двумерной постановке остается открытой проблемой и сегодня, 20 лет спустя, когда второе издание этой книги выходит в печать. Из-за вычислительной трудоемкости всех известных алгоритмов Гренандеру пришлось отказаться(!!!) от этого подхода к распознаванию образов.
Эта история иллюстрирует ценные методы разработки алгоритмов.
Ценные методы, подходы
- Сохранение данных во избежание повторных вычислений
Эта простая форма динамического программирования использовалась в алгоритмах 2 и 4. Используя память для сохранения результатов, мы исключаем необходимость повторного их вычисления. - Предварительная обработка данных и помещение их в структуры
Структура cumarr в кубическом алгоритме №2 позволяет быстро вычислить сумму подпоследовательности. - Алгоритмы «разделяй и властвуй»
Алгоритм 3 использует правило «разделяй и властвуй». В учебниках по теории алгоритмов описаны более сложные формы применения этого правила. - Сканирующие алгоритмы
Задачи с массивами часто могут быть решены с помощью вопроса «как можно расширить решение задачи с х[0..i-1] до х[0..i]?». Алгоритм 4 сохраняет предыдущий результат и некоторые дополнительные данные для вычисления следующего результата. - Кумулятивные суммы
Алгоритм №2 использует таблицу кумулятивных сумм, где i-й элемент содержит кумулятивную сумму первых i значений массива х. Такие таблицы часто используются при работе с диапазонами. - Нижняя граница
Разработчики алгоритмов могут спокойно спать только тогда, когда они знают, что придуманный алгоритм — самый быстрый из возможных. Для этого им приходится доказывать существование нижней границы. Линейная скорость решения данной задачи была доказано. Доказательство существования нижних границ может быть достаточно сложным.
Реализации:
C++(1), C#(5)
+добавить
1)
Еще один линейный алгоритм поиска максимальной суммы последовательности элементов в массиве на C++, code #629[аноним:Владимир]
Суммирование
Начнем с простейшей задачи — вычисление суммы элементов массива:
 |
( 3.1) |
Классический алгоритм выглядит так:
S = 0; for(int i = 0; i < n; i++) S = S + x[i];
Листинг
3.1.
Последовательный алгоритм вычисления суммы элементов массива
Алгоритм последовательный и не допускает распараллеливания, поскольку на каждом шаге цикла используется значение S, вычисленное на предыдущем шаге. Заметьте, цикл не допускает распараллеливания, если в теле цикла есть оператор присваивания, у которого одна и та же скалярная переменная встречается как в левой, так и в правой части оператора (S в нашем примере).
Поскольку в алгоритме используется только один цикл типа for с шагом, равным единица, то алгоритм имеет линейную временную сложность:
 |
( 3.2) |
Когда суммирование должен выполнять только один процессор, то это оптимальный по времени алгоритм. Но суммирование можно вести самыми разными способами, если к вычислению суммы привлечь несколько процессоров. В
«Параллельные вычисления»
мы уже анализировали «пирамидальный» алгоритм суммирования, допускающий распараллеливание. Вот возможная запись такого алгоритма на С#:
int[] y = new int[n];
Array.Copy(x, y, n);
int m = n;
while (m != 1)
{
for (int i = 0, j = m - 1; i < j; i++, j--)
y[i] = y[i] + y[j];
m = (m + 1) / 2;
}
S = y[0];
Листинг
3.2.
Пирамидальный алгоритм вычисления суммы элементов массива
В этом более сложном варианте алгоритма появились два цикла. Внутренний цикл for может быть распараллелен. Нетрудно видеть, что множества переменных, используемых на каждой итерации этого цикла, взаимно не пересекаются. Выполнение этого условия достаточно для распараллеливания. Внешний цикл while распараллелить нельзя, поскольку итерации «склеиваются» общей переменной m.
Для компьютера с одним процессором этот алгоритм будет хуже классического алгоритма по ряду причин:
- Ему нужна дополнительная память, поскольку промежуточные результаты необходимо запоминать. Для этого введен массив y той же размерности, что и исходный массив x.
- Алгоритм усложнен, — вместо одного цикла классического алгоритма, вводятся два цикла. Алгоритм менее понятен и отладка его может вызывать затруднение. Несомненно, что программисту потребуется больше времени на разработку и отладку такого алгоритма.
- Алгоритм при последовательном выполнении хотя и имеет ту же временную сложность — O(n), но константа у него больше, чем у классического алгоритма, поскольку во внутреннем цикле используются три переменные с индексами, вместо одной, как в классическом алгоритме.
В чем же достоинство этого алгоритма? Одно несомненное достоинство у него есть — он допускает распараллеливание. Если запускать его на идеальном метакомпьютере с неограниченным числом процессоров, то тогда, используя n/2 процессоров, все вычисления внутреннего цикла можно выполнять параллельно.
Сложность внутреннего цикла при распараллеливании будет равна O(1), а общая сложность определяется внешним циклом и равна O(log n). В
«Параллельные вычисления»
, где этот алгоритм уже анализировался, помимо ускорения в рассмотрение вводилась и такая характеристика алгоритма как эффективность. У пирамидального алгоритма эффективность низкая, поскольку для достижения максимального ускорения требуется n/2 процессоров — число, пропорциональное размерности массива. Метакомпьютеры и даже суперкомпьютеры с большим числом процессоров не всегда под рукой, но и при их наличии приходится заботиться об эффективности.
Давайте рассмотрим алгоритмы суммирования, ориентированные на конечное число процессоров — на многоядерные компьютеры. Пусть в нашем распоряжении есть компьютер с фиксированным числом процессоров — р. Как выполнить суммирование, используя все возможности такого компьютера? Естественный алгоритм, допускающий распараллеливание, понятен, — нужно провести распараллеливание по данным, разбив исходный массив на р групп, примерно равной размерности. Тогда можно параллельно выполнить суммирование для каждой группы, после чего просуммировать полученные результаты. И в этом случае понадобится дополнительная память — массив размерности р, хранящий результаты промежуточных сумм.
Разбиение массива на группы можно выполнить разными способами. Разумными представляются две стратегии. Первая состоит в том, чтобы исходный массив нарезать на р отрезков и поручить каждому процессору суммирование элементов соответствующего отрезка. Вторая стратегия основана на том, чтобы каждый процессор суммировал элементы, отстоящие на расстоянии р. Если соответствующим образом выбрать начальный элемент для каждого процессора, то это позволит вести параллельное суммирование.
Вот вариант записи сегментного алгоритма, соответствующего первой стратегии:
int count_p = Environment.ProcessorCount;
int[] y = new int[count_p];
int m = n / count_p + 1;
int start = 0, finish = 0;
for(int k =0; k < count_p; k++)
{
start = k * m;
finish = (k+1)*m < n ? (k+1)*m : n;
for (int i = start; i < finish; i++)
y[k] += x[i];
}
S = y[0];
for (int i = 1; i < count_p; i++)
S += y[i];
Листинг
3.3.
Сегментный алгоритм вычисления суммы p процессорами
Чуть проще шаговый алгоритм, соответствующий второй стратегии:
int[] y = new int[count_p];
for (int k = 0; k < count_p; k++)
{
for (int i = k; i < n; i += count_p)
y[k] += x[i];
}
S = y[0];
for (int i = 1; i < count_p; i++)
S += y[i];
Листинг
3.4.
Шаговый алгоритм вычисления суммы p процессорами
Оба эти варианта допускают параллельное выполнение тела внешнего цикла. В этом случае сложность алгоритма определяется сложностью операторов, составляющих тело этого цикла, фактически, сложностью внутреннего цикла — O(n/count_p). Ускорение для обоих вариантов равно count_p — числу процессоров, а эффективность равна единице. Таковы теоретические оценки. В последующих главах посмотрим, что можно получить на практике.
Задача суммирования крайне важна, поскольку встречается в самых разных приложениях. Она легко обобщается на случай, когда суммируются не элементы массива, а функции, зависящие от параметра i:
 |
( 3.3) |
Все, что сказано о суммировании, касается и других подобных задач — нахождение произведения элементов массива, максимального или минимального элемента и других задач этого класса.
Суммирование рядов
Нахождение суммы конечного ряда принципиально не отличается от нахождения суммы элементов массива. Поговорим о том, как вычислять сумму бесконечного сходящегося ряда:
 |
( 3.4) |
Необходимым условием сходимости ряда является стремление 
к нулю, когда i стремится к бесконечности. В программировании это условие, в отличие от математики, является и достаточным условием сходимости. В математике это не так, — примером является расходящийся гармонический ряд с общим членом ряда 1/i. В мире компьютеров все дискретно, нет иррациональности, нет бесконечности, вычисления не всегда точны и могут иметь некоторую погрешность. При нахождении на компьютере суммы гармонического ряда, начиная с некоторого i*, значение общего члена станет равным нулю (так называемому машинному нулю) из-за ограниченности разрядной сетки, отводимой для хранения числа.
В программировании не ставится задача вычисления точного значения S в формуле (3.4), — достаточно вычислить это значение с некоторой точностью. В сравнении с конечными суммами дополнительная сложность в построении алгоритма состоит в том, что заранее неизвестно, сколь много членов ряда необходимо вычислить, чтобы найти сумму ряда с нужной точностью. Классический алгоритм основан на том, что суммирование прекращается, как только очередной член суммы становится по модулю меньше заданной точности 
. При этом предполагается, что выполняется условие сходимости ряда, так что все не учитываемые члены ряда будут по модулю заведомо меньше .
Вот пример записи такого алгоритма:
double eps = 1E-15;
double i = 1;
double a = 1;
double S = 0;
while (Math.Abs(a) > eps)
{
//Вычисление общего члена ряда
a = 1.0 / ((4 * i + 1) * (4 * i - 1)); // пример
S += a;
i++;
}
Листинг
3.5.
Классический алгоритм вычисления суммы сходящегося ряда
С программистской точки зрения алгоритмы 3.1 и 3.5 во многом схожи. Разница в том, что в первом случае используется цикл for, во-втором — цикл while. Из-за этого различия труднее оценить временную сложность алгоритма, поскольку нет такого естественного параметра как n в алгоритме 3.1. Число суммирований зависит как от формулы, задающей общий член ряда, так и от выбранной точности вычислений — .
Другой подход к вычислению суммы сходящегося ряда состоит в том, чтобы вместо точности задавать N — число суммируемых элементов, сводя исходную задачу к задаче вычисления суммы конечного ряда. Иногда алгоритм усложняют, вводя дополнительный цикл while, в котором на каждом шаге цикла N увеличивается, например, вдвое. Цикл заканчивается, когда два последующих вычисленных значений суммы отличаются на величину, меньшую заданной точности . Оценить временную сложность такого алгоритма затруднительно.
Вернемся к рассмотрению алгоритма 3.5. По уже указанным причинам он не допускает распараллеливания. Но, как и для вычисления конечных сумм, нетрудно построить допускающую распараллеливание версию, ориентированную на p процессоров. Для конечных сумм мы рассматривали два варианта — сегментный и шаговый алгоритм.
Сегментный алгоритм требует нарезки на сегменты примерно равной длины, для этого нужно знать N — число суммируемых элементов. Поэтому этот вариант алгоритма следует применять тогда, когда заранее выбирается N.
Модификацию шагового алгоритма, допускающего распараллеливание, выполнить несложно. Для каждого процессора нужно задать начальное значение, после чего процессор будет вести суммирование, пока общий член не станет меньше заданной точности .
double i = 1;
double a = 0;
double[] y = new double[count_p];
for (int k = 0; k < count_p; k++)
{
i = k+1;
a = 1.0 / ((4 * i + 1) * (4 * i - 1)); //начальное значение
while (Math.Abs(a) > eps)
{
y[k] += a;
i += count_p ;
a = 1.0 / ((4 * i + 1) * (4 * i - 1));
}
}
S = y[0];
for (int k = 1; k < count_p; k++)
S += y[k];
Листинг
3.6.
Шаговый алгоритм вычисления суммы сходящегося ряда p процессорами