一道c语言题目 求大神指点下算法? 20
根据题意,随机生成红绿蓝球任意个数,并任意顺序排列。这里采用随机数实现。
统计按红绿蓝顺序排列最少交换次数,我的思路是:
第一步:循环将最后一个红色球与最靠前的其它两色球(并且满足位置在红球之前)交换。
第二步:循环将最后一个绿球与最靠前的蓝球(必须在绿球之前)交换。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MR 5//每种颜色的球随机生成的最大数量
void showList(int qs[],int len);
int jh(int qs[],int len);//返回交换次数
int main()
{
int i,len,qs[MR*3],n;
int r,g,b;//红绿蓝数量
srand(time(NULL));
r=rand()%MR+1;//1~MR的随机数
g=rand()%MR+1;
b=rand()%MR+1;
len=r+g+b;
printf("随机生成红球%d个,绿球%d个,篮球%d个\n",r,g,b);
printf("开始随机排列。。。。。。\n");
for(i=0;i<len;i++)
{
n=rand()%3+1;//位置采取抽签,生成1~3的随机数,1表示红,2表示绿,3表示蓝
switch(n)
{
case 1:
if(r>0) qs[i]=n,r--;
else i--;
break;
case 2:
if(g>0) qs[i]=n,g--;
else i--;
break;
case 3:
if(b>0) qs[i]=n,b--;
else i--;
break;
}
}
printf("随机排列后的队列情况为:\n");
showList(qs,len);
printf("\n");
jh(qs,len);
return 0;
}
int jh(int qs[],int len)//返回交换次数
{
int cnt=0;
int jhbl(int qs[],int len,int lq,int bq);
//最后的红和最前的绿或蓝(且绿球或篮球位置在红球之前)交换
cnt+=jhbl(qs,len,1,0);
//最前的篮球和最后的绿球交换
cnt+=jhbl(qs,len,2,3);
printf("总交换次数至少%d:\n",cnt);
return cnt;
}
int jhbl(int qs[],int len,int lq,int bq)//lq:交换中最靠后的球色编号(1~3),bq:交换中最靠前的球色编号(1~3),bq=0:lq与其他两种颜色任意交换
{
int i,j,qSave,cnt=0;
for(i=len-1;i>=0;i--)
{
if(qs[i]==lq)
{
for(j=0;j<len;j++)
if(((bq==0 && qs[j]!=lq)||(bq!=0 && qs[j]==bq)) && j<i)
{
printf("第%d个%s%s%s与第%d个%s%s%s交换,交换后(交换%d次):\n",i+1,lq==1?"红球":"",lq==2?"绿球":"",lq==3?"蓝球":"",j+1,qs[j]==1?"红球":"",qs[j]==2?"绿球":"",qs[j]==3?"蓝球":"",cnt+1);
qSave=qs[j],qs[j]=qs[i];qs[i]=qSave,cnt++;
showList(qs,len);
printf("\n");
i=len-1;
break;
}
}
}
return cnt;
}
void showList(int qs[],int len)
{
int i;
for(i=0;i<len;i++)
printf("%s%s%s ",qs[i]==1?"红":"",qs[i]==2?"绿":"",qs[i]==3?"蓝":"");
printf("\n");
}
广告 您可能关注的内容 |