Рубрики

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

Есть n велосипедов, и каждый может пройти 100 км при полной заправке. Какое максимальное расстояние вы можете пройти, используя n велосипедов? Вы можете предположить, что все велосипеды одинаковы, и велосипеду требуется 1 литр для покрытия 1 км.

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

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

  • Базовый случай 1: есть один велосипед: это просто, мы можем проехать только 100 км.
  • Базовый случай 2: Есть два велосипеда: какое максимальное расстояние мы можем преодолеть, когда есть два велосипеда? Чтобы максимизировать расстояние, мы должны уронить второй велосипед в какой-то момент и перенести его топливо на первый велосипед. Пусть мы сделаем перевод после х км.
    Total distance covered = Distance covered by 100 ltr in first bike +  
                             Distance covered by fuel transferred from 
                             first bike. 

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

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

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

Ниже приводится реализация общей функции.

C / C ++

#include <stdio.h>

  
// Возвращает максимальное расстояние, которое может быть пройдено n велосипедами и данным топливом
// в каждом велосипеде

double maxDistance(int n, int fuel)

{

    // dist_covered - результат этой функции

    double dist_covered = 0;

  

    while (n > 0)

    {

        // после прокачки топлива / n км мы выбрасываем один велосипед и заправляем

        // все остальные велосипеды с топливом / n литров топлива, т.е.

        // максимальный лимит (100 литров)

  

        dist_covered += (double)fuel / n;

  

        n -= 1;  // уменьшить количество велосипедов

    }

    return dist_covered;

}

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

int main()

{

    int n = 3; // количество велосипедов

    int fuel = 100;

    printf("Maximum distance possible with %d bikes is %f",

            n, maxDistance(n, fuel));

    return 0;

}

Джава

// Java программа для поиска максимума
// пройденное расстояние с использованием n велосипедов

import java.io.*;

  

class GFG 

{

    // Функция, которая возвращает максимальное расстояние, которое может быть пройдено n велосипедами

    // и дают топливо в каждом байке

    static double maxDistance(int n, int fuel)

    {

         // dist_covered - результат этой функции

        double dist_covered = 0;

   

        while (n > 0)

        {

            // после прокачки топлива / n км мы выбрасываем один велосипед и заправляем

            // все остальные велосипеды с топливом / n литров топлива, т.е.

            // максимальный лимит (100 литров)

   

            dist_covered += (double)fuel / n;

   

            n -= 1// уменьшить количество велосипедов

        }

        return dist_covered;

    }

      

    // драйверная программа

    public static void main (String[] args) 

    {

        int n = 3; // количество велосипедов

        int fuel = 100;

        System.out.println("Maximum distance possible with "

                                   + n + " bikes is " + maxDistance(n, fuel));

    }

}

  
// Предоставлено Прамод Кумар

python3

# Python 3 программа для поиска максимума
# пройденное расстояние с использованием n велосипедов

  
# Возвращает максимальное расстояние, которое может быть
# ездил на велосипедах и дал топливо
# в каждом велосипеде

def maxDistance(n, fuel):

      

    # dist_covered - это результат

    # этой функции

    dist_covered = 0

  

    while (n > 0):

          

        # после когда-либо топлива / н км мы

        # выбрасывание одного велосипеда и наполнение

        # все остальные велосипеды с топливом / н

        # литров топлива т.е. их

        Максимальный предел (100 литров)

        dist_covered = dist_covered + (fuel / n)

          

        # уменьшить количество велосипедов

        n = n - 1

  

    return dist_covered

  
Код водителя

if __name__ =='__main__':

    n = 3

      

    # количество велосипедов

    fuel = 100

    print("Maximum distance possible with"

       n, "bikes is", maxDistance(n, fuel))

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

C #

// C # программа для поиска максимума
// пройденное расстояние с использованием n велосипедов

using System;

  

class GFG {

  

    // Функция, которая возвращает максимальное расстояние

    // по которым можно ездить на велосипедах

    // и дают топливо в каждом байке

    static double maxDistance(int n, int fuel)

    {

        // dist_covered - результат этой функции

        double dist_covered = 0;

  

        while (n > 0) {

              

            // после когда-либо топлива / н км мы выбрасываем

            // один велосипед и заполнение всех других велосипедов

            // с топливом / н литров топлива, т.е. до их

            // максимальный лимит (100 литров)

            dist_covered += (double)fuel / n;

  

            n -= 1; // уменьшить количество велосипедов

        }

        return dist_covered;

    }

  

    // драйверная программа

    public static void Main()

    {

        // количество велосипедов

        int n = 3; 

        int fuel = 100;

        Console.WriteLine("Maximum distance possible with " + n +

                          " bikes is " + maxDistance(n, fuel));

    }

}

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

PHP

<?php
// Возвращает максимальное расстояние, которое может
// ездим на велосипедах и даем
// топливо в каждом байке

  

function maxDistance($n, $fuel)

{

    // dist_covered - это результат

    // этой функции

    $dist_covered = 0;

  

    while ($n > 0)

    {

        // после того, как топлива / н км мы

        // выбрасываем один велосипед и заправку

        // все остальные велосипеды с топливом / н

        // литров топлива т.е. их

        // максимальный лимит (100 литров)

  

        $dist_covered += (double)$fuel / $n;

  

        // уменьшить количество велосипедов

        $n -= 1; 

    }

    return $dist_covered;

}

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

  
// количество велосипедов

$n = 3; 

$fuel = 100;

echo "Maximum distance possible with "

                      $n, " bikes is "

                maxDistance($n, $fuel);

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


Выход :

Maximum distance possible with 3 bikes is 183.333333

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

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

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

0.00 (0%) 0 votes