frankie
BAN USERIf you want to use math operations/functions other than bit manipulation you could do this:
void print_ab(int input){
int output_length = floor(log(input + 1)/log(2));
int dividend = (input+1)-pow(2, output_length);
int divisor = pow(2, output_length-1);
for(; divisor>0; divisor/=2){
if(dividend/divisor==0){
printf("A");
}else{
printf("B");
dividend%= divisor;
}
}
printf("\n");
}
This will only work for input >= 1.
I compiled this on Manjaro with the following: gcc printing_ab_output.c -lm.
You should try being more open minded. I see nothing wrong with exploring alternative approaches to a problem. That is the whole basis of problem solving.
I think we do gain something. Suppose the question was extended to solve for a trinary tree or a b tree?
What is meant by depth?
A number of nodes to go through til we reach a leaf node starting from the root?
Example
Nodes: {A,B,C,D,E,F,G,H} Edges: {(A,B) (A,C) (B,D) (B,E) (E,F) (E,G) (F,H)}
The depth of H is 4?
The depth of G is 3?
One idea that comes to mind is the depth first search algorithm.
Below are things that I would add to the depth first search.
1. Each time we hop to a new child node we increment a distance variable.
2. Once we have reached the end of a branch (ie a leaf or a node that has
no children) we could compare the distance variable incremented thus far
to some variable container called maximum.
If it is bigger than maximum we replace the maximum thus far with this new distance value.
3. Once we go back up a traversed branch to discover a new branch in the
tree as the algorithm would, how would we account for the new distance?
Example
Nodes:{A,B,C,D,E,F} Edges:{(A,B) (A,C) (C,D) (C,F) (D,E)}
i. we traverse to B and have our max depth as 1 so far.
ii. we go back up the tree to start back at the head and go down
the right side of the binary tree. Now the new distance should be recalculated
but how do we know it should be set to 0? In this case we are at the head so
one could set back to 0 whenever we get back up to head. But there is
a better idea and I will get to it at step iiii.
iii. We discover E and recalculate the maximum to be 3.
iiii. As we go back up the branch up to C. How do we know that the distance should be set to 1 before discovering F and incrementing it to 2?
One idea is for every hop we go DOWN the tree, we INCREMENT distance by 1 BUT every time we hop UP, we DECREMENT distance by 1.
The worst time complexity would be that of depth first search, depth first search goes through all leaves before terminating. We NEED to get to all leaves to do a fair comparison of all the potential depths to find the maximum depth.
What is meant by create a maze? Draw a maze with a paper and a pencil or design a program to generate a maze? If we were writing a program did they want us to generate a data structure that represents a maze? Did they want it printed to the screen?
- frankie March 20, 2015