main.cpp

首先输入数字序列的数目,然后输入这个数字序列,程序会找出此数字序列的多数元素(即超过二分之一的数量).

/*
基本算法思想：
    首先接受字符串，从第一个字符开始进行统计。
	用index1指示当前元素，用index2指示下一个要搜索的元素，用no统计
	字符的个数，当下一个元素与前一个元素相同时no加一，index2指向下
	一个元素，当下一个元素与前一个元素不相同时，no减一，index2指向
	下一个元素，如果no等于0时，将index1指向index2的下一个元素，并进
	入递归程序(在原序列中去掉两个不同的元素后，那么原多数元素在新序
	列中还是多数元素)。
	如果index1小于或等于字符数，则返回index1所指示的数，否则返回-1。
	在主程序中还应有验证程序，统计返回的字符在原字符串中占的个数。
	如果多余半数，则输出此元素，否则没有多数元素。
*/
#include <iostream.h>
int count;
int numbers[20]; //存储输入数
int candidate(int m);
void main()
{
	int nums;
	cout << "请输入序列的数目：" ;
	cin >> nums;
	count = nums;
	cout << "请输入序列中的" << nums << "个元素" << endl;
	for(int i=0; i<nums; i++)
		cin >> numbers[i];
	int mm = candidate(0);
	int no = 0;//多数元素计数器
/************************验证程序*************************/
	for(i=0; i<nums; i++) 
	{
		if(numbers[i] == mm)
			no++;
	}
	if(no > count/2)
		cout << "多数元素是：" << mm << endl;
	else
		cout << "没有多数元素！" << endl;
	cout << count;
}

int candidate(int m)
{
	int index1 = m;//当前元素
	int index2 = m+1;//下一个要搜索的元素
	int no = 1;
	while(index2 < count)//搜索边界
	{
		if(numbers[index1] != numbers[index2])//不等于
		{
			no--;
			if(no == 0)
			{
				index1 = index2 + 1;
				return candidate(index1);//去掉成对的元素
			}
		    else
			{
			    index2++;
			}
		}
		else//等于
		{
			no++;
			index2++;
		}
	}
	if(index1 <= count)
		return numbers[index1];
	else
		return -1;
}