Рубрики

Программа, чтобы найти количество воды в данном стакане

Динамическое программирование, Математика, Рекурсия

Есть несколько стаканов с такой же емкостью, как 1 литр. Очки хранятся следующим образом: 

                   1
                 2   3
              4    5    6
            7    8    9   10

Вы можете положить воду только на верхнее стекло. Если вы наливаете более 1 литра воды в 1-й стакан, вода переливается и заполняется одинаково во 2-й и 3-й стаканах. Стакан 5 будет получать воду из 2-го и 3-го стакана и так далее.
Если у вас есть X литров воды и вы положили эту воду в верхнее стекло, сколько воды будет содержаться в j-м стекле в этом ряду?

Пример. Если вы положите 2 литра сверху.
1-й — 1 литр
2-ой — 1/2 литра
3-й — 1/2 литра

Подход аналогичен методу 2 треугольника Паскаля . Если мы более внимательно посмотрим на проблему, проблема сводится к треугольнику Паскаля .

                           1   ---------------- 1
                 2   3 ---------------- 2
                      4    5    6  ------------ 3
            7    8    9   10  --------- 4

Каждый стакан способствует двум стаканам вниз по стакану. Изначально мы помещаем всю воду в первый стакан. Затем мы держим в нем 1 литр (или менее 1 литра) и опускаем оставшуюся воду в два стакана. Мы следуем той же процедуре для двух стаканов и всех остальных стаканов до i-го ряда. До i-го ряда будет i * (i + 1) / 2 стакана.

C ++

// Программа для определения количества воды в j-ом стакане
// из i-го ряда
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

  
// Возвращает количество воды в j-м стакане i-го ряда

float findWater(int i, int j, float X)

{

    // Номер строки i имеет максимум i столбцов. Так что вход

    // номер столбца должен быть меньше чем я

    if (j > i)

    {

        printf("Incorrect Inputn");

        exit(0);

    }

  

    // До i-го ряда будут i * (i + 1) / 2 стакана

    // (включая i-ю строку)

    float glass[i * (i + 1) / 2];

  

    // Инициализируем все очки как пустые

    memset(glass, 0, sizeof(glass));

  

    // Положите всю воду в первый стакан

    int index = 0;

    glass[index] = X;

  

    // Теперь дайте воде стечь в нисходящие очки

    // до тех пор, пока номер строки не станет меньше или равен i (заданная строка)

    // коррекция: X может быть нулевым для боковых очков, так как они имеют меньшую скорость заполнения

    for (int row = 1; row <= i ; ++row)

    {

        // Заполнить очки в данной строке. Количество

        // столбцы в строке равны номеру строки

        for (int col = 1; col <= row; ++col, ++index)

        {

            // Получить воду из текущего стекла

            X = glass[index];

  

            // Сохраняем сумму меньше или равную

            // емкость в текущем стекле

            glass[index] = (X >= 1.0f) ? 1.0f : X;

  

            // Получить оставшуюся сумму

            X = (X >= 1.0f) ? (X - 1) : 0.0f;

  

            // Распределить оставшуюся сумму по

            // вниз два стакана

            glass[index + row] += X / 2;

            glass[index + row + 1] += X / 2;

        }

    }

  

    // Индекс j-го стекла в i-м ряду будет

    // be i * (i-1) / 2 + j - 1

    return glass[i*(i-1)/2 + j - 1];

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int i = 2, j = 2;

    float X = 2.0; // Общее количество воды

  

    printf("Amount of water in jth glass of ith row is: %f",

            findWater(i, j, X));

  

    return 0;

}

Джава

// Программа для поиска суммы
/// воды в j-ом стакане
// из i-го ряда

import java.lang.*;

  

class GFG

{
// Возвращает количество воды
// в j-ом стакане i-го ряда

static float findWater(int i, int j, 

                       float X)

{
// номер строки у меня есть максимум я
// столбцы. Итак, входной столбец
// число должно быть меньше чем я

if (j > i)

{

    System.out.println("Incorrect Input");

    System.exit(0);

}

  
// Будут очки i * (i + 1) / 2
// до i-го ряда (включая i-й ряд)

int ll = Math.round((i * (i + 1) ));

float[] glass = new float[ll + 2];

  
// Положите всю воду в первый стакан

int index = 0;

glass[index] = X;

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

for (int row = 1; row <= i ; ++row)

{

    // Заполнить очки в данной строке. Количество

    // столбцы в строке равны номеру строки

    for (int col = 1; 

             col <= row; ++col, ++index)

    {

        // Получить воду из текущего стекла

        X = glass[index];

  

        // Сохраняем сумму меньше или

        // равна емкости в текущем стекле

        glass[index] = (X >= 1.0f) ? 1.0f : X;

  

        // Получить оставшуюся сумму

        X = (X >= 1.0f) ? (X - 1) : 0.0f;

  

        // Распределить оставшуюся сумму

        // вниз два стакана

        glass[index + row] += X / 2;

        glass[index + row + 1] += X / 2;

    }

}

  
// Индекс j-го стекла в i-м
// строка будет i * (i-1) / 2 + j - 1

return glass[(int)(i * (i - 1) / 

                   2 + j - 1)];

}

  
// Код драйвера

public static void main(String[] args)

{

    int i = 2, j = 2;

    float X = 2.0f; // Общее количество воды

    System.out.println("Amount of water in jth " +

                         "glass of ith row is: " + 

                              findWater(i, j, X));

}
}

  
// Этот код предоставлен mits

python3

# Программа для поиска суммы
количество воды в j-ом стакане
# я бросаю

  
# Возвращает количество воды
# в j-ом стакане i-го ряда

def findWater(i, j, X):

    # Номер строки у меня есть максимум

    # я столбцы. Итак, входной столбец

    # номер должен быть меньше, чем я

    if (j > i):

        print("Incorrect Input");

        return;

  

    # Там будет я * (я + 1) / 2

    # очки до i-го ряда

    # (включая i-ю строку)

    # и инициализировать все очки

    # как пустой

    glass = [0]*int(i *(i + 1) / 2);

  

    # Положи всю воду

    # в первом стакане

    index = 0;

    glass[index] = X;

  

    # Теперь позвольте воде течь к

    # вниз очки до

    # номер строки меньше

    # чем или / равно мне (дано

    # строка) исправление: X может быть

    # ноль для боковых очков как

    # у них более низкий уровень заполнения

    for row in range(1,i):

        # Заполнить очки в данном

        # строка. Число столбцов

        # в строке равно номеру строки

        for col in range(1,row+1):

            # Получить воду

            # из текущего стекла

            X = glass[index];

  

            # Держите сумму меньше

            # чем или равно

            # емкость в текущем стекле

            glass[index] = 1.0 if (X >= 1.0) else X;

  

            # Получить оставшуюся сумму

            X = (X - 1) if (X >= 1.0) else 0.0;

  

            # Распределить оставшиеся

            # сумма до двух стаканов

            glass[index + row] += (X / 2);

            glass[index + row + 1] += (X / 2);

            index+=1;

  

    # Индекс j-го стекла

    # в i-м ряду будет

    # be i * (i-1) / 2 + j - 1

    return glass[int(i * (i - 1) /2 + j - 1)];

  
Код водителя

if __name__ == "__main__":

      

    i = 2;

    j = 2;

    X = 2.0; 

# Общее количество воды

  

    res=repr(findWater(i, j, X));

    print("Amount of water in jth glass of ith row is:",res.ljust(8,'0'));

# Этот код предоставлен mits

C #

// Программа для поиска суммы
// воды в j-ом стакане
// из i-го ряда

using System;

  

class GFG

{
// Возвращает количество воды
// в j-ом стакане i-го ряда

static float findWater(int i, int j, 

                       float X)

{
// номер строки у меня есть максимум я
// столбцы. Итак, входной столбец
// число должно быть меньше чем я

if (j > i)

{

    Console.WriteLine("Incorrect Input");

    Environment.Exit(0);

}

  
// Будут очки i * (i + 1) / 2
// до i-го ряда (включая i-й ряд)

int ll = (int)Math.Round((double)(i * (i + 1)));

float[] glass = new float[ll + 2];

  
// Положите всю воду в первый стакан

int index = 0;

glass[index] = X;

  
// Теперь дайте воде течь к
// вниз очки до ряда
// число меньше или равно
// для меня (заданная строка)
// исправление: X может быть нулем
// для боковых стекол как они есть
// ниже, чтобы заполнить

for (int row = 1; row <= i ; ++row)

{

    // Заполнить очки в данной строке.

    // Количество столбцов в строке

    // равно номеру строки

    for (int col = 1; 

            col <= row; ++col, ++index)

    {

        // Получить воду из текущего стекла

        X = glass[index];

  

        // Сохраняем сумму меньше

        // или равно емкости в

        // текущее стекло

        glass[index] = (X >= 1.0f) ? 

                              1.0f : X;

  

        // Получить оставшуюся сумму

        X = (X >= 1.0f) ? (X - 1) : 0.0f;

  

        // Распределить оставшуюся сумму

        // вниз два стакана

        glass[index + row] += X / 2;

        glass[index + row + 1] += X / 2;

    }

}

  
// Индекс j-го стекла в i-м
// строка будет i * (i-1) / 2 + j - 1

return glass[(int)(i * (i - 1) / 

                   2 + j - 1)];

}

  
// Код драйвера

static void Main()

{

    int i = 2, j = 2;

    float X = 2.0f; // Общее количество воды

    Console.WriteLine("Amount of water in jth " +

                        "glass of ith row is: " + 

                             findWater(i, j, X));

}
}

  
// Этот код предоставлен mits

PHP

<?php
// Программа для поиска суммы
// воды в j-ом стакане
// я бросаю

  
// Возвращает количество воды
// в j-ом стакане i-го ряда

function findWater($i, $j, $X)

{

    // номер строки у меня максимум

    // я столбцы. Итак, входной столбец

    // число должно быть меньше чем я

    if ($j > $i)

    {

        echo "Incorrect Input\n";

        return;

    }

  

    // Там будет i * (i + 1) / 2

    // очки до i-го ряда

    // (включая i-ю строку)

    // и инициализируем все очки

    // как пусто

    $glass = array_fill(0, (int)($i * 

                       ($i + 1) / 2), 0);

  

    // положить всю воду

    // в первом стакане

    $index = 0;

    $glass[$index] = $X;

  

    // Теперь дайте воде течь

    // нисходящие очки до

    // номер строки меньше

    // чем или / равно i (дано

    // строка) исправление: X может быть

    // ноль для боковых стекол как

    // они имеют меньшую скорость заполнения

    for ($row = 1; $row < $i ; ++$row)

    {

        // Заполнить очки в данном

        // строка. Число столбцов

        // в строке равно номеру строки

        for ($col = 1; 

             $col <= $row; ++$col, ++$index)

        {

            // Получить воду

            // из текущего стекла

            $X = $glass[$index];

  

            // Сохраняем сумму меньше

            // чем или равно

            // емкость в текущем стекле

            $glass[$index] = ($X >= 1.0) ? 

                                     1.0 : $X;

  

            // Получить оставшуюся сумму

            $X = ($X >= 1.0) ? 

                    ($X - 1) : 0.0;

  

            // Распределить оставшиеся

            // сумма до двух очков

            $glass[$index + $row] += (double)($X / 2);

            $glass[$index + $row + 1] += (double)($X / 2);

        }

    }

  

    // Индекс j-го стекла

    // в i-м ряду

    // be i * (i-1) / 2 + j - 1

    return $glass[(int)($i * ($i - 1) /

                          2 + $j - 1)];

}

  
// Код драйвера

$i = 2;

$j = 2;

$X = 2.0; // Общее количество воды

echo "Amount of water in jth " , 

        "glass of ith row is: ".

       str_pad(findWater($i, $j, 

                   $X), 8, '0');

  
// Этот код предоставлен Mits
?>


Выход:

Amount of water in jth glass of ith row is: 0.500000

Сложность времени: O (i * (i + 1) / 2) или O (i ^ 2)
Вспомогательное пространство: O (i * (i + 1) / 2) или O (i ^ 2)

Эта статья составлена Rahul и рецензирована командой GeeksforGeeks. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Программа, чтобы найти количество воды в данном стакане

0.00 (0%) 0 votes