【C语言算法连载4】三色旗
本帖最后由 iooops 于 2016-4-6 04:18 编辑【老掉牙系列之四】如果作为一个程序猿，你连这些都还不会，你就等着被https://mc.dfrobot.com.cn/static/image/smiley/chacha/07.gif叭！
【说明】
三色旗的问题最早由E.W.Dijkstra所提出，他所使用的用语为Dutch Nation Flag(Dijkstra为荷兰
人)，而多数的作者则使用Three-Color Flag来称之。
假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您
希望将之分类，并排列为红、白、蓝的顺序，要如何移动次数才会最少，注意您只能在绳子上
进行这个动作，而且一次只能调换两个旗子。
其实这是一个快速排序的算法。
好吧不理解题意的筒子打开下面这个链接：
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
然后到
Three Colours版块
https://mc.dfrobot.com.cn/forum.php?mod=image&aid=25610&size=300x300&key=44d4b993b63023d6&nocache=yes&type=fixnone
点go
然后就会出一个随机数，排好序啦。
觉得脑洞够大的筒子可以不看下面自行解决了。
好吧然后……
解决思路其实已经在链接里面被说明得很清楚了……
先来想办法把色列排成这样：
a zeroes (red)
a ones (white)
a unknown
a twos (blue)
然后再进行下面一步：
Lo := 1; Mid := 1; Hi := N;
while Mid <= Hi do
Invariant: a=0 and a=1 and a=2; a are unknown.
case a in
0: swap a and a; Lo++; Mid++
1: Mid++
2: swap a and a; Hi--
--- Dutch National Flag Algorithm, or 3-way Partitioning ---
至于配套的图嘛，看链接里的图好啦。
楼主反正是看完图才终于理解了该算法的精髓的。
有兴趣的筒子可以把上述0、1、2排序的结果用C语言实现一下。对于大神理应是轻而易举。对于楼主小白要去好好在墙角思索一下敲出代码来https://mc.dfrobot.com.cn/static/image/smiley/chacha/00k.jpg。
那么三色旗的C语言实现代码如下（假设排列为BWR哈，至于排列为RWB，筒子们可以稍微改动一下哈）：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SWAP_FLAGS(x, y) { char temp; \
temp = flags; \
flags = flags; \
flags = temp; }
void printFlags(char* flags) {
int i;
for(i = 0; i < strlen(flags); i++) {
printf("%c ", flags);
}
printf("\n");
}
void adjust(char* flags) {
int w = 0;
int b = 0;
int r = strlen(flags) - 1;
while(flags == 'B' && w < strlen(flags)) { b++; w++; }
while(flags == 'R' && r > 0) { r--; }
while(w <= r) switch(flags) {
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);
while(a == 0 && y < n) {
x++;
y++;
printf("x %d y %d z %d\n", x, y, z);
} //如果最左边是0的话，把0保留在最左边
while(a == 2 && z > 0) {
z--;
printf("x %d y %d z %d\n", x, y, z);
} //如果最右边是2的话，把2保留在最右边。
//至此第一步完成，减少第二步的工作量，提高算法效率
while(y <= z) {
switch(a) { //第二步开始，按照上面的思想
case 0:
a = a + a - (a = a);
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 = a + a - (a = a);
z--;
printf("x %d y %d z %d\n", x, y, z);
}
} //至此第二步完成
int i;
for(i = 0; i < 6; i++) {
printf("%d ", a);
}
}
int main() {
int numbers = {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);
}
return 0;
}
好吧虽然楼主觉得对于数字而言，会有比这更高效的排序算法的。
啊终于可以去睡觉啦！！！！！https://mc.dfrobot.com.cn/static/image/smiley/chacha/69.gif
参考：
http://www.openhome.cc/Gossip/AlgorithmGossip/ThreeColorsFlags.htm
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
沙发
页:
[1]