Mrrl

Некоторые стандартные структуры и алгоритмы знаю. Но в работе использую редко: обычно ситуации возникают такие, что непосредственное применение стандартного алгоритма будет не очень эффективным (или по какой-то причине вообще не подойдёт), так что приходится строить более специальные структуры и алгоритмы - обычно как комбинацию стандартных приёмов, но не обязательно.
Из стандартных приходилось писать, разве что, приоритетную очередь: почему-то в C# её не сделали. И QR-алгоритм для собственных значений матрицы (про мелочи типа многомерного метода Ньютона не говорю - они попадаются регулярно, и каждый раз со своими особенностями).
Сортировку в последний раз писал с полгода назад. Получился монстр на полтысячи строк, но он работал.
Сортировку пузырьком (или простыми вставками) приходится писать когда по какой-то причине неудобно вызывать стандартный Sort. Например, при сортировке фрагмента массива с нестандартной функцией сравнения - опять же, в C# этот метод не вывели. Там проще написать три строчки в коде, чем оформлять класс-компаратор.

Если надо, чтобы кривую можно было провести через любую точку квадрата, то гипербола, пожалуй, лучше. Уравнение выглядит привлекательно: (a^2-1)*x*y+(x-a^2*y)=0, найти значение a для любой точки, через которую проходит кривая, несложно. Немного сложнее её нарисовать, чтобы точки были расположены с нужной густотой.
Я думал над чем-нибудь вроде y^a+(1-x)^a=1, но оно вряд ли подойдёт, хоть и симметрично: семейства кривых при a<1 и a>1 получаются не симметричными друг другу.

На C это бы выглядело так:

int k=21,m=10,s,h;
	for(s=(1<<m)-1;s<(1<<k);){
		printf("%x ",s);
		h=s&-s;
		s+=h;
		s+=(s&-s)/(2*h)-1;
	}
	printf("\n");

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

В качестве расстояния можно взять что-нибудь вроде суммы модулей разностей положения каждого элемента в этих перестановках. То есть, если A, B - исходные перестановки, а A*, B* - обратные к ним, то dist(A,B)=sum_k |A*(k)-B*(k)|.
Для перестановок 9 5 4 1 2 3 6 8 7 и 9 7 4 1 3 8 6 2 5 это будет 0+3+1+0+7+0+7+2+0=20.

Если есть память N*2^N, где N - число городов, то можно воспользоваться динамикой по набору пройденных городов плюс последнему городу, где оказался коммивояжер. Для каждого такого сочетания запоминаем минимальное количество топлива, которое потребовалось, чтобы добраться до этой ситуации и город, из которого приехали в последний город. Потом для всех ситуаций проезжаем из последнего города по всем рёбрам, и попадаем в ситуации, где посещённых городов на 1 больше. Снова для каждой находим оптимальный (по топливу) путь, по которому мы туда попали... и так, пока топливо не кончится. После чего проходимся по всему списку, и смотрим, где больше собрано призов.
До 20-25 городов должно работать разумное время. Дальше придётся искать эвристики.

Если искать ответ в виде формулы - то [n*(n+2)*(2*n+1)/8]
Там для чётных и нечётных n получаются разные серии, поэтому приходится брать целую часть (или мудрить с (-1)^n).

Не получится. Нужен неприводимый многочлен, а x^5+x+1=(x^2+x+1)*(x^3+x^2+1).

Без априорной вероятности тут тяжело. Одно наблюдение (или любое число наблюдений) может уточнить вероятность той или иной ситуации, но определить её с нуля не сможет.
Например, в случае лотереи. Одно дело, когда вы считаете, что вероятность выигрыша может быть любой, скажем, от 1/100 до 1/1000, причём вероятности этих значений примерно одинаковы. Тогда, после своих наблюдений, вы можете сказать, что вероятность, скорее всего, близка к 1/550, и даже определить распределение этой вероятности. Другое дело, когда вы знаете, что в лотерее может быть вероятность выигрыша только 1/200, 1/500 или 1/1000, но не знаете, в какую из лотерей играете (хотя шансы на то, что вам подсунули каждую из них, равны). Тогда ваши наблюдения покажут, что вероятность, скорее всего, 1/500 (а вовсе не 1/550 - так как такого исхода в списке не было).
Так что надо взять или придумать априорные вероятности моделей, и воспользоваться формулой Байеса.

Если в формулировке "расставить знаки, чтобы получить 100", то у меня осталось что-то такое:
https://www.dropbox.com/s/vktq0cllod4d34s/LuckyTic...

Отсортировать в порядке убывания, потом первые два элемента положить в разные кучки, а каждый следующий - в ту из кучек, где сумма на данный момент меньше. Работать будет не всегда (например, 25,25,20,20,9,1), зато не требует перебора.

Боюсь, что количество вариантов, даже если искать минимальные, будет сравнимо с 2^80 (или, хотя бы, 2^60) - замучаетесь искать. Но если очень хочется, то можно попробовать так:
- пусть у вас есть решатель (оптимизированный до предела), который по заданному набору клеток говорит ответ - 0 решений, одно или больше одного.
Ищете перебором по дереву. Сначала про первую клетку предполагаете, открыта она или нет, потом для обоих случаев - про вторую, и т.д.
Для любого набора открытых клеток в процессе перебора есть не меньше двух решений (иначе если оно одно - мы получили вариант ответа, а нуля не бывает, мы идём от известного решения).
Когда мы решаем, открывать ли следующую клетку, делаем следующее:
1) предположим, что мы не хотим её открывать. Откроем все клетки, идущие за ней, и посмотрим, сколько у нас решений. Если два - значит эту клетку нужно открыть обязательно, если нет, то можно и не открывать.
2) посмотрим, нужно ли открывать эту клетку. Для этого подставляем в неё по очереди все цифры, кроме правильной, и смотрим, есть ли решение. Если хотя бы один раз оно есть, то клетку можно и открыть. Если ни разу решения не нашлось (например, эта клетка - 9-я в ряду, в котором уже открыто 8 клеток), то открывать её не нужно, поскольку иначе набор будет не минимальным.

Таким образом, на каждом шагу мы получаем либо один, либо два варианта дальнейшего перебора. По хорошему, после того, как мы открыли очередную клетку, надо перепроверить все открытые ранее клетки методом из пункта (2), и если хотя бы одну из них открывать было не надо, значит, мы уже в не минимальном наборе, и продолжать перебор этой ветки не имеет смысла. Может быть, делать такую проверку не каждый раз (она очень дорогая), а, например, если число открытых клеток делится на 4.