Найдите максимальное расстояние, которое можно преодолеть на n велосипедах

Опубликовано: 21 Января, 2022

Всего имеется n велосипедов, каждый из которых может проехать 100 км на заправленном топливе. Какое максимальное расстояние вы можете проехать на n велосипедах? Вы можете предположить, что все велосипеды похожи, и велосипеду требуется 1 литр, чтобы проехать 1 км.
У вас есть n велосипедов, и на одном велосипеде вы можете проехать не более 100 км. Таким образом, если n мотоциклов стартуют с одной и той же точки и едут одновременно, вы можете проехать только 100 км. Давайте подумаем немного иначе, фокус в том, что когда вы хотите преодолеть максимальное расстояние, вы всегда должны стараться тратить минимум топлива. Минимальный расход топлива означает минимальное количество велосипедов. Вместо параллельного запуска n велосипедов вы можете подумать о их последовательном запуске. Это означает, что если вы переложите некоторое количество топлива с последнего велосипеда на другой и выбросите последний велосипед, то есть не запускайте последний велосипед после определенного момента. Но вопрос в том, через какое расстояние нужно произвести перекачку топлива, чтобы было преодолено максимальное расстояние и топливный бак оставшихся байков не переполнился.

Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.

Возьмем следующие базовые случаи, а затем обобщим решение.

Базовый случай 1: Есть один велосипед: это просто, мы можем преодолеть только 100 км.
Базовый случай 2: Есть два велосипеда: Какое максимальное расстояние мы можем преодолеть, когда есть два велосипеда? Чтобы увеличить расстояние, мы должны в какой-то момент бросить второй байк и передать его топливо первому. Давайте сделаем передачу через x кмс.

 Общее пройденное расстояние = Расстояние, пройденное на 100 литров на первом велосипеде +  
                         Расстояние, пройденное за счет топлива, переброшенного из 
                         первый байк.

Остаток топлива во втором байке - 100 - x. Если мы переместим это количество топлива на первый байк, то общее расстояние составит 100 + 100 - x, что равно 200 - x. Так что наша задача - максимизировать 200-х. Ограничение: 100 - x должно быть меньше или равно пространству, созданному на первом велосипеде после x кмс, то есть 100 - x <= x. Значение 200-x становится максимальным, когда x минимально. Минимально возможное значение x - 50. Таким образом, мы можем проехать 150 км.
Базовый случай 3: Есть три велосипеда: пусть первая пересадка будет сделана через x км. После x дистанции все велосипеды содержат 100-кратное количество топлива. Если мы возьмем 100-кратное количество топлива с 3-го велосипеда и распределяем его между 1-м и 2-м велосипедами так, чтобы топливные баки 1-го и 2-го мотоциклов были заполнены. Итак, 100-x <= 2 * x; или, x = 33,333, поэтому мы должны передать оставшееся топливо третьего велосипеда и распределить это количество топлива между 1-м и 2-м велосипедом ровно через 33,33 км.

Давайте обобщим это. Если мы внимательно рассмотрим вышеупомянутые случаи, мы можем заметить, что если имеется n велосипедов, то первая передача выполняется (или велосипед падает) через 100 / n км / с. Если обобщить, то когда у нас осталось x литров топлива на каждом велосипеде и n оставшихся мотоциклов, мы бросаем велосипед через x / n км / с.

Following is the implementation of a general function.

C++

#include <stdio.h>
 
// Returns maximum distance that can be traveled by n bikes and given fuel
// in every bike
double maxDistance(int n, int fuel)
{
    // dist_covered is the result of this function
    double dist_covered = 0;
 
    while (n > 0)
    {
        // after ever fuel/n km we are discarding one bike and filling
        // all the other bikes with fuel/n liters of fuel i.e. to their
        // maximum limit (100 litre)
 
        dist_covered += (double)fuel / n;
 
        n -= 1; // reduce number of bikes
    }
    return dist_covered;
}
 
// Driver program to test above function
int main()
{
    int n = 3; // number of bikes
    int fuel = 100;
    printf("Maximum distance possible with %d bikes is %f",
            n, maxDistance(n, fuel));
    return 0;
}

Java

// Java program to find the maximum
// distance covered using n bikes
import java.io.*;
 
class GFG
{
    // Function that returns maximum distance that can be traveled by n bikes
    // and given fuel in every bike
    static double maxDistance(int n, int fuel)
    {
         // dist_covered is the result of this function
        double dist_covered = 0;
  
        while (n > 0)
        {
            // after ever fuel/n km we are discarding one bike and filling
            // all the other bikes with fuel/n liters of fuel i.e. to their
            // maximum limit (100 litre)
  
            dist_covered += (double)fuel / n;
  
            n -= 1;  // reduce number of bikes
        }
        return dist_covered;
    }
     
    // driver program
    public static void main (String[] args)
    {
        int n = 3; // number of bikes
        int fuel = 100;
        System.out.println("Maximum distance possible with "
                                   + n + " bikes is " + maxDistance(n, fuel));
    }
}
 
// Contributed by Pramod Kumar

Python3

# Python 3 program to find the maximum
# distance covered using n bikes
 
# Returns maximum distance that can be
# traveled by n bikes and given fuel
# in every bike
def maxDistance(n, fuel):
     
    # dist_covered is the result
    # of this function
    dist_covered = 0
 
    while (n > 0):
         
        # after ever fuel/n km we are
        # discarding one bike and filling
        # all the other bikes with fuel/n
        # liters of fuel i.e. to their
        # maximum limit (100 litre)
        dist_covered = dist_covered + (fuel / n)
         
        # reduce number of bikes
        n = n - 1
 
    return dist_covered
 
# Driver Code
if __name__ =="__main__":
    n = 3
     
    # number of bikes
    fuel = 100
    print("Maximum distance possible with",
       n, "bikes is", maxDistance(n, fuel))
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# program to find the maximum
// distance covered using n bikes
using System;
 
class GFG {
 
    // Function that returns maximum distance
    // that can be travelled by n bikes
    // and given fuel in every bike
    static double maxDistance(int n, int fuel)
    {
        // dist_covered is the result of this function
        double dist_covered = 0;
 
        while (n > 0) {
             
            // after ever fuel/n km we are discarding
            // one bike and filling all the other bikes
            // with fuel/n liters of fuel i.e. to their
            // maximum limit (100 litre)
            dist_covered += (double)fuel / n;
 
            n -= 1; // reduce number of bikes
        }
        return dist_covered;
    }
 
    // driver program
    public static void Main()
    {
        // number of bikes
        int n = 3;
        int fuel = 100;
        Console.WriteLine("Maximum distance possible with " + n +
                          " bikes is " + maxDistance(n, fuel));
    }
}
 
// This code is contributed by Sam007

PHP

<?php
// Returns maximum distance that can
// be traveled by n bikes and given
// fuel in every bike
 
function maxDistance($n, $fuel)
{
    // dist_covered is the result
    // of this function
    $dist_covered = 0;
 
    while ($n > 0)
    {
        // after ever fuel/n km we are
        // discarding one bike and filling
        // all the other bikes with fuel/n
        // liters of fuel i.e. to their
        // maximum limit (100 litre)
 
        $dist_covered += (double)$fuel / $n;
 
        // reduce number of bikes
        $n -= 1;
    }
    return $dist_covered;
}
 
// Driver Code
 
// number of bikes
$n = 3;
$fuel = 100;
echo "Maximum distance possible with ",
                      $n, " bikes is ",
                maxDistance($n, $fuel);
 
// This code is contributed by ajit
?>

Javascript

<script>
 
// Javascript program to find the maximum
// distance covered using n bikes
 
// Function that returns maximum distance
// that can be travelled by n bikes
// and given fuel in every bike
function maxDistance(n, fuel)
{
     
    // dist_covered is the result of this function
    let dist_covered = 0;
 
    while (n > 0)
    {
         
        // After ever fuel/n km we are discarding
        // one bike and filling all the other bikes
        // with fuel/n liters of fuel i.e. to their
        // maximum limit (100 litre)
        dist_covered += fuel / n;
         
        // Reduce number of bikes
        n -= 1;
    }
    return dist_covered.toFixed(6);
}
 
// Driver code
 
// Number of bikes
let n = 3;
let fuel = 100;
 
document.write("Maximum distance possible with " + n +
               " bikes is " + maxDistance(n, fuel));
                
// This code is contributed by divyesh072019
 
</script>

Выход :

Maximum distance possible with 3 bikes is 183.333333

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

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы

Найдите максимальное расстояние, которое можно преодолеть на n велосипедах

C++

Java

Python3

C#

PHP

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ