重庆分公司,新征程启航

为企业提供网站建设、域名注册、服务器等服务

荷兰国旗问题-创新互联

荷兰国旗问题

十年的江汉网站建设经验,针对设计、前端、开发、售后、文案、推广等六对一服务,响应快,48小时及时工作处理。网络营销推广的优势是能够根据用户设备显示端的尺寸不同,自动调整江汉建站的显示方式,使网站能够适用不同显示终端,在浏览器中调整网站的宽度,无论在任何一种浏览器上浏览网站,都能展现优雅布局与设计,从而大程度地提升浏览体验。创新互联公司从事“江汉网站设计”,“江汉网站推广”以来,每个客户项目都认真落实执行。

   上方的图片便是一个荷兰国旗,从图中我们可以很清楚的看出它的特点,它有三个区域组成,即红,白,蓝。

好,现在我们的问题出来了。现在我们面前有一张桌子,桌子上整齐的摆放着红色,白色,蓝色三种线条,但他们的顺序是凌乱的。

要求是:用一个算法把这些线条挑出来重新摆放顺序,最后的结果就像上图的荷兰国旗,红色在上,白色在中间,蓝色在最下面。

另外,要求在O(n)的复杂度下,使移动次数最少。

算法分析如下:

    荷兰国旗问题其实是一个排序问题。可以将红,白,蓝3种颜色分别用数字0、1和2表示,并使用一个数组来存储它们。将相同颜色

的线条归为一类就相当于将数组中的数组按大小进行排序,只不过数组里存储的数值只有3种而已。其解题的基本策略是遍历两个颜色区域,

如果颜色条不属于所在区域,则交换一个属于该区域的颜色条。这样,每一次都是必要的交换,从而实现最少交换次数。

代码如下:

#include
using namespace std;
const int N=10;
int flag[N]; //国旗颜色条数组
int pre[N];  //记录该白条的前白条位置
int split1;  //区域分割1
int split2;  //区域分割2
int blue_red; //红条在蓝色区域的标记
int white_red; //红条在白色区域的标记
int counts = 0;

void out()
{
 for (int i=0;i {
  cout< }
 cout<}

void swap(int& x,int& y)
{
 int temp=x;
 x=y;
 y=temp;

 counts++;
}

void work()
{
 for (int i=0;i {
  if (flag[i]!=0)    //如果不属于该区域
  {
   if(blue_red>=split2)
   {
     swap(flag[i],flag[blue_red]);
     blue_red = pre[blue_red];
   }
   else{
    swap(flag[i],flag[white_red]);
    white_red = pre[white_red];
   }
  }
 }
 int b=N-1; //白、蓝区域
 for ( i=split1;i {
  if (flag[i] != 1)
  {
   while (flag[b]==2) b--;
   swap(flag[i],flag[b]);
   b--;
  }
 }
}

//初始化
void init()
{
 int red_num = 0; //统计红色条数
 int white_num = 0; //统计白色条数
 int preI = -1;
 for (int i=0;i {
  flag[i] = rand()%3;
  if (flag[i]==0)
  {
   red_num++;
   pre[i] = preI;
   preI=i;
  }
  else
   if (flag[i]==1)
   {
    white_num++;
   }
 }

 //将国旗分成3个颜色区域:
 //0~split-1(红),split1~split2-1(白),split2~N-1(蓝)
 split1=red_num;
 split2=red_num+white_num;
 blue_red=preI;
 i=split2-1;
 while (flag[i] !=0) i--;
 white_red = i;
}

int main()
{
 init();
 cout<<"原始:"< out();

 work();
 cout<<"移动"< out();

 return 0;

}


新闻标题:荷兰国旗问题-创新互联
链接URL:http://cqcxhl.com/article/dsgjpj.html

其他资讯

在线咨询
服务热线
服务热线:028-86922220
TOP