Даны 2 массива: a(n), из n случайных чисел и b(n), из n случайных чисел.получить новый массив, который содержит сумму квадратов элементов массивов a(n) и b(n) с равными индексами. , не могу понять, 19 !
Алгоритм. Отсортируем массив за 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.
На Visual Basic так:
Нужно на форме создать текстовое поле TextBox1 и кнопку Button1, на нее повесить такую программу:
Sub Button1_Click()
Dim A() As Integer, B() As Integer, C() As Integer ' динамич. массивы
Dim n As Integer, i As Integer, Txt As String
n = InputBox ("Введите размер массивов")
ReDim A(n), B(n), C(n) ' Определяем размеры массивов
Txt = ""
For i = 1 To n
A(i) = InputBox ("Введите " & i & "-ый элемент массива A")
B(i) = InputBox ("Введите " & i & "-ый элемент массива B")
C(i) = A(i)^2 + B(i)^2 ' Присваиваем элементу C(i) сумму квадратов
Txt = Txt & C(i) & "; " ' Добавляем C(i) в текстовую переменную
Next i
TextBox1.Text = Txt ' Выводим весь массив C(i) в текстовое поле
End Sub