Пошаговое неформальное описание эффективного алгоритма




Задание

 

 

1. Написать полный набор тестов решения задачи (по данным: общий случай и крайние случаи; по алгоритму: проверяющие все ветви алгоритма).

2. Разработать пошаговое неформальное описание эффективного алгоритма решения задачи:

a. Ввести обозначение исходных данных, результатов и промежуточных данных (добавляя по мере разработки алгоритма).

b. Описать идею алгоритма.

c. Разбить алгоритм на последовательность крупных шагов с нумерацией 1, 2,…, определяя действия, а также входную и выходную информацию каждого шага.

d. Для каждого крупного шага с номером m определить либо подразбиение на более мелкие шаги с нумерацией m.1, m.2,…, либо процедуру/функцию выполнения шага с входными и выходными параметрами и отдельным неформальным пошаговым описанием этой процедуры.

e. В случае выделения процедур/функций дополнительно разработать тесты для проверки процедур.

f. Вести уточнение (пункты c, d) описания алгоритма (алгоритмов процедур) до получения элементарных шагов.

3. Прокрутить на бумаге каждый тест алгоритма (процедуры).

4. Разработать программу решения задачи.

5. Произвести отладку алгоритма (процедур), выполняя тесты.

6. Написать отчет, содержащий все указанные части и сдать его преподавателю, показав выполнение на компьютере программы с данными, указанными преподавателем.

 

 

41 вариант

 

Квадратная целочисленная матрица A размерности k2 (k>0) состоит из k2 непересекающихся квадратных подматриц Bij (i=1,…,k; j=1,…,k) размерности k. Каждая подматрица Bij, содержащая максимальный элемент матрицы A, переворачивается вокруг средних строк, а в самой матрице A все подматрицы Bij, стоящие целиком выше главной диагонали, меняются местами каждая с подматрицей, симметричной относительно главной диагонали матрицы А.

 

 

 

Полный набор тестов решения задачи

 

1. Если К=1, получается матрица.

 

 
 

 

 


В таком случае не возможно произвести операции над матрицей.

 

2. Рассмотрим крайние случаи.

Для наглядности возьмем ‘1’ за максимальный элемент, а все остальные цифры будут ‘0’.

 

1 случай: когда в матрице только 1 максимальный элемент:

 

                                                             
                                                     
                                                     
                                                     
                                                     
                                                     
                                                     
                                                     
       
Находим матрицу с мах элементом. Переворачиваем подматрицу относительно средней строки.
3

               
Подматрицы находящиеся выше главной диагонали меняем с подматрицами находящимися ниже.
3

                         

 

 

2 случай: когда в каждой подматрице есть максимальный элемент:

 

                                                             
                                                     
                                                     
                                                     
                                                     
                                                     
                                                     
                                                     
                                                     

Подматрицы находящиеся выше главной диагонали меняем с подматрицами находящимися ниже.
Находим матрицу с мах элементом. Переворачиваем подматрицу относительно средней строки.

 

 

 

Пошаговое неформальное описание эффективного алгоритма

 

 

Идея ал­го­рит­ма за­клю­ча­ет­ся в том, что находя максимальный элемент мы переворачиваем матрицы относительно горизонтальной оси. Для этого мы поочередно меняем цифры местами (как это описано на стр. 6-7). А после, меняем элементы выше главной диагонали с элементами ниже главной диагонали. Достижения оптимизации алгоритма, а именно, отслеживание крайних состояний поставленной задачи.

 

Краткий алгоритм:

 

1. Задается матрица размером КхК.

2. Находим мах элемент в матрице А.

3. Находим мах элемент в матрицах В.

4. Поворот матрицы В относительно горизонтальной оси.

5. Перестановка матриц В, находящихся выше главной диагонали в матрице А, с матрицами В, находящимися снизу главной диагонали матрицы А.

6. Конец программы. Выводится итог на экран.

 

Подробный алгоритм (с разбиением крупных шагов на более мелкие):

1. Задается матрица размером КхК.

2.

НА ВХОД НА ВЫХОД Поступает значение К (размер матрицы). Поступает матрица А, размером КхК. Уже заполненная цифрами. Например К=2. Например: Задается матрица, а в последствии заполняется.  
1 2 3 4 2 3 4 5 3 4 5 6 2 3 3 2

 


1) Проверка условия.

2) Если К=1, заполняем ее числом, а потом переходим к п.6 (матрица не меняется).

3) Если К>1, то задаем матрицу размером КхК и потом заполняем ее числами.

 

3. Находим мах элемент в матрице А.

 

НА ВХОД НА ВЫХОД Поступает матрица А. Поступает мах элемент в матрице А. В которой мы будем искать мах элемент. В нашем примере мах = 6.  
Например:

 

 


1) Задается двойной цикл, чтобы пройти по матрице А.

2) Ищем в матрице мах элемент и запоминаем в переменную.

 

4. Находим мах элемент в матрицах В.

 

1 2 2 3  
НА ВХОД НА ВЫХОД Поступают матрицы В (поочередно). Поступает мах элемент в матрице А. В которой мы будем искать мах элемент. В нашем примере мах = 6. Мах элемента нет Мах элемент есть  
5 6 3 2
В зависимости от того есть ли у нас в матрице В мах элемент или нет, мы переходим к разным пунктам алгоритма.

 

 


1) Идем по матрицам В.

2) В каждой матрице В находим элемент = мах.

3) Если такого нет, то идем к следующей матрице В, если матрицы В закончились, то переходим к п.5.

4) Если есть хоть 1 мах элемент, то переходим к п.4

 

5. Поворот матрицы В относительно горизонтальной оси.

 

НА ВХОД НА ВЫХОД Поступают матрицы В (поочередно). В которых мы нашли мах элемент.  
5 6 3 2
3 2 5 6
На выход мы получаем измененные матрицы В.

 


1) Находим среднюю строку относительно, которой будем переворачивать.

2) Если n=K/2; n=0, то меняем n строк снизу и n строк сверху.

3) Если n=K/2; n=1, то меняем n+1 строк сверху со строками снизу.

 

6. Перестановка матриц В, находящихся выше главной диагонали в матрице А, с матрицами В, находящимися снизу главной диагонали матрицы А.

 

НА ВХОД НА ВЫХОД Поступает матрицы А. Для следующего изменения.  

Поступает матрица А.

             
           
           

 

 


1) Идем по матрицам В стоящим выше главной диагонали.

2) Меняем верхние матрицы В с нижними в матрице А.

 

7. Конец программы. Выводится итог на экран.

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2018-01-27 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: