Есть ли универсальный алгоритм для задач 'Можно ли переложить 1 спичку, чтобы равенство стало верным'?

Мне кажется, это слишком в лоб.

Ксения, вам не кажется. Это настолько в лоб насколько возможно. Потому что я бы наверно смог это запрограммировать, ну, скажем, за пару часов. А имея хоть какое-то решение можно думать над его улучшением.

Есть ли универсальный алгоритм для задач 'Можно ли переложить 1 спичку, чтобы равенство стало верным'?

это NP-полная задача

Даша Циклаури, вопрос был не "какова сложность", а "как это сделать программно".

Где в отладчике отображается, что в этой программе максимальный элемент массива равен 9?

извините за дотошность

Мария, наоборот.

А теперь походит на правду?

На этой картинке -- да. Потому что в конце ds:si должен указывать на последний элемент массива, за которым идёт Max.

Почему отличаются значения в регистрах: sp, ds, es, ss, cs?

Значения сегментных регистров отличаются, потому что состояние твоего ms-dos не совпадает в точности с состоянием моего. Сегментные регистры позволяют загружать дос-программу в разные места памяти без изменений в самой программе.

Почему отличается sp -- хз. Информация о том, как инициализировать sp находится в заголовке exe-файла, в моём там записано (по смещению 0010h) 0x200:

$ hexdump -Cv TEST.EXE 
00000000  4d 5a 68 00 02 00 02 00  20 00 21 00 ff ff 07 00  |MZh..... .!.....|
00000010  00 02 00 00 00 00 00 00  3e 00 00 00 01 00 fb 50  |........>......P|

что совпадает с наблюдаемым в отладчике. Непонятно, почему линковщик записал туда 0x200, когда в исходнике написано .stack 100h. Возможно это какая-то особенность tasm4.

Где в отладчике отображается, что в этой программе максимальный элемент массива равен 9?

на нижнем сегменте -> правая кнопка мыши -> goto...

Мария, а прямо на твоей картинке, в левом нижнем углу написано: "Ctrl: G -- Goto". Ты не знала, что ^G -- это запись для Ctrl + G?

Где в отладчике отображается, что в этой программе максимальный элемент массива равен 9?

Мария, на последней картинке у тебя другая программа, с другим расположением данных в памяти. Max в ней -- по адресу ds:0010, а не то, что ты обвела. Если это лаба, то на месте препода я бы сделал вывод, что понимания того что происходит у тебя нет.

Где в отладчике отображается, что в этой программе максимальный элемент массива равен 9?

мой отладчик этого не отображает

Мария, а я беру твою программу, загружаю в TD, перехожу табом в окно внизу, нажимаю ^G, пишу в окошке ds:0 и вижу картину маслом:

-- пять элементов массива и следом за ними -- максимум.

Где в отладчике отображается, что в этой программе максимальный элемент массива равен 9?

я нашла ошибку. Если в 12-той строке mov CX, 4 вместо 4, кол-во итераций поставить 5, то программа

Мария, а, т.е. ты код не читаешь, а просто методом тыка меняешь что попало, чтобы где-то появились знакомые цифры? Ну чо, тоже подход.

Но ты имей в виду, что mov cx, 4 было правильно.

Где в отладчике отображается, что в этой программе максимальный элемент массива равен 9?

Мария, по-моему с твоей программой полный порядок, но что-то мешает тебе посмотреть в память по адресам ds:0000 ... ds:000a.

Как вычислить итоговую сложность?

как вывод элемента по индексу дает сложность O(log (n)) ?

dmshar, неправильный акцент. Правильный акцент -- как вывод индекса дает сложность O(log (n)). Поскольку индекс пробегает значения от 0 до n-1, в нём в худшем случае log(N) цифр. Это, конечно, не имеет значения для типов фиксированной ширины, но чисто теоретически...

Как вычислить итоговую сложность?

print(i, a[i])
выполняется за константу

Дмитрий Подболотов, ну если уж совсем строго, то за O(log (n)) выполняется print.

Как не откладывать обработку прерывания в долгий ящик?

Tw1ce, да

При возведении в какую степень потребуется больше операций?

Но результат это не меняет

97 степень можно получить за 8 умножений, в некотором смысле меняет...

При возведении в какую степень потребуется больше операций?

Для этого понадобится столько умножений, сколько единиц в двоичном предсьавлении числ

На одно меньше, потому что одно умножение добавляет одну единицу. Можно начать не с 0 единиц, а с одной.

Почему скрипт написанный на Bash отказывается работать?

А чем же он тогда может быть?

да чем угодно. Вот у меня в debian 9, например:

$ ls -la /bin/sh
lrwxrwxrwx 1 root root 4 Jan 23  2017 /bin/sh -> dash

где хранятся эти самые логи отладки скриптов?

нигде не хранятся, выводятся в stderr во время выполнения.

Почему в Alpine Linux невозможно ничего написать в консоли?

.то что в квадратных скобках - ответ по умолчанию при нажатии ENTER.

В квадратных скобках init-скрипты OpenRC пишут свой статус.

На старте служб происходит ошибка...
Должно быть приглашение к вводу пароля...

Как ты понял, что там происходит и особенно -- что там должно быть?

Cat в переменную. Freebsd?

cat /dev/urandom | tr -d -c '0-9' | fold -w 10 | head -1 | awk '{print substr($0, 1, 2)}'

cat /dev/urandom | tr -d -c '0-9' | head -c2?

Сильно ли print тормозит выполнение программы?

ЯП какой?

sim3x, почти не зависит же, вывод будет тормозить, на консоль -- больше, в файл -- меньше.

Почему нельзя скомпилированную программу запустить на другой ОС?

Василий Мельников, можно, но это малость ортогонально. По этой оси можно провести такие границы: оригинальный машинный код выполняется в обычном режиме процессора (WINE и WSL а так же WoW64 из этой серии) / оригинальный машинный код выполняется в аппаратной виртуализации (XEN, QEMU + KVM, WoW (16-битный, для доса) из этой серии) / машинный код выполняется в виртуальной машине с JIT (QEMU-user и подозреваю что DOSBOX из этой серии).

Почему нельзя скомпилированную программу запустить на другой ОС?

В разных ОС разные форматы исполняемых файлов.

Денис Загаевский, что может помешать ОС поддерживать несколько форматов? Вон, винда до недавнего времени поддерживала одновременнно com, MZ-, NE-, LE-, 32- и 64-битные PE-exe. Линукс так вообще имеет /proc/sys/fs/binfmt_misc -- поддерживай сам что хочешь.

Как работает арифметика указателей Си?

В общем случае это не так, правильный ответ будет 3*sizeof(char).

Во всех стандартах С и С++ sizeof(char) == 1.