Практические занятия 2 и 4 Стр - pismo.netnado.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Практические занятия 2 и 4 Стр - страница №1/1


Практические занятия 2 и 4 Стр.

Часть 1. Поиск экстремума в одномерном массиве.

Часть 2. Упорядочение одномерного массива методом выбора.

Часть 1. Поиск экстремума (максимума, минимума) в одномерном массиве.

По структуре данных и алгоритма это задача того же класса, что 4.4.0, так что образец полной разработки есть (A0_440.doc и A02_440.doc).


1. Задача Extremum. Постановка задачи (ПЗ)

Задание: Написать программу обработки одномерного массива(ов) в соответствии с условием.

Условие: Найти номер и значение максимального элемента в одномерном массиве a(n).
2.Уточненная ПЗ (уточнить структуры, типы, имена, добавить альтернативные («отрицательные» и особые) решения).

Задан одномерный целочисленный массив a, состоящий из n элементов.

Найти значение Amax и номер Kmax максимального элемента заданного массива a.

Если элементов с максимальным значением в массиве будет несколько, то найти номер первого из них.


3. Пример, на базе которого затем построим тесты. Возьмем n=6.

Максимальное значение: Amax = 9,

Номер первой 9-ки: Kmax = 4




4. Таблица данных

Класс

Имя

Описание (смысл), диапазон, точность

Тип

Структура

Формат

Входные
данные



a

заданный массив,

|ai|<100



цел

одномерный массив (20)

+XX (:4)

n

число элементов массива a,

0 < n  20



цел

простая переменная

XX (:2)

Выходные
данные



kmax

номер максимального элемента, .* . .

*

*

*

amax

его значение, . . .*


*

*

*

Промежу-точные



i

индекс текущего элемента,

. . .*


*

*

---

dat

входной файл Extr_dat<№теста>.txt

файл

текстовый

---

res

выходной файл

Extr_res<№теста>.txt

файл

текстовый

---













---

*Диапазоны, типы, точность, структуру, формат для выходных и промежуточных параметров заполнить самим.
5. Форма ввода (Extr_dat<№теста>.txt)


Данные вводить из текстового файла.


Форма ввода элементарна, поэтому образцы можно не отмечать.
Программировать ввод-вывод в точном соответствии с входной и выходной формами!

6. Форма вывода (Extr_res<№теста>.txt)


обр1


обр2

обр3


обр4

обр5
7. Аномалии не рассматриваем (но желательно успевающим сделать хоть что-то: n<1, n>20, |ai|>=100, отсутствует входной файл, неправильный формат входного файла (ошибка при чтении), невозможно создать выходной файл, ошибка при чтении/записи в файл).


8. Функциональные тесты составить самостоятельно.

В том числе будут полезными тесты, в которых:



  1. один экстремум в середине/конце массива;

  2. один экстремум, и он первый в массиве;

  3. более одного экстремума (несколько равных максимумов/минимумов: см пример);

  4. все равные элементы.

При этом опять же нужно покрыть все возможные части диапазонов исходных данных и результатов: заполните полностью таблицу, указав номера подходящих тестов в пустых ячейках:

:Исходные данные

Результаты

Тест№




аном

граница

сред




сред

граница

аном

Kmax

макс =20




N

<1

1

( 2

,

19 )

20

>20




мин = 1




Тест№

---




1





2

---




сред = (0,20)

1




аном

граница

сред

0

сред

граница

аном




не сущ = не возм-но

---

a[i]

<-99

-99

(-99,0)

0

(0,99)

99

>99




0 = не возможно

---

Тест№

---

2

1

1

1




---




Макс.вычислит. нагрузка =

при n =20



2

























Amax

макс = 99































мин = -99

2




























сред = (-99, 99)

1




























не сущ = не возм-но

---




























0 = 0

---




























Макс. выч. нагрузка = при n =20

2




теста

Входные данные

Ожидаемый результат

Смысл теста

1


n = 6

a

-4

0

-5

9

9

2




Amax =9

Kmax = 4

Несколько максимумов в середине массива (см.Пример)

2


n = 20

a

-99

-99



-99




Amax = -99

Kmax = 1

Все значения в массиве одинаковые, минимально возможные



*







*Далее заполните пробелы в этой и предыдущей таблице самостоятельно
9. Метод

Рассмотрим процесс поиска максимума и его номера на приведенном выше примере:






Начало

0 > - 4

-5 < 0

9 > 0

9  9

2 < 9

Результат

Amax

-4

0

0

9

9

9

9

Kmax

1

2

2

4

4

4

4

Сначала считаем максимальным элементом первый.

Затем, просматривая поочередно все остальные элементы массива, сравниваем каждый из них с текущим значением максимума (с Amax).

Если текущий элемент больше Amax, то заменяем значение Amax на значение текущего элемента, а значение Kmax – на его номер.


10. Алгоритм (блок-схема)

Основной алгоритм (Абстракция А0) Раскрываем абстракцию A0.1





11. Программный код.

Написать самостоятельно, используя цикл for и ветвление if внутри него.

Подсказки в файле spkmmu.doc и Coding.doc, а также A0_440.doc
Замечание 1. При решении данной задачи можно обойтись без переменной Amax. При этом для сравнения с текущим элементом и при выводе результата указать на значение максимального элемента можно по его индексу в массиве: a[Kmax].

Замечание 2. В вашей задаче может быть экстремального значения не просто самого элемента, а заданного арифметического выражения. Тогда за начальное значение Amax берется значение первого выражения (а не просто элемента) и вводится дополнительная переменная (Zmax, например) для хранения текущего значения выражения, чтобы затем сравнить его с Amax.

Замечание 3. Для поиска минимума заменяем знак при сравнении текущего и экстремального значения с ">" на "<". Желательно также сменить и названия переменных на Amin, Kmin, Zmin для улучшения читабельности кода.

Замечание 4. В массиве элементы могут совпадать, и поэтому при поиске номера требуется уточнение: найти номер первого (последнего) максимума (минимума), что и было сделано в уточненной постановке рассмотренной задачи. Например, в массиве a = (1, 9, 2, 3, 9, 7) Amax = 9, Kmax = 2 при поиске первого максимума и Kmax = 5 при поиске последнего элемента с максимальным значением. Если при поиске первого для проверки используется знак > (<); то при поиске последнего: он заменяется на >= (<=); или, не меняя знака, элементы массива можно перебирать с конца («последний с начала» = «первый с конца»), тогда за начальное значение Amax берется значение последнего элемента и используется цикл с уменьшающимся параметром (for i:= n-1 downto 1 do)

Рис. Раскрытие абстракции A0.1 для поиска максимума в матрице


Замечание 5. Метод поиска экстремума Bmax в матрице b(nm) из n строк и m столбцов и двух(!) его индексов imax, jmax аналогичен, но надо учесть, что все элементы матрицы перебираются с помощью двух вложенных один в другой циклов: один – по строкам, другой – по столбцам (элементам строки), и что начинаем оба цикла с первого элемента (i = 1, j = 1), а не со второго, иначе потеряется целый столбец или строка:



Рис. Потеря строки или столбца ри поиске не с первого элемента
Замечание 6. Если экстремальные элементы надо найти для всех (каждой в отдельности) строк или столбцов матрицы, то результатом будет не простая переменная Amax, а одномерный массив из n или m элементов соответственно.
Задание 1 для выполнения на занятии: В заданном одномерном массиве X из m элементов найти номер и значение элемента, для которого минимально значение произведения Xisin(Xi). Только блок-схему алгоритма. Если в массиве окажется несколько элементов с минимальным значением, найти номер последнего из них двумя способами: при обходе массива от начала к концу и при обходе с конца в начало.

Задание 2 для выполнения на занятии: переделать готовую блок-схемы из предыдущего задания для аналогичного поиска в матрице при обходе ее слева направо сверху вниз.

Часть 2. Упорядочение одномерного массива методом выбора.
1. Задача Sort. ПЗ.

Задание: Упорядочить массив «на месте» (без использования дополнительного массива) в порядке и направлении перемещения, указанными в условии. Для наглядности выводить измененный массив после каждого шага сортировки (прохода по массиву).

Условие: Упорядочить в порядке убывания (максимум в начало) элементы одномерного массива.

2. Уточненная ПЗ.

Задан вещественный одномерный массив a, состоящий из n элементов.

Упорядочить в порядке убывания (максимум в начало) элементы заданного массива a.
Замечание. Упорядочение делается принципиально в том же массиве (на месте), т.е. входной массив «портится». Чтобы не изменять исходные данные (это важное программистское правило, которое следует по возможности выполнять), можно использовать другой массив, например, b, который и будет выходным. Тогда первым шагом обработки будет перепись а в b (при совпадении типа по имени для статических массивов выполняется простым присваиванием), а вторым – упорядочение b.
3. Пример.

Пусть n=6.


В результате должен получиться массив


4

. Таблица данных



Класс

Имя

Описание (смысл), диапазон, точность

Тип

Структура

Формат

Входные
данные



a

заданный массив,

|ai|<100, точн. 0.1



вещ

одномерный массив (10)

+XX.X (:5:1)

n

число элементов массива a,

0 < n  10



цел

простая переменная

XX (:2)

Выходные
данные

a

упорядоченный массив,

|ai|<100, точн. 0.1



вещ

*

*

Промежу-точные

i

индекс текущего элемента,

. . .*


*

*

---

dat

входной файл Sort_dat<№теста>.txt

*

*

---

res

выходной файл

Sort_res<№теста>.txt

*

*

---

amax

значение максимального элемента,

. . .


*

*

---

k

номер максимального элемента,

. . .


*

*

---

z

шаг упорядочения, 1  z  9

*

*

---







*

*

---

*Диапазоны, типы, точность и структуру для промежуточных параметров заполнить самим.
5. Форма ввода

Сами, по аналогии с предыдущими задачами, согласуясь с типом элементов заданного массива

6. Форма вывода


обр1
обр2

обр3
обр4

обр5


обр6
7. Аномалии не рассматриваем

8. Функциональные тесты составить самостоятельно.

Обязательны тесты, где:



  1. частично неупорядоченный массив (см Пример);

  2. массив, упорядоченный в обратном порядке;

  3. массив, уже упорядоченный в требуемом порядке.

И заполните полностью таблицу, указав номера подходящих тестов в пустых ячейках:

Исходные данные

Результаты

Тест№




аном

граница

сред




сред

граница

аном

перестановок

макс = N-1

2

N

<1

1

( 2

,

9 )

10

>10

мин = 0




Тест№

---














---

сред = (0,N-1)

1




аном

граница

сред

0

сред

граница

аном

не сущ = при N=1

5

A[i]

<-99

-99

(-99,0)

0

(0,99)

99

>99

0 = см.мин




Тест№

---
















---

Макс.вычисл. нагрузка =

см. макс



2






Входные данные

Ожидаемый результат

Смысл теста

1


n=6

A

4

3

5

9

5

2




Упорядоченный массив:

9 5 5 4 3 2



Частично упорядоченный массив из примера

2


n=10

A

-99

99

-7

50

-9

8

-8

6

-5

1




Пошагово (9 шагов):

99 -99 -7 50 -9 8 -8 6 -5 1

99 50 -7 -99 -9 8 -8 6 -5 1

99 50 8 -99 -9 -7 -8 6 -5 1

99 50 8 6 -9 -7 -8 -99 -5 1

99 50 8 6 1 -7 -8 -99 -5 -9

99 50 8 6 1 -5 -8 -99 -7 -9

99 50 8 6 1 -5 -7 -99 -8 -9

99 50 8 6 1 -5 -7 -8 -99 -9

99 50 8 6 1 -5 -7 -8 -9 -99

Упорядоченный массив:

99 50 8 6 1 -5 -7 -8 -9 -99


Частично упорядоченный массив для пошагового просмотра

Видно направление сортировки – максимум в начало – за первый же шаг максимум встал в начало, затем второй по величине элемент встал на вторую позицию и т.д.



Максимальное число обменов

3


n=10*

A


































*

Массив, упорядоченный в обратном порядке

4


*

*

Массив, уже упорядоченный в требуемом порядке

5


n =1*

A







*

Особый случай

*Продолжить составление тестовых примеров самостоятельно

9. Метод сортировки – метод выбора (максимум в начало):
1 шаг (z=1). Ищем в массиве, начиная с первого элемента, значение максимального элемента amax и его номер k, затем меняем значениями первый и k-й элементы.





Первый элемент поставлен на место.

2-й шаг (z=2). Ищем в массиве, начиная со второго элемента, значение максимального элемент amax и его номер k. Меняем значениями 2-й и k-й элементы.




Теперь и второй элемент поставлен на место.

z-ый шаг. Часть массива с первого по (z-1)-й элемент уже упорядочена.

Ищем в массиве, начиная с z-го элемента, значение максимального элемента amax и его номер k. Меняем значениями z-й и k-й элементы.





z-й элемент тоже поставлен на своё место.
Последний (z = n-1) шаг. Часть массива с первого по (n-2)-й элемент уже упорядочена.

Ищем в массиве, начиная с (n-1)-го элемента (их осталось всего два: последний и предпоследний), значение максимального элемента amax и его номер k. Меняем значениями (n-1)-й и k-й элементы.




Теперь и последние два элемента тоже стоят в правильном порядке.

Массив упорядочен.


Замечание 1. Обратите внимание, что в данном массиве элементы фактически оставались на своих местах уже с третьего шага, и далее все элементы менялись местами сами с собой. Внесем небольшую модификацию в алгоритм: будем проверять индексы z и k меняющихся значениями элементов.

Замечание 2. Для направления перемещения «максимум/минимум в конец» удобнее шаги отсчитывать в обратном порядке с (n-1) до 2, и, соответственно, использовать цикл for z:=n-1 downto 2 do вместо
for z:=1 to n-1 do. Сам максимум/минимум тоже логичнее начинать искать с конца неупорядоченной части массива, либо искать последний из элементов с максимальным/минимальным значением.

10. Алгоритм.

Рис. Блок-схемы алгоритма для задачи Extremum


Подзадача А0.1.1 – модификация задачи Extremum: начальное значение индекса элемента, с которого начинается поиск, заменяется с 1 на z.

Подзадача А0.1.2 – обмен значениями z-го и k-го элементов (в amax лежит A[k]).
Пусть в общем случае необходимо обменять значениями переменные c и d.


c:=d;


d:=c;
Способ 1).

Неверно, т.к. после первого же присваивания теряется начальное значение переменной c:


c



d

4


4

Надо его сохранить…




f:=c;

c:=d;

d:=f;



Введем для этого дополнительную переменную f


В рассмотренном алгоритме сортировки роль переменной c играет A[z], роль переменной d играет A[k].

Другие способы обмена: 2) c:= c+d; d:= c-d; c:= c-d; 3) для целых чисел c:=c xor d; d:= c xor d; c:=c xor d;

11. Программный код.

Написать самостоятельно, используя циклы for и ветвление if.

Подсказки в файлах spkmmu.doc и Coding.doc, а также A0_440.doc

Домашнее задание

1. Задание 1.4.3.(№+1) из задачника Зубова ВС и др. (под ред. Котаровой ИН, 1998)


2. Упорядочить одномерный массив методом выбора. Задание – согласно таблице.


Порядок

Возрастание

Убывание

Что ищем и переставляем

Min в начало

Max в конец

Max в начало

Min в конец

Тип данных

цел

вещ

сим

цел

вещ

сим

цел

вещ

сим

цел

вещ

сим

№ варианта

1

13*


25

2*

14

26*



3

15

27



4*

16

28*



5

17*


29

6

18

30



7*

19*


31*

8*

20*


32*

9

21


10*

22


11

23*


12

24


вариантах, помеченных звездочкой, сортировать численные значения по значению абсолютной величины. Например, массив ( 0, -1, 2, -3, 10, -11) упорядочен по возрастанию абсолютной величины.
Символьный тип описан в TextFile.doc и имеет особенности ввода: разделители не нужны, они (разделители) – тоже символы!

Желающие усложнить себе задачу при сортировке символов могут сортировать не любые символы (кроме управляющих, конечно) по кодам символов (как это происходит по умолчанию при сравнении двух символов), а сделать, например, сортировку символов кириллицы по алфавиту, включаю букву ё, или символов кириллицы/латиницы по алфавиту независимо от регистра: AaaBCccDDeZz, АаБВГДддЯя.


Чуть позднее будет рассмотрен еще один метод сортировки (пузырьком), и в итоге документация по задаче сортировки должна иметь вид:

– Пункты 1-8 общие, добавится одна логическая переменная;

– Основной алгоритм и программа с пустой заглушкой (пункты 10-11), куда можно будет вставить алгоритм упорядочения массива;

– Далее – решение методом выбора (с новой страницы пункты 9-11: метод, алгоритм, фрагмент кода, вставляемый вместо заглушки);

– Далее – решение методом пузырька (с новой страницы пункты 9-11: метод, алгоритм, фрагмент кода, вставляемый вместо заглушки).

Оба метода сортировки можно совместить в одной программе. При этом не забудьте зарнее сделать копию исходного массива, чтобы не пытаться упорядочивать вторым методом уже упорядоченный первым методом массив.