Трудный вопрос на собеседовании #6
Александр СкакуновОпубликовано 7.07.2008 в Статьи
Итак, мы продолжаем серию переводов цикла “Трудные вопросы на собеседовании“.
Задача #6
У вас есть плитка шоколада, состоящая из n×m прямоугольных сегментов. При условии, что можете отламывать один сегмент за один раз, сколько раз нужно отламывать, чтобы из изначальной плитки n×m получилась кучка сегментов 1×1? Сколько раз достаточно?
UPDATE: правильный ответ.
Загрузка ...Понравилась статья? Подпишись на обновления по RSS/E-mail
>> У вас есть плитка шоколада, состоящая из n×m сегментов. При условии, что можете отламывать один сегмент за один раз …
В такому формулюванні, очевидно, відповідь (n×m – 1). Але, думаю, малось на увазі, що можна робити за раз один прямий розлом будь-якої довжини.
Гм… более чем странное задание… интересно как можно отломать один сегмент НЕ из плитки 1хM или Nх1???
А если можно делать один прямой отлом – тогда ответ тоже очевиден – ………
Блин… посидел посчитал – как не отламывай (хоть по одному, хоть полосками, шириной в один сегмент – как в реальной жизин можно отломать)- всё-равно – количество = n×m – 1
Правильный ответ: положить плитку на стол и ударить головой. Итого: ноль отломов, один удар.
2 Стюард
Правильне формулювання наступне:
За один раз можеш ламати скільки завгодно сегментів, але тільки по прямій.
Наприклад, плитку 2*2 можна розламати двома варіантами (вертикально і горизонтально), але все одно вийде дві плитки по 1 * 2. Плитку 3 * 2 можна розламати кількома варіантами:
ХХХ X XX XX X XXX
ХХХ –> X XX or XX X or
XXX
А відповідь все одно (n×m – 1) і доведення цього досить просте – з кожним розломом кількість шматків збільшується на один.
Якщо я правильно зрозумів задачу, то відповідь буде [(n * m) / 2], де [x] – ціла частина x. Розфарбуємо нашу плитку у вигляді шахматки, тоді для того щоб наша плитка розпалася на кусочки розміру 1 на 1, достатньо відламувати всі кусочки зафарбовані тільки в білий або тільки в чорний колір. Оскільки можливі варіанти коли кількість білих та чорних клітинок буде відрізнятися рівно на один (при умові що n та m – непарні), то вигідніше буде вибрати конкретний колір, кількість плиток якого менша, тому ми беремо цілу частину від (n * m) / 2.
2 Olexiy.
В умові задачі сказано, що за раз можна відламувати один сегмент. У першому реченні визначено сегмент, як частину плитки розміру 1 на 1. Якщо ж малося на увазі інше, то Ваш розвязок правильний.
+1. Рейтинг этих “трудных вопросов” показывает, насколько они нужны здесь (сейчас – 1.4/5).
Ну тут можно и хитрее
Если можно ламать много сегментов одновременно, то выходит : (n-1)+(m-1) (Это количечсство всех полос в шеколадке, по которым мы и ламаем )
А если нельзя (тоесть за раз можно ламать один лишь сегмент), то n*m-1… Что Олексий очень красиво обьяснил
Нык1каво…
2 Всеволод – рейтинг минулих був набагато вищим, так що просто це питання не дуже
@7
Будь я владельцем сайта я бы так не думал: во-первых посещаемость у вопросов явно высокая, во-вторых контингент у них правильный в том смысле, что один из источников доходов — обьявления о работе и чем больше посетителей обеспокоеных этим вопросом тем лучше должны идти продажи.
А то что к разработке никакого отношения нет, ну так это уже другой вопрос.
и что ктото такой отстой на собеседовании спрашивает?
Имхо: авторы смотрите первую задачу из этой рубрики (про магов и гномов) на нее и равняйтесь.
На сколько я понял задачу, то следует доказать, что n*m-1 является как достаточной величиной, так и необходимой.
Достаточность доказывается просто:
n*m плитку делим (m-1) разломом на m плиток размером n*1. Чтобы разделить получившиеся плитки на куски размером 1*1, надо каждую плитку поломать (n-1) раз.
Итого: (m-1)+m*(n-1)=m-1+m*n-m= m*n-1, ч.т.д.
Необходимость доказывается сложнее – по индукции.
База индукции:
m=1, n=1, тогда S=m*n-1=1*1-1=0 – количество разломов.
m=2, n=1, S=2*1-1=1
Предположение индукции (n=1):
Утверждение верно при m=(k-1), т.е. S=1*(k-1)-1
тогда оно должно быть равно верно при m=k, т.е. S=1*k-1
Док-во: плитку размером k*1 можно разбить на две: 1*1 и (k-1)*1.
Т.о. кол-во разломов общее для двух плиток S(общ)=S(1)+S(2)+1(разлом на две плитки).
S(1)=1*1-1=0 – по базе индукции
S(2)=1*(k-1)-1 – по предположению индукции
В итоге: 0+1*(k-1)-1+1=1*k-1 ч.т.д.
Аналогичным образом по индукции доказывается для m-произвольного.
База: m, n=1, S=1*m-1 (верно по предыдущему доказательству)
Предположение: n=k, S=m*k-1
и надо доказать, что при n=k+1, S=m*(k+1)-1
PS: Если что не так. сильно не пинайте.
)), особенно необходимости. 
PPS: Очень хочется увидеть полное доказательство от автора
2Щетинин Сергей: Если б твои статьи так же бурно и вовлеченно обсуждали, материалы на сайте б несколько другими. Эти же задачки хоть понятны всем
Наивно ждать что сами они представляют большой интерес, можно их все сразу и на оригинальном сайте найти. Однако обсуждения самих задачек довольно интересные получаются как правило.
Сергей, так и я о том же =) В смысле что поржать с задачек можно, но это не значит что их нужно перестать публиковать.
2 Сергіям Волошину та Щєтініну.
Саме ця задачка, звичайно, не дуже вдала. Але взагалі задачки потрібні щоб побачити як людина думає, що вона знає, як підходить до розв’язку, як реагує на труднощі, що робить, якщо помилилась і т.п. І така задача + розмова за п’ять хвилин може дати більше інформації, ніж якщо людина буде дві-три години писати код (на що у багатьох не буде часу просто).
2 Сергіям Волошину та Щєтініну.
І, звичайно, вони популярні, бо доступні всім.
2 Дима
Про гномів, НМД, якраз теж не дуже
В задачі, бажано, щоб треба було писати код – хоча б три-чотири рядки. Так що я б питав одну з задач про обернення рядка і т.п.
(n-1)*(m-1)
если пожно вырезать середины, то надо резать в шахматном поядке, m*n/2
тут есть правильный ответ и он n*m-1 ….. ето обьяснил Олексей .
вопросы как на поступлении в кулинарное ПТУ
Если ломать можно только один кусочек — ответ (M*N-1)
При каждом разламывании становится на один кусочек больше. Изначально их 1, нужно получить M*N.
Если ломать можно по несколько — ответ (M+N-2)
Например: если плитка 6*3 (Корона), ломаем 5 раз поперёк и 2 вдоль.
Я тут при чтении комментариев пришел к одному выводу.
Задача может и не совсем программистская, но она показала проблемы с чтением/пониманием и со счетом, у подавляющего большинства отвечающих. Все принялись сразу решать, ругать и обсуждать.
Сколько вопросов в задаче? И на сколько большинство отвечает?
Что означает фраза “можете отламывать один сегмент за один раз”?
Не знаю, кто как программирует (а на собеседовании я знать и не могу), но факт остается следующим – передо мной сидит человек, который недочитав и не поняв условие (спецификацию), принялся решать и обсуждать/ругать автора задачи (заказчика). Вы бы взяли к себе в команду человека, который гипотетически что-то умеет, но будет делать то, что он хочет, а не то, что от него требуют?
Кстати, даже если допускается разлом не только по прямой, то ответ все-равно (n*m)-1, Olexiy дал совершенно правильный ответ.
Правильный ответ:
Также представлен более длинное и скучное индуктивное доказательство.
Да уж.
Индуктивного доказательства как раз и нет. Есть доказанная достаточность, и рассказ о “длинном и скучном идуктивном” доказательстве необходимости.
Как бы Вы отреагировали, если бы кандидат сказал Вам – “Ответ длинный и скучный по индукции”?
Идеи таковы:
во-первых: никогда не видел чтоб кто-то идеально отламал клетку шоколада.
во-вторых: если у меня есть плитка скажем 2*3 куска, то достаточно умно изъять три из них, а три сами по себе отваляться.
Так что к каждому случаю своя формула – будет плитка 3*3 – достаточно выламать четыре клетки.итд
Внимательно читаем условие.
плитка из M x N прямоугольных (не квадратных и не 1х1) сегментов
нужно получить кучку сегментов именно 1 х 1, т.е. квадратных…
способ деления – разлом
Если нельзя сегменты складывать между собой (то есть ломать пачками)
тогда количество разломов = (площадь шоколадки – 1).
Если можно сегменты складывать, то столько же, сколько складываний понадобится для бумажного листа нулевой толщины и таких же размеров, как и шоколадка, до состояния 1х1. то есть складывания листа = разломам шоколадки.