2.cpp

简单的事例程序

/*问题描述：给定含有n个元素的集合，设计一个递归算法在其中找出最大和次大元素*/

#include <iostream>
using namespace std;

//////////////////////////////////////////////////////////////////////////////////////////////////
int * input( int &n );                                      //输入函数
void operate( int i, int j, int *p, int &max, int &side );  //分治法找数组中最大值和次大值
                                                            //i,j为数组下标
//////////////////////////////////////////////////////////////////////////////////////////////////
void main( )                                                 //主函数
{
	int n, max, side, *anrry=NULL;                          //数组anrry的长度为n，最大值为max,
	                                                        //次大值为side	
	anrry = input( n );
	operate( 0, n-1, anrry, max, side );
	cout << "最大元素是：" << max << endl
		 << "次大元素是：" << side << endl;
	delete[n] anrry;
} 

//////////////////////////////////////////////////////////////////////////////////////////////////
int * input( int &n )                                       //输入函数
{
	int *p;
	cout << "请输入测试序列长度:";
	cin >> n;
    p = new int[n];
	cout << "请输入数据:";
	for( int i=0; i<n; i++)
		cin >> p[i];
	return p;
}

//////////////////////////////////////////////////////////////////////////////////////////////////
void operate( int i, int j, int *p, int &max, int &side )   //分治法找数组中最大值和次大值
{
	int k, maxl, maxr, sidel, sider;

	if( 1 < j-i )
	{		    
		k = ( i+j ) / 2;
		operate( i, k, p, maxl, sidel );                    //递归寻找左边的最大值和次大值
        operate( k+1, j, p, maxr, sider );                  //递归寻找右边的最大值和次大值
		
		if( maxl > maxr )                                   //最大值为左右两边最大值中较大的
		{                                                   //次大值为左右两边最大值中较小的与左右
			max = maxl;                                     //两边次大值中较大的比较得到
			side = ( maxr>sidel ) ? maxr : sidel;		
		}
		else
		{
			max = maxr;
			side = ( maxl>sider ) ? maxl : sider;
		}	
    }
	else                                                    //当数组被分解为只剩两个元素时
	{                                                       //最大值为两个元素中较大的	
		max = ( p[i]>=p[j] ) ? p[i]: p[j];                  //次大值为两个元素中较小的
		side = ( p[i]<p[j] ) ? p[i]: p[j];		
	}
}