Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Основные структуры алгоритмов).pdf

Листинг 2. Оператор ветвления с двумя ветками

if answer == "да":

print "Я угадал!"

else:

print "Ошибочка вышла..."

Условие по else выполняется в том случае, если не выполняется условие по if. В операторе if можно указать условие else. Цель else – предоставить блок кода «если нет». Код else выполняется, если условие в if ложно. Ветвление можно усилить, предоставив оператору больше возможностей с использованием блоков elif. Elif используется как «else if» (листинг 3).

Листинг 3. Оператор ветвления с тремя ветками

if answer == "да":

print "Я угадал!"

elif answer == "нет":

print "Ошибочка вышла..."

else:

print "Вы должны ответить либо «да», либо «нет»."

Здесь немного меняется логика работы программы. Пользователи программы должны будут ответить «да» или «нет». Если они ответят что-нибудь иное, то они получат сообщение об ошибке. Можно вставить любое количество elif, чтобы учесть множество вариантов. Всякий раз, когда используется структура if. . . elif. . . elif. . . else, будет выполняться только один из блоков кода кода. Else будет выполняться, только если ни одно из условий не выполняется.

1.3 Циклические алгоритмы

Несмотря на то, что ветвящиеся алгоритмы могут предоставить больше возможностей, чем линейные, при их использовании все еще не хватает одной важной концепции программирования – нужно иметь возможность выполнять один и тот же код несколько раз (итерация). В большинстве языков программирования есть несколько способов итерации. В рамках работы будут рассмотрены два способа использования циклов в Python: цикл с параметром for и цикл с предусловием while.

Примером использования цикла for может служить, например, алгоритм нахождения факториала числа.

1. Напечатать «Введите натуральное число»;
2. Получить число;
3. Пусть factorial = 1;
4. Для i от 1 до n с шагом 1 выполнить:
   1. Присвоить factorial = factorial × i;
5. Напечатать factorial.

В некоторых задачах заранее известно, сколько раз необходимо выполнить один и тот же код. Факториал числа n записывается как «n!» и является произведением всех чисел от 1 до n. Таким образом, для поиска результата необходимо выполнить всего n произведений.

Самый простой способ создать цикл for в языке Python – использовать функцию range. Когда для цикла for задан диапазон x, тело цикла будет выполняться x раз (листинг 4).

Листинг 4. Программа поиска факториала натурального числа с использованием цикла for

n = int(raw_input("Введите натуральное число: "))

factorial = 1

for i in range(n)

factorial = factorial * (i+1)

print factorial

Следует отметить, что что диапазон начинается с нуля, и счет ведется до n - 1. В примере из листинга 4 по этой причине выполняется обращение к i + 1, поскольку для вычисления факториала нужны значения от 1 до n, а не от 0 до n - 1.

По исторической причине переменная i является стандартным выбором в качестве переменной цикла for, если ничто другое не подходит лучше. По возможности нужно выбирать описательное имя переменной, но для быстрых и коротких циклов i – хорошее значение по умолчанию.

Цикл for называется конечным циклом.

Если неизвестно точно, сколько итераций требуется для того, чтобы тело цикла выполнялось, с циклом for сложно работать. Например, с использованием цикла в игре на угадывание из листинга 1 необходимо продолжать угадывать, пока не будет получено правильное решение. Таким образом, может быть сделано от 1 до 7 предположений.

В Python можно решить эту проблему с помощью цикла while. Чтобы создать цикл while, необходимо использовать условие, как в операторе if. Тело цикла будет выполняться столько раз, сколько необходимо, пока условие не станет ложным.

В качестве примера можно привести программу из листинга 5. Она просит пользователя ввести свое имя. Если пользователь просто нажимает клавишу ввода, программа будет продолжать спрашивать, пока пользователь не ответит. В конце программа выполняет приветствие, обращаясь к пользователю по полученному имени.

Листинг 5. Программа приветствия пользователя с применением цикла с предусловием

name = raw_input("Как ваше имя? ")

while name=="":

name = raw_input("Пожалуйста, введите свое имя: ")

print "Привет, " + name

Итак, когда цикл while выполняется, повторяются следующие действия:

1. Проверить значение условия. Если оно ложно (False), то цикл завершается, и программа переходит к пункту 4;
2. Запустить тело цикла;
3. По окончании тела цикла перейти к пункту 1;
4. Перейти к следующему участку кода.

По сути, цикл while использует свое условие, чтобы спросить: «Следует ли мне продолжать?» Если да, он запускает цикл еще раз и снова спрашивает.

Когда используется неопределенный цикл while, необходимо убедиться, что условие цикла в конечном итоге станет ложным. В противном случае программа просто будет бесконечно зацикливаться. Цикл while по этой причине называется бесконечным циклом.

1.4 Выбор алгоритмической структуры

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

При выборе нет никаких жестких правил. Чаще всего есть много способов сделать одно и то же программным способом, особенно когда требуемая задача становится сложнее.

Прежде чем выбирать нужную структуру, необходимо иметь довольно хорошее представление о том, что нужно, чтобы компьютер делал (то есть получить алгоритм). Как только это будет достигнуто, можно подумать о том, как заставить программу делать то, что от нее требуется.

• Просто сделать что-то.

Большинство операторов в Python (и большинстве других языков программирования) выполняются в том порядке, в котором они появляются. Таким образом, присваивание переменной значения или оператор вывода будут выполняться сразу после предыдущего оператора (если структура управления не меняет способ работы).

Эти утверждения говорят компьютеру, что необходимо сделать. Управляющие структуры позволяют указать, когда это произойдет.

• Может быть, сделать, а может, и нет.

Если есть код, который требуется выполнить только в определенной ситуации, тогда подойдет условный оператор if. Он будет запускать свое тело ноль или один раз. Если нужно выполнять похожие действия более одного раза, то лучше использовать цикл.

Если требуется логика «либо то, либо то», тогда нужно использовать if с ветвлением по else. Если нужно сделать «одно из этих действий», лучше использовать оператор if... elif...elif...else.

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

• Сделать несколько раз.

Когда нужно что-то сделать несколько раз, нужен цикл. Следует помнить, что циклы могут выполняться ноль, один или несколько раз, в зависимости от условий (значений переменных, типов использования и т. д.).

Действие, выполняемое внутри цикла, не обязательно должно быть одинаковым каждый раз. Можно использовать переменную цикла (в цикле for) и любые другие переменные в программе, чтобы отследить, что именно на этот раз нужно сделать в цикле. Например, можно проверить переменную цикла, чтобы увидеть, есть ли у нее определенное свойство, и вывести его на экран, если оно есть. Для этого необходимо использовать оператор if в цикле и написать условие, которое выражает искомое свойство.

• Сделать много раз.

Если известно, когда цикл запускается, сколько раз он будет выполняться (например, выполнить подсчет до определенного значения или совершить действие для каждого элемента в коллекции), лучше всего использовать цикл for.

• Делать, пока не будет выполнено.

Часто возникают ситуации, когда невозможно точно сказать, сколько раз повторять цикл. Обычно они имеют форму «продолжайте делать это, пока не закончите».

В этих случаях, вероятно, понадобится цикл while. Цикл while похож на if, в нем нужно написать логическое выражение, описывающее, когда «идти». В отличие от if, цикл while будет многократно выполнять тело, пока его условие не станет ложным.

При написании условия для цикла while нужно выяснить, как компьютер определит, что еще есть действия, которые необходимо выполнить, прежде чем цикл будет завершен. Часто это описывает фраза «Нужно сделать еще один шаг, если...». Тело while – это код, необходимый для выполнения «шага».

1.4 Практическая реализация алгоритма

В этом разделе с учетом полученных ранее знаний будет разработка приложения для конвертации денежной суммы. Для реализации цели необходимо выполнить ряд задач. Программа, написанная на языке высокого уровня Python, должна предоставить возможность перевести заданную в числовом виде сумму в рублях в ее аналог прописью. В программе должны быть учтены моменты, позволяющие пользователю легко освоить программу, для этого необходимо также создать удобный интерфейс приложения.

Анализ предметной области

В официальных бумагах (доверенностях, договорах между двумя сторонами, кассовых документах и т.д.) для взаимной безопасности между сторонами сделки нередко возникает потребность расшифровки суммы (как правило, в рублях), записанной цифрами, в письменном виде. Кроме того, такое дублирование суммы позволяет подтвердить правильность суммы в цифровом виде (тем более в том случае, когда это значение напечатано). Так, если цифровое обозначение суммы противоречит буквенному написанию, по соглашению сторон превалирующей может считаться сумма, указанная в договоре прописью. Таким образом, приоритет буквенного написания над цифровым делает актуальной задачу автоматизации такого рода записей в документах, особенно когда речь идет о массовом заполнении однотипных бумаг.

Задача перевода цифровых обозначений в буквенные также возникает при исправлении некоторых ошибок, допущенных в изданной литературе. Так, например, однозначные числа, стоящие в косвенных падежах не при денежных единицах, принято записывать в словесной форме («три рубля» вместо «3 рубля»). Такая же форма используется и в том случае, если количественное числительное является первым в предложении («Пять рублей…» вместо «5 рублей…»), поскольку прописная буква предложения исчезает при использовании цифровой записи, что мешает читателю увидеть начало предложения. Частичное использование словесной формы рекомендуется также и при использовании нескольких чисел, идущих подряд («три 100-рублевых купюры» вместо «3 100-рублевых купюры»).

1.5 Обоснование выбора языка программирования

Для программной реализации приложения, предназначенного для задачи перевода суммы в цифровой форме в сумму в словесной форме, был выбран высокоуровневый язык программирования общего назначения Python; версия языка – 3.6.4.

Python был создан Гвидом Ван Россумом в конце 80-х годов и остается одним из самых простых и эффективных языков программирования на сегодняшний день [5.]. Он может использоваться как для начальных шагов в программировании, так и для решения серьезных научных задач. Python является интерпретируемым и объектно-ориентированным языком, поддерживающим при этом несколько парадигм программирования, в том числе функциональную и императивную [6.]. Основными архитектурными чертами языка можно назвать автоматическое управление памятью, динамическую типизацию и удобные высокоуровневые структуры данных (такие, как кортежи, множества, словари и списки). В Python имеются встроенные типы: булевый, строка, Unicode-строка, целое число произвольной точности, число с плавающей запятой, комплексное число и многие другие [7.]. Код в Python организовывается в функции и классы, которые могут объединяться в модули (они в свою очередь могут быть объединены в пакеты). Все значения, в том числе встроенные коллекции и типы данных, функции, методы, модули, классы являются объектами [8.].

Одним из главных достоинств языка считается его реализация на большинстве современных платформ и операционных систем. Для одного из первых переносимых языков программирования – языка С – существенным недостатком оказывалось разное количество занимаемой на разных машинах памяти языковыми типами данных, чего удалось избежать в реализации Python.