Сложность вычисления школьных примеров

Калькулятор дает оценку сложности вычисления примеров школьных задач. Может быть использован для сравнительной оценки сложности вариантов школьных заданий.

Эта страница существует благодаря следующим персонам

Anton

Создан: 2014-09-23 07:13:32, Последнее изменение: 2020-11-03 14:19:31
Creative Commons Attribution/Share-Alike License 3.0 (Unported)

Этот материал распространяется на условиях лицензии Creative Commons Attribution/Share-Alike License 3.0 (Unported). Это означает, что вы можете размещать этот контент на своем сайте или создавать на его основе собственный (в том числе и в коммерческих целях), при условии сохранения оригинального лицензионного соглашения. Кроме того, Вы должны отметить автора этой работы, путем размещения HTML ссылки на оригинал работы https://planetcalc.ru/3929/. Пожалуйста оставьте без изменения все ссылки на других авторов данной работы или работы, на основе которой создана данная работа (если таковые имеются в спроводительном тексте).

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

PLANETCALC, Оценка сложности арифметических операций

Оценка сложности арифметических операций

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



Расшифровка операций с указанием сложности.
++ сложность 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

-89600/25=-3584
-89600/25=-3584



На каждом шаге деления осуществляется подбор множителя таким образом, чтобы произведение его на делитель было близко к числу, составляемому первыми разрядами текущего остатка от деления. Эта операция засчитывается как элементарное деление, после чего выполняется умножение и вычитание, сложность которых рассчитывается по аналогии с предыдущими шагами.
В частности при делении первых разрядов (86) на 25 выбираем множитель = 3. Далее производится умножение 25*3-75, далее вычитание 89-75=14.
Итого при вычислении 89600/25 имеем: 4 деления и 4 вычитания, 8 произведений, 3 сокращения, два умножения с переносом, при умножении с переносом осуществляется одно сложение.

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

P.S. Все временные оценки и сам алгоритм вычисления сложности сделаны на основе субъективных предположений автора, комментарии и замечания приветствуются.

Ссылка скопирована в буфер обмена
PLANETCALC, Сложность вычисления школьных примеров

Комментарии