Алгоритмы

Алгоритмы. Появление алгоритмов связывают с зарождением математики. Более 1000 лет назад (в 825 году) ученый из города Хорезма Абдулла (или Абу Джафар) Мухаммед бен Муса аль-Хорезми создал книгу по математике, в которой описал способы выполнения арифметических действий над многозначными числами. Само слово алгоритм возникло в Европе после перевода на латынь книги этого математика.Алгоритм – описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.Вы постоянно сталкиваетесь с этим понятием в различных сферах деятельности человека (кулинарные книги, инструкции по использованию различных приборов, правила решения математических задач...). Обычно мы выполняем привычные действия не задумываясь, механически. Например, вы хорошо знаете, как открывать ключом дверь. Однако, чтобы научить этому малыша, придется четко разъяснить и сами эти действия и порядок их выполнения:1. Достать ключ из кармана.2. Вставить ключ в замочную скважину.3. Повернуть ключ два раза против часовой стрелки.4. Вынуть ключ.Если вы внимательно оглянитесь вокруг, то обнаружите множество алгоритмов, которые мы с вами постоянно выполняем. Мир алгоритмов очень разнообразен. Несмотря на это, удается выделить общие свойства, которыми обладает любой алгоритм.^ Свойства алгоритмов:1. Дискретность (алгоритм должен состоять из конкретных действий, следующих в определенном порядке);2. Детерминированность (любое действие должно быть строго и недвусмысленно определено в каждом случае);3. Конечность (каждое действие и алгоритм в целом должны иметь возможность завершения);4. Массовость (один и тот же алгоритм можно использовать с разными исходными данными);5. Результативность (отсутствие ошибок, алгоритм должен приводить к правильному результату для всех допустимых входных значениях).Виды алгоритмов:1. Линейный алгоритм (описание действий, которые выполняются однократно в заданном порядке);2. Циклический алгоритм (описание действий, которые должны повторятся указанное число раз или пока не выполнено задание);3. Разветвляющий алгоритм (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий) 4. Вспомогательный алгоритм (алгоритм, который можно использовать в других алгоритмах, указав только его имя). Для более наглядного представления алгоритма широко используется графическая форма - блок-схема, которая составляется из стандартных графических объектов. ^ Вид стандартного графического объекта Назначение Начало алгоритма Конец алгоритма Выполняемое действие (записывается внутри прямоугольника) Условие выполнения действий (записывается внутри ромба) Счетчик кол-во повторов Последовательность выполнения действий. Блок ввода и вывода информации ^ Стадии создания алгоритма:1. Алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает.2. Алгоритм должен быть представлен в форме, понятной тому объекту (в том числе и человеку), который будет выполнять описанные в алгоритме действия.Объект, который будет выполнять алгоритм, обычно называют исполнителем.Идеальными исполнителями являются машины, роботы, компьютеры...Компьютер – автоматический исполнитель алгоритмов.Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой.^ Основы языка Бейсик Для представления алгоритма в виде, понятном компьютеру, служат языки программирования. Сначала разрабатывается алгоритм действий, а потом он записывается на одном из таких языков. В итоге получается текст программы - полное, законченное и детальное описание алгоритма на языке программирования. Затем этот текст программы специальными служебными приложениями, которые называются трансляторами, либо переводится в машинный код (язык нулей и единиц), либо исполняется.Языки программирования - искусственные языки. От естественных они отличаются ограниченным числом "слов", значение которых понятно транслятору, и очень строгими правилами записи команд (операторов).Для написания текста программы можно использовать обычный текстовый редактор (например, Блокнот), а затем с помощью компилятора перевести её в машинный код, т.е. получить исполняемую программу. Но проще и удобнее пользоваться специальными интегрированными средами программирования.Basic (Бейсик) создавался в 60-х годах в качестве учебного языка и очень прост в изучении. По популярности занимает первое место в мире.^ Некоторые операторы языка Basic.REM – оператор комментария. Все что следует после этого оператора до конца строки игнорируется компилятором и предназначено исключительно для человека. Т.е. здесь можно писать что угодно. Удобно использовать комментарий в начале программы для указания её названия и назначения.пример:REM Это комментарий^ CLS - очистить экран. Вся информация, которая была на экране, стирается.PRINT (вывод, печать) – оператор вывода.пример:PRINT "Привет! Меня зовут Саша."^ На экран будет выведено сообщение: Привет! Меня зовут Саша.INPUT (ввод) – оператор ввода. Используется для передачи в программу каких-либо значений.пример:INPUT аНа экране появится приглашение ввести данные (появится знак "?") и компьютер будет ждать их ввода. Для ввода необходимо ввести данные с клавиатуры и нажать ввод (enter).INPUT "Введите число а: ", а^ Компьютер выведет на экран: 'Введите число а:' и будет ждать ввода данных.Под переменной в языках программирования понимают программный объект (число, слово, часть слова, несколько слов, символы), имеющий имя и значение, которое может быть получено и изменено программой.Если "заглянуть" в компьютер, то переменную можно определить так:^ Переменная - это имя физического участка в памяти, в котором в каждый момент времени может быть только одно значение.Переменная - это ячейка в оперативной памяти компьютера для хранения какой-либо информации.Само название "переменная" подразумевает, что содержимое этого участка может изменяться.В качестве имен переменных могут быть латинские буквы с индексами. Причем может быть не одна буква, а несколько.Операторы:Ввода Формат записи:Input A, B, C, DInput “текст”; A, B, C, DПринцип работы: при выполнении данного оператора необходимо ввести числовые значения указанных переменных (A, B, C, D). Для упрощения ввода переменных можно использовать текстовую информацию, которая будет напечатана при выполнении данного оператораПример:Input A1, BН5, CUInput “vvedi 4-e chisla”; A1, BН5, CUВывода:Формат записи:Print A, B, C, DPrint “текст”;Print “текст”; A, B, C, DPrint арифметическое_выражениеПринцип работы: при выполнении данного оператора печатаютсячисловые значения указанных переменных (1-й пример)текстовая информация, расположенная в кавычках (2-й пример)текстовая информация и значения переменных (3-й пример)значение арифметического выражения (4-й пример)Пример:Print Y1, Y2Print “reshenii net”Print “Otvet=”; Y1, Y2Print ABS(2-X*X)Присваивания:Формат записи:LET переменная=арифметическое_выражениеПринцип работы: вначале выполняется арифметическое выражение, стоящее справа от знака присваивания. Затем полученное значение присваивается переменной, стоящей слева от знака присваивания. Пример:Let D=SQR(B*B-4*A*C)D=SQR(B*B-4*A*C)D=D+25Условного перехода:Формат записи:IF условие THEN операторыIF условие THEN операторы ELSE операторыПринцип работы: вначале проверяется условие. Если оно верно (True), то выполняются операторы, стоящие после THEN. В противном случае выполняется следующая строка (1-й пример) или операторы, стоящие после ELSE (2-й пример). Пример:IF D=0 THEN Print “1-n koren”IF DБезусловного перехода:Формат записи:GOTO NN – номер строкиПринцип работы: при выполнении данного оператора управление передается на строку с номером N Пример:30 IF D=0 THEN Print “1-n koren”: GOTO 80окончания программы:Формат записи:ENDПринцип работы: при выполнении данного оператора работа программы прекращаетсяПример: IF D=0 THEN Print “1-n koren”: ENDЦиклаФормат записи:^ For имя_переменной=А TO B STEP C Тело цикла (операторы)Next имя_переменнойГде А – начальное значение переменной, В – конечное значение переменной, С – шаг изменения (если С=1, то STEP 1 можно не писать).Принцип работы: при выполнении данного оператораимени переменой присваивается начальное значение Авыполняется /тело цикла\Проверяется условие: имя переменной больше конечного значения В? Если «нет», то к значению переменной присваивается шаг С и выполняется п.2. Иначе управление передается на следующую строку.Пример: PRINT “Таблица умножения на N” INPUT “Ввести N”; NFor А=1 TO 9PRINT A; “x”; N; “=”; A*N^ Next имя_переменнойОператоры, стоящие в одной строке, разделяются знаком «:» (двоеточие).Арифметические операции на языке Basic. Операция Обозначение Пример Результат Сложение + 2+5 7 Вычитание - 10-8 2 Умножение * 3*4 12 Деление / 15/3 5 Возведение в степень ^ 2^3 8 Остаток от деления MOD 13 MOD 5 3  ^ Математические функции на языке Basic.  Корень SQR(X)  Модуль числа ABS(X)  Синус SIN(X)  Косинус COS(X)  Тангенс TAN(X)  Целая часть числа INT(X)  Натуральный логарифм LOG(X) ^ Линейная структура программы. Программа имеет линейную структуру, если все операторы (команды) выполняются последовательно друг за другом.                                          Программа, выводящая на экран сообщение: Привет! Меня зовут Саша! REM Первая программаPRINT “Привет! Меня зовут Саша!”END Программа, складывающая два числаREM Сумма двух чиселa = 5b = 6c = a + bPRINT "Результат: ", cEND Программа, складывающая два числаREM Сумма двух чиселDIM a, b, c AS INTEGERa = 5 : b = 6 : c = a + bPRINT "Результат: ", cEND Пример: Вычислите площадь прямоугольника по его сторонам.REM Площадь прямоугольникаINPUT "Введите сторону а", аINPUT "Введите сторону b", bs = a * bPRINT "Площадь равна: ", sEND Пример: Вычислить выражение REM Вычисление выраженияINPUT "Введите а", аINPUT "Введите b", bc = SQR(2*a*b)/(a+b)PRINT "Площадь равна: ", sEND Пример: Вычислите длину окружности и площадь круга по данному радиусу.REM Вычисление длины окружности и площади кругаINPUT "Введите радиус ", rPI = 3.14 : l = 2 * PI * r : s= PI * r * rPRINT "Длина окружности равна: ", lPRINT "Площадь равна: ", sEND ^ Ветвление в алгоритмах и программах. Разветвляющий алгоритм – это алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.Во многих случаях требуется, чтобы при одних условиях выполнялась одна последовательность действий, а при других - другая.       Вся программа состоит из команд (операторов). Команды бывают простые и составные (команды, внутри которых встречаются другие команды). Составные команды часто называют управляющими конструкциями. Этим подчеркивается то, что эти операторы управляют дальнейшим ходом программы.Рассмотрим запись условного оператора на языке Basic.Простая форма оператора выглядит следующим образом:IF THEN  илиIF              …END IFЕсли условие справедливо, то программа выполняет тот оператор, который стоит после ключевого слова ^ THEN (или серию операторов от ключевого слова THEN до END IF), и дальше руководствуется обычным порядком действий. Если уловие не справедливо, то оператор, стоящий после THEN (или серия операторов от THEN до END IF) не выполняется, и программа сразу переходит к обычному порядку действий.Конструкция IF...THEN  позволяет в зависимости от справедливости условия либо выполнить  оператор, либо пропустить этот оператор.Конструкция IF...THEN...END IF  позволяет в зависимости от справедливости условия либо выполнить группу операторов, либо пропустить эту группу операторов.Условия - еще один тип логических выражений. В них используются следующие операторы сравнения: = равно не равно > больше меньше >= больше или равно меньше или равно Справа и слева от знака сравнения должны стоять величины, относящиеся к одному типу. В результате сравнения получается логическая величина, имеющее значение ИСТИНА (TRUE) или ЛОЖЬ (FALSE).Пример:58=12  - ЛОЖЬ (проверяем: равно ли 8 12? Именно проверяем, а не утверждаем, что 8=12);Предыдущие конструкции позволяли обойти или выполнить серию оператор в зависимости от справедливости условия. Это еще не было ветвлением. Чтобы вычисления могли разветвляться по нескольким направлениям, служит конструкция IF...THEN...ELSE...END IF. IF  ELSEEND IFЕсли условие справедливо (ИСТИНА), то выполняются (стоящие между THEN и ELSE), а (стоящие между ELSE и END IF) будут пропущены.Если условие не справедливо (ЛОЖЬ), то игнорируются и выполняются .IF - если, THEN - тогда, ELSE - иначе.^ Если в комнате темно, тогда надо включить свет. Если пойдет дождь, тогда надо взять зонтик, иначе, зонтик не брать. Пример: Проверить, равно ли введенное число некоторому значению, и в случае равенства выдать  на экран сообщение о равенстве чисел.REM сравнить число с каким-то значениемINPUT "Введите а", аIF a=7 THEN PRINT "Числа равны"END^ После запуска программы проверяется равно ли введенное значение семи или нет. Если равно, то на экран выводится сообщение 'Числа равны'.Пример: Определить большее из двух чисел, вывести его на экран, затем - увеличить его в двое и вывести результат на экран.REM определить большее из двух чисел...INPUT "Введите а", аINPUT "Введите b", bIF a>b THENPRINT "Большее число: ", aс=2*aELSEPRINT "Большее число: ", bс=2*bEND IFPRINT "результат: ", cENDСначала программа запрашивает оба числа, затем проверяет условие a>b. Если условие верно, то на экран выводится число a, затем это число удваивается. Иначе на на экран выводится число b, затем  число b удваивается. В завершении на экран выводится удвоенное значение большего числа.Обратите внимание: программа имеет один недостаток - не учитывается тот случай, когда введенные числа равны. Исправим это, использовав вложение одного условия в другое.REM определить большее из двух чисел...INPUT "Введите а", аINPUT "Введите b", bIF a=b TNENPRINT "Числа равны"с=2*aELSE    IF a>b THEN    PRINT "Большее число: ", a    с=2*a    ELSE    PRINT "Большее число: ", b    с=2*b    END IFEND IFPRINT "результат: ", cENDВ этой программе два условных оператора, первым проверяется условие равенства чисел и, в случае его выполнения, будет выдано сообщение о равенстве чисел, если числа не равны, то проверяется второе условие...Пример: Решение квадратного уравнения.Решение квадратного уравнения зависит от значения дискриминанта.REM Решение квадратного уравненияINPUT "Введите коэффициент a: ", аINPUT "Введите коэффициент b: ", bINPUT "Введите коэффициент c: ", cd=b*b-4*a*cIF d=0 THENPRINT "Корней нет"ELSE    IF d=0 THEN    x=-b/(2*a)    PRINT "корень уравнения: ", x    ELSE    x1=(-b-SQR(d))/(2*a)    x2=(-b+SQR(d))/(2*a)    PRINT "корни уравнения: ", x1, x2    END IFEND IFEND ^ Структура "Выбор". Структура IF... позволяет выбрать между двумя вариантами. Если требуется осуществить выбор между большим числом вариантов, то это можно организовать, используя лишь структуру IF... Но можно (что чаще проще) и с помощью структуры "Выбор". Эта структура имеет вид: ^ SELECT CASE CASE CASE...CASE ELSEEND SELECT Выражение, заданное после ключевых слов SELECT CASE, сравнивается с определенными значениями - условиями и если они истинны, то выполняется соответствующая серия команд. Если не одно условие не истинно, то выполняется серия команд между CASE ELSE и END SELECT. Пример: Выдать словесное значение числа REM Преобразование чисел в словаINPUT "Введите число", aSELECT CASE aCASE 1PRINT "один"CASE 2PRINT "два"CASE 3PRINT "три"...CASE 10PRINT "десять"CASE ELSEPRINT "это число не могу перевести"END SELECTEND В данном примере введенное число сравнивается с числами от 1 до 10 и если наше число равно одному из этих чисел, то на экран выводится словесное значение числа. Если это не так на экран выводится сообщение: "это число не могу перевести".Примеры задач:Найти периметр и площадь прямоугольника: Вариант №1 Вариант №2 Вариант №3 10 Input a, b20 p=2*(a+b): s=a*b30 print “P=”; p40 print “S=”; s 10 Input a, b20 p=2*(a+b): s=a*b30 print “P=”; p: print “S=”; s 10 Input “a,b=”; a, b20 print “P=”; 2*(a+b)30 print “S=”; a*b Найти минимальное из 2-х чисел Вариант №1 Вариант №2 Вариант №3 10 Input a, b20 с=а30 if c 40 print b 10 Input a, b20 if a 30 print b 10 Input a, b20 if a 30 print b 40 end Вариант №4 Вариант №5 10 Input a, b20 if a>b then print b: goto 4030 print a 40 end ? Найти значения функции Y = 2 * X для Х = 2, 4, 6, 8 Вариант №1 Вариант №2 Вариант №3 10 x=220 y=2*x: print y30 x=x+240 y=2*x: print y50 x=x+260 y=2*x: print y70 x=x+280 y=2*x: print y 10 x=220 y=2*x: print y30 x=x+240 if x50 end 10 FOR x=2 TO 8 STEP 220 y=2*x: print y40 NEXT x ^ Основы логики Логика – наука о формах и способах мышления.Основные формы мышления:понятиесуждениеумозаключение.Понятие – это форма мышления, фиксирующая основные, существенные признаки объекта. Основные характеристики П. – содержание и объем.Пример: Понятие – «персональный компьютер».Содержание – «ПК – это устройство для автоматической обработки информации, предназначенное для одного пользователя»Объем – «ПК – совокупность ВСЕХ существующих в мире ПК»Высказывание – имеющее смысл языковое утверждение, допускающее однозначную констатацию: истина (False; 1) или ложь (True, 0).Примеры:А. Москва – столица России (истина)  А=1В. Лошадь – хищное животное (ложь)  В=0С. Который час? (не высказывание)Операции над высказываниямиОтрицание (инверсия) Отрицанием высказывания ^ А называется новое высказывание А (А), которое является истинным, если А=0, и ложью, если А=1 А А 0 1 1 0 Логическое умножение (коньюнкция) К. двух высказываний х и у называется новое высказывание z, которое является истиной только при истинности обоих высказываний. Х Y Z (X&Y) 1 1 1 1 0 0 0 1 0 0 0 0 Х= «6 делится на 2» = 1Y= «6 делится на 3» = 1Тогда Z=X&Y=1^ Логическое сложение (дизъюнкция) Д. двух высказываний х и у называется новое высказывание z, которое является истиной, если хотя бы одно из высказываний истинно. Х Y Z (X\/ Y) 1 1 1 1 0 1 0 1 1 0 0 0 Х= «6 делится на 2» = 1Y= «18 – трехзначное число» = 0Тогда Z=X Y=0Для наглядной геометрической иллюстрации объемов понятий и соотношений между ними используются диаграммы Эйлера-Венна (объем каждого понятия представляется в виде круга, а отношения между этими объемами – в виде пересекающихся кругов).Принцип построения таблицы истинности:Количество строк = 2n, где n – количество логических переменныхКоличество столбцов = количеству логических переменных + количеству логических операцийПостроить таблицуЗаполнить таблицу по столбцамПорядок выполнения операция: скобки, отрицание, коньюнкция, дизъюнкция.Логические законыЗакон двойного отрицанияА=(А) Переместительный (коммуникативный) законAB = BA AB = BA Сочетательный (ассоциативный) закон (AB)С = A(BС) (AB) С = A (BС)Распределительный (дистрибутивный) закон(AB)  C = (AC)  (BC) (AB)  C = (AC)  (BC)Закон общей инверсии (закон де Моргана) (AB) = AB  (AB) = ABЗакон идемпотентностиAА = AА=АЗакон исключения константA1 = 1 A0 = А A1 = А A0 = 0Закон противоречияAA=0Закон исключения третьегоAA=1Закон поглощенияA (АВ) = A A(АВ) = AЗакон исключения (склеивания)(АВ)  (АВ) = В (АВ)  (АВ) = В0>