Главная › Новости

Сумма элементов одномерного массива

Опубликовано: 06.09.2018

27 Сумма элементов массива

Презентация «Сумма элементов одномерного массива» . Размер 268 КБ. Автор: Андрюшина .

содержание презентации «Сумма элементов одномерного массива.ppt»

№	Слайд	Текст
1		Сортировка элементов одномерного массива Тема: «Сортировка элементов одномерного массива» Автор: Андрюшина А.В. Школа №616 г. Зеленоград 2009 г. Нахождение суммы отрицательных елементов одномерного массива. С++
2		Понятие массива А. Понятие массива. 1 2 3 4 5 6 7 8 9. -5 14 7 10 32 9 -45 34 16. Ряд однотипных данных, имеющих имя, порядковый номер и численное значение называются массивами.
3		Одномерный массив Пример: Сформировать одномерный массив из 9 элементов и распечатать его.
4		Сортировка элементов в массиве Сортировка элементов в массиве. Сортировка представляет собой процесс упорядочения элементов в массиве по возрастанию или убыванию их значений. Например: Массив Х из n элементов будет отсортирован в порядке возрастания значений его элементов, если X[1] <= X[2] <= … <= X [n] И в порядке убывания, если X[1] >= X[2] >= … >= X [n].
5		Способы сортировки массива Способы сортировки массива:
6		Сортировка массива методом «пузырька» Сортировка массива методом «пузырька». Сортировка методом пузырька использует метод обменной сортировки и основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов.
7		Принцип сортировки массива Принцип сортировки массива по возрастанию методом «пузырька». Сравним первый элемент массива со вторым. Если первый окажется больше второго, то поменяем их местами. Те же действия выполним для второго и третьего, третьего и четвёртого, I-го и (I + 1)-го, (n – 1)-го и n-го элементов. В результате этих действий самый большой элемент станет на последнее (n-е) место. Теперь повторим данный алгоритм сначала, но последний (n-й) элемент, рассматривать не будем, так как он уже занял своё место. После проведения данной операции самый большой элемент оставшегося массива встанет на (n - 1) место. Так повторяем до тех пор, пока не упорядочим весь массив.
8		Таблица сортировки массива Таблица сортировки массива по возрастанию. Сортировка массива А состоящего из 5 элементов, по возрастанию методом «пузырька». Номер элемента. Номер элемента. Номер элемента. Номер элемента. Номер элемента. Номер элемента. Исходный массив. 7. 3. 5. 4. 2. Первый просмотр. 3. 5. 4. 2. 7. Второй просмотр. 3. 4. 2. 5. 7. Третий просмотр. 3. 2. 4. 5. 7. Четвертый просмотр. 2. 3. 4. 5. 7. 1. 2. 3. 4. 5.
9		Блок-схема сортировки массива Блок-схема сортировки массива методом «пузырька».
10		Сформировать массив Сформировать массив из n элементов и упорядочить элементы в массиве по возрастанию их значений (метод «пузырька»).
11		Сортировка массива методом «перестановки» Сортировка массива методом «перестановки».
12		Таблица сортировки Таблица сортировки массива по убыванию методом «перестановки». 1. 7. 14. 14. 14. 14. 2. 9. 9. 9. 9. 9. 3. 1. 1. 1. 7. 7. 4. 14. 7. 7. 1. 5. 5. 5. 5. 5. 5. 1. Перестановки. Перестановки. Перестановки. Перестановки. Первая. Вторая. Третья. Четвертая. № Элементов. Значения элементов массива. Если n элементов, то количество перестановок n2.
13		Сортировка массива Перестановки. Перестановки. Перестановки. Перестановки. Таблица сортировка массива по возрастанию методом «перестановки». 1. 7. 1. 1. 1. 1. 2. 9. 9. 5. 5. 5. 3. 1. 7. 7. 7. 7. 4. 14. 14. 14. 14. 9. 5. 5. 5. 9. 9. 14. Первая. Вторая. Третья. Четвертая. № Элементов. Значения элементов массива. Если n элементов, то количество перестановок n2.
14		Блок-схема сортировки массива методом «перестановки» Блок-схема сортировки массива методом «перестановки». i:=1. J:=i+1. Нет. Да. a[i]>a[j]. Pr:=a[j] A[j:]=a[i] A[i]:=pr. j:=j+1. Нет. Да. j < n. i:=i+1. Да. i< n-1.
15		Значения элементов массива Сформировать массив А размерностью 10. Задать значения элементов массива с помощью ГСЧ . Расположить элементы массива по возрастанию (метод перестановки).
16		Задать значения Сформировать массив А размерностью 10. Задать значения элементов массива с помощью ГСЧ . Расположить элементы массива по убыванию (метод перестановки).
17		Сортировка массива методом «вставки» Сортировка массива методом «вставки». Сначала упорядочиваются два элемента массива. Затем делается вставка третьего элемента в соответствующее место по отношению к первым двум. Четвёртый элемент помещают в список из уже упорядоченных трёх элементов. Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены.
18		Массив из восьми элементов ПРИМЕР : Дан массив из восьми элементов. Первые шесть уже упорядочены, а седьмой нужно вставить между вторым и четвёртым. Сохраним его во вспомогательной переменной Х. Пятый элемент переместим на место шестого, четвёртый – на место пятого, а третий на место четвёртого. То есть выполнили сдвиг элементов массива на одну позицию вправо. Запишем содержимое вспомогательной переменной в третью позицию.
19		Блок-схема сортировки массива методом «вставки» Блок-схема сортировки массива методом «вставки». 1. Ввод n. Yi. i=1,n. Yj+1=Yj. J=j -1. i=2,n. Yj+1=X. X=Yi. i=1,n. j=i -1. Yj. Конец. Начало. 1.
20		Фрагмент программы Фрагмент программы, реализующей сортировку массива методом вставки. For i:=1 to n do Begin x:=y[i];{Сохраним текущий элемент массива.} {В переменной j будем хранить номера элементов, предшествующих текущему.} J:=i-1; {Сдвиг массива на одну позицию в право до тех пор, пока} While (x<y[j]) and (j>0) do Begin y[j+1] :=y[j]: j:=j-1; End; {Запись текущего элемента на соответствующую позицию,} {то есть перед элементами, превышающими его.} y[j+1]:=x; end;
21		Сортировка массива по возрастанию Сортировка массива по возрастанию методом «выбора». Найдем в массиве самый большой элемент и поменяем его местами с последним элементом. Повторим алгоритм поиска максимального элемента, уменьшив количество просматриваемых элементов на единицу и поменяем его местами с предпоследним элементом. Описанную выше операцию поиска проводим до полного упорядочивания элементов в массиве.. Для упорядочивания массива по убыванию необходимо перемещать минимальный элемент.
22		Схема сортировки массива методом «выбора» Блок – схема сортировки массива методом «выбора».
23		Быстрая сортировка Быстрая сортировка. Принцип работы. Один из самых быстрых алгоритмов, позволяющих достигать производительности ~ O(n*log n). 1. В исходной последовательности выбирается некоторый опорный элемент a[i]. 2. Пробегаемся по всей последовательности и элементы, меньшие, либо равные a[i] располагаем слева от него, большие - справа. Эту же самую процедуру рекурсивно запускаем для 2-х полученных половинок. <= a[i] a[i] >=a[i] Т.е. в 2-х полученных последовательностях слева и справа от выбранного на первом шаге элемента - также выбираем некоторый опорный ключ и перебрасываем соответствующие большие и меньшие чем он элементы. 4. В уже 4-х полученных последовательностях - тоже самое. Пока не получим последовательности, состоящие лишь из одного элемента. После выполнения всех рекурсий в результате получаем отсортированную исходную последовательность.
24		Выбор опорного элемента Выбор опорного элемента. При быстрой сортировке выбор опорного элемента на каждом шаге играет очень значительную роль, т.к. от этого зависит суммарная скорость выполнения всего алгоритма при различных условиях сортировки. Варианты выбора опорного элемента. Частичная упорядоченность элементов. Наиболее хаотичное расположение элементов. Самые распространенные варианты: • выбор середины отрезка • выбор случайного элемента последовательности • выбор первого элемента последовательности.
25		Алгоритм выбора опорного элемента Алгоритм выбора опорного элемента последовательности. Этот алгоритм был впервые описан К. А. Р. Хоаром в его классической статье «Быстрая сортировка».
26		Разделение массива Разделение массива. 4. 9. 7. 6. 2. 3. 8. i. j. 4. 9. 7. 6. 2. 3. 8. 4. 3. 7. 6. 2. 9. 8. 4. 3. 2. 6. 7. 9. 8. Чтобы отсортировать массив, мы разделяем его на два под массива и сортируем каждый из них рекурсивно. Например, для сортировки массива из семи элементов: Положение первого обмена. Исходное положение. i. j. i. Положение второго обмена. j. i. j. Положение третьего обмена.
27		Сформировать массив из 10 элементов Пример: Сформировать массив из 10 элементов. Значения задать ГСЧ. Отсортировать массив методом «быстрой сортировки». program Quitsort; uses crt; Const N=10; Type Mas=array[1..n] of integer; var a: mas; k: integer; function Part(l, r: integer):integer; var v, i, j, b: integer; begin V:=a[r]; I:=l-1; j:=r; repeat repeat dec(j) until (a[j]<=v) or (j=i+1); repeat inc(i) until (a[i]>=v) or (i=j-1); b:=a[i]; a[i]:=a[j]; a[j]:=b; until i>=j; a[j]:=a[i]; a[i]:= a[r]; a[r]:=b; part:=i; end; procedure QuickSort(l, t: integer); var i: integer; begin if l<t then begin i:=part(l, t); QuickSort(l,i-1); QuickSort(i+1,t); end; end; begin clrscr; randomize; for k:=1 to 10 do begin a[k]:=random(100); write(a[k]:3); end; QuickSort(1,n); writeln; for k:=1 to n do write(a[k]:3); readln; end.
28		Результат работы программы Результат работы программы.
29		Метод быстрой сортировки Заключение. Метод быстрой сортировки позволяет существенно сократить количество операций. Например: Все предыдущие методы требовали N2 операций, где N – количество элементов. Метод быстрой сортировки требует в среднем N*Log2N операций. В случае N=100, выигрыш составляет порядка 100 раз.
«Сумма элементов одномерного массива»