На заре своего существования Би-би-си передавала картинки и звук по очереди: передатчик был всего один, звук и картинку одновременно транслировать не получалось.
Даны шесть слов: ЗАНОЗА ЗИПУНЫ КАЗИНО КЕФАЛЬ ОТМЕЛЬ ШЕЛЕСТ За один шаг можно заменить любую букву в любом из этих слов на любую другую (например, за один шаг можно получить из слова ЗАНОЗА слово ЗКНОЗА. Какое наименьшее число шагов нужно, чтобы сделать все слова одинаковыми (допускаются бессмысленные)? (Спойлер приветствуется)
На самом деле тут смысловые слова заданы только лишь для того чтобы отвлечь решающего... Задача равносильна следующей: дана таблиц 6х6, в каждой ячейке которой записаны любые символы. За один шаг можно заменить любой символ на любой другой.Какое наименьшее число шагов нужно, чтобы сделать все строки одинаковыми. Тут алгоритм прост: оставить в каждой графе те символы которых больше остальных в данной графе. - В графе 1 у нас по две З и К, т.е оставляем либо 2 З либо 2 К и делаем 4 замен; - В графе 2 у нас по две А и Е, т.е оставляем либо 2 А либо 2 Е и делаем 4 замен; - В графе 3 у нас с каждого символа по одной, т.е оставляем любую из них и делаем 5 замен. - В графе 4 у нас два Е, т.е оставляем 2 Е и делаем 4 замен; - В графе 5 у нас по две Н и Л, т.е оставляем либо 2 Н либо 2 Л и делаем 4 замен; - В графе 6 у нас два Ь, т.е оставляем 2 Ь и делаем 4 замен; итого у нас получилось: 4+4+5+4+4+4=25 замен При помощи приведённой ниже записи можно получить все возможное варианты слов для даной задачи, один из смысловых вариантов указан жирными буквами. З,К - А,Е - Н,П,З,Ф,М,Л - Е - Н,Л - Ь
Сообщение отредактировал marutand - Сб, 13.07.13, 00:11
