Shulou(Shulou.com)06/02 Report--

This article mainly explains "how to write the problem of Joseph ring". The content of the explanation is simple and clear, and it is easy to learn and understand. let's study and learn "how to write Joseph ring".

The original description of the problem of Joseph's ring is that it is numbered 1pm 2,. N (n > 0) individuals form a circle, start counting from the first person, stop counting at m, then re-count from his next person, stop counting at m, report m out of circle,. It goes on like this until everyone is out of the circle. When any n and m are given, an algorithm is designed to calculate the order of n individuals out of the circle. Simplify it a little bit.

Problem description: n individuals (no. 0 ~ (nmur1)), start counting from 0, log out (mmur1), and the rest continue to count from 0. Ask for the number of the winner.

Idea: what is easy to think of is to use a linked list to build a linked list, and the number of each node is 0,1. NMI1. Move mmur1 step forward from the current position each time, and then delete the node. The last remaining node is the winner. Two methods are given, one is to customize the linked list operation, the other is to use the single linked list of STL library. It is not difficult to find that using the STL library can improve the speed of writing.

Struct ListNode {int num; / / No. ListNode * next; / / next ListNode (int n = 0, ListNode * p = NULL) {num = n; next = p;}}; / / Custom linked list implementation int JosephusProblem_Solution1 (int n, int m) {if (n)

< 1 || m < 1) return -1; ListNode *pHead = new ListNode(); //头结点 ListNode *pCurrentNode = pHead; //当前结点 ListNode *pLastNode = NULL; //前一个结点 unsigned i; //构造环链表 for(i = 1; i < n; i++) { pCurrentNode->

Next = new ListNode (I); pCurrentNode = pCurrentNode- > next;} pCurrentNode- > next = pHead; / / Loop traversal pLastNode = pCurrentNode; pCurrentNode = pHead; while (pCurrentNode- > next! = pCurrentNode) {/ / forward m-1 step for (I = 0; I

< m-1; i++) { pLastNode = pCurrentNode; pCurrentNode = pCurrentNode->

Next;} / / Delete the number of registered m-1 pLastNode- > next = pCurrentNode- > next; delete pCurrentNode; pCurrentNode = pLastNode- > next;} / / Free space int result = pCurrentNode- > num; delete pCurrentNode; return result;} / / use the standard library int JosephusProblem_Solution2 (int n, int m) {if (n)

< 1 || m < 1) return -1; list listInt; unsigned i; //初始化链表 for(i = 0; i < n; i++) listInt.push_back(i); list::iterator iterCurrent = listInt.begin(); while(listInt.size() >

1) {/ / forward m-1 step for (I = 0; I

< m-1; i++) { if(++iterCurrent == listInt.end()) iterCurrent = listInt.begin(); } //临时保存删除的结点 list::iterator iterDel = iterCurrent; if(++iterCurrent == listInt.end()) iterCurrent = listInt.begin(); //删除结点 listInt.erase(iterDel); } return *iterCurrent;} 上述方法的效率很低，其时间复杂度为O(mn)。当n和m很大时，很难在短时间内得出结果。不过好处就是可以给出n个人出圈的次序。只要在删除前保存一下即可。 下面利用数学推导，如果能得出一个通式，就可以利用递归、循环等手段解决。下面给出推导的过程： （1）第一个被删除的数为 (m - 1) % n。 （2）假设第二轮的开始数字为k，那么这n - 1个数构成的约瑟夫环为k, k + 1, k + 2, k +3, .....,k - 3, k - 2。做一个简单的映射。 k ----->

0

Kappa 1-> 1

Kappa 2-> 2

...

...

KMY 2-> nMel 2

This is an n-1 person problem. If we can deduce the solution of n-1 personal problem from the solution of n-1 personal problem and get a recursive formula, then the problem will be solved. If we already know that when there are n-1 people, the number of the final winner is x, using the mapping relation to deduce, we can get that when n individuals, the number of the winner is (x + k)% n. Where k equals m% n. Replace (x + k)% n (x + (m% n))% n (x% n + (m% n)% n)% n (x%n+m%n)% n (x% m)% n

(3) the second deleted number is (m-1)% (n-1).

(4) assuming that the starting number of the third round is o, then the Joseph ring composed of these n-2 numbers is o, o + 1, o + 2 mai. O-3, o-2. Keep mapping.

O-> 0

Oaths 1-> 1

Oaths 2-> 2

...

...

OMui 2-> nMui 3

This is a problem of n-2 people. Assuming that the final winner is y, then for n-1, the winner is (y + o)% (n-1), where o equals m% (n-1). You can get (ymerm)% (nmur1) by substituting

In order to get the solution of n-1 personal problem, we only need to get the solution of n-2 personal problem and push it backwards. When there is only one person, the winner is the number 0. The following is a recursive formula:

F [1] = 0

F [I] = (f [I-1] + m)% I; (I > 1)

With the recursive formula, the implementation is very simple, and two ways to implement the loop are given. It shows once again the convenience of using the standard library.

Int JosephusProblem_Solution3 (int n, int m) {if (n < 1 | | m < 1) return-1; int * f = new int [nx1]; f [0] = f [1] = 0; / / f [0] actually unused for (unsigned I = 2; I

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.