Кирилл: 30-летней давности - это ещё ничего. Фортран-4 или -77 был не таким уж сложным. Common-блоки, да equivalence... А вот что они напридумывали с тех пор, страшно даже представить. Как в фортран удалось добавить alloc?
Кстати, я не говорил, что 1000 строк - это одна функция :)
Кирилл: А вот разделять математику и оптимизацию алгоритма - не очень удачная идея. Знание возможностей оптимизации очень сильно влияет на выбор алгоритма и деталей его... даже не реализации, а декомпозиции, порядка обработки и выбора подалгоритмов. Человек, который знает что-то одно, скорее всего, не найдёт правильного пути, даже с помощью партнёра, который знает другое. Деревья возможностей слишком широки, и найти оптимальную ветку между ними совсем непросто.
Кирилл: Любая пещера подойдёт :) Я последние 15 лет занимаюсь одним и тем же достаточно наукоёмким проектом. Периодически отдельные его куски, да и архитектура в целом, перетряхиваются, но необходимости знать, чем отличается какой-нибудь "посетитель" от "посредника" как-то не возникает. И без современных подходов, в общем, пока обходимся.
bobrovskyserg: Да, там все траектории распадаются на три дуальных графа:
43333333 / 33333334
3******3 / 4*****4
3*****4 / 4*****3
В первом получается (n,7*n), во втором - (10*k,5*k) для k=n/2 и либо (10*k+7,5*k+1), либо (10*k+3,5*k+4) для k=(n-1)/2, в третьем - (3*n,4*n).
bobrovskyserg: При ширине 50 - получается 6204 разных конфигураций кирпичей в ряду. Сосчитать матрицу нетрудно, но перемножать их... Правда, возможно, там будет очень мало допустимых траекторий между рядами, и матрица распадётся на много маленьких.
А с числом наборов - всё плохо. Единственное возможное спасение - если для каждого типа верхнего ряда при определённой высоте удастся сказать "возможны все наборы от ... до ..., кроме небольшого количества в начале и в конце диапазона, с определёнными смещениями от начала и конца соответственно". И доказать, что формулы выполняются при всех переходах.
bobrovskyserg: Я думал обойтись одним шагом метода Ньютона, но его не хватит - там в начале или в конце перебора число, из которого извлекается корень, может очень быстро измениться. Хотя можно проверить для двух самых маленьких чисел с помощью sqrt, а дальше по непрерывности.
В общем, если p*q==N, то (p+q)^2-(p-q)^2==4*N, а p+q у нас лежит между n*sqrt(2) и n*1.5. Перебираем их, проверяем, извлекается ли корень из (p+q)^2-4*N, и если да - печатаем ответ.
brainick: Но ведь чем больше освоенная область, тем больше её граница с неосвоенным. И тем больше нужно "первопроходцев", чтобы долбить её дальше. Откуда "малое количество"?
brainick: вопрос не выглядит глупым. А если его задаст доктор физ-мат наук 50 лет, который решил, что наука его недостаточно хорошо кормит? В каком направлении IT ему развиваться, чтобы оказаться востребованным за разумное время? Понятно, что у студента возможностей гораздо больше, но при указанных ограничениях ответы должны получиться близкими. И про доктора я очевидных решений не вижу.
Придумывать алгоритмы это хорошо, но на икру и устриц только на этом не заработаешь :( Для алгоритмов тоже нужна цель - и люди (или проекты), которым именно эти алгоритмы нужны.
То, что "нужна математика" это хорошо. А паттерны там спрашивать будут? А unit-тесты? Или знания математики и умения написать работающую программу на фортране на 1000 строк достаточно?
AVKor: Проблема - как исправить одну ошибку, чтобы все четыре контрольные суммы стали нулевыми? Ведь вы утверждаете, что невозможных пакетов нет. И в "совершенных кодах", к которым относится код Хэмминга, их действительно не должно быть.
Сумма информационных битов в маске должна быть равна контрольному, которому эта маска соответствует. Или, что то же самое, сумма контрольного и информационных битов должна быть равна нулю. То есть, b1+b3+b5+b7+b9+b11=0 или b1=b3+b5+b7+b9+b11 (b1 - контрольный). А если у вас b1=b1+b3+b5+b7+b9+b11 (и так же для остальных контрольных битов), то это будет выполняться только когда все информационные биты равны нулю. Вряд ли от такого кода будет много пользы.
AVKor: да, в этом примере неправильный бит при обоих порядках окажется одним и тем же. Но вот набор информационных битов будет разным.
А насчёт невозможного сочетания - возьмите такую последовательность:
1 0 0 1 0 0 0 1 0 0 0 0
(контрольные биты - 1,2,4,8, бит 1 - самый левый). В каком бите ошибка?
AVKor: "Что такое "стандартный" код Хэмминга, я не знаю. Не встречал такого именования ни в одном источнике." - я говорю именно об этом. В вопросе фигурирует "сообщение, закодированное стандартным кодом Хемминга" - я пытаюсь выяснить, что это значит. Даже если предположить, что это код, построенный по алгоритму, описанному в русской и английской Вики - с контрольными битами 1,2,4,8 - то неизвестно, какой бит имеет номер 1 - первый или последний.
Что касается "оставшихся битов" - я смотрел на это определение:
For each integer r ≥ 2 there is a code with block length n = 2^r−1 and message length k = 2^r−r−1. Hence the rate of Hamming codes is R = k/n = 1 − r/(2^r−1), which is the highest possible for codes with minimum distance 3 (i.e., the minimal number of bit changes needed to go from any code word to any other code word is 3) and block length 2^r−1.
И примечание, что это "perfect code".
При r=4 получаем k=11 и длину блока 15 - и только. Никаких 12 бит не будет. В коде 8+4 обязательно окажутся "невозможные" сочетания, которые нельзя получить из правильных внесением одной ошибки.
AVKor: А что можно посчитать? Понятно, что можно сделать 4 контрольных бита и 8 информационных (объявив три оставшихся бита нулями). С тем же успехом можно взять 4 информационных бита и 8 контрольных - в любом случае, "совершенного" кода мы не получим, так что это будет уже не код Хэмминга.
А в книжке действительно описан "стандартный" код? Или просто одна из возможных реализаций?
Кстати, я не говорил, что 1000 строк - это одна функция :)