Блог пользователя promix17

Автор promix17, 10 лет назад, По-русски

Как лучше организовать вывод результата на С++? Когда я использую обычный вывод, то могу получить превышение TL на задачах с сложностью O(n):

cout << smth << endl;

Если же использовать printf, то решение проходит, однако я не хочу использовать printf.

Я так понимаю, что, по умолчанию, стандартный вывод записывается на диск всякий раз при получении символа новой строки. Верно ли это? Вопрос такой: какую функцию надо вызвать, чтобы изменить буферизацию стандартного выходного потока с построчной на блочную? Нужно решение как для Windowws, так и для Linux.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

Автор promix17, 12 лет назад, По-русски

Искал тут недавно список алгоритмически неразрешимых задач, и наткнулся на список в Википедии. Особенно меня удивила проблема о невозможности построения идеального архиватора. Никак не могу понять, что к чему. Задача: требуется написать программу, которая для любого входного файла напишет минимальную программу, выводящую этот файл. Утверждается, что это невозможно. Однако почему, например, не работает следующий алгоритм:

1) Положим текущим минимумом программу содержащую выходной файл и выводящую его на экран (это всегда возможно)

2) Переберём все программы меньшие данной и найдём минимум (таких программ конечное количество)

Что здеесь не так?

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

UPDATE1:

Всё, понял, спасибо всем за ответы. Невозможно выполнить шаг 2, т.к. невозможно перебрать все программы ввиду невозможности определить, завершаться они или нет за конечное время => данный алгоритм не завершиться за конечное время

UPDATE2:

Всё вышеперечисленное относится к идеальным машинам, имеющим неограниченное количество состояний. Однако такие машины физически не реализуемы. Итого некоторые алгоритмически неразрешимые задачи становятся решаемыми в реальном мире. Нет ли примеров таких задач, которые в принципе алгоритмически не разрешимы, но вполне себе решаются в реальном мире (не приближённо, а именно точно). Приветствуются примеры, имеющие суб-экспоненциальную сложность (если таковые имеются).

Полный текст и комментарии »

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится