Tencent interview: can you pour water?

Hello everyone , I'm brother Tao .

 

today , Let's look at a very interesting Tencent interview question , Pupils can understand , But it's not easy to get it right . Let's have a look at the topic , That's interesting ：

Yes A and B Two cups and enough water , The cup capacity is 9 L and 15 l , Try to judge , Can you measure n Liters of water , If you can , Please program the steps .

                                                                  Hand painted by Taoge  

What does this topic mean ？ Let me explain ：

(1)  Fill it up first A, Refill B, here A Yes 9 l ,B Yes 15 l . obviously , This measures 24 Liters of water . To put it bluntly , Namely A + B = 24.

(2)  Fill it up first A, And then A Pour all the water in B in , here A It's empty ,B Yes 9 l . Then fill it up A, Keep on putting A Pour the water in B in , until B Until it's full , here A be left over 3 l . obviously , This measures 3 Liters of water . To put it bluntly , Namely 2A - B = 2 * 9 - 15 = 3.

One . logic analysis

set up A = 9,B = 15, We can equate these two cups to A = 9,B = 6, Continue to be equivalent to A = 3,B = 6, Continue to be equivalent to A = 3,B = 3, in other words , In the end, it's actually equivalent to having a 3 L Cup . therefore , The water that can be poured out must be 3 Multiple .

The above equivalence analysis process , In fact, it is the process of finding the greatest common divisor . therefore , We can get the law ：A L cup and B L Cup , The measurable water is k * gcd(A,B) l . among K Is a nonnegative integer ,gcd Represents the greatest common divisor . therefore , The judgment function of the original question is ：

#include <iostream>
using namespace std;

int gcd(int x, int y)
{  
  int z = y;
  while (x % y != 0)
  {
    z = x % y;
    x = y;
    y = z;  
  }
  
  return z;
}

bool can(int A, int B, int n)
{
  if (n % gcd(A, B) == 0)
  {
    return true;
  }
  
  return false;
}

int main()
{
   for(int n = 0; n < 20; n++) // test
   {
      if (can(9, 15, n) )
      {
        cout << n << endl;
      }
   }

   return 0;
}

The result is ：

0

3

6

9

12

15

18

Two . Pouring steps

Now that we know what meets the conditions n Value , So how to use A and B Cup measurement n Liters of water ？ Might as well set A < B, So when n >= A when , We can always start from n Constantly subtract A, Until it's not enough . What does that mean ？

In fact, it is aimed at any n value , We can always turn it into n < A < B Questions like this , such as ：A = 9,B = 15,n = 33, We can equivalent to ：A = 9,B = 15,n = 33 - 9 - 9 - 9 = 6. below , Look at the program ：

#include<iostream>   
using namespace std;  
 
void pour(int A, int B, int target)
{
  //inA, inB respectively A,B Amount of reclaimed water 
  int inA = 0;
  int inB = 0;
  
  int flag = 0;
  while(1)   
  {   
    // Suppose that the pouring operation can be carried out in a certain while Complete within the number of cycles 
    if(flag++ > 999) 
    {
      cout << "Fail" << endl;
      break;
    }
 
    if(0 == inA)   
    {   
        cout << "fill A" << endl;
        inA = A;   
    }   
    else  
    {   
        cout << "pour A into B" << endl;
        inB += inA;   
        
        if(inB >= B)   
        {    
           inA = inB - B;  
           cout << "empty B" << endl;
           inB = 0;     
        }   
        else  
        {   
            inA = 0;   
        }   
    }   

   if(target == inA || target == inB)   
    {   
        cout << "Success, OK!" << endl;
        break;   
    }   
  }
}
 
int main()   
{   
    int A = 9;
    int B = 15;
    int n = 6;
  
    // Have proved , Any A,B,n In this topic, it can be converted into the following form 
    // namely ：0 <= n < A < B
    pour(A, B, n);
 
  return 0;
}

The result is ：

fill A

pour A into B

fill A

pour A into B

empty B

pour A into B

fill A

pour A into B

fill A

pour A into B

empty B

Success, OK!

This Tencent interview question is not difficult , The key lies in logical analysis , As for programming , Just let it be 、 What happens naturally .

I hope you can draw one example from another , The written interview went well . It's Friday again , Did you feel the darkness before dawn ？ I'll see you tomorrow Saturday .