Например, такая дурацкая задача:
Последовательность X строится так, что X[n] - наименьшее натуральное число, которое делится на [sqrt(n)] и не встречается в этой последовательности раньше (что-то вроде 1,2,3,4,6,8,10,12,9,15,18...)
Требуется найти n-й элемент.
Если у нас есть память O(n), то всё просто - просматриваем предыдущие элементы, выбираем из них те, которые удовлетворяют условию, сортируем, берём первое число, которое условию удовлетворяет, но в отсортированной последовательности отсутствует. Получается примерно O(n^2*log(n)) операций (для этой задачи - даже меньше). Но если последовательность хранить негде, то её предыдущие элементы придётся вычислять. А для их вычисления - вычислять ещё более ранние. Получается примерно 2^n операций, а то и n! (ведь для поиска дырки перевычислять последовательность придётся несколько раз).
Возможно, у этой задачи есть математическое решение, для которого достаточно конечной памяти. Но первое условие всегда можно заменить на что-нибудь посложнее.
А что такое "нештатный режим"? Ведь даже ситуацию, когда какое-то важное оборудование выходит из строя, они считают "штатной", поскольку эта ситуация и действия, которые нужно совершить при её возникновении, прописаны в документации. Нештатная ситуация - это та, которая не предусмотрена вообще. Что в этом случае будут делать программы, предсказать совсем непросто.
Сначала надо разбить на максимальное число связных компонент с нулевой суммой весов в каждой - тогда останется меньше рёбер. А кроме того, если построить произвольное дерево, то веса в нём могут получиться отрицательными. Так что с этим придётся как-то бороться.
bobrovskyserg: «Различные злоумышленники, делающие вид, будто им удалось снестись с иным миром, и даже осмеливающиеся проповедовать мнимые доказательства его существования, а тем самым вводить в соблазн и себя, и других, неоднократно возмущали спокойствие в государствах Флатландии. Посему высокий Совет единодушно постановляет: в первый день каждого тысячелетия направлять префектам области Флатландии специальные предписания, дабы они со всей строгостью учиняли розыск таких злоумышленников и своей властью, минуя формальное математическое исследование, подвергали их уничтожению, буде они Равнобедренные Треугольники с любым углом при вершине, наказанию плетьми и заключению в тюрьму, буде они Равносторонние Треугольники, отправке в приют для умалишенных, буде они Квадраты или Пятиугольники. В случае, если злоумышленник окажется особой высокого ранга, то префекту надлежит препроводить его под стражей в столицу, дабы тот был подвергнут исследованию и предстал перед Высшим Советом».
Виталий Пухов: Здесь важно, что число - произведение различных маленьких простых чисел. Но добавление к произведению очередного числа P позволяет отсеять только 1-1/P оставшихся составных чисел, а произведение растёт очень быстро. Так что я думаю, что брать число больше 30030 особого смысла нет.
Flaker:
1) Не знаю. Оно ищется "из общих соображений", но какая-то общая база, наверное, нужна.
2) K - число кубиков, M - длина нижнего ряда. Понятно, что K не может быть меньше M (рядов отрицательной длины не бывает). Наибольшее число кубиков при заданной длине нижнего ряда равно M+(M-1)+(M-2)+...+2+1=M*(M+1)/2 - как сумма арифметической прогрессии.
3) ряд A[K,M] для очередного значения K надо заполнять для всех M от 2 до K-1. Потом определить, что A[K,K]=1.
4) В данном случае, с 1. В этой задаче нулевое число кубиков и нулевая длина ступеньки смысла почти не имеют. Впрочем, вы можете задать A[0,0]=1, величину A[K,M] считать как sum(A[K-M,r],r=0..M-1), и тогда A[K,K] будет считаться по общим правилам. Не уверен, нужно ли это.
iamsawich: Во времена MS DOS я бы просто писал в графическую память. Чуть позже - попытался бы разобраться с файлом conio.h, возможно, в нём было бы что-то нужное. Но есть ли прямой доступ к символам консоли в наше время, не знаю.
Если выводить с помощью стандартного потока вывода, то при заполнении последнего, 80-го символа строки консоли курсор переходит на 81-й символ, который физически находится в начале следующей строки. Соответственно, если строка была последней, то строчки сдвинутся вверх - без какого-либо явного перевода строки.
А какая связь между машиной Тьюринга и аппаратом, которым взламывалась enigma (кроме самого Тьюринга)? Что вообще общего между устройством машины Тьюринга и архитектурой фон Неймана? Ведь в МТ: память для программ и данных различна, программу редактировать нельзя; прямой адресации нет - доступна только ячейка под кареткой; никаких соглашений на представление данных тоже нет - они могут быть в любой удобной системе счисления и в любом удобном формате.
B@rmaley.e><e: Интересно, как будут выглядеть asm-вставки для компилятора с C на МТ. Или какой будет система адресации в процессоре, работающем с бесконечной памятью.
Сергей: Кроме XOR нужна загрузка константы 1. Иначе в ситуации, когда вся память заполнена нулями, вы ничего не сможете сделать. Вот с помощью NAND можно получить что угодно из чего угодно.
vaut: К сожалению, в C существует значение выражения sizeof(char*). Оно даёт ограничение на размер доступной памяти, и, соответственно, на длину ленты. И какой бы компилятор с C на любой компьютер - и даже на машину Тьюринга, у которой память бесконечна - вы не написали, создать программу, которая после компиляции сможет работать с бесконечной лентой, не удастся.
Вот в C#, если не пользоваться unsafe режимом, обратиться к памяти по явному адресу не получится. Поэтому, формально, можно создать односвязный список сколь угодно большой длины. А для машины Тьюринга большего и не надо.
Артем: Зачем писать точно такой же компилятор? Тем более под новый процессор, с новой системой команд? Кроме того, я написал "с языка, очень похожего на си". Не факт, что все особенности си (даже образца 1974 года) будут воспроизведены. Да это и не нужно: всё равно программ не осталось, так что совместимости не требуется.
