Champaign Fountain Puzzle

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

введите описание изображения здесь>> </p>

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

<p> Учитывая, что N литров жидкости и максимальной емкости каждого стекла составляет 1 литр, дайте количество жидкости, присутствующей в любом стекле, если вы опорожните N литров жидкости, вливая в стекло, заполнив функцию <code>--- - +: = 0 =: + ----</code>, где X - номер стекла. Так, например, если я хочу иметь 4 литра в начале, и я хочу найти воду в стекле 3, то функция <code>---- +: = 1 =: + ----</code> </p >

<p> Как я могу решить эту проблему программно? Я попытался найти математическое решение, используя треугольник Паскаля. Это не сработало. Я считал это деревом, поэтому я могу добавить такой параметр, как этот <code>---- +: = 2 =: + ----</code>, а затем попробовать некоторое рекурсивное решение для каждого уровня, но параметры не допускается в этой проблеме. Есть ли что-то очевидное, какой-то трюк? </p></body></html>

30 голосов | спросил Slartibartfast 27 Jpm1000000pmSun, 27 Jan 2013 23:24:19 +040013 2013, 23:24:19

5 ответов


35

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

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];
}

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

ответил Winston Ewert 28 Jam1000000amMon, 28 Jan 2013 03:40:24 +040013 2013, 03:40:24
7

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

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

Рекурсивное мышление, проблема становится намного проще: сколько воды в стекле 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(); должно быть центральное расположение, которое отображает ведра на свои «фидеры». Но в интервью, где скорость и точность реализации важнее, чем скорость выполнения и ремонтопригодность (если не указано иное), это решение предпочтительнее. Тогда я бы предложил реорганизовать код, чтобы быть ближе к тому, что я считаю производственным качеством, и пусть интервьюер решает.

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

ответил Tom Panning 28 Jam1000000amMon, 28 Jan 2013 05:50:54 +040013 2013, 05:50:54
5

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

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

Теперь мы можем подумать об алгоритме, чтобы получить количество жидкости, вылитой в стакан, независимо от переполнения из этого стекла. Ответ, однако, много жидкости выливается в каждого родителя за вычетом суммы, хранящейся в каждом родительском стекле, и делится на 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)

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

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

Обернув все это в 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).

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

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)
ответил rzzzwilson 28 Jam1000000amMon, 28 Jan 2013 04:08:01 +040013 2013, 04:08:01
2

Интересно.

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

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
...

, который, кажется, касается права.

ответил OldCurmudgeon 28 Jpm1000000pmMon, 28 Jan 2013 17:49:15 +040013 2013, 17:49:15
-1

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

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

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

ответил DeadMG 27 Jpm1000000pmSun, 27 Jan 2013 23:39:31 +040013 2013, 23:39:31

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132