|
Название: Почтовая задача Отправлено: Overseer от Февраль 22, 2011, 12:55:23 Как-то с братом сидели за решением лабораторной работы и придумали такую задачу:
всем нам известен шрифт почтового индекса РФ: (http://cg.scs.carleton.ca/~luc/IrisCRM--IrisCRMZipCodes-2011.png) из выше-описанных символов будет учитывать лишь цифровые: 0..9 Каждая цифра задана сочетанием 9 черточек, закрашенных или не закрашенных. Но мы можем определить цифру по гораздо более меньшему количеству этих черточек: так, например, если мы имеем нижнюю диагональную черточку, мы знаем, что это цифра 2,3 либо 9. Если у нас также есть незакрашенная центральная черточка (горизонтальная), то мы точно знаем, что имеем 2. Значит мы можем определить цифру 2 по маске, содержащей 2 черточки (нижнюю диагональную и центральную вертикальную) Допустим, что нам надо определить минимальное количество черточек, необходимое для создания маски, с помощью которой мы сможем различить любую цифру. Внимание, вопрос: что это за количество, сколько вариантов масок с этим количеством черточек существует и что это за маски? Название: Re: Почтовая задача Отправлено: Overseer от Февраль 22, 2011, 14:42:48 upd.
Название: Re: Почтовая задача Отправлено: Um_nik от Февраль 22, 2011, 14:47:48 Из 5 черточек получилось =)
Название: Re: Почтовая задача Отправлено: Overseer от Февраль 22, 2011, 14:51:41 напомню, что необходимо доказать, что количество черточек минимально, найти все возможные варианты и доказать, что больше их нет (:
Название: Re: Почтовая задача Отправлено: Um_nik от Февраль 22, 2011, 14:53:47 Я просто делюсь мыслями
Название: Re: Почтовая задача Отправлено: ☭-Изделие 20Д от Февраль 22, 2011, 17:17:20 Название: Re: Почтовая задача Отправлено: Леший от Февраль 22, 2011, 17:22:23 Забавно, по-моему первый шаг очевиден :laugh:
Название: Re: Почтовая задача Отправлено: Overseer от Февраль 22, 2011, 17:23:56 предлагаю ввести единую систему, чтобы легче было обозначать черточки:
===1=== || || 2 3 4 || || ===5=== || || 6 7 8 || || ===9=== Название: Re: Почтовая задача Отправлено: Overseer от Февраль 22, 2011, 17:26:52 Название: Re: Почтовая задача Отправлено: VVV от Февраль 22, 2011, 17:41:06 Достаточно четырех. Очевидно, что трех не хватит, т.к. 2^3<10. Сравнивая 0 и 8, получим, что есть "5" (по системе Overseer'а). Сравнивая 5 и 8, получим, что есть или "4", или "6". После небольшого перебора получим 5 вариантов: 1) "1457", 2) "1458", 3) "4568", 4) "4567", 5) "4579".
Название: Re: Почтовая задача Отправлено: Um_nik от Февраль 22, 2011, 17:47:02 /me наверное уже задолбал, но: Вместе с ВиталикомНазвание: Re: Почтовая задача Отправлено: Overseer от Февраль 22, 2011, 17:50:57 Достаточно четырех. Очевидно, что трех не хватит, т.к. 2^3<10. Сравнивая 0 и 8, получим, что есть "5" (по системе Overseer'а). Сравнивая 5 и 8, получим, что есть или "4", или "6". После небольшого перебора получим 5 вариантов: 1) "1457", 2) "1458", 3) "4568", 4) "4567", 5) "4579". 5 вариант - неверен. 5 и 6 неразличимы. А так все супер: именно такого решения я и ждалНазвание: Re: Почтовая задача Отправлено: Леший от Февраль 22, 2011, 18:36:20 Очередное "спасибо Вилли"
Название: Re: Почтовая задача Отправлено: Les от Февраль 22, 2011, 19:16:51 Очередное "спасибо Вилли" ;DНазвание: Re: Почтовая задача Отправлено: Overseer от Февраль 22, 2011, 19:19:27 Виталик, может стоит кинуть всю Назву под хайд программкой Гийомчика? (:
З.Ы. ну кроме меня :tianchik: Название: Re: Почтовая задача Отправлено: Леший от Февраль 22, 2011, 19:29:15 Виталик, может стоит кинуть всю Назву под хайд программкой Гийомчика? (: Зачем всю? Трёх пока достаточно. |