форум kia ceed > Всячина > Рюмочная (Модераторы: Koteich, Гена, Мадама)

 

Задачка про бачки

Страницы: [1] 2   Вниз
Автор Тема: Задачка про бачки  (Прочитано 2627 раз)
0 Пользователей и 1 Гость смотрят эту тему.
CarUser
  • Hero Member
  • *****
  • Автор темы

  • Russian Federation Москва СВАО (Лианозово)/Мытищи

    ODO 530 km

  • Оффлайн Оффлайн
  • Сообщений: 1216

  • Благодарности
    -Выданные: 5
    -Полученные: 4


Как говориться, обещанного три года ждут. Простите, у меня ыврубался интернет на неделю :( sux
Но теперь выкладываю, как и обещал.
Итак, задача!

ОАО "Мытищистройкомплект" построило дом в 100 этажей (ГК еще не прошла)

У нас есть два абсолютно одинаковых сортирных бачка из квартир на 1 этаже.
Если сбросить бачок с N-го этажа - он может либо разбиться, либо нет. Если не разбился, то нисколько не попортился (то есть, с N-го этажа можно кидать сколько угодно).

Задача за какое минимальное число попыток для любых двух одинаковых бачков можно определить максимальный номер этажа, с которого можно скинуть бачок так, чтобы он не разбился.
Записан
.fedorov
  • Hero Member
  • *****

  • Russian Federation Москва....Нагорная - Лефортово

    ODO 0 km

  • Оффлайн Оффлайн
  • Сообщений: 610

  • Благодарности
    -Выданные: 0
    -Полученные: 1

    • Only Dropped Resto Club
0

Количество "безопасных" этажей + 1 "небезопасный".......Каждый раз подниматься на один этаж и бросать....
Т.е. N+1....Наверное так....

Хотя бачок упав с первого этажа уже разобьется.....

Ну а вообще, кому может понадобиться бросать бачки на головы прохожих?  :D
Tashka
  • Мисс CEE'D
  • Hero Member
  • *****

  • Russian Federation г.Москва, ВАО


    Авто: Kia Ceed 1.6 AT
    ODO 60550 km

  • Оффлайн Оффлайн
  • Сообщений: 1939

  • Благодарности
    -Выданные: 20
    -Полученные: 16

0

Хотя бачок упав с первого этажа уже разобьется.....

ммм...могу поспорить, что не разобьется!!!!!
Сейчас в продаже имеются бачки, которые изготовлены не из керамики (санфарфора), а из пластика.  ;)
Такими, как правило, комплектуют места общественного пользования (т.е. бюжетный вариант). :)
Записан


:-) Там где мой СИД - там ЖИЗНЬ кипит!!!
Удачи на дорогах!!!!
BRiWS
  • Full Member
  • ***

  • Russian Federation Москва

    ODO 0 km

  • Оффлайн Оффлайн
  • Сообщений: 206

  • Благодарности
    -Выданные: 1
    -Полученные: 0

0

Чтобы установить число N, которое не известно, имея в своём распоряжении лишь два бачка, кидаем первый с 50-го (или 51) этажа (делим дом пополам). Если разбивается - идем поочередно вторым бачком с первого до 49 (50) включительно. Получаем 50-51 кидание. Если не разбивается - то будет быстрее. Поэтому, думается, надо вводить коррективы.

Если разбить дом на 3 части... Кидаем первый бачок с первой трети. Т.е. с 33 этажа... Если разбивается - "просканировать" вторым бачком займет 33... Если бачок выживает - кидаем его с 66 этажа... Разбирается - "сканируем" опять с 34 по 65. Тут получается гарантированное определение за 34 кидания. О! И т.д. :) Осталось выделить формулу и найти экстремум.

При дроблении на m частей имеем формулу

q = (m-1)+(100/m)

производная q' = 1 + 100 * (-1/ m^2)
Т.е.
100/m^2 = 1
m^2 = 100
m = 10

Итог - при дроблении на 10 частей мы найдем нужный этаж за 19 попыток.
Записан
rylila
  • Гость
0

СаrUser,а представь,что с тобой сделают ХОЗЯЕВА ЭТИХ БАЧКОВ! У тебя фантазия хорошая,подумай! А надо ли их бросать. :-D
Записан
rylila
  • Гость
0

И еще подумай,ЧТО потом тебе сделают люди снизу,на чьи головы эти бачки полетят. :-D :-D  эх,бедный,бедный СаrUsеr! :-D :-D :-D
Записан
CarUser
  • Hero Member
  • *****
  • Автор темы

  • Russian Federation Москва СВАО (Лианозово)/Мытищи

    ODO 530 km

  • Оффлайн Оффлайн
  • Сообщений: 1216

  • Благодарности
    -Выданные: 5
    -Полученные: 4

0

Флудеры :D
Еще варианты ответов будут? BRiWS дал ответ 19 попыток. Кто меньше? ;)
Записан
BRiWS
  • Full Member
  • ***

  • Russian Federation Москва

    ODO 0 km

  • Оффлайн Оффлайн
  • Сообщений: 206

  • Благодарности
    -Выданные: 1
    -Полученные: 0

0

Флудеры :D
Еще варианты ответов будут? BRiWS дал ответ 19 попыток. Кто меньше? ;)
При бесконечном числе бачков теоретически возможный минимум - 7 попыток (log(2)100 - методом деления пополам)
Записан
CarUser
  • Hero Member
  • *****
  • Автор темы

  • Russian Federation Москва СВАО (Лианозово)/Мытищи

    ODO 530 km

  • Оффлайн Оффлайн
  • Сообщений: 1216

  • Благодарности
    -Выданные: 5
    -Полученные: 4

0

Нет. За 7 попыток найти искомый этаж не реально.
Записан
BRiWS
  • Full Member
  • ***

  • Russian Federation Москва

    ODO 0 km

  • Оффлайн Оффлайн
  • Сообщений: 206

  • Благодарности
    -Выданные: 1
    -Полученные: 0

0

Нет. За 7 попыток найти искомый этаж не реально.
Реально, имея бесконечный запас бачков :) Кидаем с 50-го... Разбился - кидаем с 25го... Не разбился - с 75... Затем, соответственно с 12-13, 37-38, 62-63 и 87-88... Каждый раз делим промежуток пополам. Всего за семь бросков сканируется 100-этажный дом.
На таком принципе базируется поиск по индексам типа binary-tree (бинарное дерево) в базах данных.
Записан
Kensai
  • Гость
« Ответ #10 : Апрель 06, 2008, 17:47:00 pm »
0

анекдот в тему вспомнил.
два кирпича лежат на крыше многоэтажки. Один из старой кладки, второго только вчера положили.
Внизу ходят люди. Молодой спрашивает:
1- ну,что вон мужик идёт, падаем?
2- не, неинтересно.
1- а вон второй?
2- не, не пойдёт. А вон на того в жёлтой каске падаем!
1- так мы же разобьёмся? толк какой?
2-Эх, молодёж, всему вас учить надо. Эй, мужик!
мужик в каске, поднимая голову вверх - чё?

всего навсего две попытки. После первой придёт прораб и вставит всем люлей, да так, что оставшийся бачок придёться вернуть на 1 этаж =)
 beer
Записан
Goshanchik
  • Jr. Member
  • **

  • Russian Federation Нижний Новгород - Молитовка

    ODO 0 km

  • Оффлайн Оффлайн
  • Сообщений: 94

  • Благодарности
    -Выданные: 0
    -Полученные: 0

« Ответ #11 : Апрель 06, 2008, 17:51:26 pm »
0

анекдот в тему вспомнил.
два кирпича лежат на крыше многоэтажки. Один из старой кладки, второго только вчера положили.
Внизу ходят люди. Молодой спрашивает:
1- ну,что вон мужик идёт, падаем?
2- не, неинтересно.
1- а вон второй?
2- не, не пойдёт. А вон на того в жёлтой каске падаем!
1- так мы же разобьёмся? толк какой?
2-Эх, молодёж, всему вас учить надо. Эй, мужик!
мужик в каске, поднимая голову вверх - чё?

всего навсего две попытки. После первой придёт прораб и вставит всем люлей, да так, что оставшийся бачок придёться вернуть на 1 этаж =)
 beer

Прикольно!  :D
Записан
jenya12355
  • Hero Member
  • *****

  • Russian Federation Уфа

    ODO 0 km

  • Оффлайн Оффлайн
  • Сообщений: 4427

  • Благодарности
    -Выданные: 1
    -Полученные: 9

« Ответ #12 : Апрель 07, 2008, 00:42:59 am »
0

Мне кажется, что правильный ответ 16.
Записан
Мимолет
  • Гость
« Ответ #13 : Апрель 07, 2008, 10:27:01 am »
0

У мну 14.
Записан
jenya12355
  • Hero Member
  • *****

  • Russian Federation Уфа

    ODO 0 km

  • Оффлайн Оффлайн
  • Сообщений: 4427

  • Благодарности
    -Выданные: 1
    -Полученные: 9

« Ответ #14 : Апрель 07, 2008, 11:01:55 am »
0

В 14 верится с трудом.
Как ни пробовал, даже с 15-ти попыток в худшем случае не получается.
Записан
Страницы: [1] 2   Вверх

Чтобы прокомментировать данную тему, или создать новую зарегистрируйтесь или зайдите на форум под своей учетной записью.


форум kia ceed > Всячина > Рюмочная (Модераторы: Koteich, Гена, Мадама)

 

Задачка про бачки

 

Новые фотографии галереи. Добавь и свою!
СМОТРЕТЬ ЕЩЕ! :)...
     3   настроить
или быстрая регистрация и вход через ВК

Новые фотографии ↓
Вce новые фото →
Рейтинг автосервисов kia ↓
Каширка 39 (Москва) →  70 


FAVORIT MOTORS СЕВЕР (Москва) →  51 

АвтоГЕРМЕС (Москва) →  39 

МАРЬИНО АВТО (Москва) →  33 


Весь рейтинг сервисов kia →
Чтобы добавить свой отзыв о сервисе - зарегистрируйся


  Мобильная версия Контакты администрации
Реклама: