«Ответы на тест Turbo Pascal»
К каждой теме представлены практические задачи, а также тестовые вопросы. Сборник может быть применен в курсах программирования ПРЗ на ЭВМ.
К каждой теме представлены упражнения и задания с их решением и блок-схемой, практические задачи для решения на Turbo Pascal для школьников и студентов, а также тестовые вопросы для проверки усвоенных знаний. Сборник может быть применен в курсах программирования ПРЗ на ЭВМ как в общеобразовательных так и в высших учебных заведениях.
Фрагмент работы
1. Программирование алгоритмов линейных структур
1.Для решения относительно простых задач, в которых не предусмотрен выбор из нескольких возможных альтернатив или циклическое повторение каких-либо операций, предназначены…
а) алгоритмы разветвляющейся структуры;
б) линейные алгоритмы и линейные программы;
в) оба ответа верны.
2. Простейшей алгоритмической структурой является…
а) линейная последовательность операций, которые выполняются по очереди и именно в том порядке, в котором они записаны;
б) последовательность операций, которая состоит из простейших операторов;
в) линейная последовательность операций, в которой возможно только одно разветвление.
3. Из каких блоков состоит алгоритм решения задач линейного программирования?
а) из блока ввода данных, блока вычислений и блока вывода результатов работы программы;
б) из заголовка, за которым следуют раздел объявления переменных и вывод результатов;
в) нет правильного ответа.
4. Какая инструкция ввода коэффициентов квадратного уравнения в переменные a,b и c верна, при условии, что во время работы программы коэффициенты выводились в одной строке?
в) оба ответа верны.
5.Найдите ошибку в тексте следующей программы:
write(‘задайте целое число.’);
а) перед end нельзя ставить точку с запятой;
б) отсутствует слово var в начале;
в) не соответствие типов переменных.
6. Найдите ошибку в тексте следующей программы:
write(‘задайте целое число.’);
а) вместо read набрано readln слово;
б) в операторе write используется имя необъявленной переменной j;
в) оба ответа верны.
7. Найдите ошибку в тексте следующей программы:
а) вместо writeln набрано wirteln;
б) нет точки после слова end в конце программы;
в) оба ответа верны.
8. Пусть в программе объявлены переменные:
Является ли инструкция d:=5.9*h правильной?
а) инструкция верная;
б) ошибка, переменной типа real присваивается значение переменной integer;
в) ошибка, переменной типа integer присваивается значение переменной real.
9. Какие элементы данных могут изменять свое значение в ходе выполнения программы?
10. Как называются слова begin и end в следующей конструкции:
а) начало и конец программы;
б) операторные скобки;
в) составной оператор.
2. Программирование алгоритмов разветвляющейся структуры
1. Условный оператор и оператор выбора реализуют одну из основных алгоритмических структур, а именно
2. Какое значение может принимать логическое выражение типа Boolean?
в) оба ответа верны.
3. В списках значений оператора case допустимыми являются
а) скалярные типы переменных, включая вещественные и исключая целые типы;
б) скалярные типы переменных, включая целые и исключая вещественные типы;
в) вещественные типы переменных, включая целые и исключая скалярные типы.
4. Определите значение следующего выражения
(summa>120) and (summa 10) and (A =L) or (A =L) and (A>=M) and (L =L) and (A 29) and (day =29)) or ((month=1) and (day =6) and (month 5) and (month ’);
какой из следующих условий окончания цикла верно, если выполняется, что цикл завершается, если введено 10 чисел или введено число 0.
8. Сколько раз будут выполняться инструкции между begin и end?
for i:=2 downto k do
9. Чему будет равно значение переменной х после выполнения инструкций?
10. Сколько звездочек будет выведено на экран в результате выполнения инструкций?
for j:=1 to 5 do write(‘*’);
1.Набор однотипных данных, имеющий общее для всех своих элементов имя.
2. К массивам в целом применяются
а) логические отношения равенства (=) и неравенства (<>);
б) другие операции отношения (+, -, *, /);
в) оба ответа верны.
3. Тип “массив” относится к группе
а) порядковых типов;
б) структурных типов;
в) вещественных типов.
4. Как называется процесс перестановки элементов массива с целью упорядочивания их в соответствии с каким-либо критерием?
5. Как называется последовательное сравнение элементов массива с образцом до тех пор, пока не будет найден элемент, равный образцу, или не будут проверены все элементы?
в) простой перебор.
6. Если элементы массива не упорядочены, то какой алгоритм применяется?
б) простой перебор;
в) вывод массива.
7. В основе какого метода сортировки лежит обмен соседних элементов массива?
в) оба ответа верны.
8. Какой алгоритм может использоваться для поиска как в числовых, так и в строковых массивах?
а) бинарный поиск;
в) перебор элементов.
9. Какой метод применяется для поиска в упорядоченных массивах?
а) бинарный поиск;
10. Как называется процесс, в котором выбирается средний (по номеру) элемент упорядоченного массива, и с этим элементом сравнивается образец?
а) бинарный поиск;
в) перебор элементов.
1.Совокупность однотипных элементов, рассматриваемых как единое целое.
2. Какое максимальное число элементов содержат множества?
3. Какие действия могут выполняться с элементами множества?
б) пересечения, объединения и разности;
в) действия могут выполняться только над множеством в целом.
4. Можно ли вводить значения во множественную переменную оператором ввода и выводить оператором вывода?
в) это зависит от выполняемой задачи.
5. Как называется тип элементов, входящих в множество?
6. Верно ли утверждение, что элементы множества не
в) программист сам решает: упорядочить их или нет.
7. Что означает следующая запись?
а) Каждый элемент множества С является элементом либо множества А, либо множества B;
б) Каждый элемент множества С является элементом множества А и В одновременно;
в) Каждый элемент множества С является элементом множества А, но не является элементом множества В.
8. Что означает следующая запись?
а) Каждый элемент множества С является элементом либо множества А, либо множества B;
б) Каждый элемент множества С является элементом множества А и В одновременно;
в) Каждый элемент множества С является элементом множества А, но не является элементом множества В.
9. Что означает следующая запись?
а) Каждый элемент множества С является элементом либо множества А, либо множества B;
б) Каждый элемент множества С является элементом множества А и В одновременно;
в) Каждый элемент множества С является элементом множества А, но не является элементом множества В.
10. Как организовать вывод элементов множества?
а) для вывода на экран элементов множества применяется оператор write;
б) для вывода на экран элементов множества применяется оператор цикла for;
в) через принтер.
Заключение
1.Структурный тип данных, который содержит определенное число элементов (полей) и является смесью разных типов.
2. Какие операции могут выполняться над записями?
а) операции сравнения;
б) операции отношения;
в) нет правильного ответа.
3. Записей с фиксированными частями называют так потому, что
а) в различных ситуациях имеют одинаковую структуру;
б) имеют одинаковую структуру только в одинаковых ситуациях;
в) могут иметь разную структуру в различных ситуациях.
4. Как называются записи, которые в различных ситуациях могут иметь разную структуру?
а) записи с вариантами;
б) переменные записи;
в) записи с фиксированными частями.
5. Что нужно указать, чтобы использовать в программе элемент (поле) переменной записи?
а) имя переменной и имя поля, отделяя имя поля от имени переменной точкой с запятой;
б) имя переменной и имя поля, отделяя имя поля от имени переменной точкой;
в) имя поля и имя переменной, отделяя имя поля от имени переменной точкой с запятой.
6. Какая инструкция позволяет использовать в тексте программы имена полей без указания имени переменной-записи?
7. Какие действия необходимо выполнять, чтобы сохранить запись в файле?
а) надо записать в файл имя переменной-записи;
б) надо каждое поле как отдельную переменную записать в файл;
в) запись автоматически сохраняется в файле, если указать к нему путь.
8. Какой тип могут иметь поля записи?
а) могут быть только записями;
б) любой, кроме записей;
в) любой, в частности сами могут быть записями.
9. Каким образом объявляются записи?
а) в разделе переменных var;
б) с использованием раздела типов type;
в) оба ответа верны.
10. Для чего предназначено уточненное имя?
а) с помощью уточненного имени в программе выполняется обращение к элементу записи;
б) при использовании уточненного имени увеличивается скорость выполнения программы;
в) нет правильного ответа.
1.Сколько видов файлов имеются в Turbo Pascal?
2. Какой вид файлов содержит последовательность символов, организованных в строки?
3. Количество элементов, хранящихся в данный момент в файле.
б) текущая длина;
4. Выберите процедуры, которые применяются только к текстовым файлам.
а) Readln Writeln;
в) Reset Rewrite.
5. Файл с точки зрения программирования на языке Pascal.
а) именованная структура данных, представляющая собой последовательность элементов одного типа;
б) совокупность однотипных элементов, рассматриваемых как единое целое;
в) структурный тип данных, который содержит определенное число элементов.
6. Что делает процедура Assign?
а) открывает файл в режиме замещения существующего;
б) связывает файловую переменную с конкретным файлом;
в) открывает файл в режиме перезаписи.
7. В чем заключается принцип последовательного доступа?
а) для того, чтобы прочитать n-ю запись файла, сначала нужно прочитать (n+1)-ю запись;
б) для того, чтобы прочитать n-ю запись файла, сначала нужно прочитать все предыдущие записи с 1-й по (n-1)-ю запись;
в) для того, чтобы прочитать n-ю запись файла, сначала нужно прочитать (n-1)-ю запись.
8. Какая функция является признаком конца файла?
а) Closе(имя файла);
б) Reset(имя файла);
в) Eof (имя файла).
9. Специальная ячейка памяти, которая хранит адрес элементов файла, предназначенного для текущей обработки.
а) указатель файла;
в) оба ответа верны.
10. Какая из приведенных конструкций записи файла верна?
в) оба ответа верны.
1.Что делает процедура MoveRel(dx,dy)?
а) перемещает указатель в нужную точку экрана;
б) меняет текущий цвет в указанной области экрана;
в) перемещает указатель относительно текущего положения на указанное число точек.
2. Вызовом какой процедуры задается тип линии?
3. Какие координаты имеет левый верхний пиксель?
4. Как выглядит инструкция вызова процедуры, позволяющей начертить прямоугольник внутри рабочей области экрана?
5. К какому типу относится параметр ВерхняяГраница процедуры Bar3D(x1,y1,x2,y2,Глубина,ВрехняяГраница)?
6. Какая из следующих процедур вычерчивает эллиптический сектор?
7. Как называются изображения, которые получаются следующим образом: выводится изображение, через некоторое время оно стирается, затем выводится это же изображение на новом месте?
в) графики функций.
8. Какая процедура используется для вывода текстовой информации?
в) оба ответа верны.
9. С помощью какой процедуры задаются характеристики шрифта?
10. Для чего нужна процедура CloseGraph ?
а) чтобы программа могла выводить на экран графику, нужно инициализировать графический режим работы;
б) перед завершением работы программа, установившая графический режим, должна восстановить алфавитно-цифровой режим работы видеосистемы компьютера;
в) нет правильного ответа.
Тема Программирование алгоритмов линейных структур
Вопрос 1 2 3 4 5 6 7 8 9 10
Ответ б а а в б б в а
Примечания
Есть ответы на все вопросы Форматы: Word
Определение результатов работы исполнителя
Термин «алгоритм», впервые употребленный в современном значении. Лейбницем (1646–1716), является латинизированной формой имени великого персидского математика Мухаммеда бен Муссы аль-Хорезми (ок. 783 – ок. 850). Его книга «Об индийском счете» в XII в. была переведена на латинский язык и пользовалась широкой популярностью не одно столетие. Имя автора европейцы произносили как Алгоритми (Algorithmi), и со временем так стали называть в Европе всю систему десятичной арифметики.
Научное определение алгоритма дал А. Чёрч в 1930 году. В наше время понятие алгоритма является одним из основополагающих понятий вычислительной математики и информатики.
Алгоритм — это точное и полное описание последовательности действий над заданными объектами, позволяющее получить конечный результат.
Можно сказать, что алгоритм решения какой-либо задачи — это последовательность шагов реализации (или нахождения) этого решения, а процесс построения алгоритма (алгоритмизация) — разложение задачи на элементарные действия или операции.
Область математики, известная как теория алгоритмов, посвящена исследованию свойств, способов записи, области применения различных алгоритмов, а также созданию новых алгоритмов. Теория алгоритмов находит широкое применение в различных областях деятельности человека — в технике, производстве, медицине, образовании и т. д. Появление компьютера позволило решать чрезвычайно сложные, трудоемкие задачи.
Определение алгоритма для применения в области информатики нуждается в некотором уточнении. Во-первых, решение задач в информатике всегда связано с преобразованием информации, а значит, исходными данными и результатом работы алгоритма должна быть информация. Это может быть представлено в виде схемы.
Во-вторых, алгоритмы в информатике предназначены для реализации в виде компьютерных программ или для создания некоторой компьютерной технологии. Для выполнения алгоритма требуется конечный объем оперативной памяти и конечное время.
Основные требования, предъявляемые к алгоритмам:
Дискретность (прерывность): алгоритм должен представлять решение задачи в виде последовательности простых (или ранее определенных) этапов (шагов). Каждый шаг алгоритма формулируется в виде инструкций (команд).
Определенность (детерминированность; лат. determinate — определенность, точность): шаги (операции) алгоритма должны допускать однозначную трактовку и быть понятными для исполнителя алгоритма. Это свойство указывает на то, что любое действие в алгоритме должно быть строго определено и описано для каждого случая.
Массовость: алгоритм должен давать решение не только для конкретного набора значений, а для целого класса задач, который определяется диапазоном возможных исходных данных (область применимости алгоритма). Свойство массовости подразумевает использование переменных в качестве исходных данных алгоритма.
Результативность: алгоритм должен давать конкретный результат, т. е. должны быть рассмотрены все возможные ситуации и для каждой из них получен результат. Под результатом может пониматься и сообщение о том, что задача решения не имеет.
Конечность: количество шагов алгоритма должно быть конечным.
Эффективность: количество шагов и сами шаги алгоритма должны быть такими, чтобы решение могло быть найдено за конечное и, более того, приемлемое время.
Для оценки и сравнения алгоритмов существует много критериев. Чаще всего анализ алгоритма (или, как говорят, анализ сложности алгоритма) состоит в оценке временных затрат на решение задачи в зависимости от объема исходных данных. Используются также термины «временная сложность», «трудоемкость» алгоритма. Фактически эта оценка сводится к подсчету количества основных операций в алгоритме, поскольку каждая из них выполняется за заранее известное конечное время. Кроме временной сложности, должна оцениваться также емкостная сложность, т. е. увеличение затрат памяти в зависимости от размера исходных данных. Оценка сложности дает количественный критерий для сравнения алгоритмов, предназначенных для решения одной и той же задачи. Оптимальным (наилучшим) считается алгоритм, который невозможно значительно улучшить в плане временных и емкостных затрат.
Анализом сложности алгоритмов, исследованием классов задач, решаемых с помощью алгоритмов той или иной сложности, и многими другими теоретическими вопросами занимается специальная область информатики.
Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых элементов.
Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур:
- следование — образуется из последовательности действий, следующих одно за другим;
- ветвление (развилка) — обеспечивает в зависимости от результатов проверки условия (ДА или НЕТ) выбор одного из альтернативных путей алгоритма;
- цикл — обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла.
Для описания алгоритмов наиболее распространены следующие методы (языки):
Обычный язык. Изложение алгоритма ведется на обычном языке с разделением на последовательные шаги.
Блок-схемы. Графическое изображение алгоритма с помощью специальных значков-блоков.
Формальные алгоритмические языки (языки программирования). При записи алгоритмов используют строго определенный набор символов и составленных из них специальных зарезервированных слов. Имеют строгие правила построения языковых конструкций.
Псевдокод. Синтез алгоритмического и обычного языков. Элементы некоторого базового алгоритмического языка используются для строгой записи базовых структур алгоритма.
Словесный способ (запись на обычном языке) не имеет широкого распространения, т. к. таких описаний есть ряд недостатков:
- строго не формализуемы;
- достаточно многословны;
- могут допускать неоднозначность толкования отдельных предписаний;
- сложные задачи с анализом условий, с повторяющимися действиями трудно представляются в словесной или словесно-формульной форме.
Графический способ представления информации является более наглядным и компактным по сравнению со словесным. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое графическое представление алгоритма называется блок-схемой. Определенному типу действия (ввод/вывод данных, проверка условия, вычисление выражения, начало и конец алгоритма и т. п.) соответствует определенная геометрическая фигура — блочный символ. Блоки соединяются между собой линиями переходов, которые определяют очередность выполнения действий.
| Название символа | Графическое изображение | Комментарии |
| Пуск/Останов (блоки начала и конца алгоритма) |  |
Указание на начало или конец алгоритма |
| Ввод/Вывод данных (блоки ввода, вывода |  |
Организация ввода/вывода в общем виде |
| Процесс (операторные блоки) |  |
Выполнение вычислительного действия или последовательности действий (можно объединять в один блок), которые изменяют значение, форму представления или размещение данных |
| Условие (условный блок) |  |
Выбор направления выполнения алгоритма. Если условие, записанное внутри ромба, выполняется, то управление передается по стрелке «да», в противном случае — по стрелке «нет». Таким образом, реализуется процесс изменения последовательности вычислений в зависимости от выполнения условия |
| Начало цикла с параметром |  |
Используется для организации циклических конструкций с известным количеством итераций (повторений) и известным шагом изменения параметра цикла. Внутри блока для параметра цикла указываются через запятую его начальное значение, конечное значение и шаг изменения. Цикл, для которого неизвестно количество повторений, записывается с помощью условного и операторных блоков |
| Предопределенный процесс |  |
Используется для указания обращений к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращения к библиотечным подпрограммам |
| Печать сообщений (документ) |  |
Вывод результатов на печать |
При составлении блок-схемы необходимо проверять выполнение следующих условий:
- из каждого прямоугольника и параллелограмма (кроме конца алгоритма) должна выходить только одна стрелка;
- в каждый прямоугольник и параллелограмм (кроме начала алгоритма) должна входить хотя бы одна стрелка;
- в каждый ромб должна входить хотя бы одна стрелка, а выходить из него — две стрелки, помеченные словами «ДА» и «НЕТ».
Псевдокод занимает промежуточное положение между естественным языком и языками программирования. В псевдокоде не приняты строгие синтаксические правила для записи команд, что отличает формальные языки программирования. Однако в псевдокоде есть некоторые конструкции, которые присущи формальным языкам, что облегчает переход от записи алгоритма на псевдокоде к записи алгоритма на языке программирования. Псевдокоды бывают разные. Рассмотрим учебный (школьный) алгоритмический язык АЯ.
Алфавит учебного алгоритмического языка является открытым. В него могут быть введены любые понятные всем символы: русские и латинские буквы, знаки математических операций, знаки отношений, специальные знаки и т. д. Кроме алфавита, в алгоритмической нотации определяются служебные слова, которые являются неделимыми. Служебные слова обычно выделяются жирным шрифтом или подчеркиванием. К служебным словам относятся:
| алг — заголовок алгоритма | нц — начало цикла | знач |
| нач — начало алгоритма | кц — конец цикла | и |
| кон — конец алгоритма | дано | или |
| арг — аргумент | надо | не |
| рез — результат | если | да |
| цел — целый | то | нет |
| сим — символьный | иначе | при |
| лит — литерный | всё | выбор |
| лог — логический | пока | утв |
| вещ — вещественный | для | ввод |
| таб — таблица | от | вывод |
| длин — длина | до |
Общий вид записи алгоритма на псевдокоде:
алг — название алгоритма (аргументы и результаты)
дано — условие применимости алгоритма
надо — цель выполнения алгоритма
нач — описание промежуточных величин
последовательность команд (тело алгоритма)
Часть алгоритма от слова алг до слова нач называется заголовком, а часть, заключенная между словами нач и кон, — телом алгоритма (исполняемой частью алгоритма).
В предложении алг после названия алгоритма в круглых скобках указываются характеристики (арг, рез) и тип значения (цел, вещ, сим, лит или лог) всех входных (аргументы) и выходных (результаты) переменных. При описании массивов (таблиц) используется служебное слово таб, дополненное именем массива и граничными парами по каждому индексу элементов массива.
Команды учебного языка:
1. Оператор присваивания, который обозначается «:=» и служит для вычисления выражений, стоящих справа, и присваивания их значений переменным, указанным в левой части. Например, если переменная а имела значение 5, то после выполнения оператора присваивания а := а + 1, значение переменной а изменится на 6.
2. Операторы ввода/вывода:
ввод (список имен переменных)
вывод (список вывода)
Список вывода может содержать комментарии, которые заключаются в кавычки.
3. Оператор ветвления (с использованием команды если. то… иначе…всё; выбор);
4. Операторы цикла (с использованием команд для, пока, до).
Запись алгоритма на псевдокоде:
Здесь в предложениях дано и надо после знака «|» записаны комментарии. Комментарии можно помещать в конце любой строки, они существенно облегчают понимание алгоритма.
При записи алгоритма в словесной форме, в виде блок-схемы или на псевдокоде допускается произвольное изображение команд. Вместе с тем такая запись позволяет понять человеку суть дела и исполнить алгоритм. Однако алгоритм, предназначенный для исполнения на компьютере, должен быть записан на строго формализованном языке. Такой язык называется языком программирования, а запись алгоритма на этом языке — компьютерной программой.
Для решения одной и той же задачи можно предложить несколько алгоритмов. Алгоритмы составляются с ориентацией на определенного исполнителя алгоритма. У каждого исполнителя имеется свой конечный набор команд, которые для него понятны и исполняемы. Этот набор называется системой команд исполнителя. Пользуясь системой команд, исполнитель может выполнить алгоритм формально, не вникая в содержание поставленной задачи. От исполнителя требуется только строгое выполнение последовательности действий, предусмотренной алгоритмом. Таким образом, в общем случае алгоритм претерпевает изменения по стадиям:
- первая стадия — алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает;
- вторая стадия — алгоритм должен быть представлен в форме, понятной исполнителю алгоритма (вторая стадия может отсутствовать, если исполнять алгоритм будет сам разработчик).
Примеры решения задач
Пример 1. Исполнитель Утроитель может выполнить только две команды, которым присвоены номера:
Первая команда уменьшает число на 1, вторая — увеличивает его втрое.
Написать набор команд (не более пяти) получения из числа 3 числа 16. В ответе указать только номера команд.
Ответ: 13311
Пример 2. Имеется Исполнитель алгоритма, который может передвигаться по числовой оси.
Система команд Исполнителя алгоритма:
1. «Вперед N» (Исполнитель алгоритма делает шаг вперед на N единиц).
2. «Назад M» (Исполнитель алгоритма делает шаг назад на M единиц).
Переменные N и M могут принимать любые целые положительные значения. Известно, что Исполнитель алгоритма выполнил программу из 50 команд, в которой команд «Назад 2» на 12 больше, чем команд «Вперед 3». Других команд в программе не было. Какой одной командой можно заменить эту программу, чтобы Исполнитель алгоритма оказался в той же точке, что и после выполнения программы?
1. Найдем, сколько было команд «Вперед», а сколько «Назад». Учитывая, что общее количество команд равно 50 и что команд «Назад» на 12 больше, чем команд «Вперед». Получим уравнение: x + (x + 12) = 50, где x — количество команд «Вперед». Тогда общее количество команд «Вперед»: x = 19, а количество команд «Назад»: 19 + 12 = 31.
2. Будем вести отсчет от начала числовой оси. Выполнив 19 раз команду «Вперед 3», Исполнитель алгоритма оказался бы на отметке числовой оси 57 (19 * 3 = 57). После выполнения 31 раз команды «Назад 2» (31 * 2 = 62) он оказался бы на отметке –5 (57 – 62 = –5).
3. Все эти команды можно заменить одной — «Назад 5».
Ответ: команда«Назад 5».
Пример 3. Черепашка является исполнителем для создания графических объектов на рабочем поле. При движении Черепашка оставляет след в виде линии. Черепашка может исполнять следующие команды:
| Название команды | Параметр | Действия исполнителя |
| вп | Число шагов | Продвигается в направлении головы на указанное число шагов |
| нд | Число шагов | Продвигается в направлении, противоположном направлению головы на указанное число шагов |
| пр | Число градусов | Поворачивается направо относительно направления, заданного головой черепашки |
| лв | Число градусов | Поворачивается налево относительно направления, заданного головой черепашки |
Для записи повторяющихся действий (цикла) используется команда Повтори. В этой команде два параметра: первый задает количество повторений (итераций), а второй — список команд которые должны повторяться (тело цикла); список заключается в квадратные скобки.
Записать для исполнителя Черепашка алгоритмы:
а) построения квадрата со стороной 100;
б) построения правильного шестиугольника со стороной 50.
в) построения изображения цифры 4, если голова Черепашки смотрит на север.
Ответ: а) Повтори 4 [вп 100 пр 90]; б) Повтори 6 [вп 50 пр 360/6]; в) вп 100; повтори [лв 135 вп 50].
Пример 4. Два игрока играют в следующую игру (это вариант восточной игры). Перед ними лежат три кучки камней, в первой из которых 2, во второй — 3, в третьей — 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в одной из кучек, или добавляет по два камня в каждую из них. Выигрывает игрок, после хода которого либо в одной из кучек становится не менее 15 камней, либо общее число камней в трех кучках становится не менее 25. Кто выиграет при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ следует обосновать.
Решение. Удобнее всего составить таблицу возможных ходов обоих игроков. Заметим, что в каждом случае возможны всего четыре варианта хода. В таблице курсивом выделены случаи, которые сразу же приносят поражение игроку, делающему этот ход (например, когда камней в какой-либо кучке становится больше или равно 8, другой игрок непременно выигрывает следующим ходом, удваивая количество камней в этой кучке). Из таблицы видно, что при безошибочной игре обоих игроков первый всегда выиграет, если первым ходом сделает 4, 5, 6. У второго игрока в этом случае все ходы проигрышные.
| 1-й ход | 2-й ход | |||
| Начало | 1-й игрок | 2-й игрок | 1-й игрок | 2-й игрок |
| 2,3,4 | 4,3,4 | 8,3,4 | выигрыш | |
| 4,6,4 | 8,6,4 | выигрыш | ||
| 4,12,4 | выигрыш | |||
| 4,6,8 | выигрыш | |||
| 6,8,6 | выигрыш | |||
| 4,3,8 | выигрыш | |||
| 6,5,6 | 12,5,6 | выигрыш | ||
| 6,10,6 | выигрыш | |||
| 6,5,12 | выигрыш | |||
| 8,7,8 | выигрыш | |||
| 2,6,4 | 4,6,4 | 8,6,4 | выигрыш | |
| 4,12,4 | выигрыш | |||
| 4,6,8 | выигрыш | |||
| 6,8,6 | выигрыш | |||
| 2,12,4 | выигрыш | |||
| 2,6,8 | выигрыш | |||
| 4,8,6 | выигрыш | |||
| 2,3,8 | выигрыш | |||
| 4,5,6 | 8,5,6 | выигрыш | ||
| 4,10,6 | выигрыш | |||
| 4,5,12 | выигрыш | |||
| 6,7,8 | выигрыш | |||
Пример 5. Записано 7 строк, каждая из которых имеет свой номер. В нулевой строке после номера записана цифра 001. Каждая последующая строка содержит два повторения предыдущей строки и добавленной в конец большой буквы латинского алфавита (первая строка — A, вторая строка — B и т. д.). Ниже приведены первые три строкиєтой записи (в скобках указан номер строки):
Какой символ находится в последней строке на 250-м месте (считая слева направо)?
Примечание. Первые семь букв латинского алфавита: A, B, C, D, E, F, G.
Решение. Найдем длину каждой строки. Длина каждой следующей строки в два раза больше длины предыдущей плюс один символ, длина строк составит:
(6) 1272+1=255 символов.
Так как задано 7 строк, а нумерация начинается с нулевой строки, последняя строка имеет номер 6 и содержит 255 символов. Последний символ в строке — F. Предпоследний элемент — E, далее идут символы D, C, B, A, 1 (по правилу формирования строк). Таким образом, 250-й символ — это 1.
Пример 6. Имеется фрагмент алгоритма, записанный на учебном алгоритмическом языке:
n := Длина(а)
b := Извлечь(а, k)
нц для i от 7 до n – 1
с := Извлечь(а, i)
b := Склеить(b, с)
Здесь переменные а, b, с — строкового типа; переменные n, i — целые.
В алгоритме используются следующие функции:
Длина(х) — возвращает количество символов в строке х. Имеет тип «целое».
Извлечь(х, i) — возвращает i-й символ слева в строке х. Имеет строковый тип.
Склеить(х, у) — возвращает строку, в которой находятся все символы строки х, а затем все символы строки у. Имеет строковый тип.
Какое значение примет переменная b после выполнения этого фрагмента алгоритма, если переменная а имела значение «ВОСКРЕСЕНЬЕ»?
Решение. Находим общее число символов в строке а, получим, что n = 11.
Выполняя команду b := Извлечь(а, k) при k = 2, получим, что b примет значение «О«.
В цикле последовательно, начиная с 7-го символа строки а и заканчивая предпоследним (n – 1), извлекаем символ из строки а и присоединяем к строке b.
В результате получим слово «ОСЕНЬ» (символы с номерами 2 + 7 + 8 + 9 + 10).
Ответ: «ОСЕНЬ«
Пример 7. Леонардо из Пизы, известный как Фибоначчи, был первым из великих математиков Европы позднего Средневековья. Числовой ряд, который называется его именем, получился в результате решения задачи о кроликах, которую Фибоначчи изложил в своей «Книге Абака», написанной в 1202 году. Он выглядит так:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.
В этом ряду каждое следующее число, начиная с третьего, равно сумме двух предыдущих. Составить словесный алгоритм и блок-схему проверки принадлежности введенного числа n ряду Фибоначчи.
Решение. Словесный алгоритм:
- Ввести число n.
- Установить значение первых трех чисел Фибоначчи: 1, 1, 2 (сумма двух предыдущих чисел).
- Пока введенное число n больше очередного числа Фибоначчи, взять два последних числа Фибоначчи и получить из них новое число Фибоначчи.
- Если число Фибоначчи равно введенному n или было введено число n = 1, значит, что было введено число Фибоначчи, в противном случае — введенное число не является числом Фибоначчи.
Приведенный словесный алгоритм в пункте 1, 2 содержит начальные установки, в пункте 3 — цикл с условием, а пункт 4 — это вывод результата работы алгоритма.
F — текущее число ряда Фибоначчи;
F1 и F2 — два предыдущих числа ряда Фибоначчи для числа F;
n — число, для которого требуется определить, является ли оно числом из ряда Фибоначчи.
Использование основных алгоритмических конструкций: следование, ветвление, цикл
Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур: следование, ветвление, цикл.
Базовая структура СЛЕДОВАНИЕ указывает на то, что управление передается последовательно от одного действия к другому.
| Учебный алгоритмический язык | Язык блок-схем |
| действие 1 действие 2 … действие n |
 |
Использование исключительно этой структуры возможно лишь для достаточно простых задач, ход решения которых не меняется в зависимости от конкретных исходных данных и состоит в последовательном выполнении определенных операций.
В качестве примера рассмотрим решение простой задачи.
Пример. Найти y(x) = x2 + 3x + 5, используя только операции умножения и сложения.
Решение. На рис. приводятся два алгоритма, реализующие решение поставленной задачи.
Порядок вычисления y(x) в первом случае — обычный, а во втором — (x + 3) x + 5. Обе формулы эквивалентны, но в первом случае для вычисления необходимо 2 умножения, 2 сложения и 3 переменных (x, y, z), а во втором используются 1 умножение, 2 сложения и 2 переменные (x, y).
Приведенный пример показывает, что даже простые задачи могут решаться с помощью различных вариантов алгоритмов.
Обратите внимание, как в блоке следования используется оператор присваивания.
Операция присваивания — важнейшая операция во всех языках программирования. С помощью присваивания переменные получают новые значения: в левой части инструкции ставится идентификатор величины, а в правой части — выражение, значение которого можно определить.
В операторах присваивания используется либо привычный знак равенства, либо сочетание двоеточия и знака равенства «:=». Поскольку знак присваивания — это не знак равенства, возможны записи вида Х := Х + 1 или А := А – В. Нужно учитывать, что оператор присваивания будет выполняться только в том случае, если значения всех переменных правой части уже определены.
Базовая структура ВЕТВЛЕНИЕ (РАЗВИЛКА) используется в случае, когда выполнение программы может измениться в зависимости от результата проверки условия и пойти двумя разными (альтернативными) путями. Другими словами, условие является некоторым высказыванием (предикатом) и может быть истинным или ложным (принимать значение TRUE или FALSE). Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.
Различают две структуры этого типа — полную и неполную. В случае полной структуры, если условие выполняется (является истинным), вслед за ним выполняется действие 1, иначе — действие 2. В случае неполной структуры, если условие выполняется (является истинным), то вслед за ним выполняется действие 1, иначе ничего не происходит.
Важную роль в операторах ветвления играют содержащиеся в них условия. В простейшем случае условиями служат отношения между величинами. Условия с одним отношением называют простыми условными выражениями, или простыми условиями. В некоторых задачах необходимы более сложные условия, состоящие из нескольких простых, например условие А C) (возможна запись (Х C)). Объединение нескольких простых условий в одно образует составное условное выражение, или составное условие. Составные условия образуются с помощью логических операторов not (отрицание), and (логическое И), or (логическое ИЛИ), хоr (исключающее ИЛИ).
Структура ВЕТВЛЕНИЕ существует в четырех основных вариантах:
если — то (неполная структура);
если — то — иначе (полная структура);
выбор (неполный);
выбор — иначе (полный).
Программирование. Стандартные алгоритмы
Термин «алгоритм», впервые употребленный в современном значении. Лейбницем (1646–1716), является латинизированной формой имени великого персидского математика Мухаммеда бен Муссы аль-Хорезми (ок. 783 – ок. 850). Его книга «Об индийском счете» в XII в. была переведена на латинский язык и пользовалась широкой популярностью не одно столетие. Имя автора европейцы произносили как Алгоритми (Algorithmi), и со временем так стали называть в Европе всю систему десятичной арифметики.
Научное определение алгоритма дал А. Чёрч в 1930 году. В наше время понятие алгоритма является одним из основополагающих понятий вычислительной математики и информатики.
Алгоритм — это точное и полное описание последовательности действий над заданными объектами, позволяющее получить конечный результат.
Можно сказать, что алгоритм решения какой-либо задачи — это последовательность шагов реализации (или нахождения) этого решения, а процесс построения алгоритма (алгоритмизация) — разложение задачи на элементарные действия или операции.
Область математики, известная как теория алгоритмов, посвящена исследованию свойств, способов записи, области применения различных алгоритмов, а также созданию новых алгоритмов. Теория алгоритмов находит широкое применение в различных областях деятельности человека — в технике, производстве, медицине, образовании и т. д. Появление компьютера позволило решать чрезвычайно сложные, трудоемкие задачи.
Определение алгоритма для применения в области информатики нуждается в некотором уточнении. Во-первых, решение задач в информатике всегда связано с преобразованием информации, а значит, исходными данными и результатом работы алгоритма должна быть информация. Это может быть представлено в виде схемы.
Во-вторых, алгоритмы в информатике предназначены для реализации в виде компьютерных программ или для создания некоторой компьютерной технологии. Для выполнения алгоритма требуется конечный объем оперативной памяти и конечное время.
Основные требования, предъявляемые к алгоритмам:
Дискретность (прерывность): алгоритм должен представлять решение задачи в виде последовательности простых (или ранее определенных) этапов (шагов). Каждый шаг алгоритма формулируется в виде инструкций (команд).
Определенность (детерминированность; лат. determinate — определенность, точность): шаги (операции) алгоритма должны допускать однозначную трактовку и быть понятными для исполнителя алгоритма. Это свойство указывает на то, что любое действие в алгоритме должно быть строго определено и описано для каждого случая.
Массовость: алгоритм должен давать решение не только для конкретного набора значений, а для целого класса задач, который определяется диапазоном возможных исходных данных (область применимости алгоритма). Свойство массовости подразумевает использование переменных в качестве исходных данных алгоритма.
Результативность: алгоритм должен давать конкретный результат, т. е. должны быть рассмотрены все возможные ситуации и для каждой из них получен результат. Под результатом может пониматься и сообщение о том, что задача решения не имеет.
Конечность: количество шагов алгоритма должно быть конечным.
Эффективность: количество шагов и сами шаги алгоритма должны быть такими, чтобы решение могло быть найдено за конечное и, более того, приемлемое время.
Для оценки и сравнения алгоритмов существует много критериев. Чаще всего анализ алгоритма (или, как говорят, анализ сложности алгоритма) состоит в оценке временных затрат на решение задачи в зависимости от объема исходных данных. Используются также термины «временная сложность», «трудоемкость» алгоритма. Фактически эта оценка сводится к подсчету количества основных операций в алгоритме, поскольку каждая из них выполняется за заранее известное конечное время. Кроме временной сложности, должна оцениваться также емкостная сложность, т. е. увеличение затрат памяти в зависимости от размера исходных данных. Оценка сложности дает количественный критерий для сравнения алгоритмов, предназначенных для решения одной и той же задачи. Оптимальным (наилучшим) считается алгоритм, который невозможно значительно улучшить в плане временных и емкостных затрат.
Анализом сложности алгоритмов, исследованием классов задач, решаемых с помощью алгоритмов той или иной сложности, и многими другими теоретическими вопросами занимается специальная область информатики.
Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых элементов.
Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур:
- следование — образуется из последовательности действий, следующих одно за другим;
- ветвление (развилка) — обеспечивает в зависимости от результатов проверки условия (ДА или НЕТ) выбор одного из альтернативных путей алгоритма;
- цикл — обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла.
Для описания алгоритмов наиболее распространены следующие методы (языки):
Обычный язык. Изложение алгоритма ведется на обычном языке с разделением на последовательные шаги.
Блок-схемы. Графическое изображение алгоритма с помощью специальных значков-блоков.
Формальные алгоритмические языки (языки программирования). При записи алгоритмов используют строго определенный набор символов и составленных из них специальных зарезервированных слов. Имеют строгие правила построения языковых конструкций.
Псевдокод. Синтез алгоритмического и обычного языков. Элементы некоторого базового алгоритмического языка используются для строгой записи базовых структур алгоритма.
Словесный способ (запись на обычном языке) не имеет широкого распространения, т. к. таких описаний есть ряд недостатков:
- строго не формализуемы;
- достаточно многословны;
- могут допускать неоднозначность толкования отдельных предписаний;
- сложные задачи с анализом условий, с повторяющимися действиями трудно представляются в словесной или словесно-формульной форме.
Графический способ представления информации является более наглядным и компактным по сравнению со словесным. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое графическое представление алгоритма называется блок-схемой. Определенному типу действия (ввод/вывод данных, проверка условия, вычисление выражения, начало и конец алгоритма и т. п.) соответствует определенная геометрическая фигура — блочный символ. Блоки соединяются между собой линиями переходов, которые определяют очередность выполнения действий.
| Название символа | Графическое изображение | Комментарии |
| Пуск/Останов (блоки начала и конца алгоритма) | |
Указание на начало или конец алгоритма |
| Ввод/Вывод данных (блоки ввода, вывода | |
Организация ввода/вывода в общем виде |
| Процесс (операторные блоки) | |
Выполнение вычислительного действия или последовательности действий (можно объединять в один блок), которые изменяют значение, форму представления или размещение данных |
| Условие (условный блок) | |
Выбор направления выполнения алгоритма. Если условие, записанное внутри ромба, выполняется, то управление передается по стрелке «да», в противном случае — по стрелке «нет». Таким образом, реализуется процесс изменения последовательности вычислений в зависимости от выполнения условия |
| Начало цикла с параметром | |
Используется для организации циклических конструкций с известным количеством итераций (повторений) и известным шагом изменения параметра цикла. Внутри блока для параметра цикла указываются через запятую его начальное значение, конечное значение и шаг изменения. Цикл, для которого неизвестно количество повторений, записывается с помощью условного и операторных блоков |
| Предопределенный процесс | |
Используется для указания обращений к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращения к библиотечным подпрограммам |
| Печать сообщений (документ) | |
Вывод результатов на печать |
При составлении блок-схемы необходимо проверять выполнение следующих условий:
- из каждого прямоугольника и параллелограмма (кроме конца алгоритма) должна выходить только одна стрелка;
- в каждый прямоугольник и параллелограмм (кроме начала алгоритма) должна входить хотя бы одна стрелка;
- в каждый ромб должна входить хотя бы одна стрелка, а выходить из него — две стрелки, помеченные словами «ДА» и «НЕТ».
Псевдокод занимает промежуточное положение между естественным языком и языками программирования. В псевдокоде не приняты строгие синтаксические правила для записи команд, что отличает формальные языки программирования. Однако в псевдокоде есть некоторые конструкции, которые присущи формальным языкам, что облегчает переход от записи алгоритма на псевдокоде к записи алгоритма на языке программирования. Псевдокоды бывают разные. Рассмотрим учебный (школьный) алгоритмический язык АЯ.
Алфавит учебного алгоритмического языка является открытым. В него могут быть введены любые понятные всем символы: русские и латинские буквы, знаки математических операций, знаки отношений, специальные знаки и т. д. Кроме алфавита, в алгоритмической нотации определяются служебные слова, которые являются неделимыми. Служебные слова обычно выделяются жирным шрифтом или подчеркиванием. К служебным словам относятся:
| алг — заголовок алгоритма | нц — начало цикла | знач |
| нач — начало алгоритма | кц — конец цикла | и |
| кон — конец алгоритма | дано | или |
| арг — аргумент | надо | не |
| рез — результат | если | да |
| цел — целый | то | нет |
| сим — символьный | иначе | при |
| лит — литерный | всё | выбор |
| лог — логический | пока | утв |
| вещ — вещественный | для | ввод |
| таб — таблица | от | вывод |
| длин — длина | до |
Общий вид записи алгоритма на псевдокоде:
алг — название алгоритма (аргументы и результаты)
дано — условие применимости алгоритма
надо — цель выполнения алгоритма
нач — описание промежуточных величин
последовательность команд (тело алгоритма)
Часть алгоритма от слова алг до слова нач называется заголовком, а часть, заключенная между словами нач и кон, — телом алгоритма (исполняемой частью алгоритма).
В предложении алг после названия алгоритма в круглых скобках указываются характеристики (арг, рез) и тип значения (цел, вещ, сим, лит или лог) всех входных (аргументы) и выходных (результаты) переменных. При описании массивов (таблиц) используется служебное слово таб, дополненное именем массива и граничными парами по каждому индексу элементов массива.
Команды учебного языка:
1. Оператор присваивания, который обозначается «:=» и служит для вычисления выражений, стоящих справа, и присваивания их значений переменным, указанным в левой части. Например, если переменная а имела значение 5, то после выполнения оператора присваивания а := а + 1, значение переменной а изменится на 6.
2. Операторы ввода/вывода:
ввод (список имен переменных)
вывод (список вывода)
Список вывода может содержать комментарии, которые заключаются в кавычки.
3. Оператор ветвления (с использованием команды если. то… иначе…всё; выбор);
4. Операторы цикла (с использованием команд для, пока, до).
Запись алгоритма на псевдокоде:
Здесь в предложениях дано и надо после знака «|» записаны комментарии. Комментарии можно помещать в конце любой строки, они существенно облегчают понимание алгоритма.
При записи алгоритма в словесной форме, в виде блок-схемы или на псевдокоде допускается произвольное изображение команд. Вместе с тем такая запись позволяет понять человеку суть дела и исполнить алгоритм. Однако алгоритм, предназначенный для исполнения на компьютере, должен быть записан на строго формализованном языке. Такой язык называется языком программирования, а запись алгоритма на этом языке — компьютерной программой.
Для решения одной и той же задачи можно предложить несколько алгоритмов. Алгоритмы составляются с ориентацией на определенного исполнителя алгоритма. У каждого исполнителя имеется свой конечный набор команд, которые для него понятны и исполняемы. Этот набор называется системой команд исполнителя. Пользуясь системой команд, исполнитель может выполнить алгоритм формально, не вникая в содержание поставленной задачи. От исполнителя требуется только строгое выполнение последовательности действий, предусмотренной алгоритмом. Таким образом, в общем случае алгоритм претерпевает изменения по стадиям:
- первая стадия — алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает;
- вторая стадия — алгоритм должен быть представлен в форме, понятной исполнителю алгоритма (вторая стадия может отсутствовать, если исполнять алгоритм будет сам разработчик).
Примеры решения задач
Пример 1. Исполнитель Утроитель может выполнить только две команды, которым присвоены номера:
Первая команда уменьшает число на 1, вторая — увеличивает его втрое.
Написать набор команд (не более пяти) получения из числа 3 числа 16. В ответе указать только номера команд.
Ответ: 13311
Пример 2. Имеется Исполнитель алгоритма, который может передвигаться по числовой оси.
Система команд Исполнителя алгоритма:
1. «Вперед N» (Исполнитель алгоритма делает шаг вперед на N единиц).
2. «Назад M» (Исполнитель алгоритма делает шаг назад на M единиц).
Переменные N и M могут принимать любые целые положительные значения. Известно, что Исполнитель алгоритма выполнил программу из 50 команд, в которой команд «Назад 2» на 12 больше, чем команд «Вперед 3». Других команд в программе не было. Какой одной командой можно заменить эту программу, чтобы Исполнитель алгоритма оказался в той же точке, что и после выполнения программы?
1. Найдем, сколько было команд «Вперед», а сколько «Назад». Учитывая, что общее количество команд равно 50 и что команд «Назад» на 12 больше, чем команд «Вперед». Получим уравнение: x + (x + 12) = 50, где x — количество команд «Вперед». Тогда общее количество команд «Вперед»: x = 19, а количество команд «Назад»: 19 + 12 = 31.
2. Будем вести отсчет от начала числовой оси. Выполнив 19 раз команду «Вперед 3», Исполнитель алгоритма оказался бы на отметке числовой оси 57 (19 * 3 = 57). После выполнения 31 раз команды «Назад 2» (31 * 2 = 62) он оказался бы на отметке –5 (57 – 62 = –5).
3. Все эти команды можно заменить одной — «Назад 5».
Ответ: команда«Назад 5».
Пример 3. Черепашка является исполнителем для создания графических объектов на рабочем поле. При движении Черепашка оставляет след в виде линии. Черепашка может исполнять следующие команды:
| Название команды | Параметр | Действия исполнителя |
| вп | Число шагов | Продвигается в направлении головы на указанное число шагов |
| нд | Число шагов | Продвигается в направлении, противоположном направлению головы на указанное число шагов |
| пр | Число градусов | Поворачивается направо относительно направления, заданного головой черепашки |
| лв | Число градусов | Поворачивается налево относительно направления, заданного головой черепашки |
Для записи повторяющихся действий (цикла) используется команда Повтори. В этой команде два параметра: первый задает количество повторений (итераций), а второй — список команд которые должны повторяться (тело цикла); список заключается в квадратные скобки.
Записать для исполнителя Черепашка алгоритмы:
а) построения квадрата со стороной 100;
б) построения правильного шестиугольника со стороной 50.
в) построения изображения цифры 4, если голова Черепашки смотрит на север.
Ответ: а) Повтори 4 [вп 100 пр 90]; б) Повтори 6 [вп 50 пр 360/6]; в) вп 100; повтори [лв 135 вп 50].
Пример 4. Два игрока играют в следующую игру (это вариант восточной игры). Перед ними лежат три кучки камней, в первой из которых 2, во второй — 3, в третьей — 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в одной из кучек, или добавляет по два камня в каждую из них. Выигрывает игрок, после хода которого либо в одной из кучек становится не менее 15 камней, либо общее число камней в трех кучках становится не менее 25. Кто выиграет при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ следует обосновать.
Решение. Удобнее всего составить таблицу возможных ходов обоих игроков. Заметим, что в каждом случае возможны всего четыре варианта хода. В таблице курсивом выделены случаи, которые сразу же приносят поражение игроку, делающему этот ход (например, когда камней в какой-либо кучке становится больше или равно 8, другой игрок непременно выигрывает следующим ходом, удваивая количество камней в этой кучке). Из таблицы видно, что при безошибочной игре обоих игроков первый всегда выиграет, если первым ходом сделает 4, 5, 6. У второго игрока в этом случае все ходы проигрышные.
| 1-й ход | 2-й ход | |||
| Начало | 1-й игрок | 2-й игрок | 1-й игрок | 2-й игрок |
| 2,3,4 | 4,3,4 | 8,3,4 | выигрыш | |
| 4,6,4 | 8,6,4 | выигрыш | ||
| 4,12,4 | выигрыш | |||
| 4,6,8 | выигрыш | |||
| 6,8,6 | выигрыш | |||
| 4,3,8 | выигрыш | |||
| 6,5,6 | 12,5,6 | выигрыш | ||
| 6,10,6 | выигрыш | |||
| 6,5,12 | выигрыш | |||
| 8,7,8 | выигрыш | |||
| 2,6,4 | 4,6,4 | 8,6,4 | выигрыш | |
| 4,12,4 | выигрыш | |||
| 4,6,8 | выигрыш | |||
| 6,8,6 | выигрыш | |||
| 2,12,4 | выигрыш | |||
| 2,6,8 | выигрыш | |||
| 4,8,6 | выигрыш | |||
| 2,3,8 | выигрыш | |||
| 4,5,6 | 8,5,6 | выигрыш | ||
| 4,10,6 | выигрыш | |||
| 4,5,12 | выигрыш | |||
| 6,7,8 | выигрыш | |||
Пример 5. Записано 7 строк, каждая из которых имеет свой номер. В нулевой строке после номера записана цифра 001. Каждая последующая строка содержит два повторения предыдущей строки и добавленной в конец большой буквы латинского алфавита (первая строка — A, вторая строка — B и т. д.). Ниже приведены первые три строкиєтой записи (в скобках указан номер строки):
Какой символ находится в последней строке на 250-м месте (считая слева направо)?
Примечание. Первые семь букв латинского алфавита: A, B, C, D, E, F, G.
Решение. Найдем длину каждой строки. Длина каждой следующей строки в два раза больше длины предыдущей плюс один символ, длина строк составит:
(6) 127*2+1=255 символов.
Так как задано 7 строк, а нумерация начинается с нулевой строки, последняя строка имеет номер 6 и содержит 255 символов. Последний символ в строке — F. Предпоследний элемент — E, далее идут символы D, C, B, A, 1 (по правилу формирования строк). Таким образом, 250-й символ — это 1.
Пример 6. Имеется фрагмент алгоритма, записанный на учебном алгоритмическом языке:
n := Длина(а)
b := Извлечь(а, k)
нц для i от 7 до n – 1
с := Извлечь(а, i)
b := Склеить(b, с)
Здесь переменные а, b, с — строкового типа; переменные n, i — целые.
В алгоритме используются следующие функции:
Длина(х) — возвращает количество символов в строке х. Имеет тип «целое».
Извлечь(х, i) — возвращает i-й символ слева в строке х. Имеет строковый тип.
Склеить(х, у) — возвращает строку, в которой находятся все символы строки х, а затем все символы строки у. Имеет строковый тип.
Какое значение примет переменная b после выполнения этого фрагмента алгоритма, если переменная а имела значение «ВОСКРЕСЕНЬЕ»?
Решение. Находим общее число символов в строке а, получим, что n = 11.
Выполняя команду b := Извлечь(а, k) при k = 2, получим, что b примет значение «О«.
В цикле последовательно, начиная с 7-го символа строки а и заканчивая предпоследним (n – 1), извлекаем символ из строки а и присоединяем к строке b.
В результате получим слово «ОСЕНЬ» (символы с номерами 2 + 7 + 8 + 9 + 10).
Ответ: «ОСЕНЬ«
Пример 7. Леонардо из Пизы, известный как Фибоначчи, был первым из великих математиков Европы позднего Средневековья. Числовой ряд, который называется его именем, получился в результате решения задачи о кроликах, которую Фибоначчи изложил в своей «Книге Абака», написанной в 1202 году. Он выглядит так:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.
В этом ряду каждое следующее число, начиная с третьего, равно сумме двух предыдущих. Составить словесный алгоритм и блок-схему проверки принадлежности введенного числа n ряду Фибоначчи.
Решение. Словесный алгоритм:
- Ввести число n.
- Установить значение первых трех чисел Фибоначчи: 1, 1, 2 (сумма двух предыдущих чисел).
- Пока введенное число n больше очередного числа Фибоначчи, взять два последних числа Фибоначчи и получить из них новое число Фибоначчи.
- Если число Фибоначчи равно введенному n или было введено число n = 1, значит, что было введено число Фибоначчи, в противном случае — введенное число не является числом Фибоначчи.
Приведенный словесный алгоритм в пункте 1, 2 содержит начальные установки, в пункте 3 — цикл с условием, а пункт 4 — это вывод результата работы алгоритма.
F — текущее число ряда Фибоначчи;
F1 и F2 — два предыдущих числа ряда Фибоначчи для числа F;
n — число, для которого требуется определить, является ли оно числом из ряда Фибоначчи.
Использование основных алгоритмических конструкций: следование, ветвление, цикл
Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур: следование, ветвление, цикл.
Базовая структура СЛЕДОВАНИЕ указывает на то, что управление передается последовательно от одного действия к другому.
| Учебный алгоритмический язык | Язык блок-схем |
| действие 1 действие 2 … действие n |
|
Использование исключительно этой структуры возможно лишь для достаточно простых задач, ход решения которых не меняется в зависимости от конкретных исходных данных и состоит в последовательном выполнении определенных операций.
В качестве примера рассмотрим решение простой задачи.
Пример. Найти y(x) = x2 + 3x + 5, используя только операции умножения и сложения.
Решение. На рис. приводятся два алгоритма, реализующие решение поставленной задачи.
Порядок вычисления y(x) в первом случае — обычный, а во втором — (x + 3) x + 5. Обе формулы эквивалентны, но в первом случае для вычисления необходимо 2 умножения, 2 сложения и 3 переменных (x, y, z), а во втором используются 1 умножение, 2 сложения и 2 переменные (x, y).
Приведенный пример показывает, что даже простые задачи могут решаться с помощью различных вариантов алгоритмов.
Обратите внимание, как в блоке следования используется оператор присваивания.
Операция присваивания — важнейшая операция во всех языках программирования. С помощью присваивания переменные получают новые значения: в левой части инструкции ставится идентификатор величины, а в правой части — выражение, значение которого можно определить.
В операторах присваивания используется либо привычный знак равенства, либо сочетание двоеточия и знака равенства «:=». Поскольку знак присваивания — это не знак равенства, возможны записи вида Х := Х + 1 или А := А – В. Нужно учитывать, что оператор присваивания будет выполняться только в том случае, если значения всех переменных правой части уже определены.
Базовая структура ВЕТВЛЕНИЕ (РАЗВИЛКА) используется в случае, когда выполнение программы может измениться в зависимости от результата проверки условия и пойти двумя разными (альтернативными) путями. Другими словами, условие является некоторым высказыванием (предикатом) и может быть истинным или ложным (принимать значение TRUE или FALSE). Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.
Различают две структуры этого типа — полную и неполную. В случае полной структуры, если условие выполняется (является истинным), вслед за ним выполняется действие 1, иначе — действие 2. В случае неполной структуры, если условие выполняется (является истинным), то вслед за ним выполняется действие 1, иначе ничего не происходит.
Важную роль в операторах ветвления играют содержащиеся в них условия. В простейшем случае условиями служат отношения между величинами. Условия с одним отношением называют простыми условными выражениями, или простыми условиями. В некоторых задачах необходимы более сложные условия, состоящие из нескольких простых, например условие А < X < С, т. е. Х < А и (Х >C) (возможна запись (Х < А) and (Х >C)). Объединение нескольких простых условий в одно образует составное условное выражение, или составное условие. Составные условия образуются с помощью логических операторов not (отрицание), and (логическое И), or (логическое ИЛИ), хоr (исключающее ИЛИ).
Структура ВЕТВЛЕНИЕ существует в четырех основных вариантах:
если — то (неполная структура);
если — то — иначе (полная структура);
выбор (неполный);
выбор — иначе (полный).
Методологии управления проектами: 12 популярных подходов
Управление проектами — постоянно развивающаяся область, для успешной работы в которой необходимо применять сочетание нескольких подходов. Освоив наиболее популярные методологии, вы сможете стать экспертом в этой области.
Методология управления проектами — это система принципов, техник и процедур, использующихся специалистами, работающими в этой области. Наиболее популярные методы отличаются друг от друга не только своей структурной организацией, но и требуют использования разных конечных результатов, процессов и даже разработки программного обеспечения для управления проектами.
Предлагаем вам ознакомиться с каждым из этих 12 подходов к управлению проектами, чтобы подобрать методологию, которая идеально подойдёт вашей команде и идеальным руководителем проектов.
1. Agile
Что это такое. Методология управления проектами Agile является одним из самых распространённых процессов управления проектами. Однако, по сути, Agile — это не методология как таковая, скорее, это принцип управления проектами.
В основе Agile лежат следующие характеристики:
- Совместная работа
- Скорость и эффективность
- Итеративность и ориентация на данные
- Личность важнее процессов
Когда дело доходит до внедрения Agile, команды часто выбирают определённую методологию, которую они будут использовать наряду с принципами Agile. Это может быть Scrum, Канбан, экстремальное программирование, Crystal или даже Scrumban. Делается это потому, что использование методологии Agile вместе с более подробно сформулированным подходом позволяет сформировать законченную философию управления проектом и практический план для достижения отличных результатов.
Кому подойдёт. Систему Agile может использовать практически любая команда, потому что в её основе лежат довольно универсальные принципы. Самое сложное здесь — решить, какую методологию использовать совместно с этим подходом.
2. Waterfall (Водопад)
Что это такое. Каскадная модель управления, также известная как «водопад», тоже довольно популярна. Но, в отличие от Agile, «водопад» — это настоящая методология с очень чёткими правилами. Каскадная методология, также известная как цикл разработки программного обеспечения (ЦРПО) представляет собой линейный процесс, в котором работа ниспадает каскадом (как водопад) и организована в последовательном порядке.
При использовании этого подхода все рабочие задачи связываются друг с другом зависимостями. Это означает, что для того, чтобы начать работу над задачей, должна быть выполнена предшествующая ей задача. Благодаря этому работа идёт по плану, а также обеспечивается чёткий обмен информацией в течение всего процесса.
Хотя некоторые современные организации считают данный подход устаревшим, эта методология отлично подходит для создания предсказуемого и хорошо продуманного плана проекта.
Кому подойдёт. Поскольку каскадная методология управления является очень подробной, она хорошо подходит для работы над крупными проектами с множеством заинтересованных сторон. Эта модель обеспечивает наличие чёткой информации о необходимых действиях в течение всего проекта и зависимостей, позволяющих отследить работу, которую следует выполнить для достижения целей.
3. Scrum
Что это такое. Методология Scrum предусматривать использование коротких «спринтов», из которых формируется цикл проекта. Эти промежутки длятся от одной до двух недель и рассчитаны на команды в составе не более 10 человек. Это основное отличие от каскадной методологии, где отдельные задачи связываются друг с другом зависимостями.
У Scrum много уникальных особенностей, одной из которых является наличие мастера Scrum или, другими словами, руководителя проекта, который проводит ежедневные Scrum-совещания, демонстрации, спринты и ретроспективы после окончания спринтов. Все эти встречи нужны для общения ключевых участников проекта и своевременного выполнения задач.
Несмотря на то, что технически Scrum является самостоятельной методологией управления проектами, её часто ассоциируют с системой Agile. Связано это с тем, что два эти подхода объединены общими принципами, в том числе принципом важности совместной работы и тем, что личность ценится выше процессов.
Кому подойдёт. Командам, применяющим подход Agile, также следует прибегнуть к методологии Scrum, или, по крайней мере, попробовать её в действии. Так как спринты проводятся для небольших команд, этот подход работает как для небольших, так и для крупных коллективов.
4. Канбан
Что это такое. В методологии Канбан невыполненные задачи в рамках проекта представляются с помощью визуальных элементов, а именно досок. Этот подход используется Agile-командами для эффективной визуализации процессов и хода выполнения проектов, а также снижения вероятности возникновения задержек. Чаще всего для этого используется программное обеспечение, в котором можно легко перетаскивать доски внутри проектов, хотя это и не обязательное требование.
Поскольку, в отличие от других, этот метод не имеет строго определённого процесса, команды используют его по-разному. Здесь нужно понимать, что в Канбан основное внимание уделяется наиболее важным задачам проекта, структура же остаётся довольно простой.
Кому подойдёт. Канбан-доски могут использовать коллективы любых размеров, а особенно этот вариант хорош для удалённых команд. Связано это с тем, что визуальные возможности Канбан-досок позволяют сотрудникам оставаться в курсе происходящего, где бы они ни были.
5. Scrumban
Что это такое. Как вы, возможно, уже догадались, Scrumban — это методология, истоки которой берут своё начало в методах Scrum и Канбан. Кто-то считает её гибридом этих двух подходов, сочетающим в себе лучшие черты обоих систем.
В Scrumban используется такой же цикл со спринтами, как в Scrum, но при этом в план можно вносить отдельные задачи, как в Канбан. Это позволяет выполнять наиболее важную работу, не усложняя при этом планы проектов. В Scrumban также используются встречи по методологии Scrum для улучшения совместной работы и определения приоритетов целей.
Кому подойдёт. Если вам нравится разбивать проекты на более мелкие задачи, но при этом хотите, чтобы визуально они оставались простыми, вам может подойти Scrumban. Этот метод отлично сочетает в себе простоту и ясность.
6. PRINCE2
Что это такое. PRINCE2 расшифровывается как PRojects IN Controlled Environments (проекты в контролируемой среде). В этой методологии каскадная модель используется для определения этапов проекта. Она была разработана правительством Великобритании для реализации ИТ-проектов и до сих пор в основном используется для масштабных ИТ-инициатив, связанных с традиционными продуктовыми или маркетинговыми проектами.
В основе методологии PRINCE2 лежат семь основных принципов, которые охватывают:
- Начало проекта
- Управление проектом
- Инициирование проекта
- Контроль над проектом
- Управление передачей продукта
- Управление границами этапов
- Закрытие проекта
Эти семь принципов образуют всеобъемлющий процесс ведения проекта и эффективную методологию реализации корпоративных проектов. Эта методология нацелена на определение ролей и поддержание процесса управления. Кроме того, PRINCE2 можно использовать для повышения эффективности множества отдельных задач по управлению проектами, в том числе контроль этапов, управление передачей продукта, инициирование и закрытие проекта.
Кому подойдёт. В связи с особенностями методологии управления проектами PRINCE2 она лучше всего подходит для масштабных корпоративных проектов с большим числом заинтересованных сторон. Использование этого метода для небольших проектов может привести к тому, что процессы будут сложнее и продолжительнее, чем это действительно необходимо.
7. Шесть сигм
Что это такое. В отличие от других методологий управления проектами, «Шесть сигм» или Six Sigma используется для управления качеством и часто описывается как философия, а не традиционная методология. Зачастую этот метод применяют в сочетании с системой Lean или подходом Agile и называют Lean Six Sigma и Agile Six Sigma.
Основная цель методологии «Шесть сигм» — постоянное улучшение процессов и устранение недостатков. Достигается это за счёт постоянных улучшений, которые вносят эксперты в своих областях, чтобы определять, поддерживать и контролировать процессы.
Чтобы сделать этот метод ещё эффективнее, можно использовать процесс Six Sigma DMAIC, благодаря которому формируется поэтапный подход. Он состоит из следующих этапов:
- Define — определение. Сформируйте объём проекта, экономическое обоснование и назначьте первую встречу по проекту.
- Measure — измерение. Собирайте данные, по которым можно определить потребность в улучшениях.
- Analyze — анализ. Определите основные причины проблем.
- Improve — улучшение. Устраните выявленные основные причины проблем.
- Control — контроль. Работайте над сохранением этих решений для последующих проектов.
Кому подойдёт. Методология «Шесть сигм» — это отличный вариант для крупных организаций, в штате которых работают сотни сотрудников. На этом уровне потребность выполнять проекты без потерь становится действительно важным фактором для организации.
8. Метод критического пути
Что это такое. Метод критического пути применяется для определения критически важных задач в проекте и планирования работы над ними. Сюда входит создание зависимостей между задачами, отслеживание целей проекта и хода работ над ним, определение приоритета результатов и управление сроками — все это очень похоже на структуру разбивки работ.
Цель этой методологии состоит в надлежащем управлении успешными проектами в масштабе так, чтобы вехи и ожидаемые результаты были размечены правильно.
Кому подойдёт. Метод критического пути лучше всего подходит для небольших и средних проектов и команд. Связано это с тем, что в крупных проектах множество ожидаемых результатов и заинтересованных сторон, а метод критического пути не предназначен для сложных проектов.
9. Управление проектами по методу критического пути
Что это такое. Методология управления проектами по методу критического пути тесно связана с самим методом критического пути, но представляет собой более детализированный и всеобъемлющий подход.
Наряду с использованием структуры разбивки работ, как в методе критического пути, в управлении проектами по этому методу используются определённые временные требования для каждой задачи. Это позволяет эффективнее отслеживать выполнение задач и замечать, когда на них уходит больше времени, чем заложено. В этой методологии также применяется балансирования ресурсов, благодаря чему проблема высокой нагрузки решается с помощью распределения работы по имеющимся ресурсам.
Это помогает не только повысить продуктивность и эффективность, но и связать работу, которую нужно выполнить, с целями проекта. Во многих инструментах для управления проектами даже есть специальные визуальные элементы для отображения связей с целями, что позволяет сформировать для сотрудников организованную дорожную карту.
Кому подойдёт. Управление проектом по методу критического пути подходит командам разного размера, но лучше всего использовать эту методологию для решения проблем с эффективностью проекта. Она также хорошо подходит для создания отчётов о ходе работ для руководства.
10. Методология рационального управления (Lean)
Что это такое. Методология рационального управления проектами нацелена на снижение потерь и создание простой структуры проекта. В конечном итоге это означает возможность делать больше, располагая меньшими ресурсами, с целью повышения эффективности и качества командной работы.
Изначально снижение потерь относилось к физическим продуктам (что отсылает нас к методу, который использовал Генри Форд, а позже компании Toyota и Motorola). Сейчас же речь идёт о расточительных способах выполнения работы. Они представлены тремя буквами М:
- Муда (расточительность). способы работы, которые потребляют ресурсы, но не приводят к созданию ценности
- Мура (неравномерность). Возникает при перепроизводстве и влечёт за собой потери
- Мури (перегрузка): Происходит из-за слишком большой нагрузки на ресурсы
Работа руководителя проекта — предотвращать появление этих ситуаций, чтобы улучшить реализацию проектов и оптимизировать процессы. Этот подход похож на метод рационального унифицированного процесса, который также направлен на снижение потерь. Разница состоит в том, что метод унифицированного процесса направлен на сокращении затрат на разработку, а не количества расточительных способов выполнения работы.
Кому подойдёт. Так как методология рационального управления сосредоточена на сокращении потерь, она лучше всего подойдёт командам, испытывающим проблемы с эффективностью. Хотя она будет иметь наибольший эффект для крупных организаций, пользу от её применения могут получить проектные группы любых размеров.
11. Руководство PMBOK® Института управления проектами
Что это такое. Свод знаний по управлению проектами, разработанный Институтов управления проектами считается методологией, однако это скорее набор практических рекомендаций для различных процессов разработки.
Этот подход основан на пяти этапах управления проектом, каждый из которых помогает с лёгкостью вести проект от начала до конца благодаря структурированному подходу. Вот эти пять этапов:
- Инициирование проекта
- Планирование проекта
- Реализация проекта
- Результативность проекта
- Закрытие проекта
Руководство PMBOK® можно использовать в качества основы при выработке собственного подхода к управлению проектами, поскольку оно не содержит достаточно чётких инструкций. Это означает, что вам нужно будет самостоятельно определять, какие задачи нужно выполнять на каждом из этапов.
Кому подойдёт. Руководство PMBOK® можно использовать самостоятельно для стандартных проектов небольших команд. Для больших же коллективов, работающих над крупными проектами, рекомендуется применять его совместно с более подробной методологией (например, методом критического пути).
12. Экстремальное программирование (XP)
Что это такое. Как можно догадаться по названию, экстремальное программирование используется для динамичных проектов со сжатыми сроками. В рамках этого метода работа ведётся короткими циклами разработки с множеством релизов. За счёт этого достигаются короткие сроки исполнения и повышенная продуктивность.
Методология экстремального программирования имеет свой набор ценностей, в который входят простота, коммуникация, обратная связь, уважение и смелость. В ней также предусмотрен набор определённых правил экстремального программирования, охватывающих все этапы от планирования до тестирования.
Кому подойдёт. Экстремальное программирование можно применять для отдельных проектов со сжатыми сроками, выполняемых, как правило, командами небольшого или среднего размера. Так как этот метод подразумевает высокую скорость работы, его нельзя использовать постоянно, так как это может привести к выгоранию.
Как выбрать правильную методологию управлению проектами для своей команды
Когда речь идёт о методологиях управления проектами, не может быть универсального подхода. Каждая из методологий предлагает уникальные принципы для ведения проекта от начальной стадии до завершения.
Обращать внимание следует, прежде всего, на размер и стиль работы коллектива. Вот ещё несколько факторов, которые необходимо учитывать при выборе:
- Сфера деятельности. Этот момент стоит учитывать, если вы работаете в отрасли, в которой постоянно что-то меняется, что актуально, например, для технологических компаний. Это влияет на последовательность реализации проекта и в зависимости от этого фактора необходимо выбирать гибкую или жёсткую методологию.
- Приоритеты проекта. Учтите также цели вашего проекта. Цените ли вы людей больше, чем эффективность? Это поможет вам найти методологию с похожими приоритетами.
- Сложность проектов. Ваши проекты относительно простые или достаточно сложные? Некоторые методы, например, методология критического пути, не подходят для организации работы над сложными задачами.
- Специализация ролей. Подумайте о том, насколько узкие роли у вас в команде. Могут ли разные участники команды выполнять работу однотипную работу или же вам нужен метод, который будет учитывать их специализацию?
- Размер организации. Размер организации и команды имеет решающее значение при выборе методологии. Такие методы, как Канбан, подходят для любых команд, а, например, метод критического пути лучше подойдёт для небольшой группы.
Независимо от того, предпочитают ли ваши сотрудники визуальные процессы в Канбан или более традиционные подходы к управлению проектами, такие как каскадная модель, правильная методология найдётся для любой команды. Чтобы выбранная система работала ещё эффективнее, попробуйте отслеживать и реализовывать проекты с помощью инструмента для управления проектами.
Методы, которые помогут управлять проектами с умом
Располагая правильной методологией управления проектами, вы сможете повысить эффективность реализации проектов и внедрить процессы, подходящие для команды, организации и вас лично.
Ищете способы повысить эффективность ведения проектов? Попробуйте программное обеспечение для управления проектами Asana.