1. //
   
2. //  main.c
   
3. //  三色棋
   
4. //
   
5. //
   
6. /*
   
7. Algorithm Gossip: 三色棋
   
8. 说明
   
9. 三色旗的问题最早由E.W.Dijkstra所提出，他所使用的用语为Dutch Nation Flag(Dijkstra为荷兰人)，而多数的作者则使用Three-Color Flag来称之。
   
10. 
    
11. 
    
12. 假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您希望将之分类，并排列为蓝、白、红的顺序，要如何移动次数才会最少，注意您只能在绳子上进行这个动作，而且一次只能调换两个旗子。
    
13. 解法
    
14. 在一条绳子上移动，在程式中也就意味只能使用一个阵列，而不使用其它的阵列来作辅助，问题的解法很简单，您可以自己想像一下在移动旗子，从绳子开头进行，遇到蓝色往前移，遇到白色留在中间，遇到红色往后移，如下所示：
    
15. 只是要让移动次数最少的话，就要有些技巧：
    
16. 如果图中W所在的位置为白色，则W+1，表示未处理的部份移至至白色群组。
    
17. 如果W部份为蓝色，则B与W的元素对调，而B与W必须各+1，表示两个群组都多了一个元素。
    
18. 如果W所在的位置是红色，则将W与R交换，但R要减1，表示未处理的部份减1。
    
19.  
    
20. 注意B、W、R并不是三色旗的个数，它们只是一个移动的指标；什幺时候移动结束呢？一开始时未处理的R指标会是等于旗子的总数，当R的索引数减至少于W的索引数时，表示接下来的旗子就都是红色了，此时就可以结束移动
    
21. */
    
22. #include <stdio.h>
    
23. #include <string.h>
    
24. int main(int argc, const char * argv[]) {
    
25.     char color[] = "BWRBWRBRRWWBBWW";
    
26.     long len = strlen(color);
    
27.     int start = 0;
    
28.     long end = len - 1;
    
29.     int count = 0;
    
30.     while (start < end) {
    
31.         if(color[start] != 'R'){
    
32.             start++;
    
33.         }else if (color[end] != 'B') {
    
34.             end--;
    
35.         }else if(color[start] == 'R' && color[end] == 'B'){
    
36.             char ch;
    
37.             ch = color[start];
    
38.             color[start] = color[end];
    
39.             color[end] = ch;
    
40.             count++;
    
41.         }
    
42.     }
    
43.     for (int i = 0; i < len ; i++) {
    
44.         if(color[i] == 'R'){
    
45.             end = i;
    
46.             break;
    
47.         }
    
48.     }
    
49.     start = 0;
    
50.     while (start < end) {
    
51.         if(color[start] != 'W'){
    
52.             start++;
    
53.         }else if(color[end] != 'B'){
    
54.             end--;
    
55.         }else if(color[start] == 'W' && color[end] == 'B'){
    
56.             char ch;
    
57.             ch = color[start];
    
58.             color[start] = color[end];
    
59.             color[end] = ch;
    
60.             count++;
    
61.         }
    
62.     }
    
63.     for (int i = 0 ; i < len ; i++) {
    
64.         if(color[i] == 'B')
    
65.             start = i;
    
66.     }
    
67.     end = len - 1;
    
68.     while (start < end) {
    
69.         if(color[start] != 'R'){
    
70.             start++;
    
71.         }else if(color[end] != 'W'){
    
72.             end--;
    
73.         }else if(color[start] == 'R' && color[end] == 'W'){
    
74.             char ch;
    
75.             ch = color[start];
    
76.             color[start] = color[end];
    
77.             color[end] = ch;
    
78.             count++;
    
79.         }
    
80.     }
    
81.     printf("%s\n",color);
    
82.     printf("%d\n",count);
    
83.    
    
84. }
    

复制代码

这是啥……

厉害

wjk930726 发表于 2016-7-13 00:06
这是啥……

三色旗的一个代码实现,没有写什么注释

wangxiaopang 发表于 2016-7-13 00:09
三色旗的一个代码实现,没有写什么注释

根本看不懂……（本条值一个黑马币）

wjk930726 发表于 2016-7-13 00:13
根本看不懂……（本条值一个黑马币）

66666

不想长大 发表于 2016-7-13 00:20
66666

朋友，那这串代码里面用到ASCII码了，但是这样的意义是什么呢

太长的代码，厉害

强啊！ 瞻仰大神！