Puzzle Air Mancur Champaign

Gelas air kosong diatur dalam urutan berikut:

Ketika Anda menuangkan cairan ke gelas 1 jika penuh, maka cairan ekstra akan diterbangkan ke gelas 2 dan 3 dalam jumlah yang sama. Ketika gelas 2 penuh, cairan ekstra akan diterbangkan ke 4 dan 5 dan seterusnya.

Mengingat N liter cairan dan kapasitas maksimum setiap gelas adalah 1 liter, berikan jumlah cairan yang ada di gelas apa pun jika Anda mengosongkan N liter cairan dengan menuangkan ke dalam gelas dengan mengisi fungsi di getWaterInBucket(int N, int X)mana X adalah nomor gelas. Jadi misalnya jika saya ingin memiliki 4 liter di awal dan saya ingin menemukan air dalam gelas 3 fungsinyagetWaterInBucket(4, 3)

Bagaimana cara saya menyelesaikan masalah ini secara terprogram? Saya mencoba mencari solusi matematika menggunakan segitiga Pascal. Ini tidak berhasil. Saya menganggapnya sebagai pohon sehingga saya dapat menambahkan parameter seperti ini getWaterInBucket(BTree root, int N, int X)dan kemudian mencoba beberapa solusi rekursif untuk setiap level, tetapi parameter tidak diperbolehkan dalam masalah ini. Apakah ada sesuatu yang jelas, suatu trik?

Anda hanya perlu mensimulasikan penuangan, semacamnya

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

Seperti berdiri, ini bukan pohon. Karena gelas yang berbeda mengalir ke gelas yang sama, itu mencegahnya menjadi pohon.

Inilah cara saya akan menjawab pertanyaan ini dalam situasi wawancara (saya belum pernah melihat pertanyaan ini sebelumnya, dan saya tidak melihat jawaban lain sampai saya punya solusi):

Pertama, saya mencoba untuk mencari tahu (yang Anda sebut "solusi matematika") dan ketika saya sampai di gelas 8 saya menyadari bahwa itu akan lebih sulit daripada yang terlihat karena gelas 5 mulai meluap sebelum kaca 4. Pada saat itu saya memutuskan untuk turun rute rekursi (hanya FYI, banyak pertanyaan wawancara pemrograman membutuhkan rekursi atau induksi untuk menyelesaikannya).

Berpikir secara rekursif, masalahnya menjadi lebih mudah: Berapa banyak air dalam gelas 8? Setengah dari jumlah yang telah tumpah dari kacamata 4 dan 5 (sampai penuh). Tentu saja, itu berarti kita harus menjawab berapa banyak yang tumpah dari kacamata 4 dan 5, tetapi ternyata itu juga tidak terlalu sulit. Berapa banyak yang tumpah dari gelas 5? Setengah dari bagaimanapun banyak tumpah dari gelas 2 dan 3, minus liter yang tinggal di gelas 5.

Memecahkan ini sepenuhnya (dan berantakan) memberi:

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

Pada titik ini (atau ketika saya sedang menulis ini), saya akan mengatakan kepada pewawancara bahwa ini bukan solusi yang ideal dalam produksi: ada kode duplikat antara howMuchSpilledOutOf()dan getWaterInBucket(); harus ada lokasi sentral yang memetakan ember ke "pengumpan" mereka. Tetapi dalam sebuah wawancara, di mana kecepatan dan ketepatan implementasi lebih penting daripada kecepatan eksekusi dan pemeliharaan (kecuali dinyatakan sebaliknya), solusi ini lebih disukai. Kemudian saya akan menawarkan untuk memperbaiki kode agar lebih dekat dengan apa yang saya anggap berkualitas-produksi, dan biarkan pewawancara memutuskan.

Catatan akhir: Saya yakin kode saya memiliki kesalahan ketik di suatu tempat; Saya akan menyebutkan hal itu kepada pewawancara juga dan mengatakan bahwa saya akan merasa lebih percaya diri setelah melakukan refactoring atau pengujian unit.

Memikirkan ini sebagai masalah pohon adalah herring merah, itu benar-benar grafik terarah. Tapi lupakan semua itu.

Pikirkan gelas di mana saja di bawah yang atas. Ini akan memiliki satu atau dua gelas di atasnya yang dapat meluap ke dalamnya. Dengan pilihan sistem koordinat yang tepat (jangan khawatir, lihat bagian akhir) kita dapat menulis fungsi untuk mendapatkan kacamata "induk" untuk setiap gelas yang diberikan.

Sekarang kita dapat memikirkan algoritma untuk mendapatkan jumlah cairan yang dituangkan ke dalam gelas, terlepas dari luapan dari gelas itu. Namun jawabannya adalah banyak cairan dituangkan ke masing-masing orangtua dikurangi jumlah yang disimpan dalam setiap gelas orangtua, dibagi dengan 2. Hanya jumlah itu untuk semua orangtua. Menulis ini sebagai fragmen python dari tubuh fungsi number_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)

Maks () adalah untuk memastikan kami tidak mendapatkan jumlah luapan negatif.

Kami hampir selesai! Kami memilih sistem koordinat dengan 'y' di bawah halaman, gelas baris pertama adalah 0, baris kedua adalah 1, dll. Koordinat 'x' memiliki angka nol di bawah kaca baris atas dan baris kedua memiliki koordinat x -1 dan +1, baris ketiga -2, 0, +2, dan seterusnya. Poin penting adalah bahwa gelas paling kiri atau paling kanan di level y akan memiliki abs (x) = y.

Membungkus semua itu menjadi python (2.x), kita memiliki:

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)

Jadi untuk mendapatkan jumlah sebenarnya dalam gelas di p, gunakan jumlah_in (total, p).

Tidak jelas dari OP, tetapi sedikit tentang "Anda tidak dapat menambahkan parameter" mungkin berarti pertanyaan asli harus dijawab dalam hal nomor kaca yang ditampilkan. Ini diselesaikan dengan menulis fungsi pemetaan dari nomor kaca pertunjukan ke sistem koordinat internal yang digunakan di atas. Itu fiddly, tetapi solusi iteratif atau matematis dapat digunakan. Fungsi iteratif yang mudah dipahami:

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)

Sekarang cukup tulis ulang fungsi number_in () di atas untuk menerima nomor gelas:

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)

Menarik.

Ini mengambil pendekatan simulasi.

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

yang mencetak (untuk 6 liter):

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

yang tampaknya benar.

Ini adalah fungsi binomial. Rasio air antara gelas level N dapat ditemukan menggunakan nCr untuk setiap gelas di level tersebut. Selain itu, jumlah total kacamata sebelum ke level N adalah jumlah dari 1 hingga (N - 1), sebuah formula yang Anda harus dapat menemukannya dengan cukup mudah. Jadi, mengingat X, Anda harus dapat menentukan levelnya, dan menggunakan nCr untuk memeriksa rasio kacamata untuk level itu, dan dengan demikian menentukan berapa banyak air dalam X, jika ada cukup liter untuk turun ke X.

Kedua, ide Anda menggunakan BTree baik-baik saja, hanya saja BTree adalah variabel internal, bukan parameter eksternal.

TKI, jika Anda sudah membahas matematika ini dalam pendidikan Anda (di Inggris ini diajarkan sebelum masuk universitas) maka Anda harus dapat menyelesaikannya tanpa terlalu banyak masalah.