VI синхронный турнир «Знание – Сила». Тур 2. Вопрос 20

Вопрос 20: ИКС ИГРЕКА для «ИКС» и «ИГРЕК» можно записать как Х [икс]. Напишите слова, которые мы заменили ИКСОМ и ИГРЕКОМ.

Ответ: расстояние, Левенште́йн.

Зачёт: точный ответ.

Комментарий: Расстояние Левенштейна, как и чуть более известное расстояние Хэ́мминга – число позиций, в которых соответствующие символы двух слов одинаковой длины различны, только расстояние Хэмминга определено для слов одинаковой длины, а для расстояния Левенштейна равенство длин необязательно. Расстояние Левенштейна для слов «расстояние» и «Левенштейн» равно 10 (они различаются всеми буквами, которых в этих словах по 10), что можно записать как Х.

Источник(и): https://ru.wikipedia.org/wiki/Расстояние_Левенштейна

Автор: Дмитрий Слободянюк (Краков)