Здравствуйте, sergey2b, Вы писали:

S>>>>>Это задачка из К и Р
S>>>>>И человек знающий про обратную польскую Наталию решит ее за недолго
BFE>>>>Сколько дней? С учётом входных данных, например таких: длина числа не более 1024 знака. Длина выражения не более 10 гигабайт. Ну, а что? В условиях про формат ничего не сказано.
S>>>А какие операции доступны и можно ли использовать скобки в выражениях
BFE>>Числа только в десятичной системе исчисления?
S>В восьмеричной шестначтиричной или двоичной
Двоичные числа записывать в прямом, обратном или дополнительном коде?
Почему нет поддержки троичной системы?

Здравствуйте, xarcass, Вы писали:

X>лет 20 назад это было исключительно для скорости.
Это никогда не было искючительно для скорости, т.к. доступ к битам требовался всегда.

Здравствуйте, B0FEE664, Вы писали:


BFE>>>Числа только в десятичной системе исчисления?
S>>В восьмеричной шестначтиричной или двоичной
BFE>Двоичные числа записывать в прямом, обратном или дополнительном коде?

наверное более универсально с дополнением до двух

BFE>Почему нет поддержки троичной системы?

потому что я ее не знаю

Здравствуйте, Skorodum, Вы писали:

I>>А если микроконтроллер?
S>Тогда надо добавить в исходные условия: "есть микроконтроллеи и JIT где операция умножения дорогая и не оптимизируется...".
S>Иначе такие вопросы больше говорят о квалификации того, кто их задает.

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

I>>Цитирую себя "не все ведь к С++ сводится"
S>Gnu Compiler Collection...

Я все время думал, что gcc это gnu c++

Здравствуйте, Ikemefula, Вы писали:

I>>>Цитирую себя "не все ведь к С++ сводится"
S>>Gnu Compiler Collection...

I>Я все время думал, что gcc это gnu c++

C, C++, Objective-C, Fortran, Ada, Go, and D.

Здравствуйте, B0FEE664, Вы писали:

BFE>>>Сколько дней? С учётом входных данных, например таких: длина числа не более 1024 знака. Длина выражения не более 10 гигабайт. Ну, а что? В условиях про формат ничего не сказано.
Тё>>Стек ведь необязательно держать в памяти. Можно завести в файле, и читать произвольный инпут. Сложность линейная.

BFE>Ага. И всё это расписать прямо на доске.

Тё>>Вот что делать с арифметической операцией над двумя числами в 1024 знака, это отдельная тема, к задаче не относящаяся.
BFE>Интересные новости про условия задачи!


Так ты сам усложнил задачу! В исходном сообщении было 2+2 и 2+2*3. Для этого достаточно встроенных операций и памяти под стек.

Здравствуйте, sergey2b, Вы писали:

BFE>>>>Числа только в десятичной системе исчисления?
S>>>В восьмеричной шестначтиричной или двоичной
BFE>>Двоичные числа записывать в прямом, обратном или дополнительном коде?
S>наверное более универсально с дополнением до двух

Без поддержки деления и чисел с плавающей точкой?
Нужна поддержка экспоненциальной формы для целых чисел?

BFE>>Почему нет поддержки троичной системы?
S>потому что я ее не знаю

А чего там знать-то: 0,1,2,10,11,12,20,21,22,100,101,... ?

Здравствуйте, Skorodum, Вы писали:

S>Замена умножения на сдвиг это разве оптимизация для стандартных CPU, компиляторов и С/С++? Я еще лет 10 назад пробовал разные варианты just for fun и выходило примерно шило на мыло

Помнится, во времена MS-DOS и 16-битных 80x86, был такой Watcom C Compiler, который считался очень крутым в плане кодогенерации. Так вот, он любил умножение на константу в виде последовательности сдвигов и сложений расписивать. Бывало, на полстраницы ассемблерного текста развернется. У древних x86 действительно был медленный умножатор, не то, что теперь.

Здравствуйте, Тёмчик, Вы писали:

BFE>>Ага. И всё это расписать прямо на доске.

Тё>>>Вот что делать с арифметической операцией над двумя числами в 1024 знака, это отдельная тема, к задаче не относящаяся.
BFE>>Интересные новости про условия задачи!
Тё>Так ты сам усложнил задачу!
Я? А вы предполагаете, что числа в выражении могут состоять только из одной цифры?

Тё>В исходном сообщении было 2+2 и 2+2*3. Для этого достаточно встроенных операций и памяти под стек.
В исходном сообщении было "2+2", "2*2", "2+3*2". Для этого вообще не нужно никаких операций кроме сравнения:

if ( expression == "2+2" ) printf("4");
if ( expression == "2*2" ) printf("4");
if ( expression == "2+3*2" ) printf("8");

В этот раз я ничего не усложнил?

Здравствуйте, alzt, Вы писали:

A>Мозг у людей вообще очень часто выключается. Это обычная эволюционная адаптация — глюкозу надо экономить.
A>Но человек, который не напрягает свой мозг, мне на работе не нужен. Человек, который не может это сделать даже на собеседовании — биомусор. Можно нагрузить его какой-то несложной работой, чтобы не повышать преступность, но мне кажется, сразу в биореактор.

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

Только тут важно учитывать тот момент, что иные кандидаты иные конфеты ни за что жрать не станут.

Здравствуйте, a7d3, Вы писали:

A>Это не работает. Потому что хороший специалист не станет тренироваться решать задачки на собеседованиях, а тот человек, который работать не умеет и ничего из себя не представляет — будет смотреться замечательно на фоне всех остальных. Поскольку у него выбора иного нету.

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

Здравствуйте, wraithik, Вы писали:

W>Интересно, почему мониторы были 80*25, а не 64*32 или 128*32.... Сдвиг вроде быстрее.

Потому, что в перфокарте было 80 символов, а 24 было разумным компромисом между удобством использование и ценой изделия. Почему на PC 24 превратилось в 25, я не знаю, но предполагаю потому, что 25 — это почти 24, и при этом хорошо согласуется с телевизионным стандартом по числу строк.

Здравствуйте, xarcass, Вы писали:

X>Кто в своей повседневной работе использовал разворот односвязного списка — пусть первый бросит в меня камень.

Я использовал. Подставляй голову.

P.S. Я даже умудрился в повседневной работе использовать функцию, которая переставляет местами две "половины" массива разного размера, используя O(1) дополнительной памяти и за время O(n):

[AAAAA][BBBBBBBBBBBBBB] -> [BBBBBBBBBBBBBB][AAAAA]

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>При объединении пары списков один из них нужно развернуть.

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

Здравствуйте, B0FEE664, Вы писали:

это же тест на один час а не курсовая работа

Здравствуйте, Gradiens, Вы писали:

G>неплохо, если задача сразу принадлежит обеим категориям. Пример: найти все вхождения подстроки в строке.

А тебе как больше понравится, strstr в цикле, или алгоритм Морисса-Пратта на пальцах объяснить?

P.S. Того, кто применил бы алгоритм Морисса-Пратта в маловажных по скорости задачах в боевом коде, я бы убил на месте

Здравствуйте, Gradiens, Вы писали:

G>Ну, конечно, сдвиг много эффективнее. Если не ошибаюсь, он вообще за один такт выполняется.

А за сколько тактов выполняется умножение на современном Пентиуме?

Здравствуйте, Pzz, Вы писали:

Pzz>Здравствуйте, Gradiens, Вы писали:

G>>Ну, конечно, сдвиг много эффективнее. Если не ошибаюсь, он вообще за один такт выполняется.

Pzz>А за сколько тактов выполняется умножение на современном Пентиуме?

Вот тут https://www.agner.org/optimize/instruction_tables.pdf пишут, что 1-7 в зависимости от процессора.

Здравствуйте, sergey2b, Вы писали:

Адептам разворота списка пора переходить в следующее измерение — задавать повернуть квадратную матрицу на угол кратный 90° inplace, без использования дополнительной памяти.

Или оставаться в 1D, но двигаться дальше — циклический сдвиг массива на k N позиций влево или вправо, само собой, тоже inplace.

Здравствуйте, Pzz, Вы писали:


Pzz>Да вообще, если читаешь откуда-нибудь односвязанный список, то проще построить его задом наперед, а потом развернуть.

В таком случае, где у дождевого червяка списка голова, а где хвост — это всего лишь условность, зависящая от направления движения.