Брутально и бессердечно о программировании и проектировании
ГлавнаяФорумАртПаттерныАнтипаттерныЗаметкиВопрос-ответКнигорецензииСправочная

10. Задача о переводчиках

Задача очень простая, но имеющая определенный смысл.
Представьте себе, что к вам в гости пришли N иностранных гостей, и все они говорят на разных языках, причем ни у одной пары гостей языки не повторяются. Вы хотите, чтобы любой гость имел возможность пообщаться с любым другим гостем, но при этом таким образом, чтобы никто из гостей, кроме собеседников, не смог понять смысла разговора. Предполагается что гости не знают иностранных языков.
В вашем распоряжении есть кадровое агентство, в котором вы можете набрать неограниченное количество совершенно любых переводчиков из любых стран. При этом все переводчики знают ровно два языка — родной и выученный.
Какое минимальное количество переводчиков вам понадобится, если N > 2 ?
Вот все варианты ответа, среди которых есть и правильный.
Можно на каждую пару гостей нанять отдельного переводчика. Для этого понадобится N * (N - 1) / 2 переводчиков. Математически это называется «полный граф». Если к вам пришли 100 гостей, то вам понадобится 4950 переводчиков.

Можно посадить гостей за круглый стол и посадить по одному переводчику между каждой соседствующей парой гостей таким образом, чтобы каждый переводчик знал языки своих соседей. В этом случае вам понадобится N переводчиков, однако в таком случае общение будет похоже на игру в испорченный телефон. Из-за этого часть гостей, не участвующих в беседе, будет понимать, о чем общаются собеседники. Некоторых гостей это может не устроить.

И, наконец, третий и правильный вариант. Вы выбираете такой язык, на котором не говорит ни один из ваших гостей. Пусть это будет язык «X». После этого идете в агентство и нанимаете по одному персональному переводчику на каждого из гостей. При этом родным языком у каждого из переводчиков является «X», а выученным — язык гостя, за которым закреплен переводчик. Итого — N переводчиков. Таким образом общение гостей будет происходить через преобразование в никому непонятный язык «X». Гость «A» говорит своему переводчику фразу, переводчик переводит ее на язык «X» и сообщает ее переводчику гостя «B», который, в свою очередь, сообщает ее гостю «B» на его родном языке.

Задача о переводчиках это почва для размышлений, которую я предлагаю тем, кто решил воспользоваться мультиметодами и диспетчеризацией.

Оглавление
Статистика
© 2007—2009 Inside C++ Коммерческие услугиКонтактная информация

Hyundai. раскрутка сайта и продвижение сайтов. аритмия