Search
Write a publication
Pull to refresh

Comments 53

может 78 + 78 = 156? просто так намного проще. правда, если там может быть что два гостя одному жали руку... то... не знаю

Классика же, корень из 78×2... и без графов имеем 13...

Вообще-то корень из 156 не равняется 13...

Тсссс, не пугайте миллениалов!

12.4, а теперь округлим вниз и вверх. Получим 12х13=156. Т.е. 13 человек.

По моему, это пятый класс примерно. До квадратных уравнений ещё.

12.4, а теперь округлим вниз и вверх

где то рядом прошло 1.5 землекопа ;)

Классика не пляшет как-то. Если одно рукопожатие, то челов выходит корень(2).

Не совсем. Берем формулу арифметической прогрессии (или выводим её в две строчки, если забыли):

(x-1)*x/2 = 78 => (x-1)*x = 156

И тут уже можно не решать квадратное уравнение, просто берем ближайший больший квадрат целого числа (169). Автор же какойто хрени наворотил.

И тут уже можно не решать квадратное уравнение, просто берем ближайший больший квадрат целого числа

А зачем вам квадрат целого числа, если задача свелась таки к уравнению?

А зачем вам квадрат целого числа, если задача свелась таки к уравнению?

Чтобы не сводить задачу к решению этого уравнения. Вместо задачки для 7го класса, получаем решение для 5го.

Но мы же взрослые, что было в 5 классе - забыли на 2 года раньше чем то что было в 7 ;)

А зачем прогрессия?

По условию: каждый (n) пожал руку каждому, кроме себя (n-1), при этом "он" и "ему" учитываются как одно рукопожатие.

n*(n-1)/2 = 78

И таки да, (n-1)^2 < n(n-1) < n^2, находим ближайшие квадраты - 144 и 169 и проверяем, что ответ подошёл.

Что-то из вашего объяснения нифига не понятно как вы пришли к своим формулам. Можно же проще. Так и алгоритм подобрать проще:

  1. Сначала пришел один человек, руку жать не кому, значит итого после его прихода общее количество рукопожатий = 0.

  2. Пришел второй, до него был один человек, он жмет ему руку, общее количество рукопожатий = 0 + 1 = 1

  3. Пришел третий, в группе два человека, которые уже пожали друг другу руки. Он жмет им, итого, общее количество рукопожатий стало: 1 + 2 = 3

  4. Пришел четвертый, в группе 3 человека, которые пожали руки друг другу, опять надо всего-лишь добавить к общему количеству столько, сколько этот новый человек пожмет руки. или 3 + 3 = 6.

  5. 6 + 4 = 10

  6. 10 + 5 = 15

  7. и тд

То есть решение - простейший цикл, где на каждой итерации к общему количеству прибавляется количество людей из прошлой итерации, и так, пока общее количество не сравняется искомому значению. Такой вариант размышлений приходит сразу в голову, как и простейшая реализация алгоритма. И кодится за 10 минут. А вот ваш вариант, это надо прямо во время стресса на собеседовании суметь вспомнить все эти формулы, да еще потом вспомнить школьную математику, как решаются квадратные уравнения, находится дискриминант и тд. По-моему это не реально на практике.

Т.е. если вас на собеседовании спросят, допустим, сколько нужно линков чтобы соединить 100 компьютеров друг с другом, вместо того, чтобы просто умножить 50 на 99, вы будете суммировать в столбик? Или вам понадобится 10 минут, чтобы "накодить" и компьютер, чтобы посчитать?

0+1+2+…
Сумма n элементов арифметической прогрессии — (a1+an)*d/2 = (0+99)*100/2
Кажется, это сильно проще в вычислении, чем графы и прочее

Каждый из n соединен с n-1. Перемножаем и делим пополам. Куда же уж может быть проще?

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

Ну а на вопрос на счет линков я предложу использовать свитчи с 24 портами (не знаю, больше бывают, или нет) Ну и соответственно, 100 линков до первых 6-и свитчей и еще 5 свитчей воткнуть в 6-й свитч. Итого 105 линков, а никак не 50 умножить на 99.

А кто вам сказал, что с вопросе речь идет про коммутируемый ethernet? Там сказано "соединить друг с другом"...

я никакие формулы не могу вспомнить.

Как нас учили в универе, «не можешь вспомнить — выведи!»

Все это называется "арифметическая прогрессия", а формулу суммы первых N ее членов проходят где-то в 9 классе.

Нет, я про метод, говоря простым языком, «начнём с одного, потом добавим ещё одного, потом ещё одного... повторять до опупения».

При индукции нужно не до опупения повторять, а до выведения закона, который еще нужно доказать (например методом математической индукции). В нашем случае законом как раз будет формула суммы первых N членов арифметической прогрессии. В изначальном комментарии предлагалось просто в цикле добавлять, пока ответ не получится, а не вывести формулу - это не индукция, а алгоритм.

Сколько нынче Бизнес платит за решение подобных задач в процессе трудовой деятельности?

Или Бизнес все-таки платит не за такие задачи?

"Сколько нынче Бизнес платит за решение подобных задач в процессе трудовой деятельности?"

На роли программиста микроконтроллеров у меня за 12 лет не возникало таких вот задач.
Сам не понимаю зачем спрашивать такое на собеседовании.

Речь шла о ЗП 160к RUR /мес gross.

бизнес предпочитает вообще не платить, иначе неоткуда взяться сверхприбылям.

(специально, не пошел читать комментарии)

Каждый гость на встрече обменивается рукопожатием с другим. Всего было 78 рукопожатий. Сколько гостей пришло на встречу?

что означает "с другим"?

с одним из соседей?

только с одним? (тогда, по кругу, и будет 78)

а на картинках графы, как будто каждый с каждым. зачем?

если каждый гость обменивается рукопожатиями со всеми остальными, что соответствует графам с картинок, то, если у нас n гостей, то каждый совершает n-1 рукопожатий (неуместно жать руку самому себе), а все вместе n*n-n, тогда получаем уравнение n^2-n-78=0. получается, слегка дробное число гостей.

вот, если бы их было 72...

n*(n-1) будет, если человек 1 пожал руку человеку 2 (+1) и человек 2 пожал руку человеку 1 (+1)
Если каждый с каждым здоровался только раз, будет n*(n-1)/2

а выше умножать предлагали.

да нет если на бумагу выписать к такому именно числу и подобрать можно, там не дробное можно остановить на =156 и подобрать

в вики К12 можно еще посмотреть и добавить одну вершину подсчитать

пример из 2 вершин (2*2 - 2)/2 = 1, можно проверить 3 и перейти к 12 и затем 13

Симплекс можно еще это глянуть

наверно это спрашивают потомучто там рядом деревья Binary_tree , в представлении массива(ну а там базовые структуры данных, скорее всего типо медианный вопрос наверно), тоесть там очереди, стек, деревья, деревья с сортировкой, деревья поворотами, сахи всякие вот это вот всё, например вот я обзор смотрел как построить BVH и там вот вся база в основе(почти весь курс понадобится чтобы понять бвх), ну и вот около такой задачи могут и спросить, потомучто надо понимать что там происходит почему именно так делаем. бвх это ускоренная структура типо(посути он может лежать в основе вообще, из-за того что чтобы его с нуля написать там почти всё написать придётся)

Мне кажется, собеседование о другом, никого не интересует, точнее - не должно интересовать, умеет ли кандидат считать. Такую ерунду как

Каждый гость на встрече обменивается рукопожатием с другим. Всего было 78 рукопожатий. Сколько гостей пришло на встречу?

спрашивают чтобы получить откровенный ответ. Типа

  • Пришло 79 гостей если Другой тоже гость, и 78 если Другой - хозяин.

  • Поскольку при обмене сущности не уничтожаются и не появляются, то 78 или 39 или 26 или 13 или 6 или 2 или 3 в зависимости от того, по сколько рукопожатий было у каждого гостя.

  • … (молчит и считает) … (сморкается, вытирает слёзы) … да, он трижды, трижды …

  • О, 78 - это же минимальное число рёбер многогранника в 12-мерном пространстве, значит гостей было 13.

  • Неизвестно - пока одни гости приходили, другие могли не только уходить, но и возвращаться.

А если человек не даёт откровенного ответа… то он скрытен, подозрителен, коварен и хитёр - такой и нужен нам в команду.

Я впервые в жизни встретил эту задачу, и секунды за две увидел последовательность 1+2+3+4+...=78. Какие, на фиг, "смежные вершины неориентированных графов"?

Надо же чего-то спросить на собеседовании. Как насчёт олимпиадной задачи за 6 класс?

Недоумевающие смайлик.тхт

Ну, судя по комментариям, их задают не просто так

Если это собеседование о приеме на работу, то, наверное, от кандидата ожидается максимально простое решение. Если он притащит додекаэдр в 13-мерном пространстве, он конечно же умный. Но если он код будет писать в таком же стиле - нафиг :)

За такое решение при наличии решения в две строчки на уровне 5 класса школы, гнать в шею надо таких кандидатов. Потом и проекты у таких соответствующие: надо написать простейшую функцию, они вместо трёх строчек кода для этого десяток сторонних либ подключат.

Задачу надо было решить не кодом , а карандашом на листке. Чисто аналитическим образом.

Так она и решается при желании даже не карандашом на листке, а в уме. См. коммент выше.

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

Ну а вдруг когда-нибудь мы встретим трехруких инопланетян, у которых в рукопожатии участвуют четыре особи? А тут хоба - наша программа уже умеет их считать, не надо переписывать ее заново.

Я уверен, что основная хитрость этой задачи - в умении решить квадратное уравнение. Ибо курсу к пятому этот навык уже выветривается, а доценты с кандидатами и вовсе не помнят этих странных дискриминантов Виета.

Можно решить квадратное уравнение численным методом.

А если я дал ответ "каждый гость - вершина графа, каждое рукопожатие - ребро графа, ненаправленное, циклов нет. Количество ребер известно, открывайте справочник, там была формула для количества вершин" - норм?

Ок... Каждый из гостей (всех гостей) пожал руку другому. То есть, у нас есть неизвестное полное количество, разбитое на неповторяющиеся пары. Таким образом, кмк, задача сводится к вопросу "из какого общего количества элементов можно составить 78 уникальных пар", так?

Как уже написали: первый жмёт руку никому, 0, второй - одному, 1, третий - двум, 2, четвертый трем, 3. Арифметическая прогрессия, и ее сумма - общее число рукопожатий.

Ну, если кто имел дело с такими коллективами где каждый новый должен со всеми присутствующими за руку поздороваться.

Какие графы? Зачем они тут?

А простейшая логическая выкладка за 10 секунд, что каждый из n присутствующих пожал руку всем остальным n-1 присутствующих, что даёт n(n-1) рукопожатий; и поделить на два, так как в каждом рукопожатии 2 участника, не катит уже? Нужно графы, последовательности, алгоритмы и вот это вот все?)

Постановка задачи неполная. Не сказано, обменивается ли гость рукопожатиями с каждым из других гостей или он делает это выборочно. Не указано, могут ли два гостя несколько раз пожать друг другу руки.
Так что ответ - не менее двух гостей.

Задача для тех, кто никогда не рисовал турнирную таблицу

х^2=2*78+x

Решаем, получаем два корня 13 и -12

n*n #количество рукопожатий каждый с каждым, матрица

n*n-n #вычитаем диагональ, сам с собой здороваться не имеет смысла: например A1 с A1, A2 с A2 и.т.д.

(n*n-n)/2 #если A1 поздоровался с A2, то A2 здороваться с A1 не нужно, делим на 2

(n*n-n)/2=78 #решаем квадратное уравнение n^2-n-78*2=0

n=13 #один из корней (положительный)

Гениально. Браво!

Ничего себе намудрил, конечно. Но мне иногда даже нравится таким заморачиваться.

Sign up to leave a comment.

Articles