计算众数和重数

编程基础 • 2024-12-13 17:30 • 阅读 9

计算众数和重数
给定含有n个素的多重集合S，每个素在S中出现的次数称为该素的重数。多重集S中重数最大的素称为众数。例如，S={1,2,2,2,3,5}。多重集S的众数是2，其重数为3。对于给定的n个自然数组成的多重集S，计算S的众数及其重数。

问题分析：
1、分治法
分治法解题过程主要分为分、治、合三个步骤“，应用该方法的基本过程如下：
（1）将原问题分解为若干个规模较小的子问题
（2）对这些子问题分别求解
（3）对各个子问题的解进行合并

3、根据以下实例理解分治法求解众数及其重数
给定含有n个素的多重集合S，每个素在S中出现的次数称为该素的重数。多重集S中重数最大的素称为众数。
例如，S = {1,2,2,2,3,5}。
多重集S的众数是2，其重数是3.

#include<iostream> #include<algorithm> using namespace std; int n1=0; //定义全局变量用来定义众数 int n2=0; //用来定义重数 int count(int a[],int first,int last){ 
   //firsrt为数组第一个素 last表示数组a的最后一个素 int n = a[(first+last)/2]; int count = 0; for(int i = first; i < last; i++) if( a[i] == n) cout++; return count; } int start(int a[],int first,int last){ 
    int x = 0; for( int i = first; i < last; i++){ 
    if(a[i] = a[(first+last)/2]); x = i; break; } return x; } void mode(int a[] ,int first,int last){ 
    int tnum = (first + last)/2; //tnum 中间轴 int tsum=count(a,first,last); int left=start(a,first,last); if(tsum>n2){ 
    n2=tsum; n1=a[tnum]; } if(q-(left+tsum)>n2) /如果右边素的个数大于重数sum,向右寻找 mode(a,left+tsum,e); if(left>n2) mode(a,first,left); }

今天的文章计算众数和重数分享到此就结束了，感谢您的阅读。

计算众数和重数

相关推荐