Итак, мы продолжаем серию переводов цикла «Трудные вопросы на собеседовании».
У вас есть плитка шоколада, состоящая из n×m прямоугольных сегментов. При условии, что можете отламывать один сегмент за один раз, сколько раз нужно отламывать, чтобы из изначальной плитки n×m получилась кучка сегментов 1×1? Сколько раз достаточно?
UPDATE: правильный ответ.
Вообще-то, если быть педантом и прочитать условие задачи (а именно то, что я могу отламывать 1 плитку за раз (неважно в каком месте)), то вроде напрашивается ответ m (n div 2) + n (m div 2).
Внимательно читаем условие.плитка из M x N прямоугольных (не квадратных и не 1×1) сегментовнужно получить кучку сегментов именно 1×1, т.е. квадратных...способ деления — разломЕсли нельзя сегменты складывать между собой (то есть ломать пачками) тогда количество разломов = (площадь шоколадки — 1).Если можно сегменты складывать, то столько же, сколько складываний понадобится для бумажного листа нулевой толщины и таких же размеров, как и шоколадка, до состояния 1×1. то есть складывания листа = разломам шоколадки.
Идеи таковы: во-первых: никогда не видел чтоб кто-то идеально отламал клетку шоколада.во-вторых: если у меня есть плитка скажем 2*3 куска, то достаточно умно изъять три из них, а три сами по себе отваляться.Так что к каждому случаю своя формула — будет плитка 3*3 — достаточно выламать четыре клетки.итд
Да уж. Индуктивного доказательства как раз и нет. Есть доказанная достаточность, и рассказ о «длинном и скучном идуктивном» доказательстве необходимости.Как бы Вы отреагировали, если бы кандидат сказал Вам — «Ответ длинный и скучный по индукции»?
Поскольку после каждого отламывания получается один новый кусочек, необходимо и достаточно отломить n×m-1 раз, чтобы получить n×m кусочков.
Также представлен более длинное и скучное индуктивное доказательство.
Кстати, даже если допускается разлом не только по прямой, то ответ все-равно (n*m) −1, Olexiy дал совершенно правильный ответ.
Я тут при чтении комментариев пришел к одному выводу.Задача может и не совсем программистская, но она показала проблемы с чтением/пониманием и со счетом, у подавляющего большинства отвечающих. Все принялись сразу решать, ругать и обсуждать. Сколько вопросов в задаче? И на сколько большинство отвечает? Что означает фраза «можете отламывать один сегмент за один раз»? Не знаю, кто как программирует (а на собеседовании я знать и не могу), но факт остается следующим — передо мной сидит человек, который недочитав и не поняв условие (спецификацию), принялся решать и обсуждать/ругать автора задачи (заказчика). Вы бы взяли к себе в команду человека, который гипотетически что-то умеет, но будет делать то, что он хочет, а не то, что от него требуют?
Если ломать можно только один кусочек — ответ (M*N-1) При каждом разламывании становится на один кусочек больше. Изначально их 1, нужно получить M*N.Если ломать можно по несколько — ответ (M+N-2) Например: если плитка 6*3 (Корона), ломаем 5 раз поперёк и 2 вдоль.
тут есть правильный ответ и он n*m-1... ето обьяснил Олексей.
если пожно вырезать середины, то надо резать в шахматном поядке, m*n/2
2 ДимаПро гномів, НМД, якраз теж не дужеВ задачі, бажано, щоб треба було писати код — хоча б три-чотири рядки. Так що я б питав одну з задач про обернення рядка і т.п.
2 Сергіям Волошину та Щєтініну.І, звичайно, вони популярні, бо доступні всім.
2 Сергіям Волошину та Щєтініну.Саме ця задачка, звичайно, не дуже вдала. Але взагалі задачки потрібні щоб побачити як людина думає, що вона знає, як підходить до розв’язку, як реагує на труднощі, що робить, якщо помилилась і т.п. І така задача + розмова за п’ять хвилин може дати більше інформації, ніж якщо людина буде дві-три години писати код (на що у багатьох не буде часу просто).
Сергей, так и я о том же =) В смысле что поржать с задачек можно, но это не значит что их нужно перестать публиковать.
2Щетинин Сергей: Если б твои статьи так же бурно и вовлеченно обсуждали, материалы на сайте б несколько другими. Эти же задачки хоть понятны всем:) Наивно ждать что сами они представляют большой интерес, можно их все сразу и на оригинальном сайте найти. Однако обсуждения самих задачек довольно интересные получаются как правило.
На сколько я понял задачу, то следует доказать, что n*m-1 является как достаточной величиной, так и необходимой.Достаточность доказывается просто: n*m плитку делим (m-1) разломом на m плиток размером n1. Чтобы разделить получившиеся плитки на куски размером 11, надо каждую плитку поломать (n-1) раз. Итого: (m-1) +m* (n-1) =m-1+mn-m= mn-1, ч.т.д.Необходимость доказывается сложнее — по индукции.База индукции: m=1, n=1, тогда S=mn-1=11−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 можно разбить на две: 11 и (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=1k-1 ч.т.д.Аналогичным образом по индукции доказывается для m-произвольного.База: m, n=1, S=1*m-1 (верно по предыдущему доказательству) Предположение: n=k, S=m*k-1 и надо доказать, что при n=k+1, S=m* (k+1) −1PS: Если что не так. сильно не пинайте.PPS: Очень хочется увидеть полное доказательство от автора:), особенно необходимости.;)
и что ктото такой отстой на собеседовании спрашивает? Имхо: авторы смотрите первую задачу из этой рубрики (про магов и гномов) на нее и равняйтесь.
@7Будь я владельцем сайта я бы так не думал: во-первых посещаемость у вопросов явно высокая, во-вторых контингент у них правильный в том смысле, что один из источников доходов — обьявления о работе и чем больше посетителей обеспокоеных этим вопросом тем лучше должны идти продажи.А то что к разработке никакого отношения нет, ну так это уже другой вопрос.
2 Всеволод — рейтинг минулих був набагато вищим, так що просто це питання не дуже:)
Ну тут можно и хитрее:) Если можно ламать много сегментов одновременно, то выходит: (n-1) + (m-1) (Это количечсство всех полос в шеколадке, по которым мы и ламаем) А если нельзя (тоесть за раз можно ламать один лишь сегмент), то n*m-1... Что Олексий очень красиво обьяснил:) Нык1каво...
Правильный ответ: положить плитку на стол и ударить головой. Итого: ноль отломов, один удар.
+1. Рейтинг этих «трудных вопросов» показывает, насколько они нужны здесь (сейчас — 1.4/5).
2 Olexiy.В умові задачі сказано, що за раз можна відламувати один сегмент. У першому реченні визначено сегмент, як частину плитки розміру 1 на 1. Якщо ж малося на увазі інше, то Ваш розвязок правильний.
Якщо я правильно зрозумів задачу, то відповідь буде [(n * m) / 2], де [x] — ціла частина x. Розфарбуємо нашу плитку у вигляді шахматки, тоді для того щоб наша плитка розпалася на кусочки розміру 1 на 1, достатньо відламувати всі кусочки зафарбовані тільки в білий або тільки в чорний колір. Оскільки можливі варіанти коли кількість білих та чорних клітинок буде відрізнятися рівно на один (при умові що n та m — непарні), то вигідніше буде вибрати конкретний колір, кількість плиток якого менша, тому ми беремо цілу частину від (n * m) / 2.
2 СтюардПравильне формулювання наступне: За один раз можеш ламати скільки завгодно сегментів, але тільки по прямій.Наприклад, плитку 2*2 можна розламати двома варіантами (вертикально і горизонтально), але все одно вийде дві плитки по 1 * 2. Плитку 3 * 2 можна розламати кількома варіантами: ХХХ X XX XX X XXX ХХХ —> X XX or XX X or XXXА відповідь все одно (n×m — 1) і доведення цього досить просте — з кожним розломом кількість шматків збільшується на один.
Правильный ответ: положить плитку на стол и ударить головой. Итого: ноль отломов, один удар.
Гм... более чем странное задание... интересно как можно отломать один сегмент НЕ из плитки 1хM или Nх1??? А если можно делать один прямой отлом — тогда ответ тоже очевиден -...Блин... посидел посчитал — как не отламывай (хоть по одному, хоть полосками, шириной в один сегмент — как в реальной жизин можно отломать) — всё-равно — количество = n×m — 1
>> У вас есть плитка шоколада, состоящая из n×m сегментов. При условии, что можете отламывать один сегмент за один раз...В такому формулюванні, очевидно, відповідь (n×m — 1). Але, думаю, малось на увазі, що можна робити за раз один прямий розлом будь-якої довжини.
anonymous
Alexander Skakunov
Dmytro Mantula
slav0nic
Олексій Орєшко
Sergii Voloshyn
Vsevolod Solovyov
Андрій Петруша
29 коментарів
Підписатись на коментаріВідписатись від коментарів Коментарі можуть залишати тільки користувачі з підтвердженими акаунтами.