《华为校园招聘面试笔试题 .pdf》由会员分享，可在线阅读，更多相关《华为校园招聘面试笔试题 .pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、传说这是一道华为的面试题。 。 。/* 文件名 : MinDifference(A VG).cpp 问题描述 : 有两个数组a、b，大小都为n，数组元素的值任意，无序；通过交换a,b 中的元素，使数组a元素的和与数组b 元素的和之间的差最小，最后输出两个数组和数组元素和的差值解决思路：采用动态规划思想。先求出一个规划目标的模糊值AVG ，表示“完美”的a与 b 的情况：a 的元素和sa与 b 的元素和sb 相等，并都等于 AVG 。 然后重置a 与 b：交换a 与 b 中的元素，另a 中存有最小的n 个元素（此时sa 必然大于AVG） 。b中存有最大的 n 个元素（此时sb 必然大于AVG）
2、；开始进行“完美逼近”规划：在一次ak与 b0.n-1 的循环中进行交换，使得此时的sa逼近 AVG（此时的sb 也在逼近AVG ） 。在此过程中，如果sa与 AVG 相等，这就产生了“完美”数组a 与 b，保证 sa与 sb 的差值为0。如果到an-1 时 sa与 AVG 不等， 不过此时的数组a和 b 已经能保证sa 与 sb 的差值最小了正确性证明： （用反证法易证之）时间复杂度分析：O(n2) 关键步骤： Step 0：合并数组a和 b 到数组 c，并对 c 按升序排序；Step 1：求出数组c 元素的和，除以2，其值为AVG ；Step 2：将数组c里前 n 个数设置为数组a，后 n
3、 个数设置为数组b，并分别求出a 元素与 b 元素的和，放入sa和 sb；Step 3：设置整型计数器i = 0；Step 4：ai与 bn-i-1 对换，并计算此时的sa与 sb；/（试探）Step 5：如果 sa 大于 AVG， ai与 bn-i-1 并重新算计sa与 sb；/（回溯）Step 6：否则（ sa小于 AVG 时）分别按升序排序a 和 b；Step 7：i+；Step 8：如果i n，执行 Step 4；Step 9：一次“逼近”过程结束；开发平台 : Win Xp SP2 编译环境 : CL.exe 8.0 (in Visual Studio 2005 SDK) 作者 :
4、88250 完成日期 : 2006-11-26 版本 : 2.0 修改之处： 1. 修正了算法设计思想的描述：将贪心+回溯改为动态规划2. 修正了存在重复比较数组a 和 b 元素的问题，大大提高了处理效率3. 可以从负值到正值地设定了数组元素的随机范围Blog: http:/DL E-mail: DL QQ: 845765 or 316281008 */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - i nclude i nc
5、lude i nclude / 使用快速排序i nclude i nclude #define TEST 0 / 测试开关using namespace std; / 全局数组描述：const int num_max = 100; / 最大数组容量const int range_min = -10; / 给定数组元素的最小值const int range_max = 10; / 给定数组元素的最大值vector a; / 数组 a vector b; / 数组 b vector c; / 数组 c int average = 0; / 即算法描述中的AVG int sa = 0, sb = 0
6、; / 分别保存数组a 和 b 元素的和int sum_difference = 0; / 存放数组a 和 b 的差值的绝对值/ 全局函数描述：/ 对数组 v 进行随机初始化void init(vector &v); / 显示数组v void display(const vector &v); / 对数组 v 的元素求和放到sum 里void sum(const vector &v, int &sum); / 合并数组v 到 c 中void merge(const vector &v, vector &c); / 设置数组a 的元素void set_a(void); / 设置数组b 的元素vo
7、id set_b(void); / 交换 a 与 b 的值void exchange(int &a, int &b); / 一次贪心的过程，产生符合条件的数组a 和 b / 返回这次贪心能产生的差值int kernel(int &k); / 输出当前的数组a和 b 与相应和及差值void outCurrent(void); / 主程序入口int main(int argc, char* argv) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - -
8、 - - - - / 设置随机种子srand(unsigned)time(NULL); init(a); init(b); sum(a, sa); sum(b, sb); outCurrent(); if (0 = sum_difference) / 就是最优解，不需要处理了，收工 :-p cout endl endl Okey! endl; outCurrent(); return 0; / Step 0 merge(a, c); merge(b, c); sort(c.begin(), c.end(); #if TEST / 测试合并结果cout c:; display(c); #endi
9、f vector cpy_a; vector cpy_b; int tmp_sum_diff = sum_difference, sum_difference = 0; cpy_a.assign(a.begin(), a.end(); cpy_b.assign(b.begin(), b.end(); / Step 1 average = (sa + sb) / 2; / Step 2 set_a(); sum(a, sa); set_b(); sum(b, sb); / 进行 AVG “逼近”for (int k = 0; k sum_difference) cpy_a.clear(); cp
10、y_b.clear(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - tmp_sum_diff = sum_difference; cpy_a.assign(a.begin(), a.end(); cpy_b.assign(b.begin(), b.end(); if (0 = tmp_sum_diff) / 找到“完美”解,直接结束过程k = num_max; if (tmp_sum_diff sum_difference
11、) a.clear(); b.clear(); a.assign(cpy_a.begin(), cpy_a.end(); b.assign(cpy_b.begin(), cpy_b.end(); sum(a, sa); sum(b, sb); sum_difference = tmp_sum_diff; / 最优结果输出cout endl endl Okey! endl; outCurrent(); cout The runtime of this program: (float)clock() / CLK_TCK s endl; return 0; int kernel(int &k) fo
12、r (int i = 0; i num_max; i+) #if TEST / 测试当前数组a和 b 的值及相应和的情况cout endl TEST: endl; outCurrent(); cout END TEST average) / Step 5(回溯 ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - exchange(ak, bnum_max-i-1); sum(a, sa); sum(b, sb); else if
13、 (sa average) / Step 6 sort(a.begin(), a.end(); sort(b.begin(), b.end(); break; else / 发现“完美”解break; return sum_difference = abs(sa - sb); void outCurrent(void) cout a:; display(a); cout b:; display(b); cout Sum a: sa endl; cout Sum b: sb endl; sum_difference = abs(sa - sb); cout The difference of a
14、sum and bsum: sum_difference endl; return; void init(vector &v) for (int i = 0; i num_max; i+) v.push_back(double)rand() / (double)RAND_MAX) * range_max + range_min); return; void display(const vector &v) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - -
15、 - - - - - - for (vector:const_iterator i = v.begin(); i != v.end(); i+) cout *i; cout endl; return; void sum(const vector &v, int &sum) sum = 0; for (vector:const_iterator i = v.begin(); i != v.end(); i+) sum += *i; return; void merge(const vector &v, vector &c) for (vector:const_iterator i = v.beg
16、in(); i != v.end(); i+) c.push_back(*i); return; void set_a(void) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - a.clear(); for (int i = 0; i num_max; i+) a.push_back(ci); return; void set_b(void) b.clear(); for (int i = num_max; i 2 * num_max; i+) b.push_back(ci); return; void exchange(int &a, int &b) int tmp = a; a = b; b = tmp; return; 本文来自CSDN博客，转载请标明出处：http:/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -