猫吃老鼠的系统化算法

brois

1. 一、问题描述
   
2. 　　现有n个老鼠围成一圆圈，有一只猫从任意位置开始吃老鼠，每次都隔一个老鼠吃，请给出最后一个老鼠的编号？题目要求是任给老鼠数n，输出猫最后吃的老鼠的编号。
   
3. 
   
4. 　　二、问题求解
   
5. 
   
6. 　　我们假设有N个老鼠，序号依次为1,2,3,......,N-1,N，并且按序号先后以顺时针围成一圈。
   
7. 
   
8. 　　老鼠信息的结构定义如下，使用双向列表，如下：
   
9. 
   
10. typedef struct MouseNode
    
11. {
    
12. 　　int nNO;
    
13. 　　MouseNode *pNext;
    
14. 　　MouseNode *pPre;
    
15. 　　MouseNode() { nNO = 0; pNext = NULL; pPre = NULL; }
    
16. 　　MouseNode(int NO) { nNO = NO; pNext = NULL; pPre = NULL; }
    
17. }MouseNode;
    
18. 
    
19. 　　我的算法只有一个函数，这个函数完成吃一圈老鼠。传入的参数是双向链表中本次要吃掉的第一个老鼠,返回值是下一圈吃老鼠时要第一个吃掉的老鼠。
    
20. 
    
21. 　　函数代码如下：
    
22. 
    
23. // CatEatMouses
    
24. /*
    
25. 本函数只吃一圈老鼠，循环调用它来吃完老鼠
    
26. 　　参数　　　　本次要吃掉的老鼠
    
27. 　　返回　　　　下一圈吃老鼠时候要吃的第一个老鼠
    
28. 　　　　　　　　若返回值为空，则说明老鼠已经吃完了
    
29. */
    
30. MouseNode *CatEatMouses(MouseNode *pStartMouse)
    
31. {
    
32. 　　MouseNode *pFirst = pStartMouse;
    
33. 　　MouseNode *pFirstNotEatMouse = pFirst->pNext;
    
34. 　　if(pFirst == pFirstNotEatMouse)
    
35. 　　{
    
36. 　　　　printf("%d ", pFirst->nNO);
    
37. 　　　　return NULL; // 吃完了
    
38. 　　}
    
39. 　　bool bCanEat = true;
    
40. 　　while (true)
    
41. 　　{
    
42. 　　　　if(pFirst == pFirstNotEatMouse)
    
43. 　　　　{
    
44. 　　　　　　if(bCanEat)
    
45. 　　　　　　{
    
46. 　　　　　　　　return pFirstNotEatMouse;
    
47. 　　　　　　}
    
48. 　　　　　　else
    
49. 　　　　　　{
    
50. 　　　　　　　　return pFirstNotEatMouse->pNext;
    
51. 　　　　　　}
    
52. 　　　　}
    
53. 　　　　if(bCanEat)
    
54. 　　　　{
    
55. 　　　　　　pFirst->pPre->pNext = pFirst->pNext;
    
56. 　　　　　　pFirst->pNext->pPre = pFirst->pPre;
    
57. 　　　　　　printf("%d ", pFirst->nNO);
    
58. 　　　　　　pFirst = pFirst->pNext;
    
59. 　　　　　　bCanEat = false;
    
60. 　　　　}
    
61. 　　　　else
    
62. 　　　　{
    
63. 　　　　　　pFirst = pFirst->pNext;
    
64. 　　　　}
    
65. 　　}
    
66. }三、演示函数

复制代码

dctwn

:L 看不懂