Рубрики

Программа для Шоколадно-Оберточной Головоломки

Учитывая следующие три значения, задача состоит в том, чтобы найти общее количество конфет, которое вы можете съесть.

  1. деньги: деньги, которые вы должны купить шоколад
  2. цена: цена шоколада
  3. wrap: количество упаковок, которые нужно вернуть для получения одного дополнительного шоколада.

Можно предположить, что все заданные значения являются положительными целыми числами и больше 1.

Примеры:

Input :   money = 16, price = 2, wrap = 2
Output :   15
Price of a chocolate is 2. You can buy 8 chocolates from
amount 16. You can return 8 wrappers back and get 4 more
chocolates. Then you can return 4 wrappers and get 2 more
chocolates. Finally you can return 2 wrappers to get 1
more chocolate.

Input :   money = 15, price = 1, wrap = 3
Output :   22
We buy and eat 15 chocolates
We return 15 wrappers and get 5 more chocolates.
We return 3 wrappers, get 1 chocolate and eat it
(keep 2 wrappers). Now we have 3 wrappers. Return
3 and get 1 more chocolate.
So total chocolates = 15 + 5 + 1 + 1

Input :  money = 20, price = 3, wrap = 5
Output :   7

Источник: Головоломка 22 | (Максимум конфет)

Наивным методом является постоянный подсчет количества конфет, возвращая обертки до тех пор, пока оставшиеся обертки не станут меньше, чем требуется для получения шоколада. Ниже приведена реализация этого метода.

C ++

// Рекурсивная C ++ программа для поиска максимума
// количество конфет
#include <iostream>

using namespace std;

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

int countRec(int choc, int wrap)

{

    // Если количество конфет меньше чем

    // количество оберток требуется.

    if (choc < wrap)

        return 0;

  

    // Мы можем сразу получить newChoc используя

    // обертки от choc.

    int newChoc = choc/wrap;

  

    // Теперь у нас есть оболочки "newChoc + choc% wrap".

    return newChoc + countRec(newChoc + choc%wrap,

                              wrap);

}

  
// Возвращает максимальное количество конфет, которое мы можем съесть
// с указанными деньгами, ценой на шоколад и номером
// оберток, необходимых для получения шоколада.

int countMaxChoco(int money, int price, int wrap)

{

    // Мы можем напрямую купить ниже количество конфет

    int choc = money/price;

  

    // countRec возвращает количество конфет, которые мы можем

    // есть из заданного количества конфет

    return choc + countRec(choc, wrap);

}

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

int main()

{

    int money = 15 ; // всего денег

    int price = 1; // стоимость каждой конфеты

    int wrap = 3 ; // нет оберток должен быть

    // обмен на один шоколад

  

    cout << countMaxChoco(money, price, wrap);

    return 0;

}

Джава

// Рекурсивная Java-программа для поиска максимума
// количество конфет

  

import java.io.*;

  

class GFG {

  

    // Возвращает количество конфет, которые мы можем

    // есть из заданного количества конфет

    // и количество оберток, необходимых для

    // получить шоколад.

    static int countRec(int choc, int wrap)

    {

          

        // Если количество конфет меньше чем

        // количество оберток требуется.

        if (choc < wrap)

            return 0;

      

        // Мы можем сразу получить newChoc используя

        // обертки от choc.

        int newChoc = choc / wrap;

      

        // Теперь у нас есть "newChoc + choc% wrap"

        // обертки.

        return newChoc + countRec(newChoc + 

                          choc % wrap, wrap);

    }

      

    // Возвращает максимальное количество конфет

    // мы можем есть с учетом денег, цена

    // шоколад и количество оберток

    // требуется шоколад.

    static int countMaxChoco(int money, 

                          int price, int wrap)

    {

          

        // Мы можем напрямую купить ниже количества

        // шоколад

        int choc = money/price;

      

        // countRec возвращает количество конфет

        // мы можем получить из заданного числа

        // шоколад

        return choc + countRec(choc, wrap);

    }

      

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

    public static void main (String[] args)

    {

        int money = 15 ; // всего денег

        int price = 1; // стоимость каждой конфеты

          

        // нет оберток должен быть

        // обмен на один шоколад

        int wrap = 3

        System.out.println( 

            countMaxChoco(money, price, wrap));

    }

}

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

python3

# Рекурсивная программа Python3 для поиска
# максимальное количество конфет

import math

  
# Возвращает количество конфет, которые мы можем
№ из заданного количества конфет
# и количество упаковщиков, необходимых для
# получить шоколад.

def countRec(choc, wrap):

      

    # Если количество конфет меньше

    # чем требуется количество упаковщиков.

    if (choc < wrap):

        return 0;

  

    # Мы можем сразу получить newChoc

    # используя обертки от choc.

    newChoc = choc / wrap;

  

    # Теперь у нас есть оболочки "newChoc + choc% wrap".

    return newChoc + countRec(newChoc + choc % 

                                  wrap, wrap);

  
# Возвращает максимальное количество конфет
# мы можем есть с учетом денег, цены
количество шоколада и количество оберток
# требуется, чтобы получить шоколад.

def countMaxChoco(money, price, wrap):

      

    # Мы можем напрямую купить ниже

    # количество конфет

    choc = money / price;

  

    # countRec возвращает число

    # конфет мы можем

    # с данного номера

    Количество конфет

    return math.floor(choc + countRec(choc, wrap));

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

  
# всего денег

money = 15;

      
# стоимость каждой конфеты

price = 1

      
№ обертки должны быть

wrap = 3

      
# обменяю на один шоколад.

print(countMaxChoco(money, price, wrap));

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

C #

// Рекурсивная C # программа для поиска максимума
// количество конфет

  

using System;

  

class GFG {

  

    // Возвращает количество конфет, которые мы можем

    // есть из заданного количества конфет

    // и количество оберток, необходимых для

    // получить шоколад.

    static int countRec(int choc, int wrap)

    {

          

        // Если количество конфет меньше чем

        // количество оберток требуется.

        if (choc < wrap)

            return 0;

      

        // Мы можем сразу получить newChoc используя

        // обертки от choc.

        int newChoc = choc / wrap;

      

        // Теперь у нас есть "newChoc + choc% wrap"

        // обертки.

        return newChoc + countRec(newChoc + 

                        choc % wrap, wrap);

    }

      

    // Возвращает максимальное количество конфет

    // мы можем есть с учетом денег, цена

    // шоколад и количество оберток

    // требуется шоколад.

    static int countMaxChoco(int money, 

                        int price, int wrap)

    {

          

        // Мы можем напрямую купить ниже количества

        // шоколад

        int choc = money/price;

      

        // countRec возвращает количество конфет

        // мы можем получить из заданного числа

        // шоколад

        return choc + countRec(choc, wrap);

    }

      

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

    public static void Main ()

    {

        int money = 15 ; // всего денег

        int price = 1; // стоимость каждой конфеты

          

        // нет оберток должен быть

        // обмен на один шоколад

        int wrap = 3 ; 

        Console.WriteLine( 

            countMaxChoco(money, price, wrap));

    }

}

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

PHP

<?php
// Рекурсивная PHP-программа для поиска максимума
// количество конфет

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

function countRec($choc, $wrap)

{

      

    // Если количество конфет меньше чем

    // количество оберток требуется.

    if ($choc < $wrap)

        return 0;

  

    // Мы можем сразу получить newChoc используя

    // обертки от choc.

    $newChoc = $choc/$wrap;

  

    // Теперь у нас есть оболочки "newChoc + choc% wrap".

    return $newChoc + countRec($newChoc + $choc % $wrap,

                                                  $wrap);

}

  
// Возвращает максимальное количество конфет, которое мы можем съесть
// с указанными деньгами, ценой на шоколад и номером
// оберток, необходимых для получения шоколада.

function countMaxChoco($money, $price, $wrap)

{

      

    // Мы можем напрямую купить ниже

    // количество конфет

    $choc = $money/$price;

  

    // countRec возвращает число

    // конфет мы можем

    // иметь с данного номера

    // конфет

    return floor($choc + countRec($choc, $wrap));

}

  

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

    // всего денег

    $money = 15;

      

    // стоимость каждой конфеты

    $price = 1; 

      

    // нет оберток должен быть

    $wrap = 3 ; 

      

    // обмен на один шоколад

    echo countMaxChoco($money, $price, $wrap);

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


Выход :

22

Эффективным решением является использование прямой формулы для определения количества конфет.

Find initial number of chocolates by
dividing the amount with per piece cost.
i.e. choc = money / wrap

then apply below formula
choc += (choc - 1)/(wrap - 1)

В приведенной выше наивной реализации мы заметили, что после нахождения начального количества конфет мы рекурсивно делим количество конфет на количество требуемых упаковщиков. пока мы не оставили с 1 шоколадом или оберткой.
Мы пересчитываем значения т.е. ((choc / wrap + choc% wrap) / wrap, пока не получим 1.
Замечено, что мы можем получить результат, просто уменьшив значения конфет и упаковок на 1, а затем разделив их, чтобы получить результат (choc-1) / (wrap-1)

C ++

// Эффективная программа на C ++, чтобы найти максимум
// количество конфет
#include <iostream>

using namespace std;

  
// Возвращает максимальное количество конфет, которое мы можем съесть
// с указанными деньгами, ценой на шоколад и номером
// оберток, необходимых для получения шоколада.

int countMaxChoco(int money, int price, int wrap)

{

    // Угловой корпус

    if (money < price)

       return 0;

  

    // Сначала найти количество конфет, которые

    // можно купить на заданную сумму

    int choc = money / price;

  

    // Теперь просто добавьте количество конфет с

    // шоколадки, полученные по оберткам

    choc = choc + (choc - 1) / (wrap - 1);

    return choc;

}

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

int main()

{

    int money = 15 ; // всего денег

    int price = 1; // стоимость каждой конфеты

    int wrap = 3 ; // нет оберток должен быть

    // обмен на один шоколад

  

    cout << countMaxChoco(money, price, wrap);

    return 0;

}

Джава

// Эффективная Java-программа для поиска максимума
// количество конфет

import java.io.*;

  

class GFG {

  

    // Возвращает максимальное количество конфет

    // мы можем есть с учетом денег, цены

    // шоколада и количества оберток

    // требуется шоколад.

    static int countMaxChoco(int money, 

                        int price, int wrap)

    {

          

        // Угловой корпус

        if (money < price)

            return 0;

      

        // Сначала находим количество конфет

        // которые можно купить с

        // заданная сумма

        int choc = money / price;

      

        // Теперь просто добавь количество конфет

        // с конфетами, полученными

        // обертки

        choc = choc + (choc - 1) / (wrap - 1);

        return choc;

    }

      

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

    public static void main (String[] args) 

    {

          

        // всего денег

        int money = 15;

          

        // стоимость каждой конфеты

        int price = 1

          

        // нет оберток должен быть

        int wrap = 3

          

        // обмен на один шоколад

        System.out.println(

           countMaxChoco(money, price, wrap));

    }

}

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

python3

# Эффективная программа Python3 для поиска
# максимальное количество конфет

  
# Возвращает максимальное количество
# шоколад, который мы можем съесть
# учитывая деньги, цена шоколада
# и количество упаковок
# требуется, чтобы получить шоколад.

def countMaxChoco(money, price, wrap) :

  

    # Угловой кейс

    if (money < price) :

        return 0

  

    # Сначала найдите количество конфет

    # которые можно приобрести с

    # заданная сумма

    choc = int(money / price) 

  

    # Теперь просто добавьте количество

    # шоколад с конфетами

    # полученный обертками

    choc = choc + (choc - 1) / (wrap - 1

    return int(choc )

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

money = 15 # всего денег

price = 1 # стоимость каждой конфеты

wrap = 3 № обертки должны быть

         # обменяю на один шоколад.

  

print(countMaxChoco(money, price, wrap))

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

C #

// Эффективная программа на C # для поиска максимума
// количество конфет

using System;

  

class GFG {

  

    // Возвращает максимальное количество конфет

    // мы можем есть с учетом денег, цены

    // шоколада и количества оберток

    // требуется шоколад.

    static int countMaxChoco(int money, 

                        int price, int wrap)

    {

          

        // Угловой корпус

        if (money < price)

            return 0;

      

        // Сначала находим количество конфет

        // которые можно купить с

        // заданная сумма

        int choc = money / price;

      

        // Теперь просто добавь количество конфет

        // с конфетами, полученными

        // обертки

        choc = choc + (choc - 1) / (wrap - 1);

        return choc;

    }

      

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

    public static void Main () 

    {

          

        // всего денег

        int money = 15;

          

        // стоимость каждой конфеты

        int price = 1; 

          

        // нет оберток должен быть

        int wrap = 3 ; 

          

        // обмен на один шоколад

        Console.WriteLine(

        countMaxChoco(money, price, wrap));

    }

}

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

PHP

<?php
// Эффективная программа PHP, чтобы найти максимум
// количество конфет

  
// Возвращает максимальное количество
// конфет мы можем съесть
// с учетом денег, цены
// шоколада и номера
// оберток требуется
// чтобы получить шоколад.

function countMaxChoco($money, $price, $wrap)

{

    // Угловой корпус

    if ($money < $price)

    return 0;

  

    // Сначала найти номер

    // конфет, которые

    // можно купить

    // с заданной суммой

    $choc = $money / $price;

  

    // Теперь просто добавь номер

    // конфет с

    // шоколадки, полученные по оберткам

    $choc = $choc + ($choc - 1) / 

                    ($wrap - 1);

    return $choc;

}

  

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

      

     // всего денег

    $money = 15 ;

      

    // стоимость каждой конфеты

    $price = 1; 

      

    // нет оберток должен быть

    // обмен на один шоколад

    $wrap = 3 ; 

    echo countMaxChoco($money, $price, $wrap);

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


Выход :

22

Эта статья предоставлена Сахилом Чхаброй (Акку) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Программа для Шоколадно-Оберточной Головоломки

0.00 (0%) 0 votes