Вспомогательные алгоритмы. Вспомогательный алгоритм с аргументами для рисования отдельного элемента


Алгоритмы с аргументами - Среда программирования Кумир

Вариант 1

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

2. Составьте программу закрашивания прямоугольника, размеры которого пользователь вводит с клавиатуры. Ввод данных можно осуществлять любым способом.

Вариант 2

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

2. Составьте программу закрашивания квадрата, длину стороны которого пользователь вводит с клавиатуры. Ввод данных можно осуществлять любым способом.

Вариант 3

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

2. Составьте программу рисования фигуры в виде буквы "Г". Вертикальные и горизонтальные размеры пользователь вводит с клавиатуры. Ввод данных можно осуществлять любым способом.

Вариант 4

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

2.Составьте программу рисования фигуры в виде буквы "Т". Вертикальные и горизонтальные размеры пользователь вводит с клавиатуры. Ввод данных можно осуществлять любым способом.

Вариант 5

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

2.Составьте программу рисования фигуры в виде буквы "П". Вертикальные и горизонтальные размеры пользователь вводит с клавиатуры. Ввод данных можно осуществлять любым способом.

Вариант 6

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

2.Составьте программу рисования фигуры в виде буквы "Ш". Вертикальные и горизонтальные размеры пользователь вводит с клавиатуры. Ввод данных можно осуществлять любым способом.

Вариант 7

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

2.Составьте программу рисования фигуры в виде буквы "Н". Вертикальные и горизонтальные размеры пользователь вводит с клавиатуры. Ввод данных можно осуществлять любым способом.

Вариант 8

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

2.Составьте программу рисования фигуры в виде крестика. Вертикальные и горизонтальные размеры пользователь вводит с клавиатуры. Ввод данных можно осуществлять любым способом.

Вариант 9

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

2.Составьте программу рисования фигуры в виде диагонального крестика. Вертикальные и горизонтальные размеры пользователь вводит с клавиатуры. Ввод данных можно осуществлять любым способом.

Вариант 10

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

sites.google.com

Выполнение вспомогательного алгоритма с аргументами

 

Если в основном алгоритме написать вызов "квадрат (4)", то компьютер запомнит, что аргумента равен 4, и при выполнении алгоритма "квадрат (арг веща)" скомандует Чертежнику:

опустить перо

сместиться на вектор (4, 0)

сместиться на вектор (0, 4)

сместиться на вектор (-4, 0)

сместиться на вектор (0, -4)

поднять перо

 

Если же в основном алгоритме написать вызов "квадрат (6)", то компьютер запомнит, что аргумент а равен 6, и скомандует Чертежнику:

 

опустить перо

сместиться на вектор (6, 0)

сместиться на вектор (0, 6)

сместиться на вектор (-6, 0)

сместиться на вектор (0, -6)

поднять перо

 

 

Модель памяти компьютера

 

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

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

Возможный вид памяти при исполнении алгоритма "квадрат" показан на рисунке 44 (здесь

а=4)

 

Рис. 44

 

 

 

Алгоритмы с несколькими аргументами

Алгоритм может иметь несколько аргументов. Рассмотрим пример.

алгпрямоугольник (арг веща, b)

дано| перо Чертежника в левом нижнем углу А будущего

| прямоугольника и поднято

надо| нарисован прямоугольник со сторонами а и b , перо Чертежника

| в точке А и поднято

Нач

опустить перо

сместиться на вектор (а, 0)

сместиться на вектор (0, b)

сместиться на вектор (-а, 0)

сместиться на вектор (0, - b)

поднять перо

Кон

При вызове такого алгоритма важно правильно задать порядок следования аргументов. Соответствие между аргументами в команде вызова и в заголовке алгоритма устанавливается по порядку их следования. На рисунке 45, а показано изображение, полученное при вызове "прямоугольник (3, 7)", а на рисунке 45,б — изображение, полученное при вызове "прямоугольник (7, 3)".

Рис. 45

 

14.5. Аргументы в заголовке цикла n раз

 

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

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

 

алгвлево на (аргцелn)

дано| на поле Робота стен нет

надо| Робот сместился на n клеток влево

нач

нц n раз

| влево

Кц

Кон

Аналогично можно составить алгоритмы "вниз на (арг целn)", "вверх на (арг целn)" и "вправо на (арг целn)". В дальнейшем мы часто будем пользоваться этими алгоритмами как вспомогательными.

Обратите внимание, что без помощи цикла n разалгоритм А40 составить нельзя. Таким образом, применение аргументов открывает новые возможности в использовании этой простой конструкции: цикл n разс аргументом не только сокращает запись, но и позволяет решать задачи, для которых невозможен простой линейный алгоритм.

 

Закрашивание прямоугольника

 

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

 

алгзакрасить прямоугольник (аргцелm, n)

дано| на поле Робота стен нет

надо| закрашен прямоугольник размером m*n, Робот в исходном положении

нач

нцn раз

закрасить ряд (m)

вниз

кц

вверх на (n)

Кон

 

алгзакрасить ряд (арг целm)

дано| на поле Робота стен нет

надо| Робот закрасил m клеток вправо и вернулся в исходное положение

нач

нцm раз

|закрасить; вправо

кц

нц m раз

| влево

Кц

Кон

 

алгвверх на (аргцелn)

дано| на поле Робота стен нет

надо| Робот сместился на n клеток вверх

нач

нц n раз

| вверх

Кц

Кон

 

 



infopedia.su

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

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

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

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

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

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

Задача: Робот находится в левой верхней клетке поля без стен. Нарисовать девять квадратов. Две на две клетки.

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

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

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

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

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

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

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

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

Основной алгоритм

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

Результат работы программы

В блок-схеме вспомогательный алгоритм изображается как показано на рисунке. Этот блок называется «Предопределённый процесс», внутри него записывается название вспомогательного алгоритма, входные и выходные параметры.

Изображение вспомогательного алгоритма на блок-схеме

Задача: У нас есть вспомогательный алгоритм factorial, который вычисляет значение факториала целого числа k. Составить блок-схему алгоритма вычисления значения выражения 1! + 2! + … + n!. Вспомним, что k! = 1 * 2 * … * k.

Блок-схема вспомогательного алгоритма

Изобразим блок-схему данного алгоритма. В ней через i обозначим порядковый номер слагаемого, для него же мы будем вычислять факториал. Через а обозначим значение итого слагаемого, а через r - значение данного выражения. В начале нам нужно считать значение числа n и присвоить r значение 0, т.к. оно ещё не включает ни одного слагаемого, затем будет идти цикл «Для i от 1 до n». В котором мы будем вычислять значение i-того слагаемого, используя вспомогательный алгоритм вычисления факториала, а затем увеличивать на это значение r. И в конце нам нужно вывести значение r.

Блок-схема с использованием вспомогательного алгоритма

Рассмотрим, как работает вспомогательный алгоритм в составе основного. В начале выполняются команды основного алгоритма, идущие до вызова вспомогательного. Затем, когда доходит до выполнения вспомогательного алгоритма, его формальные параметры, в нашем случае k, заменяются параметрами из основного алгоритма. В нашем случае i. Далее выполняются команды вспомогательного алгоритма. Затем значения выходных параметров вспомогательного алгоритма, в нашем случае f подставляются в основной алгоритм, в нашем случае в переменную a. После чего далее выполняются команды основного алгоритма.

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

Мы можем составить вспомогательный алгоритм для вычисления факториала, с использованием рекурсии, если примем во внимание формулу: n! = (n - 1)!. Важно при этом помнить, что 1! = 1. Блок-схема данного алгоритма будет выглядеть так.

Блок-схема рекурсивного алгоритма вычисления n!

Обратим внимание, что вспомогательный алгоритм содержит ветвление, при котором, если n > 1 – n! = (n - 1)!, а в случае если n = 1, то n! = 1. Также и в других рекурсивных алгоритмах, ссылка на алгоритм всегда указывается лишь в одной ветви условного оператора, иначе он будет вызывать сам себя бесконечно.

Задача: Робот находится в поле без стен, на определённом расстоянии от левого края. Он должен нарисовать уголок, то есть закрасить все клетки от своего текущего положения до левого края, а потом столько же клеток вниз.

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

Рекурсивный алгоритм рисования уголка

Основной алгоритм будет содержать только одну команду - вызов вспомогательного алгоритма угол. Запустим программу на выполнение. Робот действительно изобразил уголок.

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

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

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

Важно запомнить:

·       Вспомогательным называется алгоритм, который целиком используется в составе другого алгоритма.

·       Рекурсивный алгоритм – это алгоритм, в котором есть ссылка на самого себя.

·       Исполнение рекурсивного алгоритма можно представить в виде стека.

·       Если рекурсию можно заменить циклом – лучше так и поступить.

Мы научились применять вспомогательные и рекурсивные алгоритмы при решении задач.

videouroki.net


Смотрите также