用遞歸法(尾遞歸)求最多元素,即找出出現次數大于n/2的元素
基于原理:去掉兩個不同的元素,剩下數組里的最多元素仍然是整個數組的最多元素(如果存在的話)
1 #include <stdio.h>
2 int majority(int [], int,int );
3
4 int main()
5 {
6 int i = 0;
7 int c = 0;
8 int data [] = {3,5,5,2,2,2,2};
9 int maj = majority(data,1 ,7);
10 for( ; i < 7; i++)
11 {
12 if(maj == data[i])
13 c++;
14 }
15 printf("The majority num of this array is: %d\n", c>3?maj:-1);
16 return 0;
17 }
18 /*s for the begining index, and e for the ending index
19 * * find the cadidate num of majority*/
20 int majority(int data[], int s, int e)//begin s = 1, e = n(including)
21 {
22 int c = 1;// count the candidate majority num
23 int j; //fot the index move on
24 int i = 0;
25 for( j = s; j< e; j++)
26 {
27 if( data[s-1] == data[j])
28 c++;
29 else
30 {
31 if(--c==0)
32 break;
33 }
34 }
35 if(c>0)
36 return data[s-1];
37 else
38 majority(data, j+1, e);
39
40 }
posted on 2008-03-29 23:03
fullfocus 閱讀(542)
評論(1) 編輯 收藏 所屬分類:
算法