Задачка от Google

и задачки для интервью.
Forum rules
serg14
Новичок
Posts: 23
Joined: 23 Aug 2004 11:28
Location: NY

Задачка от Google

Post by serg14 »

Проводили рекрутинг на кампусе. Одна задачка показалась мне интересной ...

Шесть точек на окружности попарно соединены хордами. Длины хорд - натуральные числа. Найти минимальный радиус окружности.
Top
User avatar
Flash-04
Уже с Приветом
Posts: 63430
Joined: 03 Nov 2004 05:31
Location: RU -> Toronto, ON

Post by Flash-04 »

решили? ;)
Top
User avatar
KP580BE51
Уже с Приветом
Posts: 15007
Joined: 14 Jun 2005 11:50
Location: Ukraine

Re: Задачка от Google

Post by KP580BE51 »

serg14 wrote:Проводили рекрутинг на кампусе. Одна задачка показалась мне интересной ...

Шесть точек на окружности попарно соединены хордами. Длины хорд - натуральные числа. Найти минимальный радиус окружности.

Тока "в лоб". Перебором. :pain1:
Top
User avatar
Flash-04
Уже с Приветом
Posts: 63430
Joined: 03 Nov 2004 05:31
Location: RU -> Toronto, ON

Post by Flash-04 »

я только одного не пойму, на кой черт такие задачи решать? или им нужны математики для некоторых проектов? для прикладного программиста, это IMHO бесполезно.
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

У меня получилось 25, но то, что меньше нет - гарантировать не могу. :)
Top
User avatar
KP580BE51
Уже с Приветом
Posts: 15007
Joined: 14 Jun 2005 11:50
Location: Ukraine

Post by KP580BE51 »

Flash-04 wrote:я только одного не пойму, на кой черт такие задачи решать? или им нужны математики для некоторых проектов? для прикладного программиста, это IMHO бесполезно.

ППКС.
ИМХО более логичны более формальные задачи. Которые не требуют знания что такое простые числа. (АФАИК простые числа используются только в дебрях криптографии)
Top
serg14
Новичок
Posts: 23
Joined: 23 Aug 2004 11:28
Location: NY

Post by serg14 »

у меня получилось меньше :P
Top
User avatar
Ворона
Уже с Приветом
Posts: 1849
Joined: 06 Mar 2006 20:06

Post by Ворона »

А как это - "попарно"?
А "натуральные числа" заданы или надо "сообразить" что наименьшее возможное = 1?
Если все хорды образуют 6-угольник, то "че" тут решать..
Если они могут пересекаться как попало, то самая большая хорда - это диаметр. И, если он - возможный минимум 1, то "че тут решать".
Что я не так поняла?
Top
User avatar
AndreyT
Уже с Приветом
Posts: 3000
Joined: 14 Apr 2004 01:11
Location: SFBA (было: Минск, Беларусь)

Post by AndreyT »

Ворона wrote:А как это - "попарно"?


Значит все возможные пары точек соединены хордами, т.е. получается шестиугольник со всеми своими диагоналями. Один из вариантов изображения графа K6.

А "натуральные числа" заданы или надо "сообразить" что наименьшее возможное = 1?


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

Если все хорды образуют 6-угольник, то "че" тут решать..


Очевидно, речь также идет и о хордах-диагоналях шестиугольника.

Если они могут пересекаться как попало, то самая большая хорда - это диаметр.


И какое это имеет значение?

И, если он - возможный минимум 1, то "че тут решать".


Не понимаю. Если самая большая хорда имеет длину 1, то все остальные не будут иметь натуральную длину. А такие ситуации нас не интересуют.
Best regards,
Андрей
Top
User avatar
Poryadok
Уже с Приветом
Posts: 1383
Joined: 17 Jan 2005 22:33
Location: Minsk, Belarus - Beaverton, OR

Post by Poryadok »

Некорректная постановка задачи. Если бы глубокоуважаемый Гуугл добавил скажем "натуральные числа все разные" и "хорды образуют выпуклый многоугольник" и скажем должны ли они идти подряд в порядке возрастания или их можно тусовать?

А так получается как в анекдоте про Вовочку - ответ - учительнице 26 лет (потому что Вовочке - 13 и он полудурок)
Отлипай давай от форума и марш работать!
Top
User avatar
Poryadok
Уже с Приветом
Posts: 1383
Joined: 17 Jan 2005 22:33
Location: Minsk, Belarus - Beaverton, OR

Post by Poryadok »

О, теперь с пояснениями - формулировка сразу прояснилась. Нужно было сказать, что точки расположены на окружности симметрично через равные расстояния и _все_ пары точек соединены (я например сначала подумал что только соседние)
Отлипай давай от форума и марш работать!
Top
serg14
Новичок
Posts: 23
Joined: 23 Aug 2004 11:28
Location: NY

Post by serg14 »

Flash-04 wrote:я только одного не пойму, на кой черт такие задачи решать? или им нужны математики для некоторых проектов? для прикладного программиста, это IMHO бесполезно.


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

Poryadok wrote:Некорректная постановка задачи.


Постановка корректна и не допускает двусмысленного толкования. Про расположение точек ничего не известно, кроме того что они лежат на окружности и длины хорд выражены натуральными числами.
Top
User avatar
Ворона
Уже с Приветом
Posts: 1849
Joined: 06 Mar 2006 20:06

Post by Ворона »

Ну тогда " минимально возможный случАй" - если правильный шестиугольник со стороной 1, => все его диагонали равны 2, и "че тут решать"?
Может, какие-то данные пропущены?
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Не все диагонали целые, а только главные.
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Poryadok wrote:Нужно было сказать, что точки расположены на окружности симметрично через равные расстояния

Этого в условии нет.
Top
User avatar
Ворона
Уже с Приветом
Posts: 1849
Joined: 06 Mar 2006 20:06

Post by Ворона »

A-a-aa, Иван Иваныч... :oops:
Ну теперь все в порядке с условием :mrgreen: Ладно, потом ишшо подумаю, писать наспех, как вижу, только позориться..
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

serg14 wrote:у меня получилось меньше :P

Только что заметил, что в моём решении все расстояния чётные, так что радиус можно уменьшить в два раза. :)
Top
varenuha
Уже с Приветом
Posts: 6859
Joined: 09 Sep 2001 09:01

Post by varenuha »

Фигня полная. Задача на уровне того класса средней школы где проходят теорему Пифагора ( 6 класс в России). Ответ - 2.5
Top
Prist
Уже с Приветом
Posts: 280
Joined: 06 Apr 2004 21:25

Post by Prist »

Найти минимальный радиус

venco wrote:У меня получилось 25

25 получается диаметр.
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

varenuha wrote:Фигня полная. Задача на уровне того класса средней школы где проходят теорему Пифагора ( 6 класс в России). Ответ - 2.5

Ну-ка ну-ка?
Top
serg14
Новичок
Posts: 23
Joined: 23 Aug 2004 11:28
Location: NY

Post by serg14 »

мой ответ меньше 12.5, но больше 2.5

посему на 2.5 моя реакция тоже будет: "Ну-ка ну-ка?"
Top
User avatar
Layla
Уже с Приветом
Posts: 5813
Joined: 24 Aug 2003 07:17
Location: Seattle

Post by Layla »

Ворона wrote:А как это - "попарно"?
А "натуральные числа" заданы или надо "сообразить" что наименьшее возможное = 1?
Если все хорды образуют 6-угольник, то "че" тут решать..
Если они могут пересекаться как попало, то самая большая хорда - это диаметр. И, если он - возможный минимум 1, то "че тут решать".
Что я не так поняла?


Я, должно быть, пропустила какие-то пояснения по условию задачи? Где-то было ограничение, что все хорды - разные? Могут ли все хорды быть диаметрами (проходить через центр и иметь, соответственно, одинаковую длину, skazhem - 1)?
Top
User avatar
Layla
Уже с Приветом
Posts: 5813
Joined: 24 Aug 2003 07:17
Location: Seattle

Post by Layla »

Poryadok wrote:О, теперь с пояснениями - формулировка сразу прояснилась. Нужно было сказать, что точки расположены на окружности симметрично через равные расстояния и _все_ пары точек соединены (я например сначала подумал что только соседние)


А где это описано в условии - что симметрично и все соединены?
Top
varenuha
Уже с Приветом
Posts: 6859
Joined: 09 Sep 2001 09:01

Post by varenuha »

serg14 wrote:мой ответ меньше 12.5, но больше 2.5

посему на 2.5 моя реакция тоже будет: "Ну-ка ну-ка?"


Два прямоугольных треугольника со сторонами 3,4,5 вписанные в окружность дадут требуемый шестиугольник. Ну а почему треугольник с длиннейшей стороной равной 4 не годится - вам на закуску. :)
Top
User avatar
olg2002
Уже с Приветом
Posts: 990
Joined: 27 Mar 2002 10:01
Location: Palo Alto, CA

Post by olg2002 »

serg14 wrote:мой ответ меньше 12.5, но больше 2.5

посему на 2.5 моя реакция тоже будет: "Ну-ка ну-ка?"


Я думаю, что могу доказать, что 12.5 - минимальный радиус. Поверяйте свой ответ.
Top

Return to “Головоломки”