Python : Длинная задача на лучший и наихудший случаи

[Martin_M]

Задача на стеклянные шары и здания.
Цель: определить "критический этаж", падая с которого, шар разбивается.

Что дано: Переменная BUILDING, представляющая собой dict() с двумя ключами keys:

- первый ключ : 'nb_floors' это количество этажей в здании, значение это натуральное число не равное нулю, этажи пронумерованы от 0 до BUILDING['nb_floors']-1.
- второй ключ : 'boom' это этаж, падая с коротого шар разбивается. Значением является предикат, который отправляет True, если шар разбивается и False, если нет.

Моя версия предиката:

def check(i):
    if i >= 'критический этаж':
        return True
    else: 
        return False

Предположим, что количество этажей в здании 9, а шар начинает разбиваться с 5 этажа.
Моя версия значения BUILDING в таком случае :

BUILDING = { 'nb_floors' : list(range(1, 9)),
                      'boom' : check }

Полноценный код для определения критического этажа:

Используется синтаксис Python

def algo():
    grand_pas = int(sqrt(BUILDING['nb_floors']))
    assert BUILDING['nb_floors'] == grand_pas ** 2

    i=0
    while i < BUILDING['nb_floors'] and not BUILDING['boom'](i):
        i = i + grand_pas
    if i == 0:
        return i
    else:
        j = i - grand_pas + 1
        while j < i and not BUILDING['boom'](j):
            j = j + 1
        return j  
 

Вопрос 1.

Используя значение 'nb_floors' определите лучший случай. В этом случает сколько падений шара(обращений к BUILDING['boom']) было совершено.

Вот на этом вопросе я перестаю понимать что от меня хотят. Поиск выдал только эту статью по сортировке. http://py-algorithm.blogspot.fr/2011/11/quicksort.html

Вопрос 2.

То же самое только для худшего случая.

Найден был этот вопрос, но чтиво ситуацию не прояснило. http://stackoverflow.com/questions/4857919/why-is-does-dict-have-worst-case-on-for-so-many-operations

Что есть "лучший и худший" случаи? Как реализовать функцию в моей задаче? Объясните мне на пальцах,если это возможно.

И огромное спасибо за то, что все это прочитали!

[Aritaborian]

Martin_M в сообщении #1121380 писал(а):

И огромное спасибо за то, что все это прочитали!

А вам ни разу не спасибо на неряшливо сформулированную задачу. Я тоже сейчас изучаю Python; увидев заголовок топика, понадеялся прочесть что-то интересное. Увы, блин. Давайте вы всё это быстренько переформулируете до читаемо-воспринимаемого вида и будем вместе решать.

[Martin_M]

Aritaborian ну не спасибо мне, ладно. Может мне перед вами извиниться за то, что разочаровал вас своим вопросом? Не будте фамильярны, прошу вас, если человек задает вопрос еще не означает, что он хуже или глупее вас.

Что конткретно омерзительно и нечитаемо? код? текстовый контент? Дано? Вопросы? Что?

Есть здание в 9 этажей, при помощи кода, приведенного выше, обнаружили что шар начинает разбиваться падая с пятого этажа и выше.

Мне не понятно, что именно подразумевается в контексте задачи под "наилучшим и наихудшим" случаем для значения 'nb_floors'.

-- 06.05.2016, 13:19 --

Toucan, maxal,
Можно удалить или закрыть тему с задачей?

[12d3]

Martin_M в сообщении #1121380 писал(а):

Что есть "лучший и худший" случаи?

В зависимости от того, чему равен критический этаж, требуется разное количество сбрасываний шарика в данном алгоритме. Лучший случай - это когда требуется наименьшее количество, а худший - когда наибольшее. Вам нужно перебрать в цикле все возможные значения критического этажа и подсчитать, сколько вызовов функции функции check было сделано в каждом случае, найти наибольшее и наименьшее значение количества вызовов.

[Munin]

Конкретно в этой задаче есть и другой параметр оптимизации: разбить как можно меньше шариков.

[provincialka]

А вот кстати, да. В питоне я не разбираюсь, а вот на математической олимпиаде у нас была такая задача:

Цитата:

Имеется $k$ одинаковых стеклянных шариков. Их кидают с некоторых этажей $1000$ этажного дома. Требуется за наименьшее число бросаний $X$ определить самый нижний этаж, при бросании с которого шарики разбиваются (или убедиться, что таких этажей в доме нет). Вычислить $X$ а) для $k = 2$; б) для $k = 3$.

[StaticZero]

provincialka в сообщении #1121675 писал(а):

Вычислить $X$ а) для $k = 2$; б) для $k = 3$.

А разве двух/трёх шариков будет достаточно?..

[provincialka]

Почему нет? И одного достаточно. Бросайте начиная с первого этажа подряд, пока не разобьется.

Цитата:

Ответ. а) $X = 45$; б) $X = 19$.

У меня и решение есть, если хотите. Но только, мне кажется, это другая задача. Ваша, как мне показалось, для $k=1$

[Aritaborian]

(Оффтоп)

Martin_M в сообщении #1121485 писал(а):

Что конткретно омерзительно и нечитаемо?

Слова «омерзительно» у меня не было, не передёргивайте. Насчёт претензии к нечитаемости прошу у вас прощения, был неправ. Это не столько вы что-то плохо написали, сколько я не смог в написанном разобраться.

[mihaild]

(Оффтоп)

С помощью вычислений и OEIS есть нашлась красивая формула для "максимума этажей для $n$ попыток и $k$ шаров", доказывающаяся расписыванием: $\sum_{i=0}^k C_n^i$. До нее можно догадаться как-то честно?

[provincialka]

mihaild
У меня есть некое решение, но здесь это оффтоп. Впрочем, вдруг автору пригодится? Оно расписано только для $k=2; k=3$, поскольку задача была на олимпиаде. Приведу его как есть, для задачи с олимпиады 2010 года.

(Оффтоп)

Задача 10-8. Имеется $k$ одинаковых стеклянных шариков. Их кидают с некоторых этажей $1000$ этажного дома. Требуется за наименьшее число бросаний $X$ определить самый нижний этаж, при бросании с которого шарики разбиваются (или убедиться, что таких этажей в доме нет). Вычислить $X$ а) для $k = 2$; б) для $k = 3$.
Ответ. а) $X = 45$; б) $X = 19$.
Решение. Нам требуется по числу этажей в доме найти необходимое число бросков. Попробуем решить обратную задачу: по числу бросков найти этажность, для которой гарантировано можно определить самый нижний этаж разбития шаров.
Обозначим через $p(k, n)$ максимальную этажность дома, для которого это можно сделать $k$ шарами за $n$ бросаний. Можно считать, что $p(k, 0) = 0$.

Рассмотрим сначала случай $k = 1$. Если мы бросим шарик хотя бы со второго этажа и он разобьется, то мы не узнаем, можно ли его было бросить с первого. Итак, один шарик надо бросать с 1-го, 2-го и так далее этажей, пока он не разобьется. Значит, $p(1, n) = n$.

Пусть теперь шариков больше, чем 1. Бросим первый шарик с этажа $s_n$. Если он разбился, то у нас остается $k - 1$ шарик, $n-1$ бросок и $s_n -1$ непроверенных этажей. Значит, $s_n - 1 \leqslant p(k -1, n - 1) $ и максимальное $s_n = p(k -1, n - 1) + 1$. В частности, $s_1 = p(k -1, 0) + 1 = 1$. Более высокие, чем $s_n$, этажи проверять не надо, так что $p(k, n) \geqslant s_n$.

Если же при первом бросании шар остался цел, то мы имеем в распоряжении еще $(n - 1)$ попытку и снова $k$ целых шара. За $n - 1$ попытку мы можем проверить $p(k, n - 1)$ этажей, начиная с номера $s_n + 1$ (все более низкие проверять уже не надо). Поэтому мы можем определить нужный этаж во всем интервале от 1 до $s_n + p(k, n -1)$.

Итак, $p(k, n) = s_n + p(k, n - 1)$, откуда $p(k, n) = \sum\limits_{i=1}^n s_i$ где $s_n = p(k -1, n - 1) + 1$.
а) Пусть у нас есть два шарика. Имеем $s_n = p(1, n - 1) + 1 = n$. Тогда $p(2, n) = \sum\limits_{i=1}^n i = \frac{n(n + 1)}{2}$. Поскольку $\frac{44(44 + 1)}2 < 1000 < \frac{45(45 + 1)}2, то X = 45$.
б) Для трех шариков имеем $p(3, n) = \sum\limits_{i=1}^n s_i$ , где $s_i = p(2, i - 1) + 1 = \frac{(i-1)i}2 + 1$. Последнее выражение можно переписать в виде $\frac16(i^3 - (i - 1)^3 + 5)$. Суммируя по $i$ от $1$ до $n$, получим $p(3, n) = 1/6(n^3 + 5n)$. (Замечание. Можно использовать и стандартные формулы для сумм степеней).
Поскольку $\frac{5\cdot18 +18^3}6 < 1000 < \frac{5\cdot19 +19^3}6 $, то $X = 19$.

[maxal]

У нас эта задача также уже обсуждалась: topic9229.html

[Geen]

Martin_M в сообщении #1121485 писал(а):

Что конткретно омерзительно и нечитаемо? код? текстовый контент? Дано? Вопросы? Что?

1. При чём здесь python (в заголовке темы)?
2. Во вступительной части (до вопросов) очень трудно отделить описание задачи от ваших попыток её решения.
3. nb_floors - это таки целое или лист?
4.

Martin_M в сообщении #1121380 писал(а):

Моя версия значения BUILDING в таком случае :

- где в этой версии фигурирует число 5?
5. Что произойдёт при выполнении "полноценного кода" если этажей в здании 8?
6. Так сколько шаров есть в распоряжении? "Полноценный код" намекает, что два. Но в условиях задачи это должно ведь быть? или "тот самый код" вам дан как часть условий задачи?
7. Возможно даже вы привели дословные формулировки вопросов, но понять их смысл мешает список выше.
8.

Martin_M в сообщении #1121485 писал(а):

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

- ну давайте вместо задачи будем обсуждать кто хуже и глупее. Видимо для вас это более важный вопрос.

[_Ivana]

mihaild, я тоже с помощью бессонной ночи с Матлабом и OEIS. Даже потом эту задачку на некий сайт выложил http://www.codewars.com/kata/faberge-ea ... crush-test

[petrov_ich]

Что тут сложного с точки зрения програмиста? Зачем эти формулы?

1. Если шарик 1, то и стратегия только одна - бросать его последовательно с первого этажа и выше, пока не разобьётся.

2. Если количество шариков не ограничено, но нужно сделать как можно меньше попыток - делим этажи на 2. Для 100-этажного здания - сбрасываем с 50-го этажа. Если разбился, берём нижние этажи и делим на 2 - сбрасываем с 25-го. Если не разбился - берём верхние этажи, делим на 2 - сбрасываем с 75-го. И так далее.

3. Если шариков ограниченное количество - то сперва выполняем п. 2, а когда останется последний шарик - переход к п. 1.