C语言三色旗问题
有一根绳子,上面有红、白、蓝三种颜色的旗子。绳子上旗子的颜色并没有顺序,现在要对旗子进行分类,按照蓝色、白色、红色的顺序排列。只能在绳子上进行移动,并且一次只能调换两面旗子,怎样移动才能使旗子移动的次数最少?
若 w 指针指向的当前旗子为白色,则 w 指针增加 1,表示白旗部分增加一面。若 w 指针指向的当前旗子为蓝色,则将 b 指针与 w 指针所指向的旗子交换,同时 b 指针与 w 指针都增加 1,表示蓝旗和白旗部分都多了一个元素。若 w 指针指向的当前旗子为红色,则将 w 指针与 r 指针所指向的旗子交换,同时 r 指针减 1,即 r 指针向前移动,未处理的部分减 1。刚开始时,r 指向绳子中最后一个旗子,之后 r 指针不断前移,当其位于 w 指针之前,即 r 的值小于 w 的值时,全部旗子处理完毕,可以结束比较和移动旗子操作。
在程序中通过宏定义用大写字母 'B' 'W' 'R' 分别代表蓝色、白色和红色;字符数组 “char color[]”表示绳子上的各种颜色的旗子;旗子移动时通过一个 while 循环判断移动过程是否结束,在 while 循环中根据旗子的不同颜色进行不同的处理。
算法思想
旗子在绳子上移动,而且一次只能调换两面旗子,因此只要保证在移动旗子时,从绳子的开头开始,遇到蓝色旗子向前移动,遇到白色旗子则留在中间,而遇到红色的旗子则向后移动。要使移动次数最少,可以使用三个指针 b、w、r 分别作为蓝旗、白旗和红旗的指针。若 w 指针指向的当前旗子为白色,则 w 指针增加 1,表示白旗部分增加一面。若 w 指针指向的当前旗子为蓝色,则将 b 指针与 w 指针所指向的旗子交换,同时 b 指针与 w 指针都增加 1,表示蓝旗和白旗部分都多了一个元素。若 w 指针指向的当前旗子为红色,则将 w 指针与 r 指针所指向的旗子交换,同时 r 指针减 1,即 r 指针向前移动,未处理的部分减 1。刚开始时,r 指向绳子中最后一个旗子,之后 r 指针不断前移,当其位于 w 指针之前,即 r 的值小于 w 的值时,全部旗子处理完毕,可以结束比较和移动旗子操作。
在程序中通过宏定义用大写字母 'B' 'W' 'R' 分别代表蓝色、白色和红色;字符数组 “char color[]”表示绳子上的各种颜色的旗子;旗子移动时通过一个 while 循环判断移动过程是否结束,在 while 循环中根据旗子的不同颜色进行不同的处理。
程序代码
#include <stdio.h> #include <stdlib.h> #include <string.h> #define BLUE 'B' #define WHITE 'W' #define RED 'R' #define swap(x,y){char temp;\ temp=color[x];\ color[x]=color[y];\ color[y]=temp;} int main() { char color[]={'R','W','B','W','W','B','R','B','W','R','\0'}; int w=0; int b=0; int r=strlen(color)-1; int i; for(i=0;i<strlen(color);i++) printf("%c ",color[i]); printf("\n"); while(w<=r) { if(color[w]==WHITE) w++; else { if(color[w]==BLUE) { swap(b,w); b++; w++; } else { while(w<r&&color[r]==RED) r--; swap(r,w); r--; } } } for(i=0;i<strlen(color);i++) printf("%c ",color[i]); printf("\n"); return 0; }
调试运行结果
交换前旗子颜色排列顺序及按顺序最少次数移动旗子后的排列顺序如下所示:
R W B W W B R B W R
B B B W W W W R R R
总结
在该实例中,分别用语句“int w=0;”“int b = 0;”“int r=strlen(color)-1;”定义并初始化白旗、蓝旗、红旗的指针 w、b、r。在交换不同颜色旗子时,通过旗子的指针实现交换函数 swap 的功能。所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频