| Hi helper friends
I have this problem: Given two integers int a and int b (b is always greater than a) we want to obtain a
chain
(string) representing the least amount of transactions that must be
done to arrive from a to b. Operation is seen as multiply by 2 or add
1, in each case have to put parenthesis.
For example:
----------------------------------------------------------
a = 2, b = 4 the result is "2*(2)"
a = 3, b = 8, the result is "2*(3+1)"
a = 3, b = 9 the result is "2*(3 +1)+1"
a = 2, b = 10 the result is "2*(2 *2+1)"
a = 4, b = 9 the result is "4*(2)+1"
a = 4, b = 9 the result is "2*(4+1)" a = 2, b = 11 the result is "2*((2*2)+1)+1" ----------------------------------------------------------- Now some bad to the problem maybe can help to find the right: --------------------------------------------------------------- Bad solution one:
public static string Operations_A_to_B(int a, int b)
{
string result = string.Empty;
bool islocated = false;
bool ispos1 = false;
bool ispos2 = false;
int pos1 = 0;
int pos2 = 0;
int temp = a;
while (a < b)
{
if (!islocated)
{
for (int i = 1; i < b; i++)
{
if (2 * (a + i) <= b)
{
pos1 = i;
}
if (a * (2 + i) <= b)
{
pos2 = i;
}
else
{
islocated = true;
break;
}
}
if (pos1 != 0 || pos2 != 0)
{
if (pos1 >= pos2)
{
result += a + "*(2";
ispos2 = true;
}
else
{
result += "2*(" + a;
ispos1 = true;
}
islocated = true;
a *= 2;
}
}
if (ispos1)
{
if (2 * temp * 2 <= b)
{
if (2 * temp * 2 == b)
{
result += "*2)";
break;
}
else
{
result += " * 2";
temp *= 2;
a *= 2;
}
}
else if (2 * (temp + 1) <= 0)
{
if (2 * (temp + 1) == 0)
{
result += "+1)";
break;
}
else
{
result += "+1";
temp++;
a++;
}
}
else
{
ispos1 = false;
result += ")";
}
}
else if (ispos2)
{
if (2 * temp * 2 <= b)
{
if (2 * temp == b)
{
result += "*2)";
break;
}
else
{
result += "*2";
if (a*2 == b) result += ")";
a *= 2;
temp *= 2;
}
}
else if (temp * (2 + 1) <= 0)
{
if (temp * (2 + 1) == 0)
{
result += "+1)";
break;
}
else
{
result += "+1";
temp++;
a++;
}
}
else
{
ispos2 = false;
result += ")";
}
}
else if (result == string.Empty) result += a;
else if (b / 2 >= a && b % 2 == 0)
{
result += "*2";
a *= 2;
}
else if (b / 2 >= a && b % 2 != 0)
{
result += "*2+1";
a = a * 2 + 1;
}
else
{
result += "+1";
a++;
}
}
return result;
}
---------------------------------------------------------------
bad solution two:
string result = string.Empty;
int a = 4;
int b = 9;
int flag = 0, flag2;
While(b != 0) {
if(a*2 <= b) {
if(flag) {
result = result + "+(2*" + a + ")";
flag2 = 0
}
b = b - a * 2;
if(b == 1)
result = result + "2*(" + a + "+1)";
else if(flag2)
result = result + "2*(" + a + "+1)";
flag = 1;
flag2 = 1;
} else {
result = result + "+1";
b--;
}
}
that last was by our friend Megha P
thanks in advanse... |