Билет № 1 (стр. 7 )

Рассмотрим частный случай этой игры. Имеется 15 предметов. Соперники ходят по очереди, за каждый ход любой из играющих может взять 1, 2 или 3 предмета. Проигрывает тот, кто вынужден взять последний предмет.

Алгоритм выигрыша для первого игрока имеет следующий вид:

взять два предмета;

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

Данный алгоритм приводит к выигрышу для 7, 11, 15, 19, ... предметов.

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

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

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

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

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

Билет № 14 Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых (т. е. основных) элементов. Логическая структура любого алгоритма может быть представлена комбинацией (суперпозицией) четырех базовых структур: следование, ветвление, цикл, подпрограмма. Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.

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

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

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

Итак, с понятием величины связаны следующие характеристики (атрибуты):

имя – это ее обозначение и место в памяти;

тип – множество допустимых значений и множество применимых операций к ней, объем занимаемой памяти и способ представления в памяти ЭВМ:

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

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

Переменной называется величина, значение которой меняется в процессе исполнения алгоритма.

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

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

В общем виде оператор присваивания можно записать так:

<переменная> <знак команды присваивания> <выражение>

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

Свойства присваивания:

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

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

Различают выражения арифметические, логические и строковые.

Арифметические выражения служат для определения одного числового значения.

Например, (1+sin x)/2. Значение этого выражения при х=0 равно 0,5.

Логическое выражение может принимать только два значения – "истина" или "ложь" {"да" или "нет"). Например, логическое выражение х∙х+у∙у<r∙r определяет принадлежность точки с координатами (х, у) внутренней области круга радиусом r с центром в начале координат. При х=4, у=–2, r=5 значение этого выражения – "истина", а при х=6, у=2, r=5 – "ложь".

Строковые (литерные) выражения, значениями которых являются последовательности символов. В строковые выражения могут входить литерные и строковые константы, литерные и строковые переменные, литерные функции, разделенные знаками операции сцепления. Например, А+В означает присоединение строки В к концу строки A. Если А="Мама мыла", а В="раму.", то значение выражения А+В есть "Мама мыла раму.".

Пример 1. Пешеход шел по пересеченной местности. Его скорость движения по равнине – v1 км/ч, в гору – v2 км/ч и под гору – v3 км/ч. Время движения соответственно t1, t2 и t3 ч. Какой путь прошел пешеход?

Составим алгоритм решения этой задачи (команда присваивания здесь обозначена знаком ":="):

1.  Ввести v1, v2, v3, t1, t2, t3

2.  S1=v1*t1.

3.  S2=v2*t2.

4.  S3=v3*t3.

5.  S=S1+S2+S3.

6.  Вывести значение S.

7.  Конец.

Для проверки работоспособности алгоритма необходимо задать значения входных переменных, вычислить конечный результат по алгоритму и сравнить с результатом ручного счета. В разработанном алгоритме v1, v2, v3, t1, t2, t3 – аргументы, S – результат, S1, S2, S3 – промежуточные величины.

Билет №15 1.Алгоритмическая структура "ветвление". Команда ветвления. Примеры полного и неполного ветвления.

При составлении алгоритмов решения разнообразных задач часто бывает необходимо обусловить те или иные предписания, т. е. поставить их выполнение в зависимость от результата, который достигается на определенном шаге исполнения алгоритма. Например, алгоритм нахождения корней квадратного уравнения с помощью компьютера должен содержать проверку знака дискриминанта. Лишь в том случае, когда дискриминант положителен или равен нулю, можно проводить вычисление корней. Алгоритм перемещения в заданный пункт по улицам города обязательно должен содержать предписание проверки сигналов светофоров на пересечениях улиц, поскольку они обусловливают движение на перекрестках. Можно привести еще много примеров подобных ситуаций, которые не имеют решения в рамках структуры "следование" (линейная алгоритмическая конструкция). По этой причине в теории алгоритмов наряду со "следованием" предлагается вторая базовая структура, называемая "ветвление". Эта структура предполагает формулировку и предварительную проверку условий с последующим выполнением тех или иных действий, реализуя альтернативный выбор. В словесной форме представления алгоритма "ветвление" реализуется в виде команды: если <ЛВ> то <Серия 1> Иначе <Серия2> Здесь <ЛВ> – это логическое выражение, <Серия1> – описание последовательности действий, которые должны выполняться, когда <ЛВ> принимает значение ИСТИНА, <Серия2> – описание последовательности действий, которые должны выполняться, когда <ЛВ> принимает значение ЛОЖЬ. Любая из серий может быть пустой. В этом случае ветвление называется неполным. Каждая серия может, в свою очередь, содержать команду ветвления, что позволяет реализовать не только альтернативный выбор действий. Если для представления алгоритма используется блок-схема, структура "ветвление" изображается так: Полное ветвление Неполное ветвление В языке программирования Basic структура ветвления изображается оператором: IF (если) <ЛВ> THEN (то, тогда) <Блок1> ELSE (иначе) <Блок2>; Здесь <Блок1> и <Блок2> – последовательности операторов языка Basic. В данном случае представлен полный условный оператор, если ELSE отсутствует, то это неполный условный оператор. Рассмотрим пример использования структуры "ветвление". Одной из типичных задач информатики является задача сортировки: упорядочения по возрастанию или убыванию величин порядкового типа. Составим алгоритм и программу сортировки списка из двух фамилий, используя неполное ветвление. Алгоритм решения задачи представлен на блок-схеме. Program Sort; DEFSTR X, Y, С ·    Input "Введите две фамилии",X, Y IF X>Y THEN С=X: X=Y: Y=С PRINT "После сортировки"; X, Y Рассмотрим теперь в качестве примера использования полного ветвления алгоритм и программу вычисления отношения двух чисел с блокировкой деления на ноль и выводом соответствующего сообщения на экран монитора. Алгоритм решения задачи представлен на блок-схеме. ·  DEFDBL А, В,С ·    INPUT "Введи 2 числа";A, B IF В<>0 THEN С=А/В: PRINT C  ELSE PRINT "ДЕЛЕНИЕ НА 0"

Вложенный условный оператор

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

Пример. Даны целые числа а, b, с. Если а<b<с, то все числа заменить их квадратами, если а>b>с, то каждое число заменить наименьшим из них, в противном случае сменить знак каждого числа.

Решение. Условие задачи перепишем следующим образом:

а=а^2, b:=b^2, c:=c^2, если а≤ b≤ с а:=с, b:=с, если а>b>с а:=–а, b:=–b, с:=–с – в остальных случаях.

DEFINT a, b,c

·   

INPUT "Введите числа а, b, с"; a, b,c If (a<=b) and (b<=c) Then a=a^2: b=b^2: c=c^2 Else If (a>b) and (b>c) Then a=c: b=c Else a=–a: b=–b: c:=–c

Билет № 16

1.Алгоритмическая структура "цикл". Циклы со счетчиком и циклы по условию.

Достаточно часто при организации алгоритма решения задачи необходимо одну и ту же определенную последовательность команд выполнить несколько раз подряд. Конечно, самый простой способ – записать эти команды несколько раз друг за другом, и необходимое повторение действий будет организовано. Но как быть в тех случаях, когда количество команд, которые исполняются несколько раз, слишком велико? Или само количество повторений команд огромно? Или вообще неизвестно, а сколько же раз нужно повторить последовательность команд? Решить все эти проблемы можно, если использовать алгоритмическую структуру цикл. Командой повторения, или циклом, называется такая форма организации действий в алгоритме, при которой выполнение одной и той же последовательности команд повторяется до тех пор, пока истинно некоторое логическое выражение. Для организации цикла необходимо выполнять следующие действия: перед началом цикла задать начальное значение параметров (переменных, используемых в логическом выражении, отвечающем за продолжение или завершение цикла); внутри цикла изменять переменную (или переменные), которая сменит значение логического выражения, за счет которого продолжается цикл, на противоположное (для того, чтобы цикл в определенный момент завершился); вычислять логическое выражение – проверять условие продолжения или окончания цикла; выполнять операторы внутри цикла; управлять циклом, т. е. переходить к его началу, если он не закончен, или выходить из цикла в противном случае. Различают циклы с известным числом повторений (цикл с параметром) и итерационные (с пред - и постусловием). Приведем обозначение каждого из видов циклов на блок-схемах алгоритмов. На схемах "Серия" обозначает один или несколько любых операторов (команд); ЛВ есть логическое выражение (если его значение истина, переход происходит по ветви, обозначенной да, иначе – по нет). На схеме цикла с параметром использованы обозначения: ПЦ – параметр цикла, НЗ – начальное значение параметра цикла, КЗ – конечное значение параметра цикла, Ш – шаг изменения параметра цикла. Серию команд, которые выполняются в цикле, называют телом цикла. Опишем схематично, как выполняется каждый из циклов. Цикл с предусловием: вычисляется значение логического выражения; если значение логического выражения истина, переход к следующему пункту, иначе к п. 5); выполняется тело цикла; переход к п. 1); конец цикла. Цикл с постусловием: выполняется тело цикла; вычисляется значение логического выражения; если значение логического выражения ложь, переход к п. 1), иначе к следующему пункту; конец цикла. Замечание. Таким образом, цикл с постусловием организован, в частности, в алгоритмических языках Паскаль и QBasic. В языке Си переход к повторению вычислений, как и в цикле с предусловием, осуществляется в случае истинности логического выражения. Цикл с параметром: вычисляются значения выражений, определяющие начальное и конечное значения параметра цикла; параметру цикла присваивается начальное значение; параметр цикла сравнивается с конечным значением; если параметр цикла превосходит (при положительном шаге) конечное значение параметра цикла (или, наоборот, меньше конечного значения параметра цикла при отрицательном шаге), переход к п. 8), иначе к следующему пункту; выполняется тело цикла; параметр цикла автоматически изменяется на значение шага; переход к п. 3); конец цикла. Циклы с предусловием и постусловием в большинстве случаев (за исключением отдельных реализаций алгоритмических языков) являются более универсальными по сравнению с циклом с параметром, поскольку в последнем требуется заранее указать число повторений, в то время как в первых двух это не требуется. Цикл с параметром в любом случае может быть преобразован к циклу с пред - или постусловием. Обратное верно не всегда. Рассмотрим примеры задач, при решении которых необходим цикл. Пример 1. Подсчитать количество нечетных цифр в записи натурального числа n. Идея решения. Из заданного числа необходимо выбирать из младшего разряда цифру за цифрой (отбрасывая просмотренную) до тех пор, пока число не исчерпается, т. е. станет равным нулю. Каждую нечетную цифру учитывать. Задача решена двумя способами. Первое решение оформлено с использованием цикла с предусловием, второе – с постусловием (\ и mod обозначают операции вычисления частного и остатка при делении нацело). Первый способ (цикл с предусловием): Ввести число n. К:=0 (подготавливаем счетчик). Если n=0, переход к п. 7. Если n mod 10 mod 2=1, то К:=К+1. n:=n \ 10. Переход к п. 3. Конец.

Билет № 17

1.  Исполнители команд: робот, автомат, человек, компьютер. Компьютер, как формальный исполнитель алгоритмов (программ).