1. можно выделить лишь три основных вида алгоритмов (для краткости далее будем называть их линейные, разветвляющиеся и циклические алгоритмы):
• линейной структуры,
• разветвляющейся структуры,
• циклической структуры.
Линейный алгоритм – алгоритм, в котором порядок действий фиксирован и каждое действие выполняется только один раз.
Разветвляющаяся структура алгоритм, при выполнении которого каждый раз последовательность действий может быть разная. Схема подобного алгоритма обязательно содержит хотя бы один блок (символ) "решение", который и обеспечивает разветвление вычислительного процесса.
Алгоритм циклической структуры – это алгоритм, в котором предусмотрено неоднократное выполнение одной и той же последовательности действий. На практике часто встречаются задачи, в которых одно или несколько действий бывает необходимо повторить несколько раз.
2. Блок-схема — рас тип схем (графических моделей), описывающих алгоритмы или процессы, в которых отдельные шаги изображаются в виде блоков различной формы, соединенных между собой линиями, указывающими направление последовательности.
3. Псевдоко́д — компактный, зачастую неформальный язык описания алгоритмов, использующий ключевые слова императивных языков программирования, но опускающий несущественные для понимания алгоритма подробности и специфический синтаксис.
Алгоритм. Отсортируем массив за O(nlogn). Запустим цикл по всем k, в теле цикла будем искать индексы i <= j, такие, что A[i] + A[j] = -A[k]. Понятно, что этот поиск надо делать за O(n), чтобы общее время работы было квадратичным.
Искать будем с двух указателей. Рассмотрим кусок массива, в котором ищем ответ A[l..r] (первоначально l = 1, r = n). Посмотрим на A[l] + A[r]. Если эта сумма больше, чем нужно, уменьшим на 1 число r, если меньше - увеличим на 1 число l, если равно -A[k] - победа, выводим ответ (l, r, k). Будем повторять это в цикле, пока l не станет больше r.
Если после выполнения цикла по k искомая тройка так и не нашлась, пишем "нет".
Корректность. Пусть в какой-то момент A[l] + A[r] < -A[k]. Тогда, чтобы иметь возможность получить A[i] + A[j] = -A[k], надо сумму увеличить. A[l] оказалось настолько мало, что даже если прибавить к нему самое большое возможное число (а это как раз A[r] - массив-то отсортирован!), то всё равно получается слишком мало. Значит, A[l] в ответе не будет, и можно безбоязненно выкинуть его из рассмотрения. Аналогично будет и в случае, когда A[l] + A[r] > -A[k]. Осталось показать, что если такая тройка индексов существует, то наш алгоритм не выдаст неверный ответ "нет". Но это очевидно: если ответ (I, J, K), то уж при k = K алгоритм что-нибудь да найдёт.
Время работы. Внутренний цикл выдает ответ не более чем за линейное время: всякий раз размер массива уменьшается на 1, всего элементов в массиве n, а на каждом шаге тратится константное время; пусть время выполнения внутреннего цикла T'(n) < an. Тогда все n проходов внешнего цикла затратят время T1(n) <= n T'(n) < an^2. Сортировку можно сделать за время T2(n) < b nlogn < bn^2 Общее время работы T(n) = T1(n) + T2(n) < an^2 + bn^2 = cn^2
// PascalABC.Net 3.0, сборка 1066 var s, wd: string; n, pt: integer;
begin Write('Введите строку: ');Readln(s); n := Length(s); pt := 1; repeat // Пропускаем все символы до первого непробельного while pt <= n do if s[pt] = ' ' then Inc(pt) else break; if pt <= n then begin // Выделяем очередное слово wd := ''; while pt <= n do if s[pt] <> ' ' then begin wd := wd + s[pt]; Inc(pt) end else break; if (wd <> '') and (LowCase(wd[1]) in ['м'..'я']) then Writeln(wd) end until pt > n; end.
Тестовое решение: Введите строку: **А роза упала на лапу Азора ** роза упала на
А вот так версия 3.0 позволяет решить задачу "по-современному":
// PascalABC.Net 3.0, сборка 1066 begin var s:=ReadString('Введите строку: '); Writeln('Результат: ',s.ToWords(' ').Where(x->x[1] in ['м'..'я'])) end.
1. можно выделить лишь три основных вида алгоритмов (для краткости далее будем называть их линейные, разветвляющиеся и циклические алгоритмы):
• линейной структуры,
• разветвляющейся структуры,
• циклической структуры.
Линейный алгоритм – алгоритм, в котором порядок действий фиксирован и каждое действие выполняется только один раз.
Разветвляющаяся структура алгоритм, при выполнении которого каждый раз последовательность действий может быть разная. Схема подобного алгоритма обязательно содержит хотя бы один блок (символ) "решение", который и обеспечивает разветвление вычислительного процесса.
Алгоритм циклической структуры – это алгоритм, в котором предусмотрено неоднократное выполнение одной и той же последовательности действий. На практике часто встречаются задачи, в которых одно или несколько действий бывает необходимо повторить несколько раз.
2. Блок-схема — рас тип схем (графических моделей), описывающих алгоритмы или процессы, в которых отдельные шаги изображаются в виде блоков различной формы, соединенных между собой линиями, указывающими направление последовательности.
3. Псевдоко́д — компактный, зачастую неформальный язык описания алгоритмов, использующий ключевые слова императивных языков программирования, но опускающий несущественные для понимания алгоритма подробности и специфический синтаксис.