А что, если мы хотим не только распознавать, но и исправлять одиночные ошибки? Сколько тогда будет валидных N-значных десятичных номеров?
Рассмотрим для начала трехзначные номера. Тут мы быстро обнаружим, что валидных номеров может быть не более чем 10, потому что одна и та же цифра не может повторяться ни в одной позиции. Действительно, если номера вида ABC и ADE оба будут валидны, то мы не сможем понять, как исправить номер ABE. Или, другими словами, хэммингово расстояние между двумя валидными номерами должно быть не меньше трёх.
А сколько можно построить четырёхзначных номеров, исправляющих одиночную ошибку замены? Ровно 100 или меньше?
This entry was originally posted at https://spamsink.dreamwidth.org/1208379.html. Please comment there using OpenID.