A blacksmith has 10 scrap pieces of chain that he wants to join together to make a whole chain. It takes time to open and reweld a link, so he wants to do this as few times as possible. The number of links in the scraps are 2, 3, 4, 6, 8, 9, 12, 13, 15 and 19.
What is the most efficient way for him to join all the pieces?
It takes n-1 open links to fully link up n segments.
But if a segment is completely eliminated by opening all its links, then n is reduced by 1 and one les open link will be needed.
If you completely eliminate 2 of the 10 segments, then you need 7 open links.
Convert the 3 and the 4 to all open links then link up the remaining 8 segments with the 7 open links.
|
|
Posted by Larry
on 2024-01-07 11:51:33 |
one way
