Programa para Rompecabezas de Chocolate y Envoltura

Dados los siguientes tres valores, la tarea es encontrar el número total de chocolates máximos que puedes comer. 

  1. dinero: Dinero que tienes para comprar chocolates
  2. precio: Precio de un chocolate
  3. envoltorio: Número de envoltorios a devolver por recibir un chocolate extra.

Se puede suponer que todos los valores dados son números enteros positivos y mayores que 1.
Ejemplos:  

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

Fuente: Rompecabezas 22 | (Máximo de Chocolates)

Un método ingenuo es contar continuamente la cantidad de chocolates devolviendo los envoltorios hasta que los envoltorios que quedan no sean menos de los necesarios para obtener un chocolate. 

A continuación se muestra la implementación de este método. 

C++

// Recursive C++ program to find maximum
// number of chocolates
#include <iostream>
using namespace std;
 
// Returns number of chocolates we can
// have from given number of chocolates
// and number of wrappers required to
// get a chocolate.
int countRec(int choc, int wrap)
{
    // If number of chocolates is less than
    // number of wrappers required.
    if (choc < wrap)
        return 0;
 
    // We can immediately get newChoc using
    // wrappers of choc.
    int newChoc = choc/wrap;
 
    // Now we have "newChoc + choc%wrap" wrappers.
    return newChoc + countRec(newChoc + choc%wrap,
                              wrap);
}
 
// Returns maximum number of chocolates we can eat
// with given money, price of chocolate and number
// of wrappers required to get a chocolate.
int countMaxChoco(int money, int price, int wrap)
{
    // We can directly buy below number of chocolates
    int choc = money/price;
 
    // countRec returns number of chocolates we can
    // have from given number of chocolates
    return choc + countRec(choc, wrap);
}
 
// Driver code
int main()
{
    int money = 15 ; // total money
    int price = 1; // cost of each candy
    int wrap = 3 ; // no of wrappers needs to be
    // exchanged for one chocolate.
 
    cout << countMaxChoco(money, price, wrap);
    return 0;
}

Java

// Recursive java program to find maximum
// number of chocolates
 
import java.io.*;
 
class GFG {
 
    // Returns number of chocolates we can
    // have from given number of chocolates
    // and number of wrappers required to
    // get a chocolate.
    static int countRec(int choc, int wrap)
    {
         
        // If number of chocolates is less than
        // number of wrappers required.
        if (choc < wrap)
            return 0;
     
        // We can immediately get newChoc using
        // wrappers of choc.
        int newChoc = choc / wrap;
     
        // Now we have "newChoc + choc%wrap"
        // wrappers.
        return newChoc + countRec(newChoc +
                          choc % wrap, wrap);
    }
     
    // Returns maximum number of chocolates
    // we can eat with given money, price of
    // chocolate and number of wrappers
    // required to get a chocolate.
    static int countMaxChoco(int money,
                          int price, int wrap)
    {
         
        // We can directly buy below number of
        // chocolates
        int choc = money/price;
     
        // countRec returns number of chocolates
        // we can have from given number of
        // chocolates
        return choc + countRec(choc, wrap);
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int money = 15 ; // total money
        int price = 1; // cost of each candy
         
        // no of wrappers needs to be
        // exchanged for one chocolate.
        int wrap = 3 ;
        System.out.println(
            countMaxChoco(money, price, wrap));
    }
}
 
// This code is contributed by anuj_67.

Python3

# Recursive Python3 program to find
# maximum number of chocolates
import math
 
# Returns number of chocolates we can
# have from given number of chocolates
# and number of wrappers required to
# get a chocolate.
def countRec(choc, wrap):
     
    # If number of chocolates is less
    # than number of wrappers required.
    if (choc < wrap):
        return 0;
 
    # We can immediately get newChoc
    # using wrappers of choc.
    newChoc = choc / wrap;
 
    # Now we have "newChoc + choc%wrap" wrappers.
    return newChoc + countRec(newChoc + choc %
                                  wrap, wrap);
 
# Returns maximum number of chocolates
# we can eat with given money, price
# of chocolate and number of wrappers
# required to get a chocolate.
def countMaxChoco(money, price, wrap):
     
    # We can directly buy below
    # number of chocolates
    choc = money / price;
 
    # countRec returns number
    # of chocolates we can
    # have from given number
    # of chocolates
    return math.floor(choc + countRec(choc, wrap));
 
# Driver code
 
# total money
money = 15;
     
# cost of each candy
price = 1;
     
# no of wrappers needs to be
wrap = 3 ;
     
# exchanged for one chocolate.
print(countMaxChoco(money, price, wrap));
 
# This code is contributed by mits

C#

// Recursive C# program to find maximum
// number of chocolates
 
using System;
 
class GFG {
 
    // Returns number of chocolates we can
    // have from given number of chocolates
    // and number of wrappers required to
    // get a chocolate.
    static int countRec(int choc, int wrap)
    {
         
        // If number of chocolates is less than
        // number of wrappers required.
        if (choc < wrap)
            return 0;
     
        // We can immediately get newChoc using
        // wrappers of choc.
        int newChoc = choc / wrap;
     
        // Now we have "newChoc + choc%wrap"
        // wrappers.
        return newChoc + countRec(newChoc +
                        choc % wrap, wrap);
    }
     
    // Returns maximum number of chocolates
    // we can eat with given money, price of
    // chocolate and number of wrappers
    // required to get a chocolate.
    static int countMaxChoco(int money,
                        int price, int wrap)
    {
         
        // We can directly buy below number of
        // chocolates
        int choc = money/price;
     
        // countRec returns number of chocolates
        // we can have from given number of
        // chocolates
        return choc + countRec(choc, wrap);
    }
     
    // Driver code
    public static void Main ()
    {
        int money = 15 ; // total money
        int price = 1; // cost of each candy
         
        // no of wrappers needs to be
        // exchanged for one chocolate.
        int wrap = 3 ;
        Console.WriteLine(
            countMaxChoco(money, price, wrap));
    }
}
 
// This code is contributed by anuj_67.

PHP

<?php
// Recursive PHP program to find maximum
// number of chocolates
 
// Returns number of chocolates we can
// have from given number of chocolates
// and number of wrappers required to
// get a chocolate.
function countRec($choc, $wrap)
{
     
    // If number of chocolates is less than
    // number of wrappers required.
    if ($choc < $wrap)
        return 0;
 
    // We can immediately get newChoc using
    // wrappers of choc.
    $newChoc = $choc/$wrap;
 
    // Now we have "newChoc + choc%wrap" wrappers.
    return $newChoc + countRec($newChoc + $choc % $wrap,
                                                  $wrap);
}
 
// Returns maximum number of chocolates we can eat
// with given money, price of chocolate and number
// of wrappers required to get a chocolate.
function countMaxChoco($money, $price, $wrap)
{
     
    // We can directly buy below
    // number of chocolates
    $choc = $money/$price;
 
    // countRec returns number
    // of chocolates we can
    // have from given number
    // of chocolates
    return floor($choc + countRec($choc, $wrap));
}
 
    // Driver code
    // total money
    $money = 15;
     
    // cost of each candy
    $price = 1;
     
    // no of wrappers needs to be
    $wrap = 3 ;
     
    // exchanged for one chocolate.
    echo countMaxChoco($money, $price, $wrap);
 
// This code is contributed by anuj_67.
?>

Javascript

<script>
 
// JavaScript program to find maximum
// number of chocolates
 
// Returns number of chocolates we can
    // have from given number of chocolates
    // and number of wrappers required to
    // get a chocolate.
    function countRec(choc, wrap)
    {
          
        // If number of chocolates is less than
        // number of wrappers required.
        if (choc < wrap)
            return 0;
      
        // We can immediately get newChoc using
        // wrappers of choc.
        let newChoc = choc / wrap;
      
        // Now we have "newChoc + choc%wrap"
        // wrappers.
        return newChoc + countRec(newChoc +
                          choc % wrap, wrap);
    }
      
    // Returns maximum number of chocolates
    // we can eat with given money, price of
    // chocolate and number of wrappers
    // required to get a chocolate.
    function countMaxChoco(money,
                          price, wrap)
    {
          
        // We can directly buy below number of
        // chocolates
        let choc = money/price;
      
        // countRec returns number of chocolates
        // we can have from given number of
        // chocolates
        return choc + countRec(choc, wrap);
    }
   
 
// Driver code
          let money = 15 ; // total money
        let price = 1; // cost of each candy
          
        // no of wrappers needs to be
        // exchanged for one chocolate.
        let wrap = 3 ;
        document.write(Math.floor(
            countMaxChoco(money, price, wrap)));
             
</script>

Producción : 

22

Una solución eficiente es usar una fórmula directa para encontrar el número de chocolates. 

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

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

En la implementación ingenua anterior, notamos que después de encontrar la cantidad inicial de chocolates, dividimos recursivamente la cantidad de chocolates por la cantidad de envoltorios requeridos. hasta que nos quede con 1 bombón o capa. 
Estamos recalculando los valores, es decir ((choc/wrap + choc%wrap)/wrap hasta obtener 1. 
Se observa que podemos obtener el resultado simplemente reduciendo los valores de chocolates y envolturas por 1 y luego dividiéndolos para obtener el resultado (choc-1)/(envoltura-1) 

A continuación se muestra la implementación del enfoque anterior:

C++

// Efficient C++ program to find maximum
// number of chocolates
#include <iostream>
using namespace std;
 
// Returns maximum number of chocolates we can eat
// with given money, price of chocolate and number
// of wrapprices required to get a chocolate.
int countMaxChoco(int money, int price, int wrap)
{
    // Corner case
    if (money < price)
       return 0;
 
    // First find number of chocolates that
    // can be purchased with the given amount
    int choc = money / price;
 
    // Now just add number of chocolates with the
    // chocolates gained by wrapprices
    choc = choc + (choc - 1) / (wrap - 1);
    return choc;
}
 
// Driver code
int main()
{
    int money = 15 ; // total money
    int price = 1; // cost of each candy
    int wrap = 3 ; // no of wrappers needs to be
    // exchanged for one chocolate.
 
    cout << countMaxChoco(money, price, wrap);
    return 0;
}

Java

// Efficient Java program to find maximum
// number of chocolates
import java.io.*;
 
class GFG {
 
    // Returns maximum number of chocolates
    // we can eat with given money, price
    // of chocolate and number of wrapprices
    // required to get a chocolate.
    static int countMaxChoco(int money,
                        int price, int wrap)
    {
         
        // Corner case
        if (money < price)
            return 0;
     
        // First find number of chocolates
        // that can be purchased with the
        // given amount
        int choc = money / price;
     
        // Now just add number of chocolates
        // with the chocolates gained by
        // wrapprices
        choc = choc + (choc - 1) / (wrap - 1);
        return choc;
    }
     
    // Driver code
    public static void main (String[] args)
    {
         
        // total money
        int money = 15;
         
        // cost of each candy
        int price = 1;
         
        // no of wrappers needs to be
        int wrap = 3 ;
         
        // exchanged for one chocolate.
        System.out.println(
           countMaxChoco(money, price, wrap));
    }
}
 
// This code is contributed by anuj_67.

Python3

# Efficient Python3 program to find
# maximum number of chocolates
 
# Returns maximum number of
# chocolates we can eat with
# given money, price of chocolate
# and number of wrapprices
# required to get a chocolate.
def countMaxChoco(money, price, wrap) :
 
    # Corner case
    if (money < price) :
        return 0
 
    # First find number of chocolates
    # that can be purchased with the
    # given amount
    choc = int(money / price)
 
    # Now just add number of
    # chocolates with the chocolates
    # gained by wrapprices
    choc = choc + (choc - 1) / (wrap - 1)
    return int(choc )
 
# Driver code
money = 15 # total money
price = 1 # cost of each candy
wrap = 3 # no of wrappers needs to be
         # exchanged for one chocolate.
 
print(countMaxChoco(money, price, wrap))
 
# This code is contributed by Smitha

C#

// Efficient C# program to find maximum
// number of chocolates
using System;
 
class GFG {
 
    // Returns maximum number of chocolates
    // we can eat with given money, price
    // of chocolate and number of wrapprices
    // required to get a chocolate.
    static int countMaxChoco(int money,
                        int price, int wrap)
    {
         
        // Corner case
        if (money < price)
            return 0;
     
        // First find number of chocolates
        // that can be purchased with the
        // given amount
        int choc = money / price;
     
        // Now just add number of chocolates
        // with the chocolates gained by
        // wrapprices
        choc = choc + (choc - 1) / (wrap - 1);
        return choc;
    }
     
    // Driver code
    public static void Main ()
    {
         
        // total money
        int money = 15;
         
        // cost of each candy
        int price = 1;
         
        // no of wrappers needs to be
        int wrap = 3 ;
         
        // exchanged for one chocolate.
        Console.WriteLine(
        countMaxChoco(money, price, wrap));
    }
}
 
// This code is contributed by anuj_67.

PHP

<?php
// Efficient PHP program to find maximum
// number of chocolates
 
// Returns maximum number
// of chocolates we can eat
// with given money, price
// of chocolate and number
// of wrapprices required
// to get a chocolate.
function countMaxChoco($money, $price, $wrap)
{
    // Corner case
    if ($money < $price)
    return 0;
 
    // First find number
    // of chocolates that
    // can be purchased
    // with the given amount
    $choc = $money / $price;
 
    // Now just add number
    // of chocolates with the
    // chocolates gained by wrapprices
    $choc = $choc + ($choc - 1) /
                    ($wrap - 1);
    return $choc;
}
 
    // Driver code
     
     // total money
    $money = 15 ;
     
    // cost of each candy
    $price = 1;
     
    // no of wrappers needs to be
    // exchanged for one chocolate.
    $wrap = 3 ;
    echo countMaxChoco($money, $price, $wrap);
     
// This code is contributed by ajit
?>

Javascript

<script>
 
// Efficient Javascript program to find maximum
// number of chocolates
 
// Returns maximum number of chocolates
// we can eat with given money, price
// of chocolate and number of wrapprices
// required to get a chocolate.
function countMaxChoco(money, price, wrap)
{
      
    // Corner case
    if (money < price)
        return 0;
  
    // First find number of chocolates
    // that can be purchased with the
    // given amount
    let choc = parseInt(money / price, 10);
  
    // Now just add number of chocolates
    // with the chocolates gained by
    // wrapprices
    choc = choc + parseInt((choc - 1) /
                           (wrap - 1), 10);
    return choc;
}
 
// Driver code
 
// Total money
let money = 15;
 
// Cost of each candy
let price = 1;
 
// No of wrappers needs to be
let wrap = 3;
 
// Exchanged for one chocolate.
document.write(countMaxChoco(money, price, wrap));
 
// This code is contributed by divyesh072019
 
</script>

Producción : 

22

Complejidad de tiempo: O (1), ya que no estamos usando ninguna declaración de bucle en nuestro programa.

Complejidad espacial: O (1), ya que no estamos utilizando ningún espacio adicional.

Este artículo es una contribución de Sahil Chhabra (akku) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *