Comments 53
может 78 + 78 = 156? просто так намного проще. правда, если там может быть что два гостя одному жали руку... то... не знаю
Классика же, корень из 78×2... и без графов имеем 13...
Вообще-то корень из 156 не равняется 13...
Классика не пляшет как-то. Если одно рукопожатие, то челов выходит корень(2).
Не совсем. Берем формулу арифметической прогрессии (или выводим её в две строчки, если забыли):
И тут уже можно не решать квадратное уравнение, просто берем ближайший больший квадрат целого числа (169). Автор же какойто хрени наворотил.
И тут уже можно не решать квадратное уравнение, просто берем ближайший больший квадрат целого числа
А зачем вам квадрат целого числа, если задача свелась таки к уравнению?
А зачем прогрессия?
По условию: каждый (n) пожал руку каждому, кроме себя (n-1), при этом "он" и "ему" учитываются как одно рукопожатие.
n*(n-1)/2 = 78
И таки да, (n-1)^2 < n(n-1) < n^2, находим ближайшие квадраты - 144 и 169 и проверяем, что ответ подошёл.
Что-то из вашего объяснения нифига не понятно как вы пришли к своим формулам. Можно же проще. Так и алгоритм подобрать проще:
Сначала пришел один человек, руку жать не кому, значит итого после его прихода общее количество рукопожатий = 0.
Пришел второй, до него был один человек, он жмет ему руку, общее количество рукопожатий = 0 + 1 = 1
Пришел третий, в группе два человека, которые уже пожали друг другу руки. Он жмет им, итого, общее количество рукопожатий стало: 1 + 2 = 3
Пришел четвертый, в группе 3 человека, которые пожали руки друг другу, опять надо всего-лишь добавить к общему количеству столько, сколько этот новый человек пожмет руки. или 3 + 3 = 6.
6 + 4 = 10
10 + 5 = 15
и тд
То есть решение - простейший цикл, где на каждой итерации к общему количеству прибавляется количество людей из прошлой итерации, и так, пока общее количество не сравняется искомому значению. Такой вариант размышлений приходит сразу в голову, как и простейшая реализация алгоритма. И кодится за 10 минут. А вот ваш вариант, это надо прямо во время стресса на собеседовании суметь вспомнить все эти формулы, да еще потом вспомнить школьную математику, как решаются квадратные уравнения, находится дискриминант и тд. По-моему это не реально на практике.
Т.е. если вас на собеседовании спросят, допустим, сколько нужно линков чтобы соединить 100 компьютеров друг с другом, вместо того, чтобы просто умножить 50 на 99, вы будете суммировать в столбик? Или вам понадобится 10 минут, чтобы "накодить" и компьютер, чтобы посчитать?
0+1+2+…
Сумма n элементов арифметической прогрессии — (a1+an)*d/2 = (0+99)*100/2
Кажется, это сильно проще в вычислении, чем графы и прочее
Не знаю как для других, а для меня интервью это стресс, во время которого я никакие формулы не могу вспомнить. И мне гораздо легче разобрать как меняются данные с каждой итерацией, а уже потом зная это предложить решение и упомянуть, что можно попробовать найти формулу и посчитать одним действием.
Ну а на вопрос на счет линков я предложу использовать свитчи с 24 портами (не знаю, больше бывают, или нет) Ну и соответственно, 100 линков до первых 6-и свитчей и еще 5 свитчей воткнуть в 6-й свитч. Итого 105 линков, а никак не 50 умножить на 99.
Все это называется "арифметическая прогрессия", а формулу суммы первых 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 класс?
Недоумевающие смайлик.тхт
За такое решение при наличии решения в две строчки на уровне 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 #один из корней (положительный)
Ничего себе намудрил, конечно. Но мне иногда даже нравится таким заморачиваться.
Задача про рукопожатия