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

Скачать 179.44 Kb. Название Алгоритм это конечная последовательность действий, позволяющая по заданным исходным данным получить результат решения задачи Анкор Voprosy_dlya_ekzamena_po_informatike.docx Дата 16.01.2018 Размер 179.44 Kb. Формат файла Имя файла Voprosy_dlya_ekzamena_po_informatike.docx Тип Документы #15406 страница 1 из 4

1   2   3   4 Алгоритм Алгоритм – это конечная последовательность действий, позволяющая по заданным исходным данным получить результат решения задачи. Алгоритм разбивается на шаги. Для каждого шага есть конкретный исполнитель. Исполнитель алгоритма может быть человеком или автоматом. Вид алгоритма зависит от исходных данных. Результат работы алгоритма с одними и теми же исходными данными не зависит от исполнителя. Алгоритм , характеристики и свойства Алгоритм имеет две характеристики. Конечность, или результативность. Алгоритм приводит к получению результата за конечное число шагов.. Однозначность, или определенность. При одинаковых входных данных алгоритм выдает одинаковый результат. Алгоритм также обладает следующими свойствами. Массовость, или универсальность. Алгоритм выдает результат при любых однотипных входных данных. Модульность, или дискретность. Алгоритм можно представить в виде последовательности более элементарных алгоритмов. Проектирование сверху вниз Основной метод создания алгоритмов — проектирование, или программирование, сверху вниз, или пошаговая детализация. Он заключается в разбиении исходной задачи на последовательность нескольких меньших подзадач. Эти подзадачи, в свою очередь, тоже распадаются на подзадачи и т.д. до тех пор, пока не останутся только элементарные алгоритмы. При программировании сверху вниз алгоритмы и данные делятся на относительно независимые части, называемые модулями. Некоторые из модулей являются стандартными и поставляются в составе языков программирования, например, вычисление элементарных математических функций квадратный корень, логарифм, синус и т. д. Главные модули все равно приходится проектировать программистам. Таким образом, алгоритм является деревом модулей: одни модули вызывают другие модули, начиная с самого верхнего первого модуля, называемого корневым модулем, или головной программой. При проектировании сколько-нибудь больших алгоритмов невозможно держать в памяти одновременно детали всех модулей алгоритма. Если модуль составлен правильно, то с ним можно обращаться как с черным ящиком. Принцип черного ящика Принцип черного ящика означает, что не имеет значения, как модуль выполняет свою функцию, какие алгоритмы скрыты у него внутри. Это не важно для остальных модулей алгоритма. Для модулей, которые обращаются к этому модулю, имеет значение только следующее: 1) какова функция модуля, т. е. что он делает; 2) описание входных и выходных данных модуля. Правильное проектирование алгоритмов позволяет абстрагироваться от внутренней структуры модулей и рассматривать при сборке полного алгоритма только функции модулей. Структурное программирование Структурное программирование позволяет проектировать алгоритмы только из трех элементарных алгоритмов. Каждый модуль является иерархией этих элементарных алгоритмов. Алгоритм, состоящий только из этих трех элементарных алгоритмов, присутствующих на всех его уровнях, называется структурным. Основная теорема структурного программирования утверждает, что любой алгоритм можно преобразовать к структурному виду. Тремя элементарными структурными алгоритмами являются следующие. 1. Следование, или цепочка, или составная инструкция. 2. Выбор, или ветвление, или условная инструкция. 3. Цикл, или возврат, или циклическая инструкция. Компилятор, два способа компиляции Компилятор— программа-переводчик с языка программирования в машинные коды, а процесс перевода — это компилирование программы. Комплекс программ, включающий компилятор и другие средства написания программ, называется системой программирования. Возможны два способа компиляции. Первый способ называется трансляциейи заключается в компилировании сразу всей программы в машинные коды. Затем строится выполняемый файл, содержащий эту программу. И только потом программа выполняется путем запуска выполняемого файла. Благодаря трансляции получается более быстрая по времени работы программа, но выполняемый файл имеет большой объем. Кроме того, выполняемый файл запускается только на компьютере того типа, где программа была транслирована. Второй способ. При интерпретациикомпьютер читает программу по одной строке и сразу выполняет эту строку. При интерпретации программу не надо переводить всю сразу в машинные коды, и поэтому она имеет маленький объем, равный объему исходного текста программы. Такая программа запускается на любом компьютере, на котором находится интерпретатор или виртуальная машина. Средства изображения алгоритмов Средства изображения алгоритмов  Основными изобразительными средствами алгоритмов являются следующие способы их записи: словесный; формульно-словесный; блок-схемный; псевдокод; структурные диаграммы; языки программирования. Словесный – содержание этапов вычислений задается на естественном языке в произвольной форме с требуемой детализацией. Рассмотрим пример словесной записи алгоритма. Пусть задан массив чисел. Требуется проверить, все ли числа принадлежат заданному интервалу. Интервал задается границами А и В.  п.1 Берем первое число. На п.2. п.2 Сравниваем: выбранное число принадлежит интервалу; если да, то на п.3, если нет – на п.6. п.3 Все элементы массива просмотрены? Если да, то на п.5, если нет – то на п.4. п.4 Выбираем следующий элемент. На п.2. п.5 Печать сообщения: все элементы принадлежат интервалу. На п.7. п.6 Печать сообщения: не все элементы принадлежат интервалу. На п.7. п.7 Конец. При этом способе отсутствует наглядность вычислительного процесса, т.к. нет достаточной формализации. Линейный алгоритм (следование) Линейный алгоритм (следование) - это такой, в котором все операции выполняются последовательно одна за другой. Действия А и В могут быть: - отдельным оператором; - вызовом с возвратом некоторой процедуры; - другой управляющей структурой.  А В Алгоритмы разветвленной структуры (развилка) Алгоритмы разветвленной структуры (развилка) применяются, когда в зависимости от некоторого условия необходимо выполнить либо одно, либо другое действие Проверка P представляется предикатом, т.е. функцией, задающей логическое выражение или условие, значением которого может быть истина или ложь. Эта структура может быть неполной, когда отсутствует действие, выполняемое при ложном значении логического выражения. Цикл с постусловием Цикл с постусловием Тело цикла всегда выполняется хотя бы один раз. Тело цикла перестает выполняться, как только предикат становится истинным. Цикл с предусловием Цикл (повторение). Цикломв программировании называют повторение одних и тех же действий (шагов). Последовательность действий, которые повторяются в цикле, называют телом цикла. Цикл с параметром Безусловный циклический алгоритм (цикл с параметром) Данные в языке С++ Для решения задачи в любой программе выполняется обработка каких-либо данных. Данные могут быть самых различных типов: целые и вещественные числа, символы, строки, массивы. Данные в языке С++ описываются в начале функции. Типы данных в языке C++ В С++ определены пять основных типов данных: char – символьные, int – целые, float – с плавающей точкой, double – двойной точности, void – без значения (бестиповый). На базе этих типов формируются другие типы. Данные типа char всегда занимают один байт. Как видно из таблицы, базовые типы могут быть расширены с помощью спецификаторов (модификаторов) signed, unsigned, long, short. Следует учитывать, что вещественные числа хранятся в экспоненциальной форме mE±p, где m – мантисса (целое или дробное число с десятичной точкой), p – порядок (целое число). Для того, чтобы перевести число в экспоненциальной форме к обычному представлению с фиксированной точкой, необходимо мантиссу умножить на десять в степени порядок. Примеры -6.42Е+2 = -6.42.102 = -642 -3.2E-6 = -3.2.10-6 =-0.0000032 Арифметические операции Операция Действие Тип операнда Тип результата + Сложение Целый, вещественный Целый, вещественный - Вычитание, унарный минус Целый, вещественный Целый, вещественный * Умножение Целый, вещественный Целый, вещественный / Деление Вещественный Вещественный Операция Действие Тип операнда Тип результата / Целочисленное деление Целый Целый % Остаток от деления Целый Целый - - Декремент, уменьшение на 1 Целый Целый ++ Инкремент, увеличение на 1 Целый Целый Операция Действие Тип операнда Тип результата & "и" Целый Целый | "или" Целый Целый ^ Исключающее "или" Целый Целый Логическое отрицание Целый Целый <<�  Сдвиг влево Целый Целый >>  Сдвиг вправо Целый Целый Операция присваивания Операция присваивания В операторе присваивания  слева всегда стоит имя переменной, а справа – значение, например: a=b; где a – имя переменной или элемента массива, b – выражение, переменная, константа или функция. В результате выполнения оператора a=b переменной а присваивается значение b. Если в операции присваивания встречаются переменные разных типов, происходит преобразование типов. В операции присваивания значение в правой части преобразуется к типу переменной левой части. Множественное присваивание Множественное присваивание – присваивание нескольким переменным одного и того же значения. a=b=c=3.14159/6; Операции увеличения (инкремента) и уменьшения (декремента) Оператор p=p+1; можно записать в префиксной форме ++p; так и в постфиксной p++; Эти формы отличаются при использовании их в выражении. Если знак декремента (инкремента) предшествует операнду, то сначала выполняется увеличение (уменьшение) значения операнда, а затем операнд участвует в выражении. Пример: x=12; y=++x; В результате в y будет храниться число 13. Если знак декремента (инкремента) следует после операнда, то сначала операнд участвует в выражении, а затем выполняется увеличение (уменьшение) значения операнда. Пример: x=12; y=x++; В результате в y будет храниться число 12. Составное присваивание К операторам составного присваивания относятся +=, -=, *=, /=. Оператор x+=p; предназначен для увеличения x на величину p. Оператор x-=p; предназначен для уменьшения x на величину p. Оператор x*=p; предназначен для умножения x на p. Оператор x/=p; предназначен для деления x на p. Операции целочисленной арифметики К операциям целочисленной арифметики относятся: целочисленное деление / остаток от деления  %. При целочисленном делении операция / возвращает целую часть частного (дробная часть отбрасывается), а операция % – остаток от деления. Ниже приведены примеры этих операций 11 % 4 = 3 11 / 4 = 2 7 % 3 = 1 7 / 3 = 2 Операции битовой арифметики Во всех операциях битовой арифметики действия происходят над двоичным представлением целых чисел. К операциям битовой арифметики относятся следующие операции С++. Арифметическое И (&). Оба операнда переводятся в двоичную систему, затем над ними происходит логическое поразрядное умножение операндов по следующим правилам. 1 & 1 = 1        1 & 0 = 0        0 & 1 =0         0 & 0 = 0 #include int main () { int A, B;    A=13;    B=23;    printf("\n%d\n", A & B) } Этот участок программы работает следующим образом. Число А=13 и В=23 переводятся в двоичное представление 0000000000001101 и 0000000000010111. Затем над ними поразрядно выполняется логическое умножение. & 0000000000001101    0000000000010111    0000000000000101 Результат переводится в десятичную систему счисления, в нашем случае будет число 5. Таким образом, 13 & 23 = 5.   1   2   3   4