Пазл с фонтаном шампанского

Пустые стаканы с водой располагаются в следующем порядке:

Когда вы наливаете жидкость в 1-й стакан, если он полон, то дополнительная жидкость будет поступать в стаканы 2 и 3 в равных количествах. Когда стакан 2 заполнен, лишняя жидкость будет переливаться в 4 и 5 и так далее.

Учитывая, что N литров жидкости и максимальная вместимость каждого стакана составляет 1 литр, укажите количество жидкости, присутствующей в любом стакане, если вы опорожняете N литров жидкости, наливая в стакан, выполняя функцию, getWaterInBucket(int N, int X)где X - номер стекла. Так, например, если я хочу иметь 4 литра в начале, и я хочу найти воду в стакане 3, функцияgetWaterInBucket(4, 3)

Как мне решить это программно? Я попытался найти математическое решение, используя треугольник Паскаля. Это не сработало. Я считал, что это дерево, поэтому я могу добавить такой параметр, getWaterInBucket(BTree root, int N, int X)а затем попробовать какое-то рекурсивное решение для каждого уровня, но параметры не разрешены в этой задаче. Есть ли что-то очевидное, какая-то хитрость?

Вам просто нужно смоделировать заливку, что-то вроде

void pour(double glasses[10], int glass, double quantity)
{
    glasses[glass] += quantity;
    if(glasses[glass] > 1.0)
    {
         double extra = glasses[glass] - 1.0;
         pour( glasses, left_glass(glass), extra / 2 );
         pour( glasses, right_glass(glass), extra / 2 );
         glasses[glass] = 1.0;
    }
}

double getWaterInGlass(int N, int X)
{
    double glasses[10] = {0,0,0,0,0,0};
    pour(glasses, 0, X);
    return glasses[N];
}

В его нынешнем виде это не дерево. Поскольку разные стаканы вливаются в одни и те же стаканы, это мешает им быть деревом.

Вот как я мог бы ответить на этот вопрос в ситуации интервью (я не видел этот вопрос раньше, и я не смотрел на другие ответы, пока у меня не было своего решения):

Сначала я попытался выяснить это (что вы назвали «математическим решением»), и когда я добрался до стекла 8, я понял, что это будет сложнее, чем казалось, потому что стекло 5 начинает переливаться перед стеклом 4. В этот момент я решил пойти по маршруту рекурсии (просто к вашему сведению, многие вопросы по программированию требуют рекурсии или индукции).

Думая рекурсивно, проблема становится намного легче: сколько воды в стакане 8? Половина суммы, которая пролилась из стаканов 4 и 5 (пока она не заполнится). Конечно, это означает, что мы должны ответить, сколько разлилось из стаканов 4 и 5, но, оказывается, это тоже не сложно. Сколько разлилось из стекла 5? Половина из большого количества разлилась из стаканов 2 и 3, минус литр, который остался в стакане 5.

Решение этого полностью (и грязно) дает:

#include <iostream>
#include <cmath>
using namespace std;

double howMuchSpilledOutOf(int liters, int bucketId) {
    double spilledInto = 0.0;
    switch (bucketId) {
        case 1:
            spilledInto = liters; break;
        case 2:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 1); break;
        case 3:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 1); break;
        case 4:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 2); break;
        case 5:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 2) + 0.5 * howMuchSpilledOutOf(liters, 3); break;
        case 6:
            spilledInto = 0.5 * howMuchSpilledOutOf(liters, 3); break;
        default:
            cerr << "Invalid spill bucket ID " << bucketId << endl;
    }
    return max(0.0, spilledInto - 1.0);
}

double getWaterInBucket(int liters, int bucketId) {
    double contents = 0.0;
    switch (bucketId) {
        case 1:
            contents = liters; break;
        case 2:
            contents = 0.5 * howMuchSpilledOutOf(liters, 1); break;
        case 3:
            contents = 0.5 * howMuchSpilledOutOf(liters, 1); break;
        case 4:
            contents = 0.5 * howMuchSpilledOutOf(liters, 2); break;
        case 5:
            contents = 0.5 * howMuchSpilledOutOf(liters, 2) + 0.5 * howMuchSpilledOutOf(liters, 3); break;
        case 6:
            contents = 0.5 * howMuchSpilledOutOf(liters, 3); break;
        case 7:
            contents = 0.5 * howMuchSpilledOutOf(liters, 4); break;
        case 8:
            contents = 0.5 * howMuchSpilledOutOf(liters, 4) + 0.5 * howMuchSpilledOutOf(liters, 5); break;
        case 9:
            contents = 0.5 * howMuchSpilledOutOf(liters, 5) + 0.5 * howMuchSpilledOutOf(liters, 6); break;
        case 10:
            contents = 0.5 * howMuchSpilledOutOf(liters, 6); break;
        default:
            cerr << "Invalid contents bucket ID" << bucketId << endl;
    }
    return min(1.0, contents);
}

int main(int argc, char** argv)
{
    if (argc == 3) {
        int liters = atoi(argv[1]);
        int bucket = atoi(argv[2]);
        cout << getWaterInBucket(liters, bucket) << endl;
    }
    return 0;
}

В этот момент (или когда я писал это) я бы сказал интервьюеру, что это не идеальное решение в производстве: дублирующий код между howMuchSpilledOutOf()и getWaterInBucket(); должно быть центральное местоположение, которое сопоставляет ведра с их «кормушками». Но в интервью, где скорость и точность реализации более важны, чем скорость выполнения и ремонтопригодность (если не указано иное), это решение является предпочтительным. Затем я предложил бы реорганизовать код, чтобы он был ближе к тому, что я считаю качеством производства, и позволил интервьюеру принять решение.

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

Думать об этом как о проблеме дерева - это красная сельдь, это действительно ориентированный граф. Но забудьте об этом все.

Думайте о стакане где-нибудь ниже верхнего. Над ним будет один или два стакана, которые могут перетекать в него. При соответствующем выборе системы координат (не волнуйтесь, смотрите конец) мы можем написать функцию, чтобы получить «родительские» очки для любого данного стекла.

Теперь мы можем придумать алгоритм, позволяющий получать количество жидкости, наливаемой в стакан, независимо от переполнения из этого стакана. Ответ, однако, заключается в том, что в каждого родителя наливается много жидкости, минус количество, хранящееся в каждом родительском стакане, деленное на 2. Просто сложите сумму для всех родителей. Записываем это как фрагмент python тела функции amount_poured_into ():

# p is coords of the current glass
amount_in = 0
for pp in parents(p):
    amount_in += max((amount_poured_into(total, pp) - 1.0)/2, 0)

Max () должен гарантировать, что мы не получим отрицательное количество переполнения.

Мы почти закончили! Мы выбираем систему координат с 'y' вниз по странице, очки первой строки равны 0, вторая строка равна 1 и т. Д. Координаты 'x' имеют ноль под стеклом верхнего ряда, а вторая строка имеет координаты x -1 и +1, третий ряд -2, 0, +2 и т. Д. Важным моментом является то, что левое или самое правое стекло на уровне у будет иметь абс (х) = у.

Оборачивая все это в python (2.x), мы имеем:

def parents(p):
    """Get parents of glass at p"""

    (x, y) = p
    py = y - 1          # parent y
    ppx = x + 1         # right parent x
    pmx = x - 1         # left parent x

    if abs(ppx) > py:
        return ((pmx,py),)
    if abs(pmx) > py:
        return ((ppx,py),)
    return ((pmx,py), (ppx,py))

def amount_poured_into(total, p):
    """Amount of fluid poured into glass 'p'"""

    (x, y) = p
    if y == 0:    # ie, is this the top glass?
        return total

    amount_in = 0
    for pp in parents(p):
        amount_in += max((amount_poured_into(total, pp) - 1.0)/2, 0)

    return amount_in

def amount_in(total, p):
    """Amount of fluid left in glass p"""

    return min(amount_poured_into(total, p), 1)

Таким образом, чтобы получить сумму на самом деле в стакане при p, используйте amount_in (total, p).

Это не ясно из ОП, но немного о «вы не можете добавить параметры» может означать, что на исходный вопрос необходимо ответить в терминах показанных чисел стекла . Это решается путем записи функции сопоставления номеров витрин во внутреннюю систему координат, использованную выше. Это неудобно, но можно использовать итеративное или математическое решение. Легко понять итеративную функцию:

def p_from_n(n):
    """Get internal coords from glass 'number'"""

    for (y, width) in enumerate(xrange(1, n+1)):
        if n > width:
            n -= width
        else:
            x = -y + 2*(n-1)
            return (x, y)

Теперь просто переписайте приведенную выше функцию amount_in (), чтобы принять номер стекла:

def amount_in(total, n):
    """Amount of fluid left in glass number n"""

    p = p_from_n(n)
    return min(amount_poured_into(total, p), 1)

Интересный.

Это требует подхода моделирования.

private void test() {
  double litres = 6;
  for ( int i = 1; i < 19; i++ ) {
    System.out.println("Water in glass "+i+" = "+getWater(litres, i));
  }
}

private double getWater(double litres, int whichGlass) {
  // Don't need more glasses than that.
  /*
   * NB: My glasses are numbered from 0.
   */
  double[] glasses = new double[whichGlass];
  // Pour the water in.
  pour(litres, glasses, 0);
  // Pull out the glass amount.
  return glasses[whichGlass-1];
}

// Simple non-math calculator for which glass to overflow into.
// Each glass overflows into this one and the one after.
// Only covers up to 10 glasses (0 - 9).
int[] overflowsInto = 
{1, 
 3, 4, 
 6, 7, 8, 
 10, 11, 12, 13, 
 15, 16, 17, 18, 19};

private void pour(double litres, double[] glasses, int which) {
  // Don't care about later glasses.
  if ( which < glasses.length ) {
    // Pour up to 1 litre in this glass.
    glasses[which] += litres;
    // How much overflow.
    double overflow = glasses[which] - 1;
    if ( overflow > 0 ) {
      // Remove the overflow.
      glasses[which] -= overflow;
      // Split between two.
      pour(overflow / 2, glasses, overflowsInto[which]);
      pour(overflow / 2, glasses, overflowsInto[which]+1);
    }
  }
}

какие отпечатки (для 6 литров):

Water in glass 1 = 1.0
Water in glass 2 = 1.0
Water in glass 3 = 1.0
Water in glass 4 = 0.75
Water in glass 5 = 1.0
Water in glass 6 = 0.75
Water in glass 7 = 0.0
Water in glass 8 = 0.25
Water in glass 9 = 0.25
Water in glass 10 = 0.0
...

который кажется правильным.

Это биноминальная функция. Соотношение воды между стаканами уровня N может быть обнаружено с использованием nCr для каждого стекла в уровне. Кроме того, общее количество очков до уровня N является суммой от 1 до (N - 1), формула, по которой вы сможете найти ее достаточно легко. Таким образом, учитывая X, вы должны быть в состоянии определить его уровень и использовать nCr для проверки соотношений очков для этого уровня и, таким образом, определить, сколько воды находится в X, если в любом случае достаточно литров, чтобы спуститься к X.

Во-вторых, ваша идея использования BTree прекрасна, просто BTree является внутренней переменной, а не внешним параметром.

Итак, если вы изучали эту математику в своем образовании (здесь, в Великобритании, ее преподают до университета), вы сможете решить ее без особых проблем.