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

Лекция 2. Понятие алгоритма Повторение Компьютерное мышление сводится к решению проблем. Что нужно, чтобы решить проблему? – Входные данные (описание проблемы) – Выходные данные (решение проблемы) – и процесс решения, назовем его алгоритмом. Входные данные могут представлять собой что угодно, но в конечном итоге все сводится к набору текстовой информации, или если пойти еще дальше — чисел. Тоже самое касается и выходных данных. Если с данными работает человек, то их представление должно быть ему понятно. Иначе немудрено запутаться, ошибиться. Таким образом, хорошим тоном будет предложить пользователю ввести данные и еще лучше указать их формат. printf(“Введите целое число: ”); Данный совет сейчас не очень актуален, так как консольные приложения большая редкость, но начинать обучение нужно именно с них, так как не приходится отвлекаться на особенности, связанные с UI/Windows Forms и т. п. Но даже в приложениях с окнами вы не встретите гору полей ввода без подписей. Данный совет работает и для выходных данных, потому что пользователю будет не очень понятно, что происходит, если он видит группу странных чисел. Алгоритм Определений для данного термина можно привести десятки, например: Алгоритм – последовательность чётко определенных действий, выполнение которых ведёт к решению задачи. Алгоритм, записанный на языке машины, есть программа решения задачи. Но по убеждению автора, нет определения, точно передающего смысл этого понятия. Алгоритм можно назвать последовательностью четко определенных действий на этапе обучения, но вскоре выясняется, что алгоритмы могут быть совершенно разными и задаваться совершенно по-разному. В контексте данного курса мы предположим, что алгоритмом будет именно последовательность чётко определенных действий. Хотя и эта последовательность может ветвиться, повторяться, перепрыгивать через саму себя, вызывать сама себя и т. д. Свойства алгоритмов: Дискретность (от лат. discretus — разделенный, прерывистый) – это разбиение алгоритма на ряд отдельных законченных действий (шагов). Детерминированность (от лат. determinate — определенность, точность) - любое действие алгоритма должно быть строго и недвусмысленно определено в каждом случае. Конечность – каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения. Массовость – один и тот же алгоритм можно использовать с разными исходными данными. Результативность – алгоритм должен приводить к достоверному решению. Алгоритмы встречаются и в реальной жизни, но вы об этом вряд ли задумывались. Например, у вас есть инструкция по эксплуатации прибора. Вы строго ее придерживаетесь, чтобы прибор правильно выполнял свою задачу. В отличие от компьютера, человек не обязан строго действовать инструкции, но компьютер такой свободой воли не обладает. Вскоре вы поймете, что обучение компьютера решать задачу через написание алгоритма, очень похоже на обучение другого человека чему-то совершенно новому и непонятному. Существует несколько способов записи алгоритмов. На практике наиболее распространены следующие формы: – словесная (запись на естественном языке); – псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.); – графическая (изображения из графических символов – блок-схема); – программная (тексты на языках программирования – код программы). В начале обучения может оказаться полезным применение всех способов описания алгоритма. Опытные люди также пользуются этими формами, просто у них либо имеются более мощные инструменты, либо они строят все в голове, изредка рисуя некоторые вещи на бумаге. Так что не стесняйтесь этим пользоваться. Наконец, различают три вида алгоритма: – линейный – разветвляющийся – цикличный По мнению автора, это глупая классификация, но все же он ее приводит. С линейным алгоритмом все понятно: у вас есть последовательность действий, и она строго в определенном (заданном вами) порядке выполняется. С такими алгоритмами вы редко будете встречаться. Разветвляющийся алгоритм способен принимать решения на строго определенных условиях, опять же заданных вами. Условия (предикаты) могут быть довольно сложными, но в результате они могут принимать лишь 2 значения: истина и ложь. Казалось многого с таким инструментом не достичь, но в реальности на этом инструменте строятся почти все программы. Мы изучаем, так называемые, императивные языки. Но есть языки, которые позволяют более свободно задавать правила поведения программы. Они даже покажутся более человеческими, что ли. На деле же, только еще больше запутывают неопытных программистов. Так что стандартное условие — это очень простой, но при это и очень мощный инструмент для написания хорошей программы. И овладеть им нужно обязательно. Цикличный алгоритм способен повторять сам себя некоторое количество раз. Это количество может быть строго заданным или нет. Если человеку лень будет повторять какое-то действие многократно, то компьютеру все равно. Он будет скрупулезно повторять одно и то же действие миллион раз, и ему не станет скучно. В этом его преимущество перед человеком. Плюс, он еще и делает это очень быстро. Условия и циклы базовые инструменты программиста, не поняв их, вы никогда не продвинитесь дальше операций над числами, поэтому постарайтесь уделить этому все свое внимание. Условия в языке Си if (<условие>) { <действие> } Простейшее описание условного оператора. Что скрывается за <условие>? В языке Си — это любое выражение, которое может быть интерпретировано, как истина или ложь. Язык Си довольно незамысловатый с первого взгляда. Ложь обозначается нулем, все остальное истина. Для простоты прибегают к обозначениям 0 — ложь, 1 — истина, но еще раз повторюсь, что в языке Си, даже -100.34 — это истина. Как правило, в качестве условий выступают условные операции (операции отношения): – < (меньше) a < b – > (больше) a > b – == (равно) a == b – != (не равно) a != b – >= (больше либо равно) a >= b – <= (меньше либо равно) a <= b Также используются и логические операции – && (и) (a < b) && (a != b) – тоже самое, что (a > b) – || (или) (a < b) || (a == b) – означает математическое «меньше либо равно» – ! (не) !(a == b) – тоже самое, что (a != b) – ^ (исключающее или) если оба операнда равны — ложь, остальное истина. (Осторожно! Эта операция побитовая, поэтому справедливо только для 0 и 1. С другими числами ведет себя по-другому, подробности в лекции 4) Условные операции, полагаю, что в подробном анализе не нуждаются, они хорошо знакомы из математики. Возможно, что с логическими все сложнее. Давайте посмотрим: мы могли бы написать следующее: if (a != 0) { if (a != 1) { printf(“a не равно 0 и не равно 1”); } } На самом деле, нет необходимости в 2 условных операторах в данном случае, тоже самое можно записать короче: if ((a != 0) && (a != 1)) { printf(“a не равно 0 и не равно 1”); } Скобки обозначают приоритеты, в данном случае они не нужны, но так легче понять, какое действие происходит вначале, а какое позже. Операцию «ИЛИ» сложнее представить в виде нескольких условий, поэтому я не буду вас нагружать, а просто приведу пример: if ((a == 0) || (a == 1)) { printf(“a равно 0 или 1”); } В случае с «НЕ» все еще проще. «НЕ» просто инвертирует результат (заменяет на противоположный). Если в результате условия получается истина, то «НЕ» превратит ее в ложь. Если получилось ложь, то «НЕ» превратит ее в истину. if (!(a == 0)) { printf(“a не равно 0”); } А вот тут скобки уже важны. Дело в том, что операция «НЕ» имеет более высокий приоритет, чем операция сравнения (==), так что без скобок вы получите довольно странный результат. Например, если в переменной «a» было число 10, то в варианте без скобок, с начала сработает «НЕ», то есть 10 (истина) станет 0 (ложью) и после сравнения с нулем результат станет истиной. Часто это не то, что вы хотите. Давайте взглянем на, так называемые, таблицы истинности. Они покажутся сложными, но на самом деле все очень и очень просто, я вас уверяю. аргумент1 аргумент2 “И” ИСТИНА ИСТИНА ИСТИНА ИСТИНА ЛОЖЬ ЛОЖЬ ЛОЖЬ ИСТИНА ЛОЖЬ ЛОЖЬ ЛОЖЬ ЛОЖЬ аргумент1 аргумент2 “ИЛИ” ИСТИНА ИСТИНА ИСТИНА ИСТИНА ЛОЖЬ ИСТИНА ЛОЖЬ ИСТИНА ИСТИНА ЛОЖЬ ЛОЖЬ ЛОЖЬ аргумент “НЕ” ИСТИНА ЛОЖЬ ЛОЖЬ ИСТИНА аргумент1 аргумент2 “исключающее ИЛИ” ИСТИНА ИСТИНА ЛОЖЬ ИСТИНА ЛОЖЬ ИСТИНА ЛОЖЬ ИСТИНА ИСТИНА ЛОЖЬ ЛОЖЬ ЛОЖЬ Таблицы передают суть этих операций. Например, при использовании операции «И» истина получается только, когда и первый, и второй аргумент истинны. А в случае с «ИЛИ» - хотя бы один из аргументов. Так легче запомнить. Обратите внимание на то, что в случае с «НЕ» в таблице только один аргумент. «НЕ» унарная операция, т. е. операция над одним аргументом (операндом). Для «И» и «ИЛИ» нужны 2 операнда. Это довольно логично. Представьте, что вас бы простили: «Вам подать или утку?» Конечно, в жизни могут так спросить, потому что задающий вопрос, предполагает, что второй аргумент назовете уже вы и даже дадите точный ответ, что же вы хотите на ужин. Но это неопределенный вопрос, на который может и не быть ответа. В императивных языках так нельзя. Что хотел официант от вас, если сегодня кроме утки и лосося они больше ничего не подают? На все ваши предложения, он отвечал бы отказом. Так почему бы сразу не задать конкретный вопрос «Вам подать утку или лосось?» «И» и «ИЛИ» - это бинарные операции, предполагающие наличие двух операндов. Давайте вернемся к условному оператору if. Что же там происходит? if (<условие>) { <действие> } Действие выполняется только если внутри скобок получилась истина. Но, если мы хотим совершить действие и в другом случае? Мы могли бы написать: if (<условие>) { <действие 1> } if (!<условие>) { <действие 2> } И у нас бы получилось, но вот незадача! Компьютер 2 раза рассчитает выражение внутри скобок. Это плохо с точки зрения оптимизации, да и вполне очевидно, что «действие 2» должно выполняться при противоположном результате, а если «действие 1» приведет к тому, что условие во вторых скобках тоже станет истинным? Тогда компьютер выполнит оба действия, а вот этого нам точно не хочется. Так что придумали оператор else. if (<условие>) { <действие 1> } else { <действие 2> } Но часто нужно больше чем 2 реакции. В описанном алгоритме поиска в телефонном справочнике, у нас было 3 варианта действий. Это легко изобразить: if (<условие 1>) { <действие 1> } else if (<условие 2>) { <действие 2> } else { <действие 3> } Так можно продолжать хоть до бесконечности. Например, вы бы могли описать поведение программы для каждого значения переменной, скажем от 0 до 1000. Получилось бы довольно длинное условие, и конечно, так делать не разумно. Позже вы узнаете красивые способы выходить из положений, когда приходится писать очень ветвленные структуры кода. Но для трех действий все выглядит весьма недурно. Лабораторная 2 Задание 0 Пользователь с клавиатуры вводит 4 числа. Программа должна вывести сколько положительных и отрицательных чисел ввел пользователь. Задание 1 Реализовать программу, которая бы играла с пользователем в игру «камень-ножницыбумага». Входные и выходные данные: r — камень с — ножницы p — бумага Выходные данные: компьютер часто выигрывает наивного игрока, но не каждый раз Для реализации игры компьютера понадобится переменная, которая принимала бы случайное значение (рандом). Достигается следующим образом: int RandomNumber = rand()%10; //даст случайное число от 0 до 9 Программа будет каждый запуск выдавать один и тот же результат, чтобы этого не происходило используется функция srand в начале программы один раз. srand(time(0)); библиотеки: #include (для time()) #include (для rand()) Задание 2 Реализовать программу, которая бы играла с пользователем в игру «камень-ножницы-бумага» по следующим правилам: У игрока и компьютера 6 карточек. По две карточки каждого достоинства. Всего играется 6 раундов, после этого считаются очки. Пользователь выбирает свои карточки перед раундом, компьютер выбирает свои случайно. Вывод программы может быть таким: r – p comp wins c – p user wins r – c user wins p – r user wins p – r user wins c – c tie Total 4-1. User wins!