一道c语言题目 求大神指点下算法? 20

你有r颗红球,g颗绿球,b颗蓝球,它们排成一个直线,你想按红绿蓝顺序分成三个颜色区域,每次可以任意交换两个球的位置请问至少需要交换多少次... 你有r颗红球,g颗绿球,b颗蓝球,它们排成一个直线,你想按红绿蓝顺序分成三个颜色区域,每次可以任意交换两个球的位置 请问至少需要交换多少次 展开
 我来答
自我编程
2019-11-28 · 科技优质答主
自我编程
采纳数:1481 获赞数:4283

向TA提问 私信TA
展开全部

根据题意,随机生成红绿蓝球任意个数,并任意顺序排列。这里采用随机数实现。

统计按红绿蓝顺序排列最少交换次数,我的思路是:

第一步:循环将最后一个红色球与最靠前的其它两色球(并且满足位置在红球之前)交换。

第二步:循环将最后一个绿球与最靠前的蓝球(必须在绿球之前)交换。

#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");

}

百度网友3b5a5d8
2019-11-28 · TA获得超过1229个赞
知道大有可为答主
回答量:1279
采纳率:83%
帮助的人:125万
展开全部
你好,
按我的理解,可以将红球看做1,绿球看做2,篮球看做3.
排序最快的应该是快排。
祝你生活愉快。
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
猪猪365shine
2019-11-28 · TA获得超过321个赞
知道小有建树答主
回答量:352
采纳率:62%
帮助的人:85.8万
展开全部
能把原题复制过来不,你语言描述得不清晰
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
收起 1条折叠回答
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式