Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Игры разума
Перезагрузить страницу Задачки на сообразительность
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
IL_Agent IL_Agent вне форума
Member
 
Аватар для IL_Agent
 
Сообщений: 2,015
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.07.2005
По умолчанию 10.07.2008, 20:34

Сегодня на собеседовании предложили решить несколько задач. Вот некоторые из них:
1. Турист смотрит на Пентагон с расстояния в несколько километров. Какова вероятность того, что он видит 3 его стороны ?
2. Есть 2 стакана: первый- с молоком, другой - с кофе. Сначала из первого стакана ложку молока перелили во второй, затем из второго ложку полученной смеси в первый. Что больше: концентрация кофе в первом стакане или молока во втором ?
3. Дан односвязный список. Как узнать, зациклен ли он ? (без выделения доп. памяти под множества, матрицы и т.д.).
Ответить с цитированием
  (#2 (permalink)) Старый
Narwal Narwal вне форума
Member
 
Сообщений: 1,039
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 07.10.2003
По умолчанию 10.07.2008, 21:19

2 и 3 - я уже неоднократно встречал.
2 - вообще решается за пять минут.
3 - неоднократно мелькала как задача, которую любят спрашивать в Майкрософте. [color=#000000;background:#000000]Если мне не изменяет память, то решение - идти по списку двумя указателеми. Одним с шагом 1, другим с шагом 2. Если они встретятся - то список зациклен.[/color]
Ответить с цитированием
  (#3 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,274
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 11.07.2008, 03:01

1) Примерно 50% [color=#000000;background:#000000]Приближенно, если 2 человека смотрят на него с разных сторон, то один видит 2 стороны, а другой - 3[/color]
2) Весьма известная задача. [color=#000000;background:#000000]Поровну. Достаточно понять, что общие объемы остались прежними. Значит, сколько ушло, столько же и вернулось[/color]
3) Дурная задача какая-то.. [color=#000000;background:#000000]А вот лень считать, не может ли возникнуть ситуация, когда второй указатель будет все время перепрыгивать через первый[/color]
Ответить с цитированием
  (#4 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 11.07.2008, 04:14

Что-то не понял с третьей задачей.... а почему не судьба просто обойти весь список, запомнив начало, и проверить, что указатель опять приходит туда же?
Ответить с цитированием
  (#5 (permalink)) Старый
Dian Dian вне форума
Member
 
Сообщений: 5,243
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2004
По умолчанию 11.07.2008, 09:00

Цитата:
а почему не судьба просто обойти весь список, запомнив начало, и проверить, что указатель опять приходит туда же?
В начало может и не приходить, а цикл будет



___________________
Прикольный сайт по теме: http://www.problems.ru
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
IL_Agent IL_Agent вне форума
Member
 
Аватар для IL_Agent
 
Сообщений: 2,015
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.07.2005
По умолчанию 11.07.2008, 13:56

Ну да, всё верно. Вторую я решил сразу, а вот с остальными возникли проблемы (. До указателей я не дудумался, а про пентагон начал решать геометрически и обсчитался. Зато теперь знаю.
Ответить с цитированием
  (#7 (permalink)) Старый
Vladimir the Red Sunny Vladimir the Red Sunny вне форума
Member
 
Сообщений: 4,232
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 15.05.2003
По умолчанию 14.07.2008, 05:39

Т. е., завалил собеседование?
Ответить с цитированием
  (#8 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 14.07.2008, 10:15

Цитата:
про пентагон начал решать геометрически и обсчитался. Зато теперь знаю.
А сколько получилось?
Мне пока ясно, что заведомо меньше 25 процентов (если пентагон - правильный пятиугольник стоит на ровно месте, и ничего не мешает его видеть). Это нетрудно доказать, исходя из геометрических соображений. Можно и точно посчитать, но пока что у меня возникли громоздкие формулы (которые по идее должны потом сократиться, но я на них застряла).
Ответить с цитированием
  (#9 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 14.07.2008, 11:14

Вот так у меня вышло (выглядит, конечно, не очень):

P = 5*arctg(1/(2*tg(2*pi/5) + ctg(pi/5)))/pi

Приблизительно это равно 0.210083349988143 - немного больше 20 процентов.

Update.
Немного поторопилась - это при определенном расстоянии.
Все-таки зависимость от расстояния есть. Надо еще посмотреть.
Ответить с цитированием
  (#10 (permalink)) Старый
IL_Agent IL_Agent вне форума
Member
 
Аватар для IL_Agent
 
Сообщений: 2,015
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.07.2005
По умолчанию 14.07.2008, 11:42

Цитата:
Т. е., завалил собеседование?
Ну, вобщем-то, действительно завалил Хотя было достаточно вопросов, на которые мне удалось найти ответ.
Цитата:
P = 5*arctg(1/(2*tg(2*pi/5) + ctg(pi/5)))/pi
Точно не припомню, но подобная формула фигурировала в моём решении. Но задача подразумевает простое решение, практически без вычилений.
Ответить с цитированием
  (#11 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 14.07.2008, 12:20

Все еще раз пересчитала. Фокус оказался в том, что для общего случая в этой формуле
P = 5*arctg(1/(2*tg(2*pi/5) + ctg(pi/5)))/pi
пропущен один коэффициент.

На самом деле, если считать точно, то верятность находится так:
P = 5*arctg(k/((k+1)*tg(2*pi/5) + ctg(pi/5)))/pi,

где k - коэффициент, прямо пропорциональный расстоянию. Если, скажем, R - расстояние от центра пентагона до туриста, то можно найти точно, как они связаны.
При k = 1 получается результат, который я привела выше.

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

limit arctg(k/((k+1)*tg(2*pi/5) + ctg(pi/5))) = arctg(1/ tg(2*pi/5)) = pi/2 - 2*pi/5.

Поэтому искомая вероятность равна 1/2.

Здравый смысл Alexiski не подвел.
Ответить с цитированием
  (#12 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 14.07.2008, 12:56

Чтобы уж совсем довести решение до конца.

Пусть R расстояние от центра пентагона до туриста, a - сторона пентагона.
Тогда R и коэффициент k связаны следующим образом:

R + a*ctg(pi/5)/2 = a*(1 + (k + 1)/(2*cos(2*pi/5)))*sin(3*pi/5)

Ясно, что если R стремится к бесконечности, то и k стремится к бесконечности, и наоборот.
Чтобы все это найти, достаточно нарисовать пентагон в центре листа бумаги и попытаться его обойти на приличном расстоянии по окружности. И при этом посмотреть, когда сколько сторон будет видно. Остальное все находится из подобия треугольников.
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
IL_Agent IL_Agent вне форума
Member
 
Аватар для IL_Agent
 
Сообщений: 2,015
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.07.2005
По умолчанию 14.07.2008, 13:41

А вот ещё одну вспомнил.
На шахматной доске две фигуры: конь и король. Стоят в диагонально противоположных углах доски. Конь ходит первым. Какова должна быть тактика короля, чтобы избежать шаха.
Ответить с цитированием
  (#14 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 14.07.2008, 13:50

Если конь идет на белую клетку, то король на черную и наоборот. При этом, естественно, не ставить под удар (такие ходы все равно запрещены). Если ход таким образом - только под удар, то идти на соседнюю клетку, а потом вернуться к старой стратегии.
Ответить с цитированием
  (#15 (permalink)) Старый
wanja wanja вне форума
Member
 
Сообщений: 585
Сказал(а) спасибо: 1
Поблагодарили 25 раз(а) в 25 сообщениях
Регистрация: 08.05.2005
По умолчанию 14.07.2008, 17:20

Прилетели два чижа, два ежа и два ужа
Сколько птиц теперь всего возле дома моего?
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задачки Leo_gibson Prolog 19 30.11.2016 00:13
Задачки в Pascal OlegBo Pascal 0 13.03.2011 12:47
2 задачки Bodrik Задания за деньги 1 18.12.2009 00:11
Задачки по SQL flast1k Задания за деньги 1 21.11.2009 09:21
Задачки плиииз. Евгешка Pascal 1 20.10.2009 19:48
3 задачки sashkaman Prolog 3 12.04.2009 18:57
2 задачки Kolobov_Anton Prolog 3 27.03.2009 13:10
2 задачки alpine Prolog 0 23.05.2008 22:27
Задачки Taurus Pascal 18 24.03.2008 17:28
Задачки Micher Prolog 4 21.12.2006 20:19
4 задачки.. Cvet Prolog 6 13.12.2006 20:56
Как решить задачу на сообразительность alexa Pascal 2 16.08.2005 17:36



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов