Построение алгоритма и решение задач
Как идею алгоритма превратить в программу?
Убедиться в том, что вы сами (без компьютера) в состоянии решить задачу
- на достаточно большом (но не слишком) наборе данных:
- не интуитивно, а следуя заранее намеченному плану
Записать действия на наиболее знакомом вам языке
- можно по-русски!
можно не записывать только при условии, что вы способны повторить слово-в-слово
Подумать над моделированием данных реального мира с помощью типов данных Python
- Например, как из того, что вам предлагается вводить, сделать эти данные
Превратить придуманные вами действия в последовательность порождения и преобразования данных
- Какую дополнительную информацию вы используете
- Какое действие за каким следует
- При каких условиях вы делаете одно, а при каких — другое
- При каких условиях действия повторяются
- Есть ли чётко формулируемые подзадачи
Попытаться однозначно перевести каждое действие на Python
Обратите внимание на то, что лишних слов в формулировке не бывает!
- Например, если вы используете слово «каждый», это с точки зрения последовательности действий почти наверняка означает цикл
- И вообще про каждое слово в вашей формулировке задайте себе вопрос «а что оно значит» — наверняка вам придётся отражать это в программе
- Представить подзадачи в виде функций — тогда все действия, выполняемые одной функцией, будут выглядеть как как один шаг алгоритма
Решение задач
- Общая схема:
- Что делать, если даже на словах не решается?
- Словесная формализация
- Что дано?
- Что ввести?
- Что вывести?
- Описание алгоритма на естественном языке
- Перевод на Python
- Проверка и уточнение
- Линейные вычисления:
Известна длина окружности. Найти площадь круга, ограниченного этой окружностью.
Найти площадь кольца, внутренний радиус которого равен r, а внешний — R (R > r).
- Простые условия. Проверить, что
Треугольник со сторонами a, b, с является равнобедренным
Шахматный конь за один ход может переместиться с одного заданного поля на другое (каждое поле задано двумя координатами — целыми числами от 1 до 8).
(по результатам) ещё на простые условия отсюда
- Простые циклы.
Вычислить среднее арифметическое последовательности
- Формализация условия:
- (заранее ничего не дано)
- Ввести несколько чисел
- Вывести одно число — их среднее арифметическое
- Как решить:
- сложить все числа
- поделить сумму на количество чисел — это и есть ответ
- Как представить данные в Python:
- «Несколько чисел» — это кортеж
- Количество чисел — это длина кортежа
Остальное — это float
- Формализация решения.
- Вводим кортеж.
«Складываем все числа». Проблема — нет такого действия. Есть только сложение двух чисел. Значит, надо решить подзадачу.
- Заводим переменную для суммы всех чисел. Изначально она равна 0.
- Для каждого элемента кортежа
- Добавляем его к сумме
- Делим сумму на длину кортежа и выводим результат
- Решение.
- Запишем нашу формализацию в виде комментариев в программе. Составное действие «Складываем все числа» заменяем атомарными:
- Теперь переводим каждую строку на Python
1 # Вводим кортеж. 2 seq = eval(input("Введите числа через запятую: ") 3 # Заводим переменную для суммы всех чисел. Изначально она равна 0. 4 res = 0 5 # Для каждого элемента кортежа 6 for element in seq: 7 # Добавляем его к сумме 8 res = res + element 9 # Делим сумму на длину кортежа и выводим результат 10 print("Среднее арифметическое: ", res/len(seq))
Вообще говоря, такие комментарии только усложняют чтение программы:
- Формализация условия:
Вычислить среднее геометрическое $$ \root(n)(a_1 * a_2 * … * a_n) $$
- Планирование циклов.
Вычислить сумму цифр натурального числа.
- Формализация условия
- Известно, что число целое положительное (не 0 и записывается без минуса)
- Ввести целое число
- Вывести целое число — сумму цифр
- Как решить?
- Сложить все цифры
- Данные представим целыми числами
- Формализация решения.
- Ввести целое число
- «Сложить все цифры». Как «сложить все» мы уже знаем, но не знаем ни сколько цифр, ни как отделять от числа очередную цифру. Эти две подзадачи надо решить.
- Заводим переменную для суммы всех цифр. Изначально она равна 0.
- Посчитаем количество цифр. Например, преобразуем число в строку и возьмём длину строки.
- Повторим следующий действия столько раз, сколько цифр в числе:
- Выясним последнюю цифру числа: это остаток от деления на 10. Добавляем её к сумме.
- Отбрасываем от числа эту последнюю цифру. Для этого достаточно поделить это число нацело на 10.
- Выводим сумму
- Перевод на Python:
- Комментарии без составных действий
1 # Ввести целое число 2 # Заводим переменную для суммы всех цифр. Изначально она равна 0. 3 # Посчитаем количество цифр. Например, преобразуем число в строку и возьмём длину строки. 4 # Повторим следующий действия столько раз, сколько цифр в числе: 5 # Выясним последнюю цифру числа: это остаток от деления на 10. Добавляем её к сумме. 6 # Отбрасываем от числа последнюю цифру. Для этого достаточно поделить это число нацело на 10. 7 # Выводим сумму
- Переводим.
1 # Ввести целое число 2 N = int(input("Введите натуральное число: ")) 3 # Заводим переменную для суммы всех цифр. Изначально она равна 0. 4 res = 0 5 # Посчитаем количество цифр. Например, преобразуем число в строку и возьмём длину строки. 6 width = len(str(N)) 7 # Повторим следующий действия столько раз, сколько цифр в числе: 8 for i in range(width): 9 # Выясним последнюю цифру числа: это остаток от деления на 10. Добавляем её к сумме. 10 res = res + N % 10 11 # Отбрасываем от числа последнюю цифру. Для этого достаточно поделить это число нацело на 10. 12 N = N // 10 13 # Выводим сумму 14 print(res)
- Комментарии без составных действий
- Без комментариев
- Формализация условия
Поменять местами первую и последнюю цифру натурального числа
У гусей и кроликов вместе N лап. Сколько может быть кроликов и гусей (указать все сочетания)?
- Формализация условия
- Дано: у гуся 2 лапы, а у кролика 4.
- Ввести натуральное число лап
- Вывести все возможные пары чисел вида «количество кроликов, количество гусей», в которых у них в сумме N лап
Как решать. А это, кстати, вопрос
Идеи к решению. Это самая простая идея, есть и более сложные. Любое решение, приводящее к правильному результату считается «правильным»!
Если число N нечётное, задача не имеет решения.
Если у нас k кроликов, а остальные — гуси, то на гусей приходится N - k*4 лапы. Это число чётное (нечётное N мы отбросили), а гусей вполовину меньше, чем их лап.
k*4 не может превышать N, то есть количество кроликов 0 ⩽ k ⩽ N/4.
Организуем цикл по кроликам!
- Если лап чётное количество, выполняем алгоритм, если нечётное — не делаем ничего
- Для каждого возможного числа кроликов посчитаем соответствующее число гусей и выведем искомую пару
- Данные хранить не надо, достаточно целого числа лап и кроликов
- Как решать?
- Вводим N
- Если N чётно
Для каждого количества кроликов от 0 до N // 4 включительно
- Вычисляем количество гусей и выводим пару
- (Если N нечётно ничего не делаем)
- Перевод на Python (пункт «ничего не делать выбрасываем)
- На русском
- Сразу на Python
- Формализация условия
Одноклеточная амёба каждые 3 часа делится на 2 клетки. В колонии амёб за час погибает одна амёба. Сейчас в колонии N амёб. Сколько будет амёб через K часов.
Д/З
- Дорешать все домашние задания из прошлых лекций, если ещё не.
Поменять местами первую и последнюю цифру натурального числа.
- Пример:
Ввод
51433
Вывод
31435
- Пример:
Все одноклеточные амёбы раз в 3 часа одновременно делятся на 2 клетки. В колонии амёб каждый час погибает одна амёба. Сейчас в колонии N амёб. Сколько будет амёб через K часов?
Ввести n и k. Найти сумму всех n-значных чисел, кратных k.
Сохранить решения всех трёх задач в файлы с именами ( обратите вниманbе на 0!):
prog_0_1.py
prog_0_2.py
prog_0_3.py Отослать их в виде трёх приложений к одному письму по адресу <uneexlectures AT cs DOT msu DOT ru>
В поле Subject должно быть «слово» PhilosoPython2022 (другие слова тоже можно ☺)