Что такое цикл в компьютере
С повторяющимися действиями мы сталкиваемся и в обычной жизни и при решении задач. Проход стрелок часов каждую минуту, секунду, час, смена дня и ночи, ежедневные сборы в школу, еженедельная смена уроков, ежегодные поездки на море – примеров циклов повторения миллиарды. Несмотря на разнообразие происходящих процессов, большинство из них можно описать простыми конструкциями. Делая что-то раз за разом, мы не задумываемся, что ученые уже написали алгоритмы с повторением или циклы универсальными способами.
Цикл со счетчиком.
Цикл со счетчиком применяется когда заранее известно сколько повторений необходимо сделать. В примере выше с приседаниями именно такой случай.
Для того, чтобы написать цикл со счетчиком для исполнителя необходимо знать его синтаксис. А он такой:
Здесь мы должны указать количество повторений (число) и команды, которые будут повторяться. Команды, которые повторяются в цикле называют телом цикла .
Давайте рассмотрим это на примере.
Закрасим 7 клеток, как на рисунке. Рекомендую почитать про стартовую обстановку Робота и про его простые команды.
Изначально Робот находился в левой верхней клетке.
Давайте для начала решим задачу линейно. В этом случае мы будет закрашивать текущую клетку и перемещаться на 1 клетку вправо и программа будет выглядеть так:
использовать Робот
алг
нач
Как видим, команды закрасить и вправо повторяются 7 раз. Давайте теперь перепишем программу с использованием цикла. Кстати, чтобы вставить цикл в свою программу можно в меню Вставка выбрать пункт нц-раз-кц или нажать одну из комбинаций клавиш Esc, Р (русская буква Р) или Esc, H (латинская буква H). Причем клавиши надо нажимать последовательно — сначала Esc, отпустить ее и только потом Р или H.
Так вот, наша программа с циклом будет выглядеть так:
использовать Робот
Если мы ее запустим, то увидим, что в результате получится тоже самое — 7 закрашенных клеток. Однако программа стала короче и значительно грамотней с алгоритмической точки зрения!
В качестве разминки и закрепления предлагаю самостоятельно написать программу для Робота, которая нарисует квадрат со стороной 7 клеток. Естественно, используя цикл. Жду решения в комментариях.
Операторы циклов: цикл while
Цикл с условием.
Вернемся к физкультуре и изменим задачу. Ведь кто-то может и не сделать 7 приседаний, а другой способен сделать 27. Можно ли учесть это при создании цикла? Конечно. Только теперь мы будем использовать не счетчик (количество повторений), а условие. К примеру, пока не устал, делай приседания. В этом случае человек будет делать не конкретное число приседаний, а приседать до тех пор, пока не устанет. И наш цикл на абстрактном языке примет такой вид:
пока не устал
Слова не устал в нашем случае — это условие. Когда оно истинно, цикл выполняется. Если же оно ложно (устал) тело цикла не будет выполнено. У исполнителя Робот есть несколько условий
сверху свободно
снизу свободно
слева свободно
справа свободно
сверху стена
снизу стена
слева стена
справа стена
Теперь давайте решим следующую задачу для Робота — нарисовать вертикальную линию от левой до правой границы поля использую цикл с условием. Изначально Робот находится в левом верхнем углу.
Давайте сначала сформулируем словесный алгоритм — т. е. опишем словами что нужно делать Роботу. Этот алгоритм будет звучать примерно так:
«Пока справа свободно делай шаг вправо и закрашивай клетку»
В результате Робот пробежит по всем клеткам вправо и будет их закрашивать до тех пор, пока справа не окажется стена.
Исходный код нашей программы для Робота будет примерно такой:
использовать Робот
нц пока справа свободно
В результате выполнения этой программы мы увидим вот такую картину:
Как видим, не хватает только закрашенной первой клетки. Для этого перед циклом необходимо выполнить команду закрасить.
Для закрепления прошу написать программу, которая будет делать рамку вокруг рабочего поля Робота независимо от его размера. Конечно же с использованием циклов с условием. В итоге должно получиться так:
Все в нашей жизни циклично. дни недели, месяцы, года. И в программировании тоже не обойтись без этого.
В этой главе мы с вами будем рассматривать, так называемые циклы , а именно цикл while и цикл for . Для чего они нужны? Для того, чтобы ответить на этот вопрос давайте представим себе такую ситуацию: ну к примеру вы хотите напечатать на экране свое имя ровно 20 раз. Как вы уже знаете для этого мы должны воспользоваться оператором консольного вывода (cout - поместить в поток). Вот такая строка кода должна выводить ваше имя:
Для того, чтобы вывести имя 20 раз нам нужно написать в своей программе эту строку ровно 20 раз! Хорошо, если вы решили вывести свое имя 20 раз, а не, к примеру, 100 или 1000! Конечно же, вы понимаете, что это очень накладно и нереально. В этом случае на помощь программисту приходят циклы while и for , которые позволяют выполнять определенный участок кода (в нашем случае это печать имени) столько раз, сколько мы укажем. Иными словами, пока не выполнится какое-либо условие, требуемое для завершения цикла. В нашем случае этим условием, как вы уже догадываетесь, является число 20, т.к. печатать нам нужно именно 20 раз. Рассмотрим цикл while.
Виды циклов.
Что такое стартовая обстановка?
Цикл while с постусловием
Цикл while с предусловием мы рассмотрели, но есть еще и второй вариант использования цикла while - это цикл с постусловием. Синтаксис его таков:
В чем же разница!? Разница одна лишь в том, что тело (содержимое) такого цикла while выполниться как минимум один раз, т.к. условие теперь уже проверяется не в начале цикла, а в конце. Иногда в ваших программах нужно будет использовать именно такую разновидность цикла while. Перепишем нашу программу с использованием данной разновидности цикла while:
- Цикл while бывает двух типов: с предусловием и постусловием. В первом варианте тело цикла может ни разу не выполниться, если условие начала цикла не выполняется. Во втором варианте тело цикла выполниться как минимум один раз, т.к условие начала уже второй итерации цикла проверяется не в начале, а в конце.
- В конце цикла while с постусловием не забывайте ставить точку с запятой.
Операторы циклов: цикл for
Теперь давайте рассмотрим вторую разновидность циклов, используемых в языке программирования С++ - это цикл for. Чем же он отличается? Главное его отличие в том, что в параметрах самого цикла можно инициализировать (объявить) переменную-счетчик, которая у нас будет считать итерации (повторения) циклов, и задать ей начальное значение, задать условие выполнения цикла и изменять значение счетчика. Синтаксис цикла for таков:
Давайте теперь переиначим программу, печатающую ваше имя, под этот цикл. Вот что у нас получится:
Как видите размер кода программы у нас уменьшился, стал более компактным. Легко просматриваются по параметрам цикла for наши начальные значения, условия и приращения, что очень удобно. Какими видами циклов вам удобнее пользоваться в своих программах и в каких ситуациях вы постепенно поймете на практике.
Циклический алгоритм с постусловием
Такую конструкцию называют «цикл-До». Здесь условие является основанием окончания выполнения команд из тела, то есть, они выполнятся хотя бы раз, даже если условие ложно.
Порядок выполнения цикла с заданным условием:
- Выполнение команд из тела.
- Проверка условия (сравнения определенной величины с заданной).
- Пока ответ на условие «Нет», повторять описанные в теле операции/шаги.
- Если ответ на условие положительный, закончить процедуру.
Описание структуры с постусловием языком блок-схем и на алгоритмическом языке:
Особенности циклов с заданным условием окончания работы:
- Будет хотя бы одно выполнение процедуры;
- Условие описывает завершение повторяемых действий.
Пример: написать программу покраски забора.
Блок схема циклического алгоритма.
Цикл с предусловием
Данную конструкцию еще встречается как «цикл-пока», потому что пока выполняется условием, программа/исполнитель будет проходить шаги снова и снова.Описанный критерий, логическое сравнение - причина начала прохождения повторяемых шагов/команд.
Описание цикла с условием двумя способами:
- Проверка критерия/логического сравнения.
- Пока результат «Да», «проигрывать по кругу» однотипные операции.
- Если ответ на условие отрицательный, закончить процедуру.
Особенность этой конструкции – существуют такие условия, когда команды не будут выполнены ни разу.
Циклический алгоритм, примеры:
- Написать алгоритм постройки забора из кирпичей высотой 2 м.
алг забор
нач
нц пока есть кирпичи и раствор цемента
если высота забора < 2,0 м
то намазать слой цемента
положить слой кирпичей
иначе сделать сверху декоративный слой
все
кц
кон
- Нарисовать шуточный (но действующий) алгоритм покраски забора «от начала и до обеда.
- Написать алгоритм вычисления частного и остатка от числа, не используя операции деления. В программе используются целые числа.
Заменим деление вычитанием, будем выполнять отнимание, пока остаток не будет меньше вычитаемого – условие выполнения. Число вычитаний и будет частному от деления, это счетчик цикла, а разность, выполненная в последний раз – остаток от деления.
Обозначим x – делимое, y – делитель, q – частное от деления, r – остаток.
- Если условие ни разу не выполняется, то команды из тела не будут выполнены ни разу. Это нормально, это один из вариантов – нет необходимости в выполнении команд.
- Если же условие всегда истинно, тело операции будут выполняться бесконечное число раз. Такое положение называется зацикливанием. Фактически программа «зависает» и не сможет завершиться сама. Рекомендуется предусмотреть этот вариант.
Наш Робот находится в некой среде — это клетчатое поле, размер которого известен. Так же на этом поле могут находится стены и закрашенные клетки, а сам Робот может находится в любой клетке. Так вот — стартовая обстановка задает положение Робота на поле и расположение всех остальных элементов — стен, закрашенных клеток. И перед тем, как писать алгоритм для Робота необходимо задать стартовую обстановку. Насколько это важно давайте рассмотрим на примере. Пусть есть две стартовые обстановки:
Стартовая обстановка 1
Стартовая обстановка 2
Отличаются они только тем, что в стартовой обстановке 2 справа от Робота находится стена.
Если наша программа начнется с команды, которая переместит Робота на одну клетку вправо (о простых командах Робота), то в первом случае (стартовая обстановка 1) Робот выполнит эту команду, а во втором программа завершится аварийно, так как Робот не может ходить сквозь стены. Получается, что одна и та же программа в первом случае работает, а во втором приводит к ошибке. Именно поэтому так важно задавать стартовую обстановку для Робота.
Цикл со счетчиком в программировании
Для описания цикла с заданным повторением применяют оператор for.
Общий вид блока на языке программирования:
Программа проходит команды из тела и значение счетчика (параметра) становится больше на 1. Чтобы выйти из цикла с фиксированным числом повторений, нужно достичь максимума параметра, который указан в условии задачи.
Операторы циклов: цикл while
Циклы, их виды
Многие операции, действия выполняются однотипно много раз. Этот процесс повторения называют циклом, а повторяемая последовательность – телом цикла. Процедуру с повторяющимися этапами называют циклической.
Каждое повторение действий в алгоритмах – итерация.
Выделяют 3 основных вида повторяющихся структур:
- с условием выполнения цикла (предусловием);
- с критерием завершения (постусловием);
- с указанным числом повторений цикла.
Описывать подобные процессы удобно схематично или при помощи команд.
Почему важен такт
Сначала нужно понять, что все операции, которые вы проектируете в цифровой логической схеме, выполняются аппаратно в течение какого-то времени. Причём разные операции длятся по-разному. Переход с одного края микросхемы на другой занимает время.
Эта мысль изображена на графике. Давайте поместим сверху входные данные для нашего алгоритма, в середине — логику, а внизу — выходные данные. Ось времени отложим сверху вниз, от одного такта до другого.
Иллюстрация 5. Выполнение логики занимает время, три операции
На иллюстрации 5 показано несколько операций (сложение, умножение) и несколько раундов применения AES, хотя для нашего примера это могут быть раунды любого другого алгоритма. Вертикальный размер блоков характеризует длительность каждой операции. Кроме того, операции, зависящие от других операций, идут друг за другом. То есть если вы хотите в пределах такта выполнить много раундов применения AES, то имейте в виду, что второй раунд не начнётся до тех пор, пока не завершится первый. Следовательно, внедрение такой логики увеличит длительность между тиками тактов и замедлит общую тактовую частоту.
Посмотрите на розовые блоки.
Они отражают потери активности вашей аппаратной схемы (hardware circuit) — время, которое можно было бы потратить на выполнение каких-то операций. Но поскольку вы решили дождаться завершения такта или ждёте, чтобы сначала обработать входные данные, то вы ничего не можете делать. Например, на этом графике умножение длится не больше одного раунда применения AES, как и сложение. Однако вы не можете ничего сделать с результатами этих двух операций, пока выполняются вычисления AES, потому что для получения их следующих входных данных нужно дождаться следующего такта. То есть розовые блоки — это время простоя электронной схемы. Причём в данном случае оно увеличено из-за того, что раунды применения AES отдаляют следующий такт. Так что такая схема не сможет использовать всех возможностей оборудования.
Если бы нам нужен был лишь конвейер применения AES-алгоритма, чтобы один раунд мог быть вычислен в каждом такте, то схема могла бы работать быстрее, тратя меньше времени на ожидания.
Иллюстрация 6. Разбиение операций для ускорения тактов
После разбиения операции на более мелкие операции, каждая из которых может быть выполнена между тиками тактов, потери активности сильно уменьшаются. Причём вместо шифрования только одного блока данных за раз мы можем превратить алгоритм шифрования в конвейер. Получившаяся логика не будет шифровать одиночный блок быстрее, чем на иллюстрации 5, но если поддерживать наполненность конвейера, то это в 10—14 раз увеличит скорость AES-шифрования.
Это следствие более качественной архитектуры.
Можно ли сделать ещё лучше? Да! Если вы знакомы с AES, то знаете, что каждый раунд состоит из дискретных шагов. Их тоже можно раскидать, ещё больше увеличив скорость такта, пока выполнение логики AES-раунда не станет занимать меньше времени, чем умножение. Это увеличит количество сложений и умножений, которые вы можете выполнить, так что разложение движка шифрования на микроконвейеры позволит пропускать за такт ещё больше данных.
Также на иллюстрации 6 показана парочка других вещей.
Во-первых, будем считать стрелки задержками при маршрутизации (routing delays). График не масштабный, это лишь иллюстрация для отвлечённой дискуссии. Каждая часть логики должна получать результат предыдущей части логики. Это означает, что даже если какой-то части логики не требуется времени для выполнения — как если бы просто менялся порядок проводов, — то переход логики с одного конца микросхемы к другому всё же займёт время. Следовательно, даже если вы максимально упрощаете свои операции, всё равно будут задержки на перемещение данных.
Во-вторых, вы могли заметить, что ни одна стрелка не начинается с начала такта. И ни одна не доходит до следующего такта. Это сделано для иллюстрирования концепции времени установки и удержания (setup and hold timing). Триггеры — это структуры, которые удерживают и синхронизируют ваши данные в такте. Им нужно время до начала такта, чтобы данные стали постоянны и определены. Хотя многие считают, что такт начинается мгновенно, на самом деле это не так. В разных частях микросхемы он начинается в разное время. И это тоже требует буфера между операциями.
К каким заключениям можно прийти в результате этого урока?
- Выполнение логики требует времени.
- Чем больше логики, тем больше нужно времени.
- Скорость такта ограничена количеством времени, которое нужно для выполнения логики, находящейся между тиками тактов (плюс задержки при маршрутизации, время установки и удержания, неопределённость начала такта и т. д.).
Чем больше логики в тактах, тем ниже тактовая частота. - Скорость быстрейшей операции будет ограничена скоростью такта, необходимой для выполнения самой медленной операции.
Например, вышеописанная операция сложения. Она могла выполняться быстрее умножения и любого одиночного раунда применения AES, однако ей приходилось ждать выполнения остальной логики в схеме. - Существует аппаратное ограничение скорости такта. Какое-то время уходит даже на операции, не требующие логики.
Получается, что при сбалансированной архитектуре в тактах нужно располагать более-менее равное количество логики на протяжении всей схемы.
Цикл начала работы в программировании
Так, описанная выше команда в программировании обозначается словом While. Этот оператор обозначает многократное прохождение участка кода. Это очень востребованная операция.
"While" обозначает на английском "пока". Но не как прощание, а как то, что «делается пока, что-то происходит/выполняется». Этот оператор используется во всех языках программирования, использующих структурный подход (Pascal, Python). Обобщено его записывают так:
Как видим, это очень похоже на запись на алгоритмическом языке – написанное просто, структурировано и понятно.
Подход такой же, как и цикле-пока – проверяется условие, если оно «True», выполняется тело с командами, если «False» – блок программы заканчивается. В этой конструкции не выполненное условие - окончания работы цикла. После этого программа перейдет к следующему блоку команд, то есть «выйдет из цикла».
Урок № 1: аппаратная архитектура — это параллельная архитектура
Первая и, вероятно, самая трудная часть изучения аппаратного проектирования заключается в том, чтобы осознать, что вся аппаратная архитектура параллельна. Ничто не выполняется последовательно, как одна инструкция за другой (см. иллюстрацию 1) в компьютере. На самом деле всё происходит за раз, как на иллюстрации 2.
Иллюстрация 2. Аппаратная логика работает параллельно
Это многое меняет.
Иллюстрация 3. Программный цикл
Первое, что должно измениться, — сам разработчик. Научитесь мыслить параллельно.
Хороший пример, иллюстрирующий это различие, — аппаратный цикл.
В ПО цикл состоит из серии инструкций, как на иллюстрации 3. Они создают набор начальных условий. Затем в цикле применяется логика. Для определения этой логики используется переменная цикла, которая часто инкрементируется. Пока эта переменная не достигнет состояния прерывания, процессор будет циклически повторять инструкции и логику. Чем больше раз прогоняется цикл, тем дольше выполняется программа.
Аппаратные циклы на базе HDL работают совсем не так. Средство синтеза (synthesis tool) HDL использует описание цикла для создания нескольких копий логики, все они выполняются параллельно. Нет нужды синтезировать логику, используемую для создания цикла, — например индекс, инкрементирование этого индекса, сравнение индекса с финальным состоянием и т. д., — поэтому её обычно убирают. Более того, поскольку средство синтеза создаёт физические соединения и логические блоки, количество прохождений цикла не может изменяться после завершения синтеза.
Получающаяся структура показана на иллюстрации 4. Она очень отличается от структуры программного цикла на иллюстрации 3.
Иллюстрация 4. Цикл, сгенерированный HDL
Из этого есть ряд следствий. Например, итерации циклов необязательно зависят от выходных данных предыдущих итераций, как в ПО. В результате трудно прогонять цикл логики по всем данным в наборе, получая ответ в следующем такте.
Но… теперь мы снова вернулись к концепции цикла.
Цикл — это основа любой FPGA-схемы. Всё вращается вокруг него. Вся разработка вашей логики должна начинаться с такта. Это не второстепенная вещь, такт в первую очередь формирует структуру вашего мышления о проектировании цифровых логических схем.
Как задать стартовую обстановку?
Запустив среду Кумир в меню Инструменты выбираем пункт Редактировать стартовую обстановку Робота
Откроется окно с синим фоном. Это и есть стартовая обстановка Робота. И мы ее можем изменить.
По-умолчанию, размер окна 10 на 15 клеток. Если нам необходимо изменить количество строк и столбцов, то щелкаем Обстановка -> Новая обстановка и задаем необходимые значения
- чтобы переместить Робота в новую позицию, щелкаем по нему левой кнопкой мыши и не отпуская ее тащим Робота в нужное место.
- чтобы добавить/удалить стену, щелкаем левой кнопкой мыши по границе клетки.
- чтобы закрасить/очистить клетку, щелкаем по ней левой кнопкой мыши
- чтобы добавить или убрать точку в клетку щелкаем по клетке, удерживая клавишу Ctrl
После того, как мы задали нужную стартовую обстановку, ее необходимо сохранить (Обстановка -> Сохранить или Обстановка -> Сохранить как). После этого закрываем окно Обстановка и в основном окне программы выбираем Робот -> Сменить стартовую обстановку
Находим сохраненную ранее обстановку и загружаем ее. После этого убедимся, что загрузили правильную стартовую обстановку, щелкнув по кнопке Показать окно Робота
Если в окне с зеленым фоном (текущая обстановка Робота) вы увидите вашу обстановку, то можно переходить к написанию алгоритма, используя простые команды Робота.
Исполнитель Робот. Простые команды.
У нашего Робота тоже есть система команд. Сегодня мы рассмотрим простые команды Робота. Всего их 5:
вверх
влево
вправо
закрасить
Результат выполнения этих команд понятен из их названия:
вверх — переместить Робота на одну клетку вверх
вниз — переместить Робота на одну клетку вниз
влево — переместить Робота на одну клетку влево
вправо — переместить Робота на одну клетку вправо
закрасить — закрасить текущую клетку (клетку в которой находится Робот).
Эти команды можно писать с клавиатуры, а можно использовать горячие клавиши (нажав их команды будут вставляться автоматически):
вверх — Escape, Up (стрелка вверх)
вниз — Escape, Down (стрелка вниз)
влево — Escape, Left (стрелка влево)
вправо — Escape, Right (стрелка вправо)
закрасить — Escape, Space (пробел)
Обратите внимание, что набирать нужную комбинацию горячих клавиш нужно не привычным нам способом! Мы привыкли нажимать клавиши одновременно, а здесь их нужно нажимать последовательно.
Теперь мы готовы написать первый алгоритм для Робота. Предлагаю начать с простого — нарисуем квадрат со стороной 3 клетки. Поехали!
Запускаем Кумир, настраиваем его. Можно начинать писать программу? Конечно нет! Мы же не задали стартовую обстановку! Делаем это. Предлагаю использовать вот такую:
Вот теперь все готово. Начинаем писать программу. Пока она выглядит так
Удаляем символ «|» и называем наш алгоритм «Квадрат»
Предлагаю рисовать квадрат, двигаясь по часовой стрелке. Для начала закрасим текущую клетку, дав команду закрасить. Потом делаем шаг вправо и опять закрашиваем клетку. И еще раз шаг вправо и закрасить.
Попробуем запустить программу и посмотреть что же получилось. Для запуска нажимаем F9 или же кнопку на панели инструментов
В результате мы должны увидеть вот такую картину
Если такое окно Робота у вас не появилось, то на панели инструментов щелкните «Показать окно Робота» или в меню Робот выберите пункт "Показать окно Робота". Продолжаем дальше.
Теперь мы будем двигаться вниз и закрашивать правую сторону квадрата:
Потом пойдем влево, закрашивая нижнюю границу квадрата
У нас осталась одна незакрашенная клетка. Закрасим ее
Все готово! В итоге наша программа выглядит так:
использовать Робот
алг Квадрат
нач
закрасить
вправо
закрасить
вправо
закрасить
вниз
закрасить
вниз
закрасить
влево
закрасить
влево
закрасить
вверх
закрасить
кон
А результат ее работы вот так
Итак, сегодня мы с вами написали программу, используя простые команды Робота. Рекомендую попрактиковаться самостоятельно — придумать себе задание и написать программу. Это могут быть самые различные фигуры, узоры, буквы. К примеру, попробуйте написать программу, рисующую букву П, Р, Ш, Щ, М. А если получится и захотите поделиться — комментируйте и прикрепляйте результат к комментарию.
Исполнитель Робот. Циклы.
Итак, что такое цикл? Представьте, что мы находимся на уроке физической культуры и перед нами стоит задача сделать 7 приседаний. Это задание можно оформить в виде линейного алгоритма и тогда оно будет выглядеть примерно так:
Т. е мы повторили команду сделай приседание 7 раз. А есть ли смысл писать 7 одинаковых команд? Может проще дать команду сделай 7 приседаний? Конечно проще и правильнее. Это и есть цикл. Вы можете сами вспомнить примеры циклов из жизни — их довольно много.
Таким образом линейный алгоритм, где повторяются одни и те же команды мы можем оформить в виде циклического алгоритма — примерно так:
Вот так, на придуманном нами языке мы оформили цикл. У исполнителя Робот тоже есть возможность записывать циклы. Причем, циклы бывают разные. Тот вариант, который мы только что рассмотрели называется цикл со счетчиком или цикл с параметром.
Повторение в программировании
Не нужно недооценивать изучение простейших алгоритмических конструкций. Следование, ветвление, повторение – важные конструкции, операторы, используемые в программировании.
Зная их особенности, умея строить блок-схемы и писать решение задач на алгоритмическом языке, позволяет изучать большинство языков программирования легко и быстро.
Большинство задач можно описать при помощи первой конструкции, иногда это неудобно, для каждого типа заданий лучше подбирать оптимальный по выполнению алгоритм.
Цикл while с предусловием
Синтаксис данного оператора цикла таков:
А теперь давайте с вами запрограммируем эту программу. Итак, программа, печатающая имя, будет выглядеть так:
Мы определяем переменную i, которая у нас будет служить счетчиком, задаем нашему счетчику начальное значение равное единице перед входом в цикл. В цикле определяем условие, при котором у нас будет он работать, т.е. выполняться заключенные в него операторы. После того, как условие перестанет выполняться, цикл завершится и программа выйдет из него и перейдет к выполнению следующих после цикла операторов (у нас это оператор return 0;) . Как я уже сказал, для того, чтобы цикл работал должно выполняться указанное в нем условие (у нас это i
(Небольшое отступление) Как видите здесь используется оператор присваивания. В предыдущих главах я объяснял как он работает, повторим: то, что находится от оператора присваивания (=) справа, считается и помещается в переменную, расположенную слева от оператора присваивания (=). То есть, если в предыдущей итерации (шаге выполнения цикла) i было равно 2, то новое значение будет с помощью данной строчки кода посчитано так:
Есть и сокращенная форма записи этой строки кода, которая увеличивает значение переменной на единицу:
++ - это оператор инкремента.
Рассмотренный способ использования оператора цикла while, называется цикл с предусловием.
- Циклы в программировании позволяют выполнять отдельный кусочек программы, заключенной в его тело (между <>), столько раз - сколько мы укажем, либо пока не наступит определенное условие его завершения.
- Обязательно нужно предусмотреть условие выхода из цикла, иначе произойдет ошибка зацикливания программы.
- В языке программирования С++ существует возможность увеличения значения переменной на единицу с помощью оператора инкремента (++).
Сколько логики помещать в тактах?
Теперь вы знаете, что вам необходимо работать с тактами. Как вы измените или построите свою схему в свете этой информации? Правильный ответ: вы ограничите количество логики в тактах. Но насколько ограничить и как это понять?
Один из способов определения оптимального количества логики в такте — задать среднее значение скорости тактов, а затем построить схему с помощью набора инструментов, которые понимают ваше оборудование. Каждый раз, когда схема не будет соответствовать требованиям тайминга, вам придётся возвращаться назад и разбивать компоненты схемы либо замедлять тактовую частоту. Нужно иметь возможность использовать свои инструменты проектирования для поиска наиболее длинного пути.
Сделав это, вы освоите ряд эвристических правил, которые потом будете использовать для вычисления количества логики в тактах применительно к оборудованию, с которым вы работаете.
Например, я хочу построить схему с тактовой частотой 100 МГц с деталями серии Xilinx 7. Эти схемы потом обычно работают на 80 МГц и на Spartan-6 либо на 50 МГц и на iCE40 — хотя это и не строгие сочетания. На одном чипе пойдёт нормально, другой чип окажется избыточно мощным, на третьем появятся проблемы с проверкой синхронизации (timing check).
Вот несколько примерных эвристических правил, относящихся к тактам. Поскольку это эвристика, вряд ли она применима для всех видов схем:
1. Обычно я могу в рамках такта выполнять 32-битное сложение с мультиплексированием 4—8 элементов.
Если будете использовать более быстрые такты, например 200 МГц, то вам может понадобиться отделить сложение от мультиплексора. Самый длинный путь ZipCPU начинается с выходных данных ALU и заканчивается входными данными ALU. Звучит просто. Даже соответствует вышеописанной эвристике. Проблема, с которой борется ZipCPU на более высоких скоростях, заключается в маршрутизации выходных данных обратно в ALU.
Давайте разберём маршрут: после ALU логический путь сначала идёт через четырёхсторонний мультиплексор, чтобы решить, чьи выходные данные нужно записать обратно — из ALU, памяти или операции деления. Затем записанный результат передаётся в схему обхода (bypass circuit), чтобы определить, нужно ли немедленно передавать его в ALU в качестве одних из двух входных данных. Только в конце этого мультиплексора и обхода наконец-то выполняется ALU-операция и мультиплексор. То есть на каждом этапе логический путь может пройти через ALU. Но благодаря конструкции ZipCPU любые такты, вставленные в логический путь, пропорционально замедлят выполнение ZipCPU. Это означает, что самый длинный путь наверняка на время останется самым длинным путём ZipCPU.
Если бы меня интересовало выполнение ZipCPU с более высокой скоростью, то это был бы первый логический путь, который я попытался бы разбить и оптимизировать.
2. 16×16-битное умножение занимает только один такт. Иногда на каком-нибудь оборудовании я могу реализовать в одном такте 32×32-битные умножения. А на другом оборудовании придётся разбивать на части. Так что если мне когда-нибудь понадобится знаковое (signed) 32×32-битное умножение, я воспользуюсь конвейерной подпрограммой (pipelined routine), которую я сделал для таких случаев. Она содержит несколько вариантов умножения, что позволяет мне выбирать подходящие для текущего оборудования опции.
3. Любое блочное обращение к оперативной памяти (block RAM access) занимает один такт. Старайтесь не подстраивать индекс в ходе этого такта. Также избегайте в это время любых операций с выходным данными.
Хотя я утверждаю, что это хорошее правило, но мне приходилось успешно нарушать обе его части без (серьёзных) последствий при работе на 100 МГц на устройстве Xilinx 7 (у iCE40 с этим проблемы).
Например, ZipCPU считывает из своих регистров, добавляет непосредственный операнд к результату, а затем выбирает, должен ли результат быть регистр плюс константа, PC плюс константа либо регистр кода условия (condition code register) плюс константа — всё в одном такте.
Другой пример: долгое время Wishbone Scope определял адрес для считывания из своего буфера на основе того, выполняется ли чтение из памяти в ходе текущего такта. Разрыв этой зависимости потребовал добавления ещё одного такта задержки, так что текущая версия больше не нарушает это правило.
Эти правила — не более чем эвристика, которой я пользуюсь для определения того, сколько логики помещается в такты. Это зависит от оборудования и скорости тактов, так что вам может и не подойти. Рекомендую выработать свои эвристики.
Цикл окончания работы в программировании
Для записи такой повторяемой конструкции в языках программирования используется оператор repeat. После него следуют команды (тело), после – оператор until, обозначающий условие окончание процесса.
Для этих двух конструкций возможно зацикливание. В программировании применяется специальный оператор break принудительного окончания процесса.
Управление циклом. Команды break и countinue
Оператор break используется для прерывания выполнения цикла. Пусть, нам нужно найти некоторый элемент в массиве. Так, используя цикл, мы можем выйти из цикла, как только найдем искомый элемент.
Так мы находим индекс искомого слова в массиве, при этом не выполняем лишних операций после того, как найдем искомый элемент.
Оператор continue используется для перехода к следующей итерации цикла. Рассмотрим задачу: необходимо вычислить сумму пяти частных вида:
Как вы видите, при i = a будет получена ошибка «Деление на ноль». В данном случае мы можем пропускать значение счетчика, которое приводит к ошибке.
Если у вас есть опыт создания ПО и вы хотите познакомиться с проектированием цифровых логических схем (digital design), то одна из первых вещей, которые вам нужно понять, — это концепция тактов. Она раздражает многих программных инженеров, начинающих HDL-проектирование. Без использования тактов они могут превратить HDL в язык программирования с $display , if и циклами for , как в любом другом языке. Но при этом такты, которые новички игнорируют, — зачастую один из основополагающих элементов при проектировании любых цифровых логических схем.
Ярче всего эта проблема проявляется именно при рассмотрении первых схем, созданных начинающими HDL-разработчиками. Я недавно общался с некоторыми из них. Новички опубликовали свои вопросы на форумах, которые я читаю. Когда я проанализировал то, что они делают, от увиденного волосы встали дыбом.
Например, один из студентов попросил объяснить, почему никого в сети не заинтересовала его HDL-реализация AES. Не стану смущать его, приводить ссылку на проект или имя его создателя. Вместо этого я буду называть его студентом. (Нет, я не профессор.) Так вот, этот студент создал Verilog-схему, в которой AES-шифрование выполняется в течение не одного раунда, а каждый раунд, с комбинаторной логикой без тактов. Не помню, какой именно AES он применил, 128, 192 или 256, но AES требует от 10 до 14 раундов. В симуляторе его движок шифрования работал идеально, при этом на шифрование/дешифрование своих данных он использовал только один такт. Студент гордился своей работой, но не мог понять, почему те, кто её смотрел, говорили ему, что он мыслит как программный инженер, а не аппаратный.
Иллюстрация 1. Программное обеспечение последовательно
Теперь у меня есть возможность дать советы программным инженерам вроде того студента. Многие из них обращаются с HDL как ещё с одним языком для написания приложений. Имея опыт программирования, они берут основы из любого софтверного языка программирования — как объявлять переменные, как сделать выражение «если», оператор выбора, как писать циклы и т. д., — а затем пишут код как компьютерную программу, в которой всё выполняется последовательно, при этом полностью игнорируя реалии проектирования цифровых логических схем, где всё происходит параллельно.
Иногда эти программисты находят симулятор вроде Verilator, iverilog или EDA playground. Тогда они используют в своей логике кучу команд $display , обращаясь с ними, как с последовательными printf , заставляя код работать без применения тактов. Затем их схемы «работают» в симуляторе с использованием одной лишь комбинаторной логики.
И потом эти студенты описывают мне свои схемы и объясняют, что они «без тактов».
Дело в том, что никакая цифровая логическая схема не может работать «без тактов». Всегда существуют физические процессы, создающие входные данные. Все эти данные должны быть валидны на старте — в момент, формирующий первый «тик» тактового генератора в схеме. Аналогично некоторое время спустя из входных данных нужно получить выходные. Момент, когда все выходные данные валидны для данного набора входных данных, образует следующий «такт» в «бестактовой» схеме. Возможно, первый «тик» — это когда настроен последний переключатель на плате, а последний «тик» — когда глаза считывают результат. Неважно: такт существует.
В результате, если кто-то утверждает, что в его схеме «нет тактов», то это означает, что либо он каким-то неестественным образом использует симулятор, либо у его схемы есть какой-то внешний такт, задающий входные данные и считывающие выходные — и тогда получается, что на самом деле такты есть.
Если вы пытаетесь понять необходимость тактов при работе над цифровой логической схемой либо если вы знаете кого-то, кто ломает голову над этой концепцией, то эта статья для вас.
Давайте пока обсудим такт и важность постройки и проектирования вашей логики вокруг него.
Практические задачи по операторам циклов: цикл while
1. Повторение, управляемое счетчиком. Чтобы лучше понять алгоритм работы цикла while, рассмотрим классическую задачу усреднения:
Проведен опрос класса из 10 студентов. Вам известны оценки по этому опросу (целые числа в диапазоне 0 - 100). Нужно определить среднюю оценку класса.
Конечно же, мы помним со школьного курса, что для определения среднего числа группы чисел, нужно найти общую сумму этих чисел и разделить ее на количество суммируемых чисел. Также мы поступим и с нашей задачей. Код программы смотрим ниже:
Результат работы программы:
Разберем программу подробнее
Начинаем с объявления необходимых переменных: total - будет накапливать общую сумму баллов студентов; counter - является счетчиком итераций цикла while (в нашем случае число повторений цикла заранее известно, поэтому эту разновидность цикла еще называют повторением, управляемым счетчиком); average - будет содержать у нас наше искомое среднее значение; grade - в эту переменную будем записывать введенное пользователем значение балла.
На следующем шаге присваиваем начальные значения счетчику циклов и общей сумме баллов.
Затем организовываем цикл while, задав условие выполнения, в котором запрашиваем у студента его балл и сохраняем в переменную grade. Также в цикле предусматриваем проверку на правильность ввода данных студентами: в случае правильного ввода засчитываем балл и увеличиваем счетчик цикла на единицу, в обратном случае выводим пользователю подсказку, не засчитыаем балл и не увеличиваем счетчик, т.е. в любом случае у нас будет 10 "правильных" баллов.
Далее подсчитываем средний балл и запоминаем в переменную average, выводим результат на экран.
Здесь используется операция присваивания в сокращенном виде. Вначале в своих программах вы можете пользоваться полной записью присваивания, а потом уже переходить на сокращенную. Вот полная запись этих строк:
Ну и конечно же последнюю строку, как мы уже говорили выше можно еще записать и так:
2. Повторение, управляемое меткой. Давайте теперь немного модифицируем предыдущую программу, чтобы рассмотреть цикл while, управляемый не счетчиком, а меткой. В отличии от счетчика, когда количество повторений заранее известно, количество итераций цикла, управляемого меткой, заранее неизвестно. Т.е. мы можем использовать баллы скольких угодно студентов, пока не будет окончен ввод.
В данном варианте этого алгоритма, в котором цикл while управляется меткой (ввод продолжается, пока метка не будет равной -1), студенты могут вводить сколь угодно своих оценок, пока не будет введена метка окончания ввода "-1". Плюс в этой программе есть еще одно нововведение: теперь средний балл будет более точным, т.к. для его хранения мы объявили переменную average типа float (float - тип для хранения дробных чисел с точностью 6 - 7 знаков после запятой, в отличии от double, у которого 13 - 14 знаков).
(Еще раз небольшое отступление). Разберем по ходу еще один новый для вас момент:
В этой строке реализовано приведение типов. Что это такое и для чего служит? Мы объявили переменную average как float, но переменные total и counter у нас объявлены как int, а значит после операции деления, в случае, если получиться дробное число, дробная часть будет отброшена (потеряна). Для того, чтобы избежать потери нужно, чтобы делимое total было тоже типа float, а так как мы его не объявили изначально типа float, то приведем его сейчас к float.
3. Теперь рассмотрим пример использования цикла while с постусловием. Запрограммируем решение вот такой задачи:
Одна большая химическая компания платит своим продавцам на основе комисионных. Продавец получает $200 в неделю плюс 9% от объема продаж за неделю. Например, продавец, который продал за неделю химикалий на $5000 получит $200 плюс 9% от $5000, то есть в итоге $650. Нужно разработать программу, которая будет вводить для каждого продавца его объем продаж за последнюю неделю, рассчитывать и выводить на экран его заработок. Данные должны вводиться поочередно для каждого продавца.
Приступим к программированию. Вот такая программа будет выполнять поставленную задачу:
Результат работы программы:
4. Цикл for. Решим вот такую вот задачу:
Программа последовательно запрашивает у пользователя десять чисел и находит максимальное из них. Выводит результат на экран.
Сравнение цикличных структур
Блок-схемы повторяющихся алгоритмов позволяют оценить подобие всех 3 видов:
- обязательное наличие условия (для оператора с параметром – это число повторений);
- серия однотипных команд/шагов.
В сложных задачах алгоритм выполнения может содержать любые виды алгоритмических конструкций, в том числе разветвляющиеся циклические алгоритмы.
Хотя все алгоритмы циклической структуры описывают повторяющиеся шаги, у них много отличий.
Что мы делаем ежедневно? Думаю, у каждого из нас свой список дел. Однако раз за разом повторяются одни и те же операции для достижения одних и тех же целей. Это и есть цикл. В программировании циклы используются при обработке множеств / файлов или же для вычисления математических выражений.
Выделяют несколько видов циклов:
- while … do (с предусловием );
- do … while (с постусловием);
- for (с параметром)
Может использоваться в ситуациях, когда до входа в цикл известно количество итераций (повторений цикла). Имеет следующий вид:
- Инициализация — установка начальных параметров счетчика;
- Условие — условие выхода из цикла, как только оно вернет ложь — произойдет выход из цикла;
- Порядок выполнения — команда увеличения счетчика.
Действия, выполняемые циклически, называются телом цикла. Рассмотрим наиболее общий пример: поиск факториала числа. Факториал числа вычисляется по формуле:
Как вы видите, мы заранее знаем, сколько раз должно повториться тело цикла, потому можем использовать счетчик.
Итак, пользователь вводит любое число. После чего, мы вычисляем факториал по вышеуказанной формуле. Начальное значение факториала необходимо установить в единицу. Цикл начинаем с двойки и повторяем до тех пор, пока счетчик меньше или равен введенному пользователем значению. Если использовать оператор «меньше», мы потеряем умножение на старшее число при вычислении факториала. Порядок выполнения указан как i++, это значит, что на каждой итерации цикла счетчик i увеличивается на единицу. В виде порядка управления может выступать и более сложная математическая формула.
В данном случае действия цикла повторяются до тех пор, пока выполняется указанное условие. Этот цикл функционирует по принципу: «Сперва думаем, после делаем». В общем виде выглядит так:
Рассмотрим пример вычисления факториала при помощи while.
Чтобы не получить бесконечного цикла, необходимо изменять параметр, проверяемый в условии. Именно для этого мы увеличиваем i.
Этот вид цикла подобен while, с той лишь разницей, что проверка условия производится после выполнения тела цикла.
И снова рассмотрим вычисление факториала.
Допустим, мы имеем массив значений, не важно каких: числа, строки, символы… Для перебора массива удобно использовать этот вид цикла. Выглядит он следующим образом:
Предположим, у нас есть список городов, и нужно найти все города, начинающиеся с заданного символа.
Пользователь вводит символ, после чего для каждого элемента массива проверяется, начинается ли он с заданного символа. И, если условие выполняется, элемент массива запоминается в результирующей строке. Главным плюсом foreach является то, что он исключает возможность выхода за границы массива.
Следующие шаги
Возможно, лучший совет, что я могу напоследок дать новичкам-разработчикам FPGA, — это изучать HDL, параллельно практикуясь на реальном оборудовании, а не на одних лишь симуляторах. Инструменты, связанные с реальными аппаратными компонентами, позволят вам проверять код и необходимые тайминги. Кроме того, разрабатывать схемы для быстрых тактов — хорошо, но в аппаратном проектировании на этом свет клином не сошёлся.
Помните, аппаратная архитектура по своей природе параллельная. Всё начинается с такта.
Представьте себе клетчатое поле (как лист из тетради в клеточку) на котором находится некий объект, который мы назовем Робот. Используя специальные команды, мы можем этим Роботом управлять — перемещать его по клеткам, закрашивать клетки. И в большинстве случаев наша задача будет заключаться в том, чтобы написать такую программу для Робота, выполняя которую он будет закрашивать определенные клетки.
Запущенная программа Кумир выглядит так.
Первым делом мы должны раскомментировать первую строку нашей программы, убрав символ |
Таким образом, программа станет выглядеть так:
использовать Робот
алг
нач
кон
Удалив символ |, мы тем самым указали Кумиру на то, что будем работать с исполнителем Робот. Если этого не сделать, то при написании программы мы столкнемся с ошибкой «Нет такого алгоритма». Поэтому очень важно при создании новой программы раскомментировать первую строку. Теперь все готово для дальнейшей работы.
Но перед началом, нам необходимо задать стартовую обстановку Робота и познакомиться с простыми командами исполнителя Робот.
Стартовая обстановка Робота
Перед началом выполнения программы необходимо задать исполнителю Робот стартовую обстановку . Это значит установить Робота в нужную позицию, расставить стены, закрасить нужные клетки и т. п. Этот шаг очень важен. Если его проигнорировать, то программа может работать неправильно или вообще завершится аварийно.
Цикл с параметром
Используется для задач, в которых известно количество повторений однотипных шагов, то есть заранее известно, сколько раз нужно выполнить действия. Параметр в этой процедуре– количество повторений цикла(счетчик повторов).
Особенность алгоритмической конструкции повторение с параметром – не бывает зацикливаний, ведь после выполнений указанного числа повторов процесс остановится.
Циклы с известным числом повторений вокруг нас: прием курса лекарств, расписание уроков на неделю, посадка известного числа саженцев, поклейка определенного числа полос обоев.
Пример: написать алгоритм разгрузки и переноса 15 мониторов из авто в компьютерный класс.
Читайте также: