Построение алгоритма и решение задач

Как идею алгоритма превратить в программу?

  1. Убедиться в том, что вы сами (без компьютера) в состоянии решить задачу

    • на достаточно большом (но не слишком) наборе данных:
    • не интуитивно, а следуя заранее намеченному плану

  2. Записать действия на наиболее знакомом вам языке

    • можно по-русски!

    • можно не записывать только при условии, что вы способны повторить слово-в-слово

  3. Подумать над моделированием данных реального мира с помощью типов данных Python

    • Например, как из того, что вам предлагается вводить, сделать эти данные

  4. Превратить придуманные вами действия в последовательность порождения и преобразования данных

    • Какую дополнительную информацию вы используете
    • Какое действие за каким следует
    • При каких условиях вы делаете одно, а при каких — другое
    • При каких условиях действия повторяются
    • Есть ли чётко формулируемые подзадачи

  5. Попытаться однозначно перевести каждое действие на Python

    • Обратите внимание на то, что лишних слов в формулировке не бывает!

    • Например, если вы используете слово «каждый», это с точки зрения последовательности действий почти наверняка означает цикл
    • И вообще про каждое слово в вашей формулировке задайте себе вопрос «а что оно значит» — наверняка вам придётся отражать это в программе
    • Представить подзадачи в виде функций — тогда все действия, выполняемые одной функцией, будут выглядеть как как один шаг алгоритма

Решение задач

  1. Общая схема:
    1. Что делать, если даже на словах не решается?
    2. Словесная формализация
      • Что дано?
      • Что ввести?
      • Что вывести?
    3. Описание алгоритма на естественном языке
    4. Перевод на Python
    5. Проверка и уточнение
  2. Линейные вычисления:

    • {OK} Известна длина окружности. Найти площадь круга, ограниченного этой окружностью.

    • {i} Найти площадь кольца, внутренний радиус которого равен r, а внешний — R (R > r).

  3. Простые условия. Проверить, что

    • {OK} Треугольник со сторонами a, b, с является равнобедренным

    • {i} Шахматный конь за один ход может переместиться с одного заданного поля на другое (каждое поле задано двумя координатами — целыми числами от 1 до 8).

  4. {*} (по результатам) {i} ещё на простые условия отсюда

  5. Простые циклы.

    • {OK} Вычислить среднее арифметическое последовательности

      1. Формализация условия:
        1. (заранее ничего не дано)
        2. Ввести несколько чисел
        3. Вывести одно число — их среднее арифметическое
      2. Как решить:
        • сложить все числа
        • поделить сумму на количество чисел — это и есть ответ
      3. Как представить данные в Python:
        • «Несколько чисел» — это кортеж
        • Количество чисел — это длина кортежа

        • Остальное — это float

      4. Формализация решения.
        1. Вводим кортеж.

        2. «Складываем все числа». Проблема — нет такого действия. Есть только сложение двух чисел. Значит, надо решить подзадачу.

          1. Заводим переменную для суммы всех чисел. Изначально она равна 0.
          2. Для каждого элемента кортежа
            • Добавляем его к сумме
          3. Делим сумму на длину кортежа и выводим результат
        3. Решение.
          • Запишем нашу формализацию в виде комментариев в программе. Составное действие «Складываем все числа» заменяем атомарными: 
               1 # Вводим кортеж.
   2 # Заводим переменную для суммы всех чисел. Изначально она равна 0.
   3 # Для каждого элемента кортежа
   4 #     Добавляем его к сумме
   5 # Делим сумму на длину кортежа и выводим результат
          • Теперь переводим каждую строку на 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))

          • Вообще говоря, такие комментарии только усложняют чтение программы: 

               1 seq = eval(input("Введите числа через запятую: ")
   2 res = 0
   3 for element in seq:
   4     res += element
   5 print("Среднее арифметическое: ", res/len(seq))

    • {i} Вычислить среднее геометрическое $$ \root(n)(a_1 * a_2 * … * a_n) $$

  6. Планирование циклов.

    • {OK} Вычислить сумму цифр натурального числа.

      1. Формализация условия
        1. Известно, что число целое положительное (не 0 и записывается без минуса)
        2. Ввести целое число
        3. Вывести целое число — сумму цифр
      2. Как решить?
        1. Сложить все цифры
      3. Данные представим целыми числами
      4. Формализация решения.
        1. Ввести целое число
        2. «Сложить все цифры». Как «сложить все» мы уже знаем, но не знаем ни сколько цифр, ни как отделять от числа очередную цифру. Эти две подзадачи надо решить.
          1. Заводим переменную для суммы всех цифр. Изначально она равна 0.
          2. Посчитаем количество цифр. Например, преобразуем число в строку и возьмём длину строки.
          3. Повторим следующий действия столько раз, сколько цифр в числе:
            1. Выясним последнюю цифру числа: это остаток от деления на 10. Добавляем её к сумме.
            2. Отбрасываем от числа эту последнюю цифру. Для этого достаточно поделить это число нацело на 10.
        3. Выводим сумму
      5. Перевод на 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)
      6. Без комментариев 
        •    1 N = int(input("Введите натуральное число: "))
   2 res = 0
   3 width = len(str(N))
   4 for i in range(width):
   5     res += N % 10
   6     N //= 10
   7 print(res)

    • {i} Поменять местами первую и последнюю цифру натурального числа

    • {OK} У гусей и кроликов вместе N лап. Сколько может быть кроликов и гусей (указать все сочетания)?

      1. Формализация условия
        1. Дано: у гуся 2 лапы, а у кролика 4.
        2. Ввести натуральное число лап
        3. Вывести все возможные пары чисел вида «количество кроликов, количество гусей», в которых у них в сумме N лап

      2. Как решать. А это, кстати, вопрос :\

        1. Идеи к решению. Это самая простая идея, есть и более сложные. Любое решение, приводящее к правильному результату считается «правильным»!

          • Если число N нечётное, задача не имеет решения.

          • Если у нас k кроликов, а остальные — гуси, то на гусей приходится N - k*4 лапы. Это число чётное (нечётное N мы отбросили), а гусей вполовину меньше, чем их лап.

          • k*4 не может превышать N, то есть количество кроликов 0 ⩽ k ⩽ N/4.

          • (!) Организуем цикл по кроликам!

        2. Если лап чётное количество, выполняем алгоритм, если нечётное — не делаем ничего
        3. Для каждого возможного числа кроликов посчитаем соответствующее число гусей и выведем искомую пару
      3. Данные хранить не надо, достаточно целого числа лап и кроликов
      4. Как решать?
        1. Вводим N
        2. Если N чётно

          1. Для каждого количества кроликов от 0 до N // 4 включительно

            1. Вычисляем количество гусей и выводим пару
        3. (Если N нечётно ничего не делаем)
      5. Перевод на Python (пункт «ничего не делать выбрасываем)
        • На русском 
             1 # Вводим N
   2 # Если N чётно
   3 #     Для каждого количества кроликов от `0` до `N // 4` включительно
   4 #        Вычисляем количество гусей и выводим пару
        • Сразу на Python 
             1 N = int(input())
   2 for krol in range(0, N//4 + 1):
   3     gus = (N - krol) // 2
   4     print("Кроликов:", krol, "Гусей:", gus)

    • {i} Одноклеточная амёба каждые 3 часа делится на 2 клетки. В колонии амёб за час погибает одна амёба. Сейчас в колонии N амёб. Сколько будет амёб через K часов.

Д/З

  1. Дорешать все домашние задания из прошлых лекций, если ещё не.

  2. <!> Поменять местами первую и последнюю цифру натурального числа.

    • Пример:

      • Ввод 

        51433

      • Вывод 

        31435

  3. <!> Все одноклеточные амёбы раз в 3 часа одновременно делятся на 2 клетки. В колонии амёб каждый час погибает одна амёба. Сейчас в колонии N амёб. Сколько будет амёб через K часов?

  4. <!> Ввести n и k. Найти сумму всех n-значных чисел, кратных k.

  5. Сохранить решения всех трёх задач в файлы с именами ( /!\ обратите вниманbе на 0!):

    • prog_0_1.py

    • prog_0_2.py

    • prog_0_3.py Отослать их в виде трёх приложений к одному письму по адресу <uneexlectures AT cs DOT msu DOT ru>

      • В поле Subject должно быть «слово» PhilosoPython2022 (другие слова тоже можно ☺)

Python/PhilosoPython2022/07_Algorithm (последним исправлял пользователь FrBrGeorge 2022-11-06 21:49:52)