Главная » Java, Структуры данных и алгоритмы » Псевдокод

0

Зачастую программистам требуется создать описание алгоритма, предназначаемое только для человека. Подобные описания не являются программами, но вместе с тем они более структурированы, чем обычный текст. В частности, «высокоуровневые» описания сочетают естественный язык и распространенные структуры языка программирования, что делает их доступными и вместе с тем информативными. Такие описания способствуют проведению высокоуровневого анализа структуры данных или алгоритма. Подобные описания принято называть псевдокодом.

Пример псевдокода

Проблема «максимума в массиве» является простой задачей поиска элемента с максимальным значением в массиве А, содержащем п целых чисел. Для решения этой задачи можно использовать алгоритм аггауМах, который осуществляет просмотр массива А с использованием цикла for.

алгоритма аггауМах представлен во фрагменте кода 3.1, а полная реализация программы Java представлена во фрагменте кода 3.2.

Алгоритм аггауМах(А, п):

Input: массив А, содержащий п целых чисел (п > 1). Output: элемент с максимальным значением в массиве А.

currentMax А [0] for / 1 to л – 1 do

if currentMax <A[i\ then currentMax A [/] return currentMax

Фрагмент кода 3.1. Алгоритм аггауМах !**

* Тестирует программу алгоритма поиска максимального элемента массива. 7

public class ArrayMaxProgram {

/** находит элемент с максимальным значением в массиве А, * содержащем п целых чисел.

7

static int arrayMax(int[ ] A, int n) {

int currentMax = A[0]; // выполняется один раз for (int i=l’ i < n’ i++) // выполняется от 1 до л, л-1 раз

// соответственно, if (currentMax < A[i]) // выполняется л-1 раз currentMax = A[i]; // выполняется максимально л-1 раз

return currentMax; // выполняется один раз

/[8] Тестирующий метод, вызываемый после выполнения программы.

7

public static void main(String args[ ]) {

int[ ] num = { 10, 15, 3, 5, 56, 107, 22, 16, 85 }; int n = num.length; System.out.print("Array:");

for (int i=0; i < n; i++) System.out.print("" + num[i]); // выводит один элемент массива System.out.print("" + num[i]); System-out-printlnC’.");

System.out.println("The maximum element is" + arrayMax(num,n) + ".");

}

}

Фрагмент кода 3.2. Алгоритм arrayMax внутри законченной Java-nporpaMMbi. В комментариях указано, сколько раз выполняются определенные команды в ходе выполнения программы

Как можно заметить, псевдокод выглядит компактнее Java-кода, и его легче читать и понимать. При анализе псевдокода можно поспорить о правильности алгоритма arrayMax с простым аргументом. Переменная currentMax первоначально принимает значение первого элемента массива А. Можно утверждать, что перед началом итерации по номеру / значение currentMax равно максимальному значению среди первых i элементов массива А. Так как при повторении / значение currentMax сравнивается с A[i\, то, если это утверждение верно перед данной итерацией, оно будет верно и после нее для / +1 (которое является следующим значением счетчика /). Таким образом, после количества итераций п – 1 значение currentMax будет равно элементу массива А, содержащему максимальное значение.

Что такое псевдокод?

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

применяется в качестве оператора присваивания в командах присваивания (равнозначен оператору «=» языка Java). Знак «=» используется для передачи отношения равенства в логических выражениях (что соответствует оператору «= =» языка Java).

•          Объявление метода. Имя алгоритма (paraml, param2, …) объявляет «имя» нового метода и его параметры.

•          Структуры принятия решений. Условие if, then — действия, если условие верно [else — если условие не верно]. Отступы используются для обозначения выполняемых в том или другом случае действий.

•          Цикл while, while — условие, do действия. Отступ обозначает действия, выполняемые внутри цикла.

•          Цикл repeat, repeat — действия, которые выполняются, пока выполняется условие until. Отступ обозначает действия, выполняемые внутри цикла.

•          Цикл for. for — описание переменной и инкремента, do — действия. Отступ обозначает действия, выполняемые внутри цикла.

•          Индексирование массива. А[/] обозначает /-ую ячейку массива А. Ячейки массива А с количеством ячеек п индексируются от А[0] до А[п – 1] (как в Java).

•          Обращения к методам, object.method (args) (часть object необязательна, если она очевидна).

•          Возвращаемое методом значение. Значение return. Данный оператор возвращает значение, указанное в методе, вызывающим данный метод.

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

Дополнительно, для лучшей передачи сущности алгоритма или структуры данных, описание алгоритма должно начинаться с краткого абстрактного объяснения характера входного и выходного потока данных, а также основных действий и используемых идей алгоритма.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии