小球荷兰国旗问题

荷兰vps  时间:2020-12-31  阅读:()

1 .问题描述

我们将乱序的红白蓝三色小球排列成有序的红白蓝三色的同颜色在一起的小球组。这个问题之所以叫荷兰国旗 是因为我们可以将红白蓝三色小球想象成条状物有序排列后正好组成荷兰国旗。

2.问题分析

这个问题我们可以将这个问题视为一个数组排序问题 这个数组分为前部 中部和后部三个部分每一个元素红白蓝分别对应0、 1 、 2必属于其中之一。 由于红、 白、蓝三色小球数量并不一定相同 所以这个三个区域不一定是等分的也就是说如果我们将整个区域放在[0, 1]的区域里 由于三色小球之间数量的比不同此处假设1 :2:2 可能前部为[0,0.2) 中部为[02,0 6)  后部为[06, 1] 。 我们的思路如下将前部和后部各排在数组的前边和后边 中部自然就排好了。具体的

设置两个标志位begin和end分别指向这个数组的开始和末尾 然后用一个标志位current从头开始进行遍历

1 若遍历到的位置为0 则说明它一定属于前部 于是就和begin位置进行交换然后current向前进 begin也向前进表示前边的已经都排好了 。

2若遍历到的位置为1  则说明它一定属于中部 根据总思路 中部的我们都不动然后current向前进。

3若遍历到的位置为2 则说明它一定属于后部 于是就和end位置进行交换 由于交换完毕后current指向的可能是属于前部的 若此时current前进则会导致该位置不能被交换到前部所以此时current不前进。而同1   end向后退1 。

//author:何佳

#include<iostream>usingnamespacestd;voidSwap(int*n1, int*n2) {inttemp;temp=*n1 ;

*n1=*n2;

*n2=temp;

}voidPrint(int*num, intlen)

{for(inti=0; i<len;++i)

{cout<<num[i]<<"";

}cout<<endl;

}

//0, 1,2, 1, 1,2,0,2, 1,0,2, 1,0,2,0, 1,2,0voidWork(int*num, intbegin, intend)

{intcur=begin;whi le(num[cur]==0)

{begin++;cur=begin;

}whi le(num[cur] !=2)

{cur++;

}while(cur!=end)

{if(num[cur]==2)

{

Swap(&num[cur] ,&num[end]) ;end--;

}if(num[cur] !=num[begin]&&num[cur] !=2) {Swap(&num[begin] ,&num[cur]) ;begin++;

}while(num[cur]==num[begin])

{cur++;

}

}if(num[end] !=2)

{

Swap(&num[cur] ,&num[begin]) ;

}

}intmain()

{intnum[]={0, 1,2, 1, 1,2,0,2, 1,0,2,0, 1,2,0, 1,2,0, 1, 1, 1,2, 1,2, 1, 1} ; int len=sizeof(num)/sizeof(int) ;

Print(num, len) ;

Work(num,0, len-1) ;

Print(num, len) ;

}

/*左飞C++数据结构与经典问题求解*/

/*荷兰国旗问题*/

/*众所周知荷兰国旗由红色、 白色和蓝色3中颜色组成现在假设有很多这3中颜色的线被存放在一个数字里 要求每次操作仅能进行一次交换 待对数字进行一遍扫描后 3中颜色自然分开颜色顺序应为红、 白、蓝。 另外 要求在O(n)的复杂度下使移动次数最小。

*/

#include<iostream>usingnamespacestd;constintN=15;intflag[N];intpre[N];intspl it1;intspl it2;intblue_red;intwhite_red;intcounts=0;

//输出结果voidPrint()

{for(inti=0;i<N;++i)

{cout<<flag[ i] ;

}cout<<endl;

}voidSwap(int&x, int&y)

{inttemp=x;x=y;y=temp;counts++;

}voidWork()

{for(inti=0;i<spl it1;++i)

{if(flag[i] !=0)

{if(blue_red>=spl it2)

{

Swap(flag[ i] ,flag[blue_red] ) ;blue_red=pre[blue_red];}else

{

Swap(flag[ i] ,flag[white_red] );white_red=pre[white_red];}

}

}intb=N-1;for(inti=spl it1;i<spl it2;++i)

{if(flag[i] !=1)

{whi le(flag[b]==2)b--;

Swap(flag[ i] ,flag[b]) ;b--;

}

}

}

//初始化voidInit( )

{intred_num=0;intwhite_num=0;intpreI=-1;for(inti=0;i<N;++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~spl it1-1(红),spl ite1~spl it2-1(白)  spl it2~N-1(蓝)spl it1=red_num;spl it2=red_num+white_num;blue_red=preI;inti=spl it2-1;whi le(flag[i] !=0) i--;//检查白色中有没有红色white_red=i;

}intmain()

{

Init();cout<<"原始 "<<endl ;

Print( ) ;

Work();cout<<"移动 "<<counts<<"次"<<endl;Print( ) ;return0;

}

wordpress外贸企业主题 wordpress高级全行业大气外贸主题

wordpress高级全行业大气外贸主题,wordpress通用全行业高级外贸企业在线询单自适应主题建站程序,完善的外贸企业建站功能模块 + 高效通用的后台自定义设置,更实用的移动设备特色功能模块 + 更适于欧美国外用户操作体验 大气简洁的网站风格设计 + 高效优化的网站程序结构,更利于Goolge等SEO搜索优化和站点收录排名。点击进入:wordpress高级全行业大气外贸主题主题价格:¥398...

2021年国内/国外便宜VPS主机/云服务器商家推荐整理

2021年各大云服务商竞争尤为激烈,因为云服务商家的竞争我们可以选择更加便宜的VPS或云服务器,这样成本更低,选择空间更大。但是,如果我们是建站用途或者是稳定项目的,不要太过于追求便宜VPS或便宜云服务器,更需要追求稳定和服务。不同的商家有不同的特点,而且任何商家和线路不可能一直稳定,我们需要做的就是定期观察和数据定期备份。下面,请跟云服务器网(yuntue.com)小编来看一下2021年国内/国...

腾讯云2核4GB内存8M带宽 年74元

一般大厂都是通过首年才有可以享受爆款活动,然后吸引我们注册他们商家达到持续续费和购买的目的。一般只有大厂才能有这样的魄力和能力首年亏本,但是对于一般的公司和个人厂家确实难过,这几年确实看到不少的同类商家难以生存。这里我们可以看到有对应的套餐方案。不过这两个套餐都是100%CPU独享的,不是有某云商家限制CPU的。但是轻量服务器有个不好的就是带宽是较大且流量是限制的额,分别是1GB和1.2TB月流量...

荷兰vps为你推荐
域名主机域名与主机的对应关系在哪里可以看到?台湾vps香港vps和台湾vps哪个好用海外域名求国外域名商列表云服务器租用云服务器租用需要注意哪些方面云服务器租用云服务器租用费用是多少独立ip虚拟主机独立ip的虚拟主机和vps的区别和优势??韩国虚拟主机韩国虚拟主机好还是香港的好山东虚拟主机山东东营制作网站的公司在哪里?asp虚拟主机怎样查看虚拟主机是支持ASP还是PHP程序的域名解析什么是域名解析?它有什么作用?
过期域名查询 php空间租用 网站域名备案 花生壳域名贝锐 东莞电信局 阿里云邮箱登陆首页 zpanel oneasiahost vmsnap3 账号泄露 天猫双十一抢红包 青果网 河南移动邮件系统 秒杀汇 美国堪萨斯 metalink 万网空间购买 789电视剧 香港亚马逊 域名dns 更多