华为面试题(8分钟写出代码)

wuxiaoqiang118

9楼效率应该更好

rockyr

1. 将两个数组合并，排序，求和后得到平均值ave；
排序后数组：c1<=c2<=c3...
2. 交叉排放排序后的数组至两个数组a，b：
a:c1,c3,c5...
b:c2,c4,c6...
3. 数组a求和得到aSum, 求取与均值之差(由a的生成过程可知aSum<=ave)：
diff = ave－aSum；
4. 由a(0)开始与b数组相比较，找出差值最接近于diff的元素:
Min (diff-(b[n]-a[m])); #n>=m
交换b[n], a[m].

得解。

[ 本帖最后由 rockyr 于 2007-12-10 17:13 编辑 ]

UCfree

嘿嘿   你以为就那么简单？
a  142 3 2 -12
b  31  4 2 1
这是最优解？？

那你看看最优的吧
a  142 2 1 -12
b  31  4 3 2

UCfree

你的算法结果一样错
最优的是
a 132 1  1  1
b 13  13 12 12

UCfree

我的程序没31楼那么好
但一样实现了算法

1. 
   
2. #include <stdio.h>
   
3. 
   
4. int main()
   
5. {
   
6.         int a[20], b[20];
   
7.         int n, i, t;
   
8. 
   
9.         /* load data */
   
10.         do
    
11.         {
    
12.                 printf("Set the size of array:");
    
13.                 scanf("%d", &n);
    
14.         }while (n < 1 || n > 20);
    
15. 
    
16.         printf("arry a:");
    
17.         for(i = 0;i < n; i++)
    
18.                 scanf("%d", a + i);
    
19.         printf("arry b:");
    
20.         for(i = 0;i < n; i++)
    
21.                 scanf("%d", b + i);
    
22. 
    
23.         /* sort array a,b and let sum(a) < sum(b) */
    
24.         sort(a, n);
    
25.         sort(b, n);
    
26.         if (sum(a, n) > sum(b, n))
    
27.         {       /* exchange a,b */
    
28.                 for(i = 0;i < n;i++)
    
29.                 {
    
30.                         t = a[i];
    
31.                         a[i] = b[i];
    
32.                         b[i] = t;
    
33.                 }
    
34.         }
    
35. 
    
36.         /* now sum(a) <= sum(b),if lower to make sum(a) near to sum(b) */
    
37.         if (sum(a, n) < sum(b, n))
    
38.                 make_near(0 , n, a ,b);
    
39. 
    
40.         /* output the result */
    
41.         sort(a, n);
    
42.         puts("\nsum a:");
    
43.         for (i = 0;i < n;i++)
    
44.                 if (i < n - 1)
    
45.                         printf("%d+", a[i]);
    
46.                 else
    
47.                         printf("%d = ", a[i]);
    
48.         printf("%d\n", sum(a, n));
    
49. 
    
50.         puts("sum b:");
    
51.         for (i = 0;i < n;i++)
    
52.                 if (i < n - 1)
    
53.                         printf("%d+", b[i]);
    
54.                 else
    
55.                         printf("%d = ", b[i]);
    
56.         printf("%d\n", sum(b, n));
    
57. 
    
58.         printf("value between a and b is:%d\n", sum(b, n) - sum(a, n));
    
59. 
    
60.         return 0;
    
61. }
    
62. 
    
63. /* sort the array: small to big */
    
64. void sort(int *arr, int n)
    
65. {
    
66.         int i, j;
    
67. 
    
68.         for (i = n - 1;i > 0;i--)
    
69.                 for(j = 1;j <= i ;j++)
    
70.                 {
    
71.                         if (arr[j - 1] > arr[j])
    
72.                                 exchange_p(arr + (j - 1), arr + j);
    
73.                 }
    
74. }
    
75. 
    
76. int sum(int *arr, int n)
    
77. {
    
78.         if (n == 1)
    
79.                 return *arr;
    
80. 
    
81.         return *arr + sum(arr + 1, n - 1);
    
82. }
    
83. 
    
84. /* exchange tow pointer value */
    
85. void exchange_p(int *a, int *b)
    
86. {
    
87.         int t;
    
88. 
    
89.         t = *a - *b;
    
90.         *b += t;
    
91.         *a -= t;
    
92. }
    
93. 
    
94. /* exchange the elements of array a and b,
    
95.    to make sum(a) nearest to sum(b),
    
96.    and make sure sum(b) always greater than sum(a),
    
97.    if not,should exchange the elements back.
    
98.    the condition of return: sum(a) == sum(b) or m point to the end of a
    
99. */
    
100. void make_near(int m, int n, int *a, int *b)
     
101. {/* m point to the current element of a, n is the array's size */
     
102.         int i;
     
103. 
     
104.         for (i = n - 1;i >= 0;i--)
     
105.         {
     
106.                 if (a[m] < b[i])
     
107.                 {
     
108.                         exchange_p(a + m, b + i);
     
109.                         /* success to exchange and go to next step */
     
110.                         if (sum(a, n) < sum (b, n))
     
111.                                 break;
     
112.                         /* sum(a) == sum(b) ,return */
     
113.                         else if (sum(a, n) == sum(b ,n))
     
114.                                 return;
     
115.                         /* failure to exchange,exchange back */
     
116.                         else
     
117.                                 exchange_p(a + m, b + i);
     
118.                 }
     
119.                 else/* it's no need to process a[m] >= b[i],go to next step */
     
120.                         break;
     
121.         }
     
122.         sort(b ,n);
     
123. 
     
124.         /* m point to the end of a*/
     
125.         if (m == n)
     
126.                 return;
     
127. 
     
128.         /* m move to the next element */
     
129.         make_near(m + 1, n, a, b);
     
130. }
     
131. 
     

复制代码

[ 本帖最后由 UCfree 于 2007-12-13 17:00 编辑 ]

srdrm

很多人简单一想就回答, 排序, 交叉取数.
这样很多情况下并不能满足要求
其实这题其实没这么简单, 牵涉到一个叫"模拟退火"的算法.
具体我也不太清楚,算法搞不明白. 也懒得看啦.
不过算法有机会还是要系统学学的~

暗底

楼上的,你真狠,  处子贴就挖出来个尸体,  你不挖 我还真没看过这贴 .  从头看到尾,  觉得挺有意思,  也发现了一个问题, CU高手潜水严重!