Старый 03.12.2010, 11:30   #51
lukmus
 
Аватар для lukmus
 
Регистрация: 11.08.2010
Сообщений: 133
Репутация: 20
По умолчанию

Цитата:
Сообщение от Cthulchu Посмотреть сообщение
с яйцом и этажами. во первых, этаж не влияет на яйца, разбивай их не сходя с места.
если я не прав и все же, в условии задачи нужно сбрасывать яйца, то сбросим их с наивысшего этажа, ибо сказано о минимуме ничего небыло.
а вообще-то, мне кажется, что речь идет о человеческих яйцах, такие глупые повороты характерны в шуточках HR'ов.
Цитата:
Необходимо одназначно определить с какого этажа бьются яица за минимальное количество шагов.
тут как бы намекалось, что результат должен был быть один и как бы 99,99% людей поняли что в данном случае надо искать минимальный этаж. Но Ктулху, он же не человек, а повелитель тьмы, поэтому я дополню условие минимальностью этажа )).
__________________
Контактный XMPP: lukmus[собака]wallstreetjabber.biz
lukmus вне форума   Ответить с цитированием
Старый 03.12.2010, 12:02   #52
Cthulchu
 
Аватар для Cthulchu
 
Регистрация: 06.07.2010
Сообщений: 36
Репутация: 3
По умолчанию

не серчай, разные люди по разному задачки задают, ориентированные на разные вещи, так что невнимательность в любом случае - помеха в такого рода делах.
загадывайте дальше, только не шлак с гугла, а то, что самим нравится.
Cthulchu вне форума   Ответить с цитированием
Старый 19.04.2011, 19:03   #53
ont
 
Аватар для ont
 
Регистрация: 16.12.2010
Сообщений: 57
Репутация: 92
По умолчанию

Цитата:
Сообщение от lukmus Посмотреть сообщение
2. Условие
У вас 2 яица. Есть 100-этажное здание.
Яиц только 2 поэтому и шанса разбить яицо будет тоже только 2.
Вопрос
Необходимо одназначно определить с какого минимального этажа бьются яица за минимальное количество шагов.
Важна стратегия, а не число. В данном случае скажу что количество шагов наилучшей стратегии при наихудшем раскладе (яица бьются с 100-го этажа) будет 19.
Почему так много ? У меня при наихудшем раскладе (не обязательно 100 этаж) получается не более 15 бросков. Опечатка ?
Подсказка ( если бъется на 100 этаже):
Код:
15 + 14 + 13 + 12 + 11 + 10 + 9 + 8 + 7 = 99
ont вне форума   Ответить с цитированием
Старый 20.04.2011, 01:57   #54
Cthulchu
 
Аватар для Cthulchu
 
Регистрация: 06.07.2010
Сообщений: 36
Репутация: 3
По умолчанию

(все прищурились и оглянулись на некрофила.)
Cthulchu вне форума   Ответить с цитированием
Старый 20.04.2011, 18:44   #55
ont
 
Аватар для ont
 
Регистрация: 16.12.2010
Сообщений: 57
Репутация: 92
По умолчанию

Цитата:
Сообщение от Cthulchu Посмотреть сообщение
(все прищурились и оглянулись на некрофила.)
Хорошие задачи никогда не стареют) Просто очень интересно узнать игровую стратегию lukmus'a... А такую задачу, похоже, могли давать на собеседовании в google.
ont вне форума   Ответить с цитированием
Старый 21.04.2011, 01:23   #56
lukmus
 
Аватар для lukmus
 
Регистрация: 11.08.2010
Сообщений: 133
Репутация: 20
По умолчанию

Цитата:
Сообщение от ont Посмотреть сообщение
Почему так много ? У меня при наихудшем раскладе (не обязательно 100 этаж) получается не более 15 бросков. Опечатка ?
Подсказка ( если бъется на 100 этаже):
Код:
15 + 14 + 13 + 12 + 11 + 10 + 9 + 8 + 7 = 99
Это не опечатка, я гораздо площе (от прил. плоский) смотрел на решение, поэтому мое решение не верное, правда не факт что твое решение верно, хотя безусловно ты нехреново расширил рамки задачи.

Все дело в том что я смотрел на задачу так:
Пусть c - кол-во этажей, а y - интервал разбиений множества этажей C={1,2,..,100} .
Тогда s(y) - максимальное кол-во шагов для определения нужного этажа.

Мое плоское решение:
y(y-1)+1=c
s=y+(y-1)=2y-1


y^2 -y+1-c=0 => y1=(1+SQR(4c-3))/2, y2=(1-SQR(4c-3))/2
и т.к. y2<=0 при любых cͼN у нас остается только y=y1
s=SQR(4c-3)

В таком случае если c=100 => s=19
y=(s+1)/2=10 (да я знаю, что y(y-1)+1=91 но это потому, что я округляю, на самом деле y=(1+SQR(397))/2=10,462429423)

Эмпирическим путем установлено, что s=[SQR(4c-3)], где [ ] - целая часть.

И это значит, что мы берем кидаем сначала яицо с 10 этажа, если оно бьется значит кидаем последовательно с 1го, 2го, ..., 9го до тех пор пока второе яицо не разобьется. Если же 1-е не разбилось с 10го, кидаем с 20го итд.
В самом худшем случае мы бы кинули с 100го первое яицо и оно разбилось, а затем бы еще кинули второе с 91, 92, ... , 99. В таком случае максимальное число шагов было бы 19 т.к. мы кидали с 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 91, 92, 93, 94, 95, 96, 97, 98, 99.

Что произошло когда за дело взялся ont
построив ряд чисел как ont, получается что y вовсе не число, а функция, а точнее ряд.
Проще говоря y=Y(i).
Тогда задача приобретает вид:

c=СУММАi=1..n(y(i))
s=n+y(n)-1

где n - кол-во разбиений
Задача здесь сводиться к поиску ф-ции y=Y(i). В варианте ont'а y=16-i, а n=9 => s=9+y(9)-1=9+7-1=15. И пусть здесь с=99, а не 100 это ничего не меняет т.к. зная результат 99го мы знаем результат 100го => с точки зрения меры снятия неопределености этот вариант монопенисуальный, да и к тому же возможно я просто напутал что-то с единицами. Хотя скорее всего в варианте ont'а 10 отрезков и последний должен быть длиной 6 т.е. s=10+y(10)-1=10+6-1 просто в нем нет никакого смысла т.к. при этажности в 100 его конец (105) выходит за рамки т.е. нам нужно ограничить конец в 100 => длина будет 1 т.е. y(10)=1 и тогда s=n+y(n-1)-1. Но это уже похоже на подгон поэтому забьем.

Под такую универсальную формулу легко укладывается мое первое решение т.к. оно является частным случаем y(i)=const:

y=10
n=10
s=10+10-1=19
c=10+10+10+10+10+10+10+10+10+10=100


Цитата:
А такую задачу, похоже, могли давать на собеседовании в google
Задачу дали на собеседовании в контору _http://herocraft.com/, примечательно, что когда я сказал свое решение они сказали что ответ сами не знают.
__________________
Контактный XMPP: lukmus[собака]wallstreetjabber.biz
lukmus вне форума   Ответить с цитированием
Ответ

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра

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

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

Быстрый переход



Powered by vBulletin® Version 3.8.5
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd. Перевод: zCarot