[Summary] This article briefly introduces Chinese traditional intelligence games - nine links, analyzes the laws, gives the algorithm for solving problems. [Key words] nine-link, N serial, recursion, dismantling, installation
I. Introduction to Jiuyi
Nine-winning games are Chinese people's own inventions, and its history is very long, and it is said to originate from the Warring States Period. The nine consecutive ring is mainly composed of a frame and nine rings: there is a straight rod on each ring, and this straight rod is passed through a circle, and the other end of nine straight rods uses a wooden board or The ring is relatively fixed.
Second, the law of nine links
You will find such a rules by playing nine links:
(1) The first ring can be free to up and down (2) (n> 1), then (n> 1) must be satisfied: (a) N-1 ring on the frame (b) front n-2 All the ring is under the rack
Third, the process of dismantling / installation
The correct dismantling is the first to go to the 9th ring, first remove it, simplify to remove an 8 link. Then, the 8th ring is another target, and it is removed, simplifies to remove a 7th link. Up to this class until all dismantles.
In fact, installation and dismantling is a truth because they are all done using the laws mentioned above. Correctly installation is also a target first, first install it, simplifies into a 8-year ring. Then, the eighth ring is another target, install it, simplifies into a 7-link. Push it until all installations. Of course, now, it is easy to understand. When you understand the laws above, you will find that after installing the 9th ring, the problem can be simplified into a 7-year-old ring, while the 7th ring After that, the problem is simplified to load a 5 serving, huh, just like this, don't know if you understand what I mean now ...
Fourth, a conjecture
Carefully observe the structure of the nine links, thinking about the law of nine links and dismantling / installation, do you have a feeling: Jiuyi ring will have a connection with recurrence. You see that the basic idea of recursive is to break a big problem into a smaller problem, from these smaller problems, construct a big problem, and the smaller problems, with the same method to decompose Come smaller problems, from smaller problems, construct smaller problems, one layer, generally finally decomposed to a small problem that can be solved directly. Hey, the dismantling / installation of Jiuyi Ring is in line with this rule ... ^ _ ^
V. Algorithm implementation
The following is the implementation of the algorithm, the program is very simple, omitted a lot of functions, such as counting, if you think it is necessary, you can add it, I believe it is easy, don't change much.
The C Code Here:
/ *************************** / Arbitrary N serving aid Date: 2002/11/6 program Design: Dao Can Tencent QQ : 3908000 Email: Havelife@mail.9cbs.net / **************************** /
Void Upring (); / * Function declaration * /
Void DownRing (int N) / * lower ring logic * / {if (n> 2) DOWNRING (N-2); Printf ("lower% D ring / n", n); if (n> 2) upring N-2); if (n> 1) DOWNRING (N-1);}
Void Upring (int N) / * Uplined logic * / {if (n> 1) upring (n-1); if (n> 2) DOWNRING (N-2); Printf ("upper-definition D ring / n ", n); if (n> 2) upring (n-2);} void main () / * principal function * / {printf (" dismantling / N "); DOWNRING (9); Printf (" Install / n "); upring (9); printf (" end / N ");}
2002 Nine Edition Edition No. 1: Chinese Traditional Intelligence Game - Recursive Algorithm of Jiuyi Ring (Nine Link Algorithm 1st)
2006 Nine Wild Ring Algorithm 2nd Edition: Nine Connected Recursive Algorithm (Jiubi Ring Algorithm 2nd Edition)
2016 Nine Eclipse Algorithm Item 3: Jiuyi Ring Algorithm (3rd Edition)
