В
Все
М
Математика
О
ОБЖ
У
Українська мова
Д
Другие предметы
Х
Химия
М
Музыка
Н
Немецкий язык
Б
Беларуская мова
Э
Экономика
Ф
Физика
Б
Биология
О
Окружающий мир
Р
Русский язык
У
Українська література
Ф
Французский язык
П
Психология
А
Алгебра
О
Обществознание
М
МХК
В
Видео-ответы
Г
География
П
Право
Г
Геометрия
А
Английский язык
И
Информатика
Қ
Қазақ тiлi
Л
Литература
И
История
Dzhyzefina
Dzhyzefina
20.03.2020 12:31 •  Информатика

Упростить логические выражения: ̄̄̄̄̄̄̄̄̄ – ( ∨ ∨ )( ∨ ∨ )( ∨ ∨ )( ∨ ∨ )( ∨ ∨ )
̄̄̄̄̄
– ↔ ( → ( ∨ ( ↔ )))
̄̄̄̄
– ↔ ∨ → ↔ ∨ ( ∨ )


Упростить логические выражения: ̄̄̄̄̄̄̄̄̄ – ( ∨ ∨ )( ∨ ∨ )( ∨ ∨ )( ∨ ∨ )( ∨ ∨ ) ̄̄̄̄̄ – ↔ ( → ( ∨ (

Показать ответ
Ответ:
jova20011p0bpf9
jova20011p0bpf9
23.02.2023 07:54
Алгоритм. Отсортируем массив за 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
0,0(0 оценок)
Ответ:
Викусик1258
Викусик1258
29.04.2021 11:08
:D 
Ну го Ничего если  на паскале напишу ? 
uses crt;
var  a:array[1..50] of integer ;i,j,n,x,t,k:integer;b:string;
begin
read(n);     
for i:= 1 to n do     
begin     
a[i]:=random(15);     
write(a[i],' ');     
end;     
writeln;     
for i:= 1 to n-1 do     
for j:= i+1 to n do     
if a[i]> a[j] then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end;     
for i:= 1 to n do     
write(a[i],' ');     
writeln;     
read(x);     
for i:= 1 to n do     
 if a[i] = x then k:=k+1;     
 str(k,b);     
n:=length(b);     
 if k in  [11..19] then write (k,' раз') else     
 if k = 0 then  write('число ',x,' не встречается ')else     
case b[n] of     
 '0','1','5','6','7','8','9': write (k,' раз');     
 '3','4','2': write (k,' раза') ;     
end;
end.
0,0(0 оценок)
Популярные вопросы: Информатика
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота