М
Молодежь
К
Компьютеры-и-электроника
Д
Дом-и-сад
С
Стиль-и-уход-за-собой
П
Праздники-и-традиции
Т
Транспорт
П
Путешествия
С
Семейная-жизнь
Ф
Философия-и-религия
Б
Без категории
М
Мир-работы
Х
Хобби-и-рукоделие
И
Искусство-и-развлечения
В
Взаимоотношения
З
Здоровье
К
Кулинария-и-гостеприимство
Ф
Финансы-и-бизнес
П
Питомцы-и-животные
О
Образование
О
Образование-и-коммуникации
ната1187
ната1187
31.03.2020 13:16 •  Информатика

Дан массив чисел: 33, 55, 25, 7, 16, 45, 22, 30, 41, 83,12, 17,31, 77 выполнить сортировку массива с метода методом шейкерной сортировки. описать последовательность действий. выполнить подсчет сравнений.

👇
Ответ:
Tigrmigr
Tigrmigr
31.03.2020

I. Последовательность действий

- Выделить массив от a[l] до a[r], где a - сортируемый массив, а l & r - крайний левый и крайний правый сортируемый елемент

- Провести сравнение елементов попарно двигаясь слева на право, если первый елемент больше второго - необходимо поменять их местами

- Откинуть крайнеправый елемент из сортируемого участка

- Провести сравнение елементов попарно двигаясь справа на лево, если первый елемент меньше второго - необходимо поменять их местами

- Откинуть крайне левый элемент из сортируемого участка

- Повторить с начала пока не останется сортируемых элементов

II. Оптимизация

Выполнение абсолютно всех проверок (прохождение по всем под массивам) не является обязательным при наличии механизма определяющего является ли массив отсортированным. Таковым может служить флаг, который будет выставлен при отсутствии перемещений элементов в выделенном под массиве на текущей итерации сортировки. Если он выставлен, следующая итерация - не выполняется.

III. Пример сортировки

Элементы что находятся в текущем под массиве - выделены [] скобками.

Элементы что сравниваются в текущей итерации выделены ()

[(33 55) 25 7 16 45 22 30 41 83 12 17 31 77] | 33 < 55 -> пропускаем

[33 (55 25) 7 16 45 22 30 41 83 12 17 31 77] | 55 > 25 -> меняем местами

...

7 12 16 [17 22 25 30 31 (33 41) 45] 55 77 83 | 33 < 41 -> пропускаем

7 12 16 [17 22 25 30 31 33 (41 45)] 55 77 83 | 41 < 45 -> пропускаем

Так как на протяжении всего прохода по под массиву не было перемещений -> сортировка завершена.

(Полное решение представлено в прикрепленной картинке)

Кол-во сравнений при оптимизации сортировки: 71

Если считать кол-во сравнений в сортировке без оптимизации (либо в самом неудачном раскладе сорируемого массива) то его можно будет посчитать так:

кол-во сравнений 2n - 3 - для прохода по подмостиву туда и обратно (n - кол-во элементов массива)

кол-во сравнений в сортировке - сумма сравнений для прохода по каждому из под массивов туда и обратно

кол-во под массивов в массиве будет равно n / 2

Соответственно имеем формулу \sum_{i=n}^{i1}(2n-3)_{i};i=i-2, или же другими словами: сумма элементов (2i - 3) от i, где i = n, пока i > 1, когда i = i - 2.

Ну и переведем её на наш пример:

n = 14

i = n

(2 * 14 - 3) + (2 * 12 - 3) + (2 * 10 - 3) + (2 * 8 - 3) + (2 * 6 - 3) + (2 * 4 - 3) + (2 * 2 - 3) =

25 + 21 + 17 + 13 + 9 + 5 + 1 = 91

Кол-во сравнений при оптимизации сортировки: 91


Дан массив чисел: 33, 55, 25, 7, 16, 45, 22, 30, 41, 83,12, 17,31, 77 выполнить сортировку массива с
4,6(68 оценок)
Открыть все ответы
Ответ:
tatiana85gandzii
tatiana85gandzii
31.03.2020
ответ: K = 0, L = 0, M = 0, N = 1.

Строишь таблицу истинности. Просто выполняешь каждое действие и заносишь его в таблицу.
⇒ импликация. Таблица истинности во вложении. Если математически, то это условие: a ≤ b. Если оно выполняется, то условие истинно.
Т.е. если a = 1, b = 0, то a ⇒ b = 0(ложь). Во всех остальных случаях 1(истина).

Выполнять надо по приоритету, как в математике. Сначала отрицание ¬, умножение ∧, сложение ∨ и т.д. Импликацию ⇒  обычно делают в конце, если нет эквивалентности ~. Ну и стоит обращать внимание на скобки.
4,5(22 оценок)
Ответ:

В курсе информатики при изучении раздела "Алгоритмы и исполнители" рассматривают исполнителя Чертежник.

Чертежник - это виртуальный компьютерный исполнитель, который предназначен для построения рисунков и чертежей на координатной плоскости, и представляет собой перо, которое  может поднимать, опускать и перемещать.

При перемещении опущенного пера за ним остается след.

Среда обитания - часть координатной плоскости (1-я четверть, где х и у - положительны).

Начальное положение Чертежника - точка (0; 0) и перо поднято.

После исполнения программы перо должно быть поднято и и находится в начале координат - точке (0; 0).

Основные команды:

field(m,n) - создать поле размером m×n

topoint(x,y) - переместить перо в точку (х; у)

penup - поднять перо

pendown - опустить перо

onvector(a,b) - сместить перо на вектор (a; b)

m и n - натуральные числа

х и у - целые числа

Подробнее - на -

Объяснение:

4,5(10 оценок)
Это интересно:
Новые ответы от MOGZ: Информатика
logo
Вход Регистрация
Что ты хочешь узнать?
Спроси Mozg
Открыть лучший ответ