Теоретические основы алгоритмизации и программирования

Теоретические основы алгоритмизации и программирования Алгоритм. Свойства алгоритма. Способы описания алгоритма Алгоритм – это точное и просто описание последовательности действий для решения данной задачи. Алгоритм содержит несколько шагов, которые должны выполняться в определенной последовательности. Каждый шаг алгоритма может состоять из одной или нескольких простых операция. Например: 1. Достать ключ. 2. Вставить ключ в замочную скважину. 3. Повернуть ключ два раза против часовой стрелки. 4. Вынуть ключ. Представим, что мы поменяли местами второе и третье действия. Мы сможем выполнить и этот алгоритм, но дверь не откроется, т. е. алгоритм станет невыполнимым. Для алгоритма важен не только набор действий, но и то, в каком порядке они выполняются. Понятие алгоритма в информатике является фундаментальным. Свойства алгоритма: • дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых шагов (этапов); • определенность – каждый шаг алгоритма должен быть четким и однозначным. Выполнение алгоритма носит механический характер и не требует никаких дополнительных сведений о решаемой задаче; • результативность – алгоритм должен приводить к решению задачи за конечное число шагов; • массовость – алгоритм решения разрабатывается в общем виде, т. е. он должен быть применим для решения некоторого класса задач, различающихся лишь исходными данными. Способы описания алгоритмов • словесный; • графический; • табличный; • формульный; Способы описания алгоритмов 1. Словесный способ каждый из нас использует ежедневно, пересказывая собеседнику, например, различные инструкции, правила, кулинарный рецепты, т. е. какую-то последовательность, приводящую к конечному результату. 2. Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным. В программировании данный способ предпочтителен, поскольку позволяет с помощью последовательности функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий, представить ход решения той или иной задачи. 3. Табличный способ используется, например, в бухгалтерии при составлении ежегодных отчетов, сводок и т. д. 4. Формульный способ находит свое применение при решении задач из области математики, физики и т. д. Например, при решении квадратного уравнения мы приступаем к нахождению дискриминанта уравнения, а затем, в зависимости от полученного результата, находим корни уравнения по известным всем формулам. Назначение функциональных блоков Начало и конец алгоритма Ввод/вывод данных Начало циклического алгоритма Вычислительная операция Проверка условия (логического выражения) Разрыв соединительных линий на странице Линии потоков Вызов пользовательской функции Вывод на печать Комментарий Основные этапы решения задач 1-й этап. Общая постановка задачи. • На этом этапе описывается содержание задачи, составляется перечень исходных данных. 2-й этап. Разработка математической модели. • Цель этого этапа состоит в установлении формализованных связей между исходными данными и искомыми результатами. Этап заключается в записи расчетных формул или функциональных зависимостей. 3-й этап. Разработка алгоритма. • Этап состоит в описании последовательности действий, в результате которых может быть получено решение задачи. 4-й этап. Разработка программы. • Программа составляется в полном соответствии с разработанным алгоритмом решения задачи. 5-й этап. Отладка программы. • Процесс поиска ошибок в программе и их устранение. 6-й этап. Анализ результатов. • Позволяет принять решение о необходимости внесения изменений в программу, проведении дополнительных расчетов или их окончании. Алфавит языка Python 1. Латинские буквы от a до z и от A до Z. В Python есть различия между прописными и строчными буквами алфавита, например, chislo, CHISLO, Chislo – разные имена переменных. 2. Цифры от 0 до 9. 3. Специальные символы, например +, -, *, /. 4. Зарезервированные (служебные) слова: for, if, class, def и т.д. Идентификаторы и общие правила их написания Для обозначения в программе переменных и постоянных величин используется имена – идентификаторы (identification – установление соответствия объекта некоторому набору символов). Программа на Python представляет собой последовательность инструкций, которые называются операторами. Необходимо учитывать, следующее: • • • • в идентификатор не могут входить пробелы, специальные символы алфавита; идентификатор начинается только с буквы или со знака подчеркивания; идентификатор может состоять из букв, цифр и знака подчеркивания; при написании идентификаторов можно использовать как прописные, так и строчные буквы латинского алфавита; • идентификатор не должен являться зарезервированным словом. Например: summa1 правильно 2delta ошибка Block_35 правильно Nomer.doma ошибка Сумма ошибка Оператор присваивания Изменение значения переменной осуществляется оператором присваивания. Присваивание в Python означает связывание значения с некоторым именем переменной. Действие, выполняемое этим оператором, обозначается знаком «=». Слева от этого знака записывается имя той переменной, которой нужно присвоить новое значение (например, x=). Справа может быть: 1. Число, например x=5. При выполнении оператора x=5 в оперативной памяти по некоторому адресу будет создан объект, получивший значение 5. Затем будет создана переменная x, которой будет присвоен адрес этого объекта. Такой механизм занесения значений в ячейки памяти отличает Python от других языков программирования. Однако в дальнейшем при объяснении материала, связанного с операторами присваивания, мы будем использовать упрощенный вариант и выражаться так: «в ячейку x заносится число 5». 2. Выражение, например, арифметическое x=(3*a)/2 или логическое x=a>1. 3. Другая переменная, например x=a. Операторы выполняются в той последовательности, в которой они записаны в программе. Например, фрагмент программы нахождения среднего арифметического включает операторы: a=5 b=10 s=a+b v=s/2 Возможна запись оператора присваивания в следующем виде: *= оператор – умножение с присваиванием, например, x*=5 идентичен оператору x=x*5. /= оператор – деление с присваиванием, например, x/=5 идентичен оператору x=x/5. %= оператор – остаток от деления с присваиванием, например, x%=5 идентичен оператору x=x%5. += оператор – сложение с присваиванием, например, x+=5 идентичен оператору x=x+5. -= оператор – вычитание с присваиванием, например, x-=5 идентичен оператору x=x-5. Типы данных Типы данных относятся к самым фундаментальным понятием любого языка программирования. Для определения (объявления) переменных, интерпретатору компилятору нужна следующая информация: • имя переменной – по имени осуществляется связь переменной в программе с оперативной памятью компьютера; • тип переменной – позволяет компилятору определить, какого вида информация хранится в переменной; • значение переменной – определяет содержание информации, которая помещается в переменную. В программах, написанных на Python, нет как такого раздела описания переменных. В Python используется так называется динамическая типизация, когда типы данных выясняются во время выполнения программы. Переменная сохраняет ссылку на объект определенного типа, а не сам объект. В момент переприсваивания значения другого типа переменная будет ссылаться на другой объект, при этом изменится и типа переменной. Python будет изменять тип переменной в вашей программе в соответствии с теми данными, которые вы собираетесь «отправить» в ту или иную переменную. Выяснить, на какой тип данных ссылается переменная, поможет функция type, имеющая синтаксис: type(имя переменной) или type(значение) Например, в программе вы можете написать оператор type(a) или type(196228), и если переменная a имела в первом случае, предположим, целочисленный тип, то ответ будет таким: . Во втором случае, очевидно, что 196228 – целое число, поэтому результат будет таким же. Слово int как раз и указывает на принадлежность к целочисленному типу. Целые типы данных. Используются для представления целых чисел. Размер числа ограничен объемом имеющейся оперативной памяти. Как уже было сказано, при вызове функции type, как type(10) результатом будет Над данными целого типа определены следующие арифметические операции: + сложение вычитание * умножение / деление // деление нацело % остаток от целочисленного деления Результат операции % можно вычислить по формуле: a%b=a – (a/b)*b. Ниже приведены результаты выполнения примеров с помощью операция % и //: 36 % 6 = 0 5%2=1 2%5=2 20 // 3 = 6 0%5=0 Вещественные типы данных В языке Python допускается представление вещественных (дробных) значений в форме с плавающей и фиксированной точкой. В форме с фиксированной точкой число представляется последовательностью десятичных цифр со знаком «плюс» или «минус». Например, 7.32; 456.721; 0.015; 192.0; -15.0 Форма с плавающей точкой (экспоненциальный формат) используется для представления очень больших или очень маленьких чисел. В этой форме число записывается в виде: ±𝑚𝐸 ± 𝑝 где m – мантисса числа; E – символ, обозначающий основание десятичной ССЧ; p – порядок (степень) числа; Например: 7.32e+00 4.56721e+02 1.5e-02 1.92e+02 -1.5e+01. За вещественными типами данных закреплен тип float. type(1.5e-02) Результатом функции type будет Строковые типы данных Значениями строковых переменных являются строковые константы (строки). В языке Python объекты строкового типа обозначены как str. type(“Лабораторная работа”) Результатом функции type будет Один из самых популярных операторов в Python – это оператор print, который служит для вывода на экран текста, при этом текст должен быть заключен в двойные кавычки, иначе он работать не будет. print (“Лабораторная ‘Вычисление арифметических выражений’ работа “) print(“Выполнил”, “студент”, “МТУСИ”) print(‘Гуриков Сергей Ростиславович’) print( “”” ___________________________ ___________________________ “”” ) input(“\n\nНажмите ENTER, чтобы выйти”) Строковые типы данных Заключительный в этом коде оператор input позволяет остановить запущенную на выполнение программу, и выводит сообщение “Нажмите ENTER, чтобы выйти”. В данной программной строке используется, так называемая Escape-последовательность, состоящая из обратного слеша и символа n, повторяющаяся несколько раз (\n\n). \n – переводит курсор на следующую строку; \t – равносильно использованию клавиши Tab; \\ – выводит обратный слеш \; \’ – выводит одиночную кавычку; \’’ – выводит двойную кавычку. Конкатенация (соединение) строк в языке Python возможна с помощью символа +. Например: print(“Москва ” + ”2016” \ + “ МТУСИ”) Для того чтобы много раз повторить одну и ту же строку, в языке Python допустимо выполнить операцию умножения над строкой, что показано в следующем примере: print(“МТУСИ”*5). Логические типы данных (Булевский тип) Переменные этого типа могут принимать одно из двух значений: True (Истина) или False (Ложь). Объект логического типа в Python обозначается как bool. Применение функции type к объектам логического типа type(True) или type(False) Вызовет ответ , результатом int(True) будет 1, а int(False) – 0. Над данными логического типа могут выполняться логические операции. Некоторые из них приведенные в табл. 1. Операция Действие Выражение and (коньюнкция) Логическое И A and B or (дизьюнкция) Логическое ИЛИ A or B not (отрицание) Логическое НЕ not A Функции приведения типов • y=bool(объект) – приводит объект к логическому типу. В переменной y будет храниться ссылка на объект логического типа, а не сам объект, хотя до выполнения оператора присваивания переменная у могла содержать ссылку на объект другого типа. Такая же ситуация будет с другими функциями преобразования типов данных; • y=int(объект) – приводит объект к целому типу; • y=float(объект) – приводит объект к вещественному типу; • y=str(объект) – приводит объект к строковому типу; • y=list(последовательность) – преобразует элементы последовательности в список; • y=tuple(последовательность) – преобразует элементы последовательности в кортеж. Комментарии Для лучшего понимания программы в ней часто записывается пояснительный текст – комментарий. Комментарии выполняют несколько важных функций: • делают программу легко читаемой, поясняя смысл отдельных программных строк; • временно отключают фрагменты программы при ее отладке. В языке Python комментарий к программной строке возможен с использованием символа #. Например, # Вычисляется сумма двух чисел sum=a+b Запись математических функций Таблица 2. Общие математические функции модуля Math Функция Запись на Python Действие Sin x Math.sin(x) Возвращает значение функции Sin от числа x Cos x Math.cos(x) Возвращает значение функции Cos от числа x Tg x Math.tan(x) или math.sin(x)/ math.cos(x) Возвращает значение функции Tg от числа x Ctg x math.sin(x)/ math.cos(x) Возвращает значение функции Ctg от числа x 𝑥 Math.abs(x) Возвращает абсолютную величину числа x 𝑒𝑥 Math.exp(x) Возвращает результат возведения числа e в степень x Ln x Math.Loglp(x) Возвращает натуральный логарифм от x+1 √𝑋 Math.sqrt(x) Возвращает результат извлечения квадратного корня числа x 𝐿𝑜𝑔10 𝑥 Math.log(x) Возвращает логарифм числа x по основанию 10 𝐶𝑜𝑠 2 𝑥 Math.cos(x)*math.cos(x) Возвращает результат возведения функции Cos x в квадрат Acos x Math.acos(x) Возвращает значение функции арккосинус от числа x Asin x Math.asin(x) Возвращает значение функции арксинус от числа x Atan x Math.atan(x) Возвращает значение функции арктангенс от числа x Pi Pi Возвращает 3.141592653589793 Degrees(x) Math.degrees(x) Преобразует радианы в градусы Radians(x) Math.radians(x) Преобразует градусы в радианы Floor(x) Math.floor(x) Возвращает значение, округленное до ближайшего меньшего целого Ceil(x) Math.ceil(x) Возвращает значение, округленное до ближайшего большего целого Factorial(x) Math.factorial(x) Возвращает факториал числа. 3!=1*2*3 Запись математических функций Функции для работы с числами Функция Запись на Python Описание Round (x) round(x) Возвращает результат округления числа x до ближайшего меньшего целого значения для чисел с дробной частью меньше 0.5 или результат округления числа x до ближайшего большего целого значения для чисел с дробной частью больше 0.5 Pow (x, y) pow(x,y) другой вариант x**y Возвращает результат возведения числа x в степень y Max (x, y) max(список чисел через запятую Возвращает большее значение из списка чисел Min (x, y) min(список чисел через запятую) Возвращает меньшее значение из списка чисел Sum(x,y) sum(список чисел через запятую) Возвращает сумму значений элементов последовательности Int(объект) int(объект) Преобразует объект (например, строковое значение, дробное значение) в целое число Float(объект) float(объект) Преобразует объект (например, строковое значение, целое значение) в вещественное число Операции отношения Операции отношения представлены в табл. 4. Таблица 4. Операции отношения Операция Описание Операнд1 < Операнд2 Меньше Операнд1 > Операнд2 Больше Операнд1 <= Операнд2 Меньше или равно Операнд1 >= Операнд2 Больше или равно Операнд1 != Операнд2 Не равно Операнд1 == Операнд2 Равно Контрольные вопросы 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. Что называется алгоритмом? Какими свойствами он обладает? Назовите и поясните способы описания алгоритмов. Нарисуйте функциональные блоки, используемые в блок-схемах. Поясните их назначение. Перечислите этапы решения задачи, выполняемые в процессе ее программирования. Что входит в алфавит языка Python? Поясните понятие «идентификатор» и расскажите об общих правилах написания идентификаторов. В чем заключается действие оператора присваивания? Каковы две формы записи дробных чисел? Какова особенность динамической типизации, используемой в языке Python? Дайте характеристику каждого типа данных языка Python. Какие операции определены над данными целого типа? Каково назначение операторов print и input? Приведите примеры использования таких операторов. Какие логические операции могут выполняться над данными логического типа? Назовите функции приведения типов. Приведите примеры. Для каких целей используются комментарии в программах? Как можно закомментировать участок программного кода в Python? Какие инструкции необходимо прописывать в программах, написанных на языке Python, для использования в них математических функций?