查看: 6370|回复: 1

【C语言算法连载4】三色旗

本帖最后由 iooops 于 2016-4-6 04:18 编辑

【老掉牙系列之四】如果作为一个程序猿，你连这些都还不会，你就等着被

叭！

【说明】
三色旗的问题最早由E.W.Dijkstra所提出，他所使用的用语为Dutch Nation Flag(Dijkstra为荷兰
人)，而多数的作者则使用Three-Color Flag来称之。
假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您
希望将之分类，并排列为红、白、蓝的顺序，要如何移动次数才会最少，注意您只能在绳子上
进行这个动作，而且一次只能调换两个旗子。

其实这是一个快速排序的算法。

好吧不理解题意的筒子打开下面这个链接：
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

然后到
Three Colours版块

点go
然后就会出一个随机数，排好序啦。

觉得脑洞够大的筒子可以不看下面自行解决了。

好吧然后……

解决思路其实已经在链接里面被说明得很清楚了……

先来想办法把色列排成这样：

a[1..Lo-1] zeroes (red)
a[Lo..Mid-] ones (white)
a[Mid..Hi] unknown
a[Hi+1..N] twos (blue)

然后再进行下面一步：

      Lo := 1; Mid := 1; Hi := N;
      while Mid <= Hi do
         Invariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and a[Hi+1..N]=2; a[Mid..Hi] are unknown.
         case a[Mid] in
            0: swap a[Lo] and a[Mid]; Lo++; Mid++
            1: Mid++
            2: swap a[Mid] and a[Hi]; Hi--

--- Dutch National Flag Algorithm, or 3-way Partitioning ---

至于配套的图嘛，看链接里的图好啦。
楼主反正是看完图才终于理解了该算法的精髓的。

有兴趣的筒子可以把上述0、1、2排序的结果用C语言实现一下。对于大神理应是轻而易举。对于楼主小白要去好好在墙角思索一下敲出代码来

。

那么三色旗的C语言实现代码如下（假设排列为BWR哈，至于排列为RWB，筒子们可以稍微改动一下哈）：

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

#define SWAP_FLAGS(x, y) { char temp; \
                     temp = flags[x]; \
                     flags[x] = flags[y]; \
                     flags[y] = temp; }

void printFlags(char* flags) {
    int i; 
    for(i = 0; i < strlen(flags); i++) {
        printf("%c ", flags[i]); 
    }
    printf("\n");     
}

void adjust(char* flags) {
    int w = 0;
    int b = 0;
    int r = strlen(flags) - 1;
    while(flags[w] == 'B' && w < strlen(flags)) { b++; w++; }
    while(flags[r] == 'R' && r > 0) { r--; }
    while(w <= r) switch(flags[w]) {
        case 'W':
               w++;
               break;
        case 'B':
               SWAP_FLAGS(b, w);
               b++; w++;
               break;
        case 'R':
               SWAP_FLAGS(r, w);
               r--;
    }
}

int main() {
    char flags[] = {'R', 'W', 'B', 'W', 'W', 
                    'B', 'R', 'B', 'W', 'R', '\0'}; 

    printFlags(flags);
    adjust(flags);
    printFlags(flags);

    return 0; 
} 

复制代码

输出结果如下：

R W B W W B R B W R
B B B W W W W R R R

好吧容我做一下代码的搬运工 - -
论数学的重要性 = =

刚刚提到排序0、1、2
楼主小白花了大概4个小时终于把上面的0、1、2能排出来了…………虽然还是参考了很多上述的代码，啊感觉还是要多多思索深入理解一下啊。

#include <stdio.h>
#include <stdlib.h>

void adjust(int *a, int n) {
        int x = 0;
        int y = 0;
        int z = n - 1;
        printf("x %d y %d z %d\n", x, y, z);
        printf("%d\n", a[x]);
        while(a[y] == 0 && y < n) {
                x++;
                y++;
                printf("x %d y %d z %d\n", x, y, z);
        }                                                                        //如果最左边是0的话，把0保留在最左边
        while(a[z] == 2 && z > 0) {
                z--;
                printf("x %d y %d z %d\n", x, y, z);
        }                                                                        //如果最右边是2的话，把2保留在最右边。
                                                                                //至此第一步完成，减少第二步的工作量，提高算法效率
        while(y <= z) {
                switch(a[y]) {                //第二步开始，按照上面的思想
                        case 0:
                                a[y] = a[y] + a[x] - (a[x] = a[y]);   
                                x++;
                                y++;
                                break;
                                printf("x %d y %d z %d\n", x, y, z);
                        case 1:
                                y++;
                                break;
                                printf("x %d y %d z %d\n", x, y, z);
                        case 2:
                                a[y] = a[y] + a[z] - (a[z] = a[y]); 
                                z--;
                                printf("x %d y %d z %d\n", x, y, z);
                }
        }                                                                        //至此第二步完成
        int i;
        for(i = 0; i < 6; i++) {
                printf("%d ", a[i]);
        }
}

int main() {
        int numbers[6] = {0, 2, 1, 0, 2, 1};        //我这里懒得生成随机数了 - -
        int i;

        adjust(numbers, 6);

        printf("\nsorted numbers are \n");
        for(i = 0; i < 6; i++) {
                printf("%d ", numbers[i]);
        }

        return 0;
}
复制代码