Сложность вычисления школьных примеров
Калькулятор дает оценку сложности вычисления примеров школьных задач. Может быть использован для сравнительной оценки сложности вариантов школьных заданий.
Данный калькулятор пытается оценить сложность вычисления без калькулятора (на листочке) задач с использованием арифметических операций сложения, вычитания, умножения и деления.
Калькулятор определяет количество элементарных операций в примере, дает условную сложность выраженную в миллисекундах, требуемых для вычисления примера. Сложность складывается из суммы элементарных операций, помноженных на коэффициент сложности (время в миллисекундах, требуемое для выполнение операции). Расшифровка элементарных операций дается в таблице в нижней части калькулятора.
Оценка сложности арифметических операций
Расшифровка операций с указанием сложности.
++ сложность 200, увеличение на единицу, например, при умножении 2003000 - будет одно умножение 23 и 5 раз выполнится подсчет нулей
+ сложность 500, элементарное сложение например 5+4
- сложность 500, элементарное вычитание, например 3-2
* сложность 1000, элементарное умножение, например 2*2
/ сложность 1000, деление — операция деления сводится к последовательном выполнении операций умножения и вычитания, при этом мы прикидываем всякий раз какой множитель необходимо выбрать, чтобы произведение получилось чуть меньше или равно текущего делимого. Эта элементарная операция подсчитывается в данной колонке. Необходимые умножения и вычитания подсчитываются дополнительно.
0+ сложность 100, сложение с нулем — частный случай выделен отдельно, так как это более простая операция чем сложение.
0 сложность 100, подстановка нулей
°+ сложность 700, сложение с переносом единицы, например 16+7 — содержит две операции — элементарное сложение и перенос единицы в следующий разряд.
=0 сложность 200, сокращение — операции вычитания равных величин, например 100-100
°- сложность 600, заем единицы при вычитании, например при вычитании 11-9 будет выполнен один заем и одна операция вычитания.
** сложность 400, повторное умножение. часто случается, что при выполнении элементарных ( и не только ) операций умножения выполняются одни и те же операции. Например 2533 будет содержать два элементарных умножения и один повтор, мы просто можем переписать результат умножения 253 еще один раз.
*0 сложность 100, частный случай умножения на ноль
*1 сложность 200, частный случай умножения на единицу
°* сложность 700, перенос при умножении, например 234 — два элементарных умножения плюс один перенос (1) при умножении 34
+- сложность 300, смена знака
<> сложность 500, перестановка вычитаемых, выполняется если мы пытаемся вычесть из меньшего большее
. сложность 500, операций с плавающей точкой
Рассмотрим вычисление сложности на примере (4567+987-8354)*32/25:
Пример содержит все четыре арифметических операции.
Сначала выполняется сложение 4567+987=5554
Как видим, в этом примере имеется три элементарных сложения: 7+7, 6+8, 5+9, при выполнении каждого из которых осуществляется перенос единицы в старший разряд.
Затем вычитание 5554-8354=-2800
Так как из меньшего вычитается большее число, результат получается отрицательным, перед вычитанием выполняется перестановка операндов. Первые два разряда 5,4 сокращаются, затем при вычислении 3-5 осуществляется элементарное вычитание с займом единицы, затем просто вычитание 8-1-5=2.
Третьим действием выполняем умножение -2800*32=-89600
Так как первый множитель заканчивается нулями, выполняем подсчет их количества, чтобы в конце умножения приписать нули к результату. Затем умножаем 2832. При умножении на 38 и 28 выполняется перенос в след. разряд. 22 и 2*3 — просто элементарные умножения. Итого 4 элементарных умножения, 2 переноса, 2 подсчета.
Последнее действие — деление -89600/25=-3584
На каждом шаге деления осуществляется подбор множителя таким образом, чтобы произведение его на делитель было близко к числу, составляемому первыми разрядами текущего остатка от деления. Эта операция засчитывается как элементарное деление, после чего выполняется умножение и вычитание, сложность которых рассчитывается по аналогии с предыдущими шагами.
В частности при делении первых разрядов (86) на 25 выбираем множитель = 3. Далее производится умножение 25*3-75, далее вычитание 89-75=14.
Итого при вычислении 89600/25 имеем: 4 деления и 4 вычитания, 8 произведений, 3 сокращения, два умножения с переносом, при умножении с переносом осуществляется одно сложение.
В конечном итоге в ходе вычисления всего примера произведено 52 элементарные операции — с учетом обозначенных весовых коэффициентов, общая сложность составляет 28500. Таким образом для решения данного примера понадобится примерно полминуты (28.5 секунды).
P.S. Все временные оценки и сам алгоритм вычисления сложности сделаны на основе субъективных предположений автора, комментарии и замечания приветствуются.
Комментарии