0001 #include <cstdio> 0002 #include <cstring> 0003 #include <cstdlib> 0004 #include <ctime> 0005 #include "_share/util.h" 0006 #include "UniPrint/print.h" 0007 #include "vector/vector.h" 0008 #include "majority.h" 0009 #include "majorityCandidate.h" 0010 #include "majorityCheck.h" 0011 0012 /****************************************************************************************** 0013 * 众数算法测试 0014 ******************************************************************************************/ 0015 int main ( int argc, char* argv[] ) { 0016 if ( 2 > argc ) { printf ( "Usage: %s <n>\a\a\n", argv[0] ); return 1; } 0017 Rank n = atoi ( argv[1] ); 0018 if ( n < 1 ) { printf ( "Invalid arguments\a\a\n" ); return 1; } 0019 srand ( ( unsigned int ) time ( NULL ) ); 0020 // 随机生成向量 0021 Vector<int> A; //以整型为例 0022 int maj = rand() % n; printf ( "%d is highly possible to be a majority\n", maj ); //随机确定一个maj候选 0023 while ( A.size() < n ) { //继续不断插入n,直至共有n个元素 0024 int ele = ( rand() % 100 < 50 ) ? maj : rand() % n; //49%的概率确定是maj,51%随机(可实验不同概率的效果) 0025 A.insert ( A.size(), ele ); 0026 } 0027 print ( A ); //均匀随机置乱 0028 // 计算众数 0029 majority ( A, maj ) ? 0030 printf ( "Majority element found as %d\n", maj ) : 0031 printf ( "Majority element NOT found\n" ); 0032 // 通过排序进一步验证 0033 A.sort(); print ( A ); 0034 // 返回 0035 return 0; 0036 }