Вектор в блок схеме (5 видео) | Курс школьной геометрии

Как будет выглядеть блок-схема этой функции?

или хотя бы подскажите как отобразить вектор в блок-схеме
// Раскрасить
void Graph::colorize()
<
// Находим степени вершин
// Степень вершины — количество принадлежащих ей ребер
std::vector degree;// Вектор со степенями

// Добавим в вектор номера вершин
for (int x = 0; x tops.size(); x++)
degree.push_back(0);

// Проставим степени
for (int x = 0; x edges.size(); x++)
<
++degree.at(this->edges.at(x).top1);
++degree.at(this->edges.at(x).top2);
>

// Упорядочим
std::sort (degree.begin(), degree.end ());

// Вектор с векторами смежных вершине вершин
std::vector > adjacentTops;
// Несмежных
// std::vector > unAdjacentTops;

// Найдем смежные вершины
for (int x = 0; x tops.size(); x++)
<
// Вектор со смежными текущей вершине вершинами (сама вершина тоже окажется смежной самой себе, но это не важно)
std::vector currentAdjacentTops;

// Проходим по ребрам
for (int e = 0; e edges.size(); e++)
<
if (this->edges.at(e).top1 == x)
currentAdjacentTops.push_back(this->edges.at(e).top2);

if (this->edges.at(e).top2 == x)
currentAdjacentTops.push_back(this->edges.at(e).top1);
>

// // Найдем несмежные вершины
// for (int x = 0; x tops.size(); x++)
// <
// std::vector curV;
// for (int i = 0; i tops.size(); i++)
// <
// curV.push_back(0);
// >
// unAdjacentTops.push_back(curV);
// >

// for (int x = 0; x tops.size(); x++)
// <
// for (int i = 0; i = 0; x—)
<
// if (countColorize >= this->tops.size())
// break;

// Текущий рандомный цвет
QColor currentColor = QColor (rand () % 255, rand () % 255, rand () % 255, 255);

Содержание

One more step
Please complete the security check to access www.canva.com
Why do I have to complete a CAPTCHA?
What can I do to prevent this in the future?
Вектор в блок схеме
💥 Видео

Видео:0.Блок схема. 8 классСкачать

One more step

Видео:Блок-схемы для начинающих (Блок схемы алгоритмов)Скачать

Please complete the security check to access www.canva.com

Видео:Самый подробный урок про Блок-схемы, Понимание, Чтение и Создание блок-схемСкачать

Why do I have to complete a CAPTCHA?

Completing the CAPTCHA proves you are a human and gives you temporary access to the web property.

Видео:Исполнитель чертёжник Сместиться на векторСкачать

What can I do to prevent this in the future?

If you are on a personal connection, like at home, you can run an anti-virus scan on your device to make sure it is not infected with malware.

If you are at an office or shared network, you can ask the network administrator to run a scan across the network looking for misconfigured or infected devices.

Another way to prevent getting this page in the future is to use Privacy Pass. You may need to download version 2.0 now from the Chrome Web Store.

Cloudflare Ray ID: 6cc773a7b8557a64 • Your IP : 85.95.179.65 • Performance & security by Cloudflare

Видео:ЭТЗ "ВЕКТОР": ОТКАЗ БЛОК-КОНТАКТОВ И ДРУГИЕ ПРОБЛЕМЫ В ЭКСПЛУАТАЦИИ И ПУТИ ИХ РЕШЕНИЯ.Скачать

Вектор в блок схеме

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

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

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

В любом случае рекомендуем обратить внимание на следующее. Разбирая или составляя алгоритм, нужно мысленно представить некоторый автомат по обработке данных (компьютер), который будет выполнять действия, предписанные этим алгоритмом. Без такого представления невозможно понять сам алгоритм. Ниже, при разборе примеров, станет понятно, что такой мысленный автомат совсем несложен. Во всяком случае он несравнимо пpoщe реального компьютера, хотя общие принципы их функционирования в основном одинаковы. Допустимо (например, при составлении описания) отождествлять работу такого автомата с работой самого алгоритма.

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

1. Алгоритм и алгоритмизация

Алгоритм – это инструкция для автомата о том, в какой последовательности нужно выполнить действия при переработке исходного материала в требуемый результат.

Наряду с понятием алгоритма используют термин алгоритмизация, под которой понимают совокупность приемов и способов составления алгоритмов для решения алгоритмических задач.

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

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

На практике получили известность два способа изображения алгоритмов:

в виде пошагового словесного описания;

в виде блок-схем.

Первый из этих способов получил значительно меньшее распространение из-за его многословности и отсутствия наглядности.

Второй, напротив, оказался очень удобным средством изображения алгоритмов и получил широкое распространение в научной и учебной литературе. Именно этот способ будет использован ниже при составлении и описании алгоритмов.

Блок-схема – это совокупность блоков, предписывающих выполнение определенных операций, и связей между этими блоками. Внутри блоков указывается информация об операциях, подлежащих выполнению. Конфигурация и размеры блоков, а также порядок графического оформления блок-схем регламентированы ГОСТ 19.701-90 (ИСО 5807-85) «Единая система программной документации. СХЕМЫ АЛГОРИТМОВ, ПРОГРАММ, ДАННЫХ И СИСТЕМ. Условные обозначения и правила выполнения» [1]. В табл. 1 приведены наиболее часто используемые блоки, изображены элементы связей между ними и дано краткое пояснение к ним. Блоки и элементы связей называют символами блок-схем. Представленных в таблице символов вполне достаточно для изображения алгоритмов, которые необходимы при выполнении студенческих работ.

Таблица 1

Название

Символ

Комментарий

Терминатор

О тображает выход во внешнюю среду и вход из внешней среды (начало или конец схемы программы, алгоритма).

Процесс

Вычислительное действие или последовательность вычислительных действий

Решение

Проверка условияГраницы цикла

Верхняя граница

Нижняя границаПодготовка

Отображает модификацию команды или группы команд с целью воздействия на некоторую последующую функцию

Предопределенный процесс

О тображает процесс, состоящий из одной или нескольких операций или шагов программы, которые определены в другом месте (в подпрограмме, модуле)

Документ

О тображает данные, представленные на носителе в удобочитаемой форме.

Будет использоваться нами как символ вывода данных

Карта

О тображает данные, представленные на носителе в виде карты (перфокарты, магнитные карты и др.).

Будет использоваться нами как символ ввода данных

Данные

Может использоваться для ввода/вывода данных

Соединитель

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

Комментарий

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

Линии

Линии горизонтальных и вертикальных потоков, предназначенные для связей между символами

Слияние

Слияние линий потоков

Межстраничный соединитель

При соединении блоков следует использовать вертикальные и горизонтальные линии потоков.

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

Желательно чтобы линии потоков были параллельны линиям внешней рамки или границам листа.

Рекомендуется расстояние между параллельными линиями потоков устанавливать кратным 5 мм.

Горизонтальный и вертикальный размеры блока рекомендуется назначать кратно 5-ти мм.

Для размещения блоков рекомендуется поле листа разбивать на горизонтальные и вертикальные (для разветвлявшихся схем) зоны.

Для удобства описания блок-схемы каждый ее блок следует пронумеровать. Удобно использовать сквозную нумерации блоков. Номер блока располагают в разрыве в левой верхней части рамки блока или над ним.

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

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

3. Константы, переменные и ячейки памяти

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

В состав такого автомата входят:

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

Головка, получив указание от процессора, может записывать в ячейку или считывать из нее одну константу.

В простейшем случае константой является любое арифметическое число. Например, 12, 0.78, 0, –45.33 и т. д. ( Константами могут быть такие строки символов, структуры данных и др.).

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

Переменные имеют буквенно-символьное обозначение. Например, 1, n, a, a1, b, H2 – переменные. Одновременно обозначение переменной является индексом ячейки, в которую будут записываться константы. Любая из таких констант называется значением переменной. Например, Z является переменной и адресом ячейки Z одновременно. С алгоритмической точки зрения понятия “ переменная ” и “ адрес ячейки ” памяти являются идентичными.

Запись вида Y = 5.5 следует понимать так: записать константу 5 . 5 в ячейку с адресом Y (если до этой операции в ячейку была записана константа, то она будет затерта, а на ее место будет помещена константа 5.5). Произносить эту запись следует так : “ переменной Y присвоить значение 5.5 ”.

Запись вида L = M следует понимать так: прочитать константу, расположенную по адресу M и скопировать эту константу в ячейку с адресом L (при этом константа из ячейки M не удаляется, а остается такой, какой она была до чтения). Произносить эту запись нужно так: «переменной L присвоить значение переменной M (или просто : L присвоить M)».

4. Массивы

Другой разновидностью переменных являются так называемые индексированные переменные или массивы . Массив – это некоторая совокупность ячеек, объединенная одним обозначением (массивом может быть одна ячейка). Всякий массив обязательно имеет размерность. Массивы бывают одномерными, двумерными, трехмерными и т. д.

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

2.3

-6

4.4

-3

8.2

-4.7

Рис. 1. Одномерный массив q

Массив имеет имя q . Для того чтобы можно было отличить одну ячейку массива от другой ячейки этого же массива, их нумеруют. Нумерация ячеек обычно начинается с 1. Номер ячейки массива называется его индексом , а константа в ячейке – элементом массива. Теперь становится возможной работа с отдельной ячейкой такого массива. Например, команда q₇ = 8.2 означает, что в 7-ю ячейку массива q надлежит записать константу 8.2. Команда r₄₁ = q₂ + q₅ означает, что нужно сложить константы, записанные во 2-ю и 5-ю ячейки массива q, и результат записать в 41-ю ячейку одномерного массива r . Эту же операцию можно описать другими словами: 41-му элементу массива r присвоить значение суммы 2-го и 5-го элементов массива q.

Двумерный массив по расположению ячеек напоминает математическую матрицу (рис. 2). Элемент такого массива характеризуется двумя индексами: первый показывает строку, в которой расположена ячейка, второй – ее столбец. Например, команда d _{2, 5} = 43 означает, что в ячейку, размещенную на пересечении 2-й строки и 5-го столбца двумерного массива d , нужно записать константу 43.

1	2	3	4	5	6
1

234

Рис.2. Двумерный массив d

Аналогично устроена структура массивов трех- и большей размерности.

5. Линейные алгоритмы

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

На рис. 3 приведен пример блок-схемы алгоритма вычисления периметра Р и площади S квадрата со стороной длины A.

Блок-схема алгоритма состоит из шести блоков. Выполнение алгоритма начинается с блока 1 «Начало». Этот блок символизирует включение автомата, настройку его на выполнение алгоритма и выделение памяти под все переменные, которые задействованы в алгоритме. В алгоритме рис. 3 таких переменных три: A, Р, S . Следовательно, под каждую из них алгоритмом будет выделено по одной ячейке памяти. На этом блок 1 будет отработан.

Как видно из рис.3, блок 1 связан вертикальной линией потока с блоком 2. Эта линия не имеет стрелки, указывавшей направление потока. Следовательно, этот поток направлен вниз. Таким образом, после выполнения блока 1 управление будет передано на блок 2. Блок 2 «Перфокарта» ( см. табл. 1) показывает, что переменной A следует присвоить значение. Это означает, что в ячейку, отведенную автоматом под эту переменную, нужно поместить константу. На реальной компьютере эта константа может быть введена самыми разными способами. Способ зависит от того, как запрограммирован данный фрагмент. Можно, например, потребовать ввод константы с клавиатура или получить его из заранее подготовленного файла. Возможно эта константа будет получена через внешние источники данных, например, от физической установки, подключенной к компьютеру.

Рис. 3. Линейный алгоритм

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

Далее управление по линии потока передается к блоку 3 «Процесс». В этом блоке при выполнении размещенной в ней команды число 4 умножается на константу, помещенную в ячейку А (т. е. 5), и результат (т. е. 20) присваивается переменной Р (т. е. константа 20 записывается в ячейку по адресу Р). После выполнения этих операций управление передается к блоку 4.

В блоке 4 аналогичным образом производится умножение значений переменной А и результат (константа 25) присваивается переменной S (в ячейку по адресу S будет занесена константа 25). После этого выполняется переход к блоку 5.

При выполнении команд блока 5 выводятся (например, на экран, бумагу, во внешний файл и т. д.) значения переменных А, Р, S, которые сохранились в соответствующих ячейках к этому моменту. Понятно, что для конкретного примера А = 5 будут выведена константы 5, 20, 25, т. е. длина сторона квадрата, его периметр и площадь. Далее управление передается последнему блоку 6.

В блоке б “ Конец ” производится освобождение ячеек памяти, которые были зарезервированы под переменные А, P, S , и алгоритм заканчивает работу.

Понятно, что при новом запуске этого же алгоритма можно получить совсем другие числа. Так, если в блоке 2 переменной А присвоить значение 20, то алгоритм выдаст в блоке 5 константы 20, 80, 400.

Детальное описание алгоритма рис. 3 приведено для того, чтобы показать, в какой последовательности автомат выполняет предписанные операции и как при этом меняется состояние памяти автомата, т. е. для того, чтобы объяснить суть происходящих в автомате процессов. Из сказанного нужно уяснить, что автомат выполняет предписанную ему работу шаг за шагом. Всякий шаг обрабатывается процессором. Помимо вычислений процессор при необходимости отдает команды считывавшей/записывавшей головке, что и куда записывать, откуда читать. Конечный результат следует искать в ячейках памяти, каждая из которых до окончания алгоритма имеет известный адрес и хранит записанную в нее константу.

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

6. Разветвляющиеся алгоритмы

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

В блок-схемах ветвление начинается на выходах символа «Решение», с помощью которого в алгоритме выполняется проверка какого-либо условия. Количество ветвей тем больше, чем больше проверяемых условий.

Для пояснения рассмотрим решение задачи нахождения значения функции z = y/x.

На первый взгляд представляется, что алгоритм решения этой задачи имеет линейную структуру. Однако, если учесть, что делить на нуль нельзя из-за переполнения ячейки, то, во-первых, нужно из вычислений исключить вариант х = 0 и, во-вторых, проинформировать пользователя алгоритма о возникшей ошибке. Если этого не сделать, то при вычислениях может возникнуть аварийный выход до получения результата. В профессиональной практике аварийные завершения крайне нежелательны. т. к. к этому моменту уже может быть накоплено определенное количество результатов, которые окажутся необработанными и попросту пропадут. Можно привести другие примеры, когда аварийный останов компьютера может повлечь куда более серьезные последствия.

Решение задачи представлено блок-схемой рис. 4.

Она состоит из 7 блоков. После начала работы алгоритм в блоке 2 требует ввода аргументов X и Y. Затем в блоке 3 производится проверка условия X = 0. Здесь автомат проверяет равна ли нули константа, введенная в ячейку с адресом X. Результатом такой проверки является ответ «Да» или «Нет». В зависимости от этого ответа выполнение алгоритма пойдет по одной или другой ветви. Если результат проверки окажется отрицательным, то на х можно делить и управление передается блоку 4.

В блоке 4 будет получен результат Z, затем в блоке б значения всех трех переменных будут отпечатаны и в блоке 7 алгоритм закончит работу. Если же ответ окажется положительным, то управление будет передано блоку 4. Выполняя команду блока 4, автомат выведет сообщение «Ошибка» и затем закончит работу в том же блоке 7.

Рис. 4 . Разветвляющийся алгоритм

7. Циклические алгоритмы

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

Различают циклы с наперед известным и наперед неизвестным количеством проходов.

Пример 1. Рассмотрим пример алгоритма с циклом, имеющим наперед неизвестное количество проходов. Для этого решим следующую задачу. Указать наименьшее количество членов ряда натуральных чисел 1, 2, 3, . сумма которых больше числа К.

Блок-схема алгоритма решения этой задачи приведена на рис. 5. Она состоит из восьми блоков.

После начала работы в блоке 2 вводится значение числа К. Далее в блоке 3 переменная i получает значение 1, т. е. значение, с которого начнется отсчет натуральных чисел. Переменная S, предназначенная для накопления сумма этих чисел, перед началом суммирования получает значение 0. После этого управление передается блоку 5.

В нем при выполнении команды S = S + i производится сложение содержимого ячеек S и i , а результат записывается в ячейку S . Поскольку до операции сложения было S = 0, i = 1, то после операции будет S = 1 . При записи нового значения старое содержимое ячейки S (нуль) стирается, а на его место записывается число 1.

Нужно обратить внимание на то, что если бы до этой операции в блоке 3 не была выполнена команда S = 0 (записать нуль в ячейку S ), то при нахождении суммы S + 1 возникла бы ошибка, поскольку из ячейки S была бы извлечена константа, которая оказалась там после распределения памяти.

После суммирования первого члена последовательности в блоке 6 выполняется проверка условия о превышении суммы S заданного числа К.

Если условие 6 не выполнится, то производится переход к блоку 4, где при выполнении операции значение переменной увеличивается на 1 и становится равным 2. Теперь алгоритм вновь вернется к блоку 5 и к старому значении суммы добавит новый член 2. После этого сумма станет равной 3. В блоке б вновь проверяется условие получения требуемой суммы и т. д. Цепочка блоков 5-4 будет обрабатываться вновь и вновь до того момента, когда однажды при определенном значении переменной i, наконец, выполнится условие S > К, т. е. когда накапливаемая в таком цикле сумма впервые превысит заданное значение К. Переменная i, значение которой при очередном проходе цепочки этих блоков увеличивается на 1, играет роль счетчика этого цикла.

Далее производится переход к блоку 7 , где отпечатается значение количества членов ряда (извлечено и отпечатано число из ячейки i , которое там хранится в момент выполнения условия), суммы S и в блоке 8 алгоритм закончит работу.

Рис. 5. Циклический алгоритм

Другие способы изображения циклов

Рис. 6. Структура цикла,
использующего символ «Цикл»

Рис. 7. Структура цикла, использующая
символ «Подготовка»

На рис. 6. показана структура цикла, которая может быть использована, когда условие выхода из цикла определяется символом его начала или символом его конца. Наряду с этим в качестве заголовка цикла может быть использован и символ «Подготовка». Структура такого цикла показана на рис. 7.

Пример 2. Теперь приведем пример алгоритма, содержащего цикл с наперед известным количеством проходов (повторений). Алгоритм решает задачу накопления суммы положительных элементов одномерного массива Z длины N (под длиной массива понимается количество его элементов).

Блок-схема алгоритма дана на рис. 8 . Вначале в блоке 2 производится ввод двух переменных N и Z. Первая из них представляет одну ячейку. В нее записывается константа – число, равное количеству элементов массива Z. Именно такое количество ячеек объединяет другая переменная – массив Z .

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

Далее в блоке 3 переменной S присвоено начальное значение 0. Это сделано для того, чтобы приготовить ячейку к накоплению необходимой суммы.

Блоки 4-7 представляет собой цикл, в котором накапливается сумма. Заголовок цикла представлен блоком 4. Роль счетчика цикла играет переменная j , которая будет изменяться в цикле изменяться от 1 до N . Поскольку шаг изменения счетчика j явно не указан, то по умолчанию он подразумевается равным 1. Тело цикла образуют блоки 5 и 6.

Сразу после входа в цикл переменная j примет начальное значение j = 1. Далее в блоке 5 выполняется проверка положительности первого элемента массива Z (т. к . j = 1). Если этот элемент действительно положителен, то в блоке б значение элемента будет добавлено к переменной S , после чего в блоке 7 выполнится возврат к заголовку цикла. Если этот элемент неположителен (т. е. нуль или отрицательный), то оператор суммирования не будет исполнятся.

На втором круге цикла счетчик j в заголовке увеличится на 1 и станет равным 2. Теперь, при новом выполнении тела цикла, в блоке 5 проверяется на положительность второй элемент массива Z и , если он положителен , то добавляется в сумму и т. д. Последний раз тело цикла выполнится при i = N . При этом значении счетчика проверяется последний элемент массива. Наконец, в заголовке цикла i примет значение N +1. Это значение выходит за предписанный предел, следовательно, произойдет выход из цикла и управление перейдет блоку 8 . В этом блоке выводится накопленная сумма и алгоритм закончит работу в блоке 9.

Рис. 8. Циклический алгоритм

Тест на алгоритм Министерства образования и науки РФ

Задание 29

Варианты ответов

Вариант

Условие : x

Условие : x + 3 > y

Выделенный блок 1) x = 2; y = 4; z = 32+2 + 3 > 4+1) x := x + 1 = 3; z := z -1 = 23+3 + 3 > 4+2) x := x + 1 = 4 ; z := z -1 = 14 1+4 + 3 > 4+3) x := x + 1 = 5 ; z := z -1 = 05 0— 2) x = 2; y = 4; z = 12 1+2 + 3 > 4+1) x := x + 1 = 3; z := z -1 = 03 0+3 + 3 > 4+2) x := x + 1 = 4 ; z := z -1 = -14 -1— 3) x = 3 ; y = 3 ; z = 13 3 + 1+6 + 3 > 3+1) x := x + 1 = 4 ; z := z -1 = 04 3 + 0— 4) x = 1 ; y = 4; z = 01 0+1 + 3 > 4—

Таким образом, выделенный блок выполнится при x = 2; y = 4; z = 1 (вариант 2 ).

8. Алгоритмы со структурами вложенных циклов

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

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

Пример 1. Рассмотрим задачу нахождения наименьшего элемента в двумерном массиве Z размером 8 х 6 .

Блок-схема алгоритма показана на рис. 9. Она включает 11 блоков. После начала работы в блоке 2 массив Z заполняется константами. В блоке 3 новая переменная S получает значение элемента, расположенного в левом верхнем углу массива Z . Далее с помощью вложенных друг в друга цикла будет совершен последовательный проход по всем элементам массива Z и в случаях, когда текущий элемент окажется меньшим S , значение этой переменной будет заменено на значение такого элемента .

Наружный цикл образован блоками 4 — 9, а внутренний блоками 5 — 8. В наружном цикле переменная i сначала примет значение 1, после чего будет выполнено тело этого цикла, которым, как видно из схемы, является внутренний цикл.

Во внутреннем цикле на каждом его шаге переменная j последовательно поменяет свои значения от 1 до 6. При этом текущем шаге будет проведено сравнение элемента, расположенного на пересечении строки i и столбца j , со значением переменной S и, если среди них найдется тот, который меньше S, то S будет заменено значением такого элемента. Проверка условия производится в блоке 6, а замена при выполнении этого условия — в блоке 7.

После завершения работы внутреннего цикла произойдет возврат к заголовку наружного цикла, где значение переменной i увеличится на 1 и станет равным i = 2. Затем вновь выполнится весь внутренний цикл, что соответствует проходу по всем элементам второй строки массива Z.

Таким образом, после завершения наружного цикла будет совершен проход по всем элементам массива и в переменной S будет находиться константа, равная значению наименьшего элемента массива Z.

В блоке 10 будет выведено это значение и затем в блоке 11 алгоритм закончит свою работу.

Рис. 9. Алгоритм нахождения наименьшего элемента в двумерном массиве

9. Вспомогательные алгоритмы

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

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

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

Первый блок схемы рис. 10 в отличие от ранее рассмотренных примеров, где этот блок имел наименование “Начало”, включает имя процедуры Warn и один формальный параметр i .

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

Из схемы рис. 11 видно, что если при обращении к процедуре Warn на ее вход подать i = 0, то она в блоке 3 выдаст сообщение «Введите данные». При любом другом i будет выведено сообщение «Конец расчетов». Этим исчерпываются возможности процедура Warn.

Рис. 10. Процедура Warn

На рис. 11 дана схема головного алгоритма (первый блок имеет наименование «Начало»). Этот алгоритм в блоках 2 и 8 обращается к процедуре Warn (вызывает ее). Опишем последовательность и механизм обработки данных, которые предписаны алгоритмами рис. 10 и 11.

Выполнение алгоритмических действий всегда начинаются с головного алгоритма. Поэтому сначала будет выполнен блок 1 схемы рис. 11. Далее в блоке 2 головной алгоритм выполняет обращение к процедуре Warn при конкретном значении ее аргумента (0).

Теперь управление временно переходит в алгоритм рис. 10 процедуры Warn . Здесь и далее по всей процедуре Warn формальный параметр i заменяется на фактический параметр 0 (нуль) всюду, где он встречается.

Далее обрабатывается блок 2 процедуры, где с учетом сказанного проверяется условие 0 = 0. Результатом проверки станет перевод управления к блоку 3 , в котором выводится сообщение «Введите данные». На этом процедура заканчивается и управление вновь передается в головной алгоритм к блоку 3.

Далее в блоках 3-5 алгоритма рис. 11 выполняются уже понятные действия по вводу, суммированию и выводу переменных. Затем управление передается в блок б, который содержит новое обращение к процедуре Warn с фактическим параметром 1.

Снова управление переключается на схему рис. 10, где вместо формального параметра i всюду записывается фактический параметр – константа 1. Поскольку в блоке 2 условие 1 = 0 не выполнится, то будет выполнен блок 4 и алгоритм выведет сообщение «Конец расчетов».

После этого управление возвращается в головной алгоритм к блоку 7, где и будет окончательно завершен алгоритмический процесс.

Рис. 11. Головной алгоритм

Внешне такой процесс может выглядеть примерно так.

На экран выводится сообщение «Введите данные» и компьютер переходит в режим ожидания ввода двух констант с клавиатуры. Затем после их ввода на экране появляется три константы и надпись «Конец работы».

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

Действительно, рассмотренную здесь задачу проще решить одним алгоритмом, не прибегая к составление процедуры. Однако при составлении алгоритма решения сложной задачи очень быстро становится ясно, что без использования процедур обойтись просто невозможно. На практике при решением серьезных алгоритмических задач часто одному программисту не под силу выполнить весь объем работ. Поэтому над ее решением работает обычно коллектив программистов под руководством координатора. Образно говоря, координатор здесь работает как головной алгоритм, а его программисты как процедуры. При этом каждый программист (часто независимо от других) получает от координатора задание по составление процедур определенного назначения. В результате такой организации работы задача получает разрешение.

10. Декомпозиция алгоритма

Под декомпозицией алгоритма понимают разложение его o 6щeй алгоритмической схемы на вспомогательные алгоритмы (процедуры и функции) и головной алгоритм. Напомним, такая задача ставится перед студентом при выполнении курсовой или контрольной работы. Одним из условий, которое должно быть обязательно выполнено, является наличие в работе хотя бы одной процедуры или функции (кроме того, работа должна содержать текст описания всех вспомогательных алгоритмов и головного алгоритма).

Метод, при помощи которого обычно выполняется декомпозиция, достаточно прост. Сначала вычленяют основные этапы предстоящей работы. Наиболее сложные этапы оформляют в виде вспомогательных алгоритмов верхнего уровня. Затем, если необходимо, такие этапы делят на этапы более низкого уровня. Наиболее сложные из них также оформляют вспомогательными алгоритмами и т. д. Следуя методу «от сложного к простому», в конечном итоге получают решение поставленной задачи.

Приведем пример декомпозиции для решения задачи сортировки массива в порядке возрастания его элементов.

Решение задачи декомпозиции состоит из трех основных этапов: 1) ввода данных, 2) сортировки массива и 3) вывода отсортированного массива. Первый и третий этапы вследствие их простоты не нуждаются в декомпозиции, поэтому выполняются в головном алгоритме. Второй этап представляет достаточно сложный и самостоятельный фрагмент алгоритмической работы, поэтому его целесообразно выделить в отдельную процедуру, которой можно дать имя Sort.

Процедура сортировки требует перестановки значений двух простых переменных. Вспомогательный алгоритм, реализующий эту процедуру, показан на рис. 12. Алгоритм имеет имя Perm ( от английского permutation — перестановка ) и два формальных параметра — переменные a, b. Тело алгоритма состоит из одного символа, где выполняется три оператора присваивания. Сначала оператором c:= a значение ячейки a копируется во вспомогательную переменную c , затем оператором a:= b из ячейки с адресом b производится копирование значения в ячейку с адресом a, последним оператором b:= c из вспомогательной ячейки с адресом c значение копируется в переменную с адресом b . В результате такого кругового копирования содержимое ячеек a и b поменяется местами.

Выполним далее сортировку массива в порядке возрастания его элементов «методом пузырька». Этот метод достаточно прост. Сначала совершают проход по всем соседним парам элементов массива и в случае, если они не отсортированы, то значения элементов всякой такой пары меняют местами. Если была совершена хотя бы одна перестановка, то такую процедуру повторяют до тех пор, пока при проходе по массиву не будет совершено ни одной перестановки. В результате массив будет отсортирован.

Вспомогательный алгоритм сортировки массива приведен на рис. 13. Алгоритм имеет имя Sort и содержит два формальных параметра : N — длина массива, Z — имя массива, который надлежит отсортировать.

Сортировка производится при помощи двух сложенных друг в друга цикла. Наружный цикл образован блоками 2 — 7 и предназначен для многократного прохода по массиву. Внутри него находится цикл, содержащий блоки 3 — 6. Этот цикл нужен для однократного прохода по всем парам соседних элементов массива с целю перестановки несортированных пар элементов. Переменная L играет роль параметра, по которому можно определить производились ли перестановки при выполнении внутреннего цикла.

Алгоритм работает следующим образом. Сначала в блоке 2 параметр L получает значение 0 (нуль). Далее выполняется цикл блоков 3 — 6. В нем счетчик цикла i будет последовательно принимать значения 1, 2, 3, . N-1. При каждом таком значении счетчика в блоке 4 производится сравнение соседних элементов с номерами i и i+1 . В том случае, если пара не отсортирована, то в блоке 5 путем обращения к вспомогательному алгоритму Perm эта пара будет отсортирована путем перестановки значений этих элементов. После каждой перестановки счетчик перестановок L будет увеличиваться на 1. После прохода по парам элементов на выходе из внутреннего цикла выполнится проверка количества совершенных перестановок. Если перестановок не было ( L = 0 ), то это значит, что массив отсортирован и можно заканчивать работу процедуры сортировки. Если же это не так, то управление предается на блок 2 и процесс сортировки продолжится по той же схеме. Наружный цикл будет выполняться до тех пор, пока при проходе по внутреннему циклу не будет выполнено ни одной перестановки.

На рис. 14 показан головной алгоритм, который и решает поставленную задачу. Сначала в блоке 2 задается количество N элементов массива и все N ячеек массива A заполняются числами. Затем в блоке 3 происходит вызов вспомогательного алгоритма Sort. В нем на место формального параметра N подставляется фактическое значение параметра N головного алгоритма, а на место формального массива Z подставляется фактический м ассив A . Теперь управление передается в алгоритм Sort, который выполнит сортировку массива A.

После сортировки в блоке 4 головного алгоритма отсортированный массив будет выведен и в блоке 5 алгоритм закончит свою работу.

Рис. 12. Процедура Perm

Рис. 13. Процедура Sort

Рис. 14. Головной алгоритм

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

Рассмотрим задачу вычисления факториала числа N! = 1 . 2 . 3 . . . N. Результатом будет одно число, поэтому лучше алгоритм оформить в виде функции .

Б лок — схема алгоритма-функции показана на рис. 15. Переменная К используется для накопления произведения и, поскольку 0! = 1 и1! = 1, то в блоке 2 ей сразу присваивается значение 1. Далее, если N > 1 , то в цикле, образованном блоками 4-5, накапливается искомое произведение и помещается в переменную К. В блоке 6 имя Fact функции получает значение вычисленного произведения из ячейки К. Для процедур действия, размещенного в блоке 6, не может быть, а для функций оно должно быть обязательно, поскольку иначе значение функции на выходе окажется неопределенным.

Обращение к функции в других алгоритмах (головных, процедурах, функциях) производится по ее имени.

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

Пример использования функции Fact показан на рис. 16. В операторе присваивания используется обращение к функции для N = 6. После передачи этого значения в алгоритм рис. 15 и вычислений внутри него результат будет сначала присвоен имени функции, т. е. переменной Fact, а затем в операторе присваивания — переменной L.