Тема 15 : Этапы решения задач на компьютере (углубленный)

 

Тема 15 : Этапы решения задач на компьютере

https://profspo.ru/old-viewer?publicationType=books&publicationId=132236

Глава 8 §51 стр 126-131

https://profspo.ru/reader/book/132235 Глава 4  §27,28 стр 211-223

 

В решении любой задачи с помощью компьютера можно выделить несколько этапов. 

1. Постановка задачи. Нужно чётко определить, что в задаче дано (исходные данные) и что нужно найти (результаты).

2. Формализация. На этом этапе строится модель, которая включает только существенные данные, влияющие на решение задачи. Например, при моделировании полёта брошенного в воду камня нужно решить, учитываем ли мы притяжение Земли, сопротивление воздуха и влияние Луны. Затем модель записывается с помощью формального языка, например в виде математических формул или уравнений, связывающих исходные данные и результаты.

Далее мы можем использовать готовое программное обеспечение или составить свою собственную программу. Рассмотрим второй вариант.

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

 4. Составление программы на языке программирования.

 5. Тестирование и отладка программы. Цель тестирования — найти как можно больше ошибок в программе. Для этого используют тесты — специально подобранные наборы исходных данных, для которых известен правильный результат.

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

6. Выполнение расчётов. В отличие от тестирования на этом этапе мы выполняем расчёты для тех исходных данных, для которых результаты неизвестны. 

7. Анализ результатов. После завершения расчётов нужно проверить, не противоречат ли результаты теории и здравому смыслу. Например, время движения автомобиля не может быть отрицательным. Если такие противоречия обнаружены, нужно искать ошибку в модели, алгоритме или программе. Ключевой этап в этой последовательности — построение алгоритма.

Алгоритм — это точное описание последовательности действий некоторого исполнителя.

Основные свойства алгоритма:

• дискретность — алгоритм состоит из отдельных команд, каждая из которых выполняется ограниченное (не бесконечное) время;

• понятность — алгоритм содержит только команды, входящие в систему команд исполнителя, для которого он пред-назначен;

• определённость — при каждом выполнении алгоритма с од-ними и теми же исходными данными должен быть получен один и тот же результат.

 

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

 

 

Анализ алгоритмов

Для того чтобы грамотно использовать исполнителей, нужно понимать алгоритмы, по которым они работают.

Часто мы не создаём алгоритмы сами, а используем готовые. В таких случаях полезно выполнять анализ алгоритмов, например, выяснив:

• какие исходные данные нужно подать на вход алгоритма, чтобы получить нужный результат;

• какие результаты могут быть получены при заданных исходных данных.

Рассмотрим несколько примеров.

Задача1. По каналу связи передаются трёхзначные целые числа. Для каждой пары таких чисел строится контрольная сумма, позволяющая обнаруживать ошибки при передаче:

а)записывается сумма старших разрядов передаваемых чисел; к ней справа дописывается сумма средних разрядов, а за-тем слева — сумма младших разрядов тех же чисел;

б)контрольная сумма — это три цифры полученного числа: число тысяч, число сотен и число десятков. Пример: передаются числа 768 и 156. Поразрядные суммы — 8,11,14. После шага

а) получаем число N = 14811, контрольная сумма — 481.Найдите минимальное и максимальное значения, которые может принимать контрольная сумма.

Решение. Поскольку числа трёхзначные, все они находятся на отрезке [100; 999]. Очевидно, что сумма значений двух любых десятичных цифр не меньше 0 и не больше 18. Минимальное число (N), которое может быть получено после шага а), равно 20 (при обработке чисел 100 и 100), а максимальное — 181818 (для чисел 999 и 999). Отсюда сразу следует, что минимальное значение контрольной суммы — 2

Определим максимальное значение контрольной суммы. Допустим, что контрольная сумма равна 999. Это значит, что число N имеет вид «..999.», где точка обозначает десятичную цифру, возможно — 0. Сумма значений двух цифр не может быть больше 18, поэтому есть только один вариант разбиения такого числа на поразрядные суммы: 9|9|9x, где x — какая-то цифра. Но этот вариант невозможен — сумма средних разрядов не может быть больше 18, поэтому максимальное значение контрольной суммы— 991. Такая контрольная сумма получается, например, для чисел 259 и 760

Задача2. Для условия задачи 1 приведите примеры данных, при которых контрольная сумма равна 106.

Решение. Если контрольная сумма равна 106, то число N может быть записано в виде «..106.». Возникает вопрос — как разбить это число на 3 поразрядные суммы? Поскольку вторая справа цифра — 6, а двузначная сумма значений двух цифр не может начинаться с 6, есть только один вариант: 10|6|x, где x — неизвестная однозначная сумма средних разрядов чисел. Поэтому нужно найти два трёхзначных числа, у которых сумма старших разрядов равна 6, сумма младших разрядов равна 10, а сумма средних разрядов меньше 10. Это могут быть, например, пары 209 и 491 или 138 и 522

Мы увидели, что для нашей контрольной суммы может возникнуть коллизия — ситуация, когда при разных данных контрольная сумма одинакова. Коллизии возникают практически всегда, ведь у нас есть всего 990 теоретически возможных значения контрольной суммы (от 2 до 991), на которые «отображаются» 900·900 вариантов пар передаваемых чисел (напомним, что все числа — трёхзначные, на отрезке [100,999])

Задача3. Для условия задачи 1 определите, сколько существует пар чисел, для которых контрольная сумма равна 421.

Решение. Если контрольная сумма равна 421, то число N может быть записано в виде «..421.». Сумма старших разрядов не может быть равна ни 42, ни 21, поэтому такое число может быть разбито на отдельные суммы только так: «.4|2|1.». Это значит, что сумма старших разрядов равна 2, сумма младших разрядов равна 4 или 14, а сумма средних может принимать любые значения от 10 до 18.

Подсчитаем, сколько есть возможных вариантов составления каждой из возможных сумм. Сумму 2 в старших разрядах мож-но получить только как 1+1. Для суммы 4 имеем 5 вариантов: 0+4, 1+3, 2+2, 3+1 и 4+0. Для суммы 10 минимальное из двух слагаемых равно 1, получается всего 9 вариантов: от 1+9 до 9+1. Рассуждая так же, для суммы 14 получаем 5 вариантов (от 5+9 до 9+5), а для суммы 18 — один вариант (9+9). Таким образом, существует 5+5=10 вариантов различных пар младших разрядов и 9+8+7+6+5+4+3+2+1=45 различных подходящих пар средних разрядов. Общее количество подходящих пар равно 1·45·10=450