Шпоры по информатике

1.Понятие алгоритма

Алгоритм - точное предписание исполнителю выполнить команды для решения поставленной задачи (АльХарезми).

Требования:

1. отсутствие ошибок

2. однозначность – четкое предписание что и как делать в каждой конкретной ситуации

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

4. результативность – отсутствие зацикливаний.

О программе, выполняющей действия, предписанные алгоритмом, говорят, что она реализует данный алгоритм на ЭВМ.

5. массовость

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

Способы записи:

1. словесная – ориентирована на исполнителя человека. Команды записываются на обычном языке.

«+» – понятность.

« - » - неоднозначность, избыточность, отсутствие наглядности связей.

2. схемы программ – графическое отображение алгоритма согласно утвержденным стандартам (блок схемы). Каждое действие записывается внутри блоков. Блоки соединяются линиями, которые указывают последовательность действий.

Естественная последовательность – сверху вниз и слева направо.

- начало или конец;

- решение, проверка условия;

- процесс;

- ввод / вывод;

- начало и конец цикла с заданным числом повторений

«+» - наглядность.

« - » - большая трудоемкость выполнения.

3. псевдокоды – занимают промежуточное место между естественным и формальным языком. Используют некоторые служебные слова, которые подчеркиваются.

АЛГ – название алгоритма

НАЧ, …, КОН

ДЛЯ i ОТ 1 ДО 100 ВЫП

ЕСЛИ

ТО

ИНАЧЕ

Нц

Кц

4. языки программирования.

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

По синтаксису можно разделить на классы:

• машинные – воспринимаемые аппаратной частью компьютера (машинные коды – двоичная запись).

• машинно – ориентированные – отражают структуру конкретного типа компьютера – ассемблеры.

• алгоритмические – не зависящие от архитектуры компьютера (Pascal, Basic, Фортран). Программы транслируются с языка высокого уровня на машинный.

• процедурно – ориентированные – имеется возможность описания программы как совокупности процедур подпрограмм.

• проблемно – ориентированные – решают определенный класс задач (Prolog).

Классификация алгоритмов:

2. линейные – команды выполняются в естественном порядке, как они записаны – сверх вниз.

3. разветвленные – в этих алгоритмах в зависимости от некоторых условий выполняются те или иные действия.

АЛГ КВУР

Вещ a, b, c, X1, X2, D

Стр Y

НАЧ

D:= b*b-4*a*c

ЕСЛИ

D < 0

ТО

Y:= «нет решений».

ИНАЧЕ

X1:= (-b + sqrt (D)) / 2*a

X2:= (-b - sqrt (D)) / 2*a

ВСЕ

ВЫВОД X1, X2

КОН

-неполное ветвление

- более полное ветвление

1. циклические – для многократно повторяемых действий используют специальную конструкцию – цикл. Команды цикла содержат условия для определения количества повторов. Существует три типа циклов:

• счетчик (с параметром) – когда заранее определено количество повторов.

• с предусловием – сначала проверяется условие. Если оно выполняется, то затем выполняется действие в теле цикла. Если условие не выполняется, то цикл завершается (будет выполняться следующий оператор после цикла).

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

Пример: Сумма 10 чисел

S:= 0

Нц Для i от 1 до 10

S:= S + i

Кц