博弈论，蓝桥云课，驯服灵兽

Question

https://www.lanqiao.cn/problems/5112/learning/?page=229
博弈论，请教教怎么写

Answer 1

【相关推荐】

• 你可以看下这个问题的回答https://ask.csdn.net/questions/7810935
• 这篇博客也不错, 你可以看下小根堆创建，插入，删除，排序等操作图解
• 除此之外, 这篇博客: 排序算法：简单选择排序，堆排序，直接插入排序，二分法插入排序，冒泡排序，快速排序，归并排序中的 归并排序 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

  我使用的是二路归并排序法

  归并主要通过分治法的思想，先对当前要排序的序列，通过递归调用二分法将要排序的序列划分成每一个要排序的区间都只有一个元素，整体形状像一棵二叉树。然后同一层级的相邻两区间进行合并，合并时需要对数值进行比较，将小的数据放置到要合并的区间的前面，不断回归合并最终合并成一个已经排序完整的区间。（归并法的代码是思考了最久才写成功的）

  具体代码如下：

  #include<iostream.h>
  //归并排序法
  //merge函数用来合并两个区间,需要传递排序的数组a，两个区间的最小下标，中间下标和最大下标
  void merge(int a[],int l,int mid,int r)
  {
  //先输出当前所要合并成的区间的左下标和右下标
  cout<<"l的值为："<<l<<"  "<<"r的值为："<<r<<endl;
  //采用临时变量numl，numr来记录左区间和右区间的元素个数
  int numl=mid-l+1;
  mid=mid+1;
  int numr=r-mid+1;
  //采用两个新的数组来存放，划分的左区间和右区间的元素
  int la[10];
  int ra[10];
  //采用indexl和indexr来作为新的数组的下标，同时用一个新的变量k来存放初始l的值
  //因为将原数组中的元素复制到新的数组的过程中，l的值会发生改变
  int indexl=0,indexr=0,k=l;
  cout<<"左区间：";
  //将划分的左区间的元素复制到新的数组la中，并输出当前区间的元素
  for(int i=0;i<numl;i++)
  {
  la[i]=a[l];
  cout<<la[i]<<" ";
  l++;
  }
  cout<<"右区间：";
  //将划分的右区间的元素复制到数组ra中，并输出当前区间的元素
  for(int j=0;j<numr;j++)
  {
  ra[j]=a[mid];
  cout<<ra[j]<<" ";
  mid++;
  }
  cout<<endl;
  //采用一个for循环，对要合并的区间进行数值比较，将较小的数据放在区间前面，总共有四种取值情况
  //需要注意的是因为定义的数组为la[10]和ra[10]，当排序数组较小时，会有多余的空间，其中默认值为0
  //所以要做不超过所存放数据个数的判断
  for(;k<=r;k++)
  {
  //情况一：右边区间的值大于等于左边区间的值，并且左边区间的下标没有超出所存放的数据元素个数
  //a[k]取值左区间元素
  if(ra[indexr]>=la[indexl]&&indexl<numl)
  {
  a[k]=la[indexl];
  indexl++;
  }
  //情况二：右边区间元素值大于等于左边区间的元素值，但是左边区间的数据已经取完
  //a[k]取值右边区间元素
  else if(ra[indexr]>=la[indexl]&&indexl>=numl)
  {
  a[k]=ra[indexr];
  indexr++;
  }
  //情况三：右边区间元素值小于左边区间的元素值，并且右边区间的所存放的数据还没有被取完
  //a[k]取值右边区间元素
  else if(ra[indexr]<la[indexl]&&indexr<numr)
  {
  a[k]=ra[indexr];
  indexr++;
  }
  //情况四：右边区间元素小于左边区间元素值，但是右边区间所存放的元素已经被取完了
  //a[k]取值左边区间的元素
  else if(ra[indexr]<la[indexl]&&indexr>=numr)
  {
  a[k]=la[indexl];
  indexl++;
  }
  }
  }
  //mergesort函数通过递归划分区间，每次从当前区间的中点划分，直到该区间只有一个数
  //同时划分完毕之后通过merge函数排序合并已经划分的区间
  void mergesort(int a[],int l,int r)
  {
  if(l>=r)
  return;
  else
  {
  int mid=(l+r)/2;
  mergesort(a,l,mid);
  mergesort(a,mid+1,r);
  merge(a,l,mid,r);
  }
  }
  //输出已经排序好的数组
  void out(int a[],int n)
  {
  	cout<<"排序后数组顺序为："<<" ";
  	for(int i=0;i<=n-1;i++)
  	{		
  		cout<<a[i]<<" ";
  	}
  		cout<<endl;
  }
  void main()
  {
  int a[10]={3,5,4,2,7,7,3,8,22,15};
    mergesort(a,0,9);
    out(a,9);
  }

  最后放上一张归并排序的截图吧！

  

  以上，祝好！

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^