Рашэнне для бутэлек з вадой


Узровень складанасці Лёгка
Часта пытаюцца ў Microsoft
Прагны

Пастаноўка праблемы

У задачы "Бутэлькі з вадой" мы атрымліваем два значэнні, а менавіта "numBottle", у якім будзе захоўвацца агульная колькасць поўных бутэлек з вадой, і "numExchange", у якім будзе захоўвацца агульная колькасць пустых бутэлек з вадой, якія мы можам абмяняць адначасова і атрымаць поўны бутэлька з вадой.

Пасля ўжывання вады з поўнай бутэлькі яна ператвараецца ў пустую. Наша задача - высветліць максімальную колькасць поўных бутэлек з вадой, якую мы можам выпіць.

Прыклад

numBottles = 15, numExchange = 4
19

Тлумачэнне:

Рашэнне для бутэлек з вадой

Першы тур: піць 15 бутэлькі вады дае 15 пустых бутэлек.

Другі тур: з гэтых 15 бутэлек з вадой мы атрымліваем 3 поўныя бутэлькі з вадой і пакідаем 3 пустыя бутэлькі. Піць 3 у нас цяпер засталося 6 пустых бутэлек з вадой.

Трэці раўнд: з гэтых 6 бутэлек з вадой мы атрымліваем 1 поўную бутэльку з вадой і пакідаем 2 пустыя бутэлькі. Выпіце 1 бутэльку вады, якую мы зараз пакінулі, у агульнай складанасці 3 пустыя бутэлькі.

Паколькі для замены бутэлькі патрабуецца мінімум 4 бутэлькі, мы больш не можам купіць поўную бутэльку з вадой. Такім чынам, максімальная колькасць бутэлек з вадой, якую мы можам выпіць, гэта 15 + 3 + 1 = 19.

Падыход для бутэлек з вадой

Асноўны падыход да вырашэння праблемы - рабіць тое, што задаюць пытанні.

  1. Выпіце ўсе поўныя бутэлькі з вадой, пасля чаго яна ператворыцца ў пустыя бутэлькі з вадой.
  2. З усіх пустых бутэлек з вадой купіце поўныя бутэлькі з вадой.
  3. Паўтарайце гэтыя дзеянні, пакуль мы не зможам купіць поўную бутэльку з пустой бутэлькай.
  4. Вярніце агульную колькасць поўных бутэлек з вадой, якія мы выпілі падчас працэсу.

Мы можам палепшыць складанасць рашэння, зрабіўшы некалькі назіранняў:

  1. У нас ёсць колькасць поўных бутэлек з вадой, таму гэта будзе мінімальная колькасць поўных бутэлек, якія мы можам выпіць.
  2. 1 поўная бутэлька вады = 1 адзінка вады + 1 пустая бутэлька вады.
  3. З пустых бутэлек з вадой numExchange мы атрымліваем 1 поўную бутэльку з вадой (1 адзінка вады + 1 пустая бутэлька з вадой). Гэта таксама можна інтэрпрэтаваць як (numExchange-1) бутэлькі з вадой даюць 1 адзінку вады.
  4. Але калі ў апошнім туры, калі ў нас ёсць (numExchange-1) колькасць пустых бутэлек, то мы не можам атрымаць адну адзінку вады.
  5. Такім чынам, наш вынік будзе numBottle + (numBottle / (numExchange -1)), а калі numBottle% (numExchange -1) == 0, то ад канчатковага адказу адымем 1.

Рэалізацыя

Код C ++ для бутэлек з вадой

#include <bits/stdc++.h> 
using namespace std; 
    int numWaterBottles(int numBottles, int numExchange) {
        int ans= numBottles + (numBottles) / (numExchange - 1);
        if((numBottles) %(numExchange - 1)==0)
            ans--;
        return ans;
    }
int main() 
{ 
 int numBottles = 15, numExchange = 4;
 int ans=numWaterBottles(numBottles,numExchange);
 cout<<ans<<endl;
 return 0;
}
19

Код Java для бутэлек з вадой

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static int numWaterBottles(int numBottles, int numExchange) {
        int ans= numBottles + (numBottles) / (numExchange - 1);
        if((numBottles) %(numExchange - 1)==0)
            ans--;
        return ans;
    }
  public static void main(String[] args) {
     int numBottles = 15, numExchange = 4;
     int ans=numWaterBottles(numBottles,numExchange); 
        System.out.println(ans);
  }
}
19

Аналіз складанасці раствора з бутэлькамі з вадой

Часовая складанасць

Часавая складанасць вышэйзгаданага кода O (1).

Касмічная складанасць

Касмічная складанасць вышэйзгаданага кода складаецца ў O (1) таму што мы выкарыстоўваем толькі зменную для захоўвання адказу.

Спасылкі