I have a algorithm problem to ask:
There are N persons, and each of them knows one distinct gossip message. The two of them just make a phone call, so they could share messages they know. Then at least how many phone calls do they need make , so that each of them knows all the N messages?
- 2 Contributors
- forum2 Replies
- 11 Views
- 9 Years Discussion Span
- comment Latest Post by alien2006.happy
eggmatters 21
Hey there,
As with almost any algorithm, you want to define a base case. Also you want to have at least one testable condition, and then you need at least one exit condition. So . . . your exit condition will be :
for all N:
what needs to be known for all N? (hint: it's in the last sentence of your question. Also, you may want to introduce another variable here, call it P maybe to stand for something like . . . maybe a phone call.
Your base case is probably the most important as it is the first element in the formation of your algorithm:
Base Case:
N = (what should N equal?)
What is guaranteed to happen when N equals that number?)
And finally, your testable condition. This will be a set of true or false statements assigned based on whether or not assumptions are proven about your statement. When or if they are not met, something needs to change in order to attempt to satisfy the problem. I know this sounds text bookish, but base case thinking helps give you a starting point to flesh out the algorithm.
In short you have a set of N and a set of P for each N represents a message and a person. Basically, P represents the cross product of N onto itself. You can make the algorithm even more robust to determine what needs to happen if each N contains K messages.
Good Luck!
very impressive. Thank you. But now, I have some idea about this problem. I wanna use divide and conquer to solve this problems. First, the N is divided into [N/2] and [N/2] + 1 if N is odd, or [N/2] and [N/2] if N is even. Then we recursive solve the [N/2] or [N/2] + 1.
Secondly, after the divide, then they just need to make [N/2] + 1 more phone calls to make all the persons know all the gossip messages. For example, let's say N==5, then we firstly divide the 5 into 2 and 3. We need to solve what would happen when N==2 and N==3. After that, we just need to make 3 more phone calls. So they need to make 3 + 1 + 3 = 7 phone calls in all.
But the problem is that I could not prove that the answer is the right answer, or the least phone calls.
Edited
by alien2006.happy: .