mAn1Ac
BAN USERohhhh !!! actually i was working on some other code and when i wrote this code so everything here got mixed up !! sorry for that .. i take all back .. u seem a pretty decent guy .. sorry for my outburst :)
also u saw my unedited code thats y ... i edited it afterwards ... thanks anyways :)
and who do u think u r .. u are in a public forum so act accordingly !!
GCC is a well renowned compiler !! people everywhere use it !!
and best code is not one with complex statements and lots of symbols with big names !! best code is with best logic !! main question is of logic .. anyone can convert it in some language ..
and if u r such a genius so y don't u give ur code .. y r u going around and just blurting non sense all over the place .. people come here to learn something and morons like u are spoiling that !!!
struct node
{
char data;
struct node* link;
};
struct node * modification(struct node * start ) // start is pointer to start of linked list
{
struct node *p , *q;
char temp;
if(!start || !start-> link)
return;
p = start;
q = start->link;
while (q)
{
temp = p->data;
p->data = q->data;
q->data = temp;
p = q->link;
q = p->link;
}
return start;
}
divide the 8 balls in 3 groups
say .. group A => 3 balls
group B=> 3 balls
group C =>2 balls
put group a and b on balance ..
case 1) A = B .. implies either both a and b have the one heavy ball or group c have both the balls
so choose any two balls from any one of the group ie. A or B (suppose i chose group A) and weigh them against group C ..
if (the balance balances)
{
that means the third ball of group A is heavier one and the other heavy ball is in group B .. so to get it choose any two balls from group B and weigh them against each other ..
if (they are equal)
{that means its the third ball of group B..}
else
{its the one which is giving more weight on balance ..}
}
else if (the side with group C on it is heavier)
{ both the balls of group C are heavy balls .. the required balls ..
THIS IS THE BEST CASE }
else // side with group A's balls is heavier
{
this means one of the two balls are heavier .. (THIS IS THE WORST CASE)
now weigh both balls against each other u will get one heavy ball ..
for next heavy ball take any two balls from group B and weigh them .. if they are equal then its the third ball otherwise which ever is heavier ...
}
Case 2) side with A is heavier ..this means either one heavy ball is in A and another in C or both are in A ...now take 2 balls from A and weigh them against group C
if(balance balances)
{
this means each side has one heavy ball .. now in each of these groups weigh one ball against another to get the heavy balls .. THIS IS ALSO WORST CASE
}
else if(side with C on it is heavier)
{
weigh the balls of C against each other .. if equal means these are the two required balls .. if not then u will get one heavy ball and the other heavy ball is the third ball of group A ..
}
else
{
weigh the two balls of group A .. if equal then they are the required ones .. if not then u will get one heavy ball and the other heavy ball is the third ball of group A...
}
Case 3) side with B is heavier .. same as case (2) ..
FINALLY,
for BEST CASE => 2 comparisions
for AVERAGE CASE => 3 comparisions
for WORST CASE => 4 comparisions ..
@Psycho ya ur modification in algo. is better than original .. but this is not the one which i gave .. thanks :)
@ eugene.yarovoi try with the modified one .. and also try with the threshold i suggested .. see if there is any improvement .. i'll post some test input against which u can check the algos.
@ eugene.yarovoi .. first of all awesome analysis !! thanks :)
secondly coming to ur question .. according to my original algo. 243+3+4 will be taken which will give worst result .. so what i m suggesting is we can decide some threshold value and if the difference between the given number and closest power of 3 is less than that threshold then we'll go with ur algo. otherwise we'll go with mine for one iteration .. then for next iteration we can check once again ... i thought of this because ur algo. is giving best result with worst case and mine with average case .. so by combining both we can get the best result for every value of n ..
for threshold i am thinking it should be something like next lower power of three .. i am not sure though ... so if u can try to come up with some expression for threshold which will give best results, it would be great .. i'll also try ..
by using this method the time complexity of algo will definitely increase a bit because at every step some extra computations will be done but we are also getting best results for each value of n ...
also we need to do this comparison at each iteration because i am thinking that on an average the worst case also will eventually convert to the average case .. obviously u can always come up with some value of n which always gives worst case but it might not happen that often ..
ya u can do that also but the thing is with ur approach u will need more number of iterations .. while with my approach iteration will be less but no. of groups will increase a bit .. so finally i think both approach will give nearly same number hits required .. so it depends on where u want to compromise ..
also i haven't checked both approaches ... i am just thinking this must be whats going on .. if someone actually checked with both approaches please comment .. :)
divide in group such that each group contain elements equal to certain power of 3 which is nearest to the total number of elements ..
for example if total 25 elements are given divide in groups of 9 element each so there will be 2 groups of 9 elements and 1 group of 3 elements .. each group will be further divide into 3 groups of 3 element each ....
coming to given problem of 8 cue balls .. divide into 3 groups ..
2 groups of 3 elements each .. say A and B
1 group of 2 element ..
put group A and B in balance ... there are 3 cases ..
case 1) if side with group A is lighter then remove the groups from balance and choose any 2 balls from group and put on balance .. if any one of them is lighter then u will directly know but if the balance is balanced then its the third ball (the one which u didnt put on balance) ..
case 2) if side with B on it is lighter .. apply the same logic as above ..
case 3) if balance is balanced then its the group 3 .. take the given 2 balls and put it on balance ... u r done :)
since u said number of queues are not fixed you can take a linked list where each node will contain address to a queue so whenever u need a new queue you just create a new node ..
Pros ..
1) Flexibility of size
2) Max. space utilization
Cons ..
1) no random access
2) overhead of pointer
definition of node of linked list will depend on how queue is implemented ..
1) if size of queue is constant use array .. then node is defined as follows :
struct node
{
int * queue; // queue is name of pointer pointing to base address of queue
struct node * link // link to next node
};
2) if variable size of queue is required and u don't mind the pointer overhead you can use linked list ... then definition of node will be ..
struct Qnode // node of queue using linked list
{
int data; // store data at node
struct Qnode * next; // pointer to next node
};
struct node // node containing start address of queues
{
struct Qnode * queue; // stores address of first node of queue liked list
struct node * link; // link to next node of linked list
};
there is one more way .. fill 3ltr jar with 5ltr jar ... now 2ltr left in 5ltr jar .. empty 3ltr jar and fill it with the liquid left in 5ltr jar .. now 5ltr jar is empty .. fill it again and completely fill the 3ltr jar ie. the 1ltr left in it ... so now 5ltr jar contain 4ltr ..
- mAn1Ac March 25, 2013