Post date: Jul 18, 2013 9:54:57 AM
Problem
There are some glasses with equal volume 1 litre. The glasses kept as follows
1
2 3
4 5 6
7 8 9 10
You can put water to only top glass. If you put more than 1 litre water to 1st glass, water overflow and fill equally both 2nd and 3rd glass. Glass 5 will get water from both 2nd glass and 3rd glass and so on..
If you have X litre of water and you put that water in top glass, so tell me how much water contained by jth glass in ith row.
Example. If you will put 2 litre on top.
1st – 1 litre
2nd – 1/2 litre
3rd - 1/
*/
/*
level 0: 1
level 1: 1/2 1/2
level 2: 1/4 2/4 1/4
level 3: 1/8 3/8 3/8 1/8
level 4: 1/16 4/16 6/16 4/16 1/16
*/
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Calculate how many water contained by jth glasses
Created Data : 18-07-2013
Last Modified :
============================================================================
*/
using namespace System;
using namespace System::Diagnostics;
using namespace System::Collections::Generic;
float CalcWaterInGlass1(int jth, int ith, float x)
{
Debug::Assert(ith >= 0);
Debug::Assert(jth >= 0);
Debug::Assert(jth <= ith);
int level = 0;
array<float>^ prevCol = gcnew array<float>(ith + 2);
array<float>^ currCol = gcnew array<float>(ith + 2);
prevCol[0] = x;
for(level = 0; level < ith; ++level){
for(int i = 0; i <= level; ++i){
if(prevCol[i] > 1.0f){
currCol[i] += (prevCol[i] - 1.0f) / 2;
currCol[i + 1] += (prevCol[i] - 1.0f) / 2;
}
}
for(int i = 0; i <= level + 1; ++i){
prevCol[i] = currCol[i];
currCol[i] = 0.0f;
}
}
return (prevCol[jth] > 1.0) ? 1.0 : prevCol[jth];
}
void DoTest(int jth, int ith, float water)
{
Console::WriteLine(L"Total water:{0}", water);
Console::WriteLine(L"({0}, {1}) = {2}",
jth, ith, CalcWaterInGlass1(jth, ith, water), water);
Console::WriteLine("---------------------------------------");
}
int main(array<System::String ^> ^args)
{
DoTest(0, 0, 0);
DoTest(0, 0, 0.5);
DoTest(0, 0, 1.0);
DoTest(0, 0, 1.5);
DoTest(0, 1, 0.5);
DoTest(0, 1, 1);
DoTest(0, 1, 1.5);
DoTest(0, 1, 3);
DoTest(0, 1, 3.5);
DoTest(1, 1, 0.5);
DoTest(1, 1, 1);
DoTest(1, 1, 1.5);
DoTest(1, 1, 3);
DoTest(1, 1, 3.5);
DoTest(0, 2, 0.5);
DoTest(0, 2, 3.0);
DoTest(0, 2, 4.5);
DoTest(0, 2, 6);
DoTest(1, 2, 1.5);
DoTest(1, 2, 3);
DoTest(1, 2, 5);
DoTest(1, 2, 6);
DoTest(2, 2, 1.5);
DoTest(2, 2, 3);
DoTest(2, 2, 5);
DoTest(2, 2, 6);
DoTest(0, 3, 8);
DoTest(1, 3, 8);
DoTest(2, 3, 8);
DoTest(3, 3, 8);
return 0;
}
Output
Total water:0
(0, 0) = 0
---------------------------------------
Total water:0.5
(0, 0) = 0.5
---------------------------------------
Total water:1
(0, 0) = 1
---------------------------------------
Total water:1.5
(0, 0) = 1
---------------------------------------
Total water:0.5
(0, 1) = 0
---------------------------------------
Total water:1
(0, 1) = 0
---------------------------------------
Total water:1.5
(0, 1) = 0.25
---------------------------------------
Total water:3
(0, 1) = 1
---------------------------------------
Total water:3.5
(0, 1) = 1
---------------------------------------
Total water:0.5
(1, 1) = 0
---------------------------------------
Total water:1
(1, 1) = 0
---------------------------------------
Total water:1.5
(1, 1) = 0.25
---------------------------------------
Total water:3
(1, 1) = 1
---------------------------------------
Total water:3.5
(1, 1) = 1
---------------------------------------
Total water:0.5
(0, 2) = 0
---------------------------------------
Total water:3
(0, 2) = 0
---------------------------------------
Total water:4.5
(0, 2) = 0.375
---------------------------------------
Total water:6
(0, 2) = 0.75
---------------------------------------
Total water:1.5
(1, 2) = 0
---------------------------------------
Total water:3
(1, 2) = 0
---------------------------------------
Total water:5
(1, 2) = 1
---------------------------------------
Total water:6
(1, 2) = 1
---------------------------------------
Total water:1.5
(2, 2) = 0
---------------------------------------
Total water:3
(2, 2) = 0
---------------------------------------
Total water:5
(2, 2) = 0.5
---------------------------------------
Total water:6
(2, 2) = 0.75
---------------------------------------
Total water:8
(0, 3) = 0.125
---------------------------------------
Total water:8
(1, 3) = 0.875
---------------------------------------
Total water:8
(2, 3) = 0.875
---------------------------------------
Total water:8
(3, 3) = 0.125
---------------------------------------
Press any key to continue . . .