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

greensky_34

原帖由 s5unty 于 2006-11-13 22:43 发表


不行阿，我理解后用c实现，结果不正确，可能是我理解有问题？

1. 
   
2. #include <iostream>
   
3. 
   
4. using namespace std;
   
5. 
   
6. void change(int* a, int* b) {
   
7.     int t = *b;
   
8.     *a = t;
   
9.     *b = * ...

复制代码

完整的程序是这样的，可以参考一下

1. 
   
2. #include <stdio.h>
   
3. #include <math.h>
   
4. 
   
5. #define N 10
   
6. 
   
7. void ary_init(int a[], int b[]){ //初始化数组
   
8.     int i;
   
9.     for (i=0; i<N; i++){
   
10.         a[i] = rand()%100;
    
11.     }
    
12.     for (i=0; i<N; i++){
    
13.         b[i] = rand()%100;
    
14.     }
    
15.     return;
    
16. }
    
17. long sum(int a[]){ //数组求和
    
18.     int i;
    
19.     int s;
    
20.     for (s=0,i=0; i<N; i++){
    
21.         s += a[i];
    
22.     }
    
23.     return s;
    
24. }
    
25. 
    
26. void change(int *a, int *b){ //数组元素交换
    
27.     int tmp;
    
28.     tmp = *a;
    
29.     *a = *b;
    
30.     *b = tmp;
    
31.     return;
    
32. }
    
33. 
    
34. void prt_ary(int a[], int b[]){ //列印两数组元素及各自元素和
    
35.     int i;
    
36.     for(i=0; i<N; i++){
    
37.         printf("%5d   ", a[i]);
    
38.     }
    
39.     printf("\n");
    
40.     for(i=0; i<N; i++){
    
41.         printf("%5d   ", b[i]);
    
42.     }
    
43.     printf("\n");
    
44.     printf("%d\n", sum(a));
    
45.     printf("%d\n", sum(b));
    
46. }
    
47. 
    
48. int main(){
    
49.     int i;
    
50.     int j;
    
51.     int a[N];
    
52.     int b[N];
    
53.     int a_sum;
    
54.     int b_sum;
    
55.     int tmp;
    
56.     int ab_diff;
    
57. 
    
58.     ary_init(a,b);//初始化
    
59.     prt_ary(a, b);//列印当前数组状态
    
60.     ab_diff = abs(sum(a)-sum(b));
    
61.     for (i=0; i<N; i++){//交换数组元素
    
62.         for (j=0; j<N; j++){
    
63.             change(a+i, b+j);
    
64.             if (abs(sum(a)-sum(b)) > ab_diff){
    
65.                 change(b+j, a+i);
    
66.             }
    
67.             else{
    
68.                 ab_diff = abs(sum(a)-sum(b));
    
69.             }
    
70.         }
    
71.     }
    
72.     prt_ary(a, b);//列印交换后数组状态
    
73.     getch();
    
74. }
    

复制代码

[ 本帖最后由 greensky_34 于 2006-11-14 00:30 编辑 ]

小帅哥飞飞

比如说总共加起来为数组：1，2，3，4，5，6

如果算6-5，4-3，2-1（12楼的算法），然后求和结果最小差是3

但我可以这样分组（1，6）一组，（2，5）一组，4，3分到两个组，结果最小差才是1

jinjianlee

首先可以用穷举的方式来实现该方法
在此基础上再优化算法（即排除没有必要的计算），最后必然可以得到想要的结果

pinyin

原帖由 mill888 于 2006-11-13 17:29 发表
8分钟就能写出正确方法的人，建议就不要去华为了，应当去更好的公司。
招聘中，建议华为公司应当定好自己的位。

共鸣

天山峰右

可以用背包算法

轮流取数、按差值取数都不能保证正确性

比如对于原始数组：
a[]={1,2,3}
b[]={4,10,20}

或者：
a[]={1,29,30}
b[]={50,90,100}

banboy

首先看图片信息-------这个题不一定就能交叉，你们能确定交叉就对吗，不对的，这也是我刚开始错误的思路，哈哈
我很就没写程序了，我是个做网页的，现在也不知道用哪种语言表达了，希望写程序比较好的朋友，把程序写出来把，就一个函数，我认为就能解决这个问题，

你们的程序中只要不区分当N为奇数还是偶数的情况，你们的算法就是错误的，我可以这么肯定的说，

你们只需要看N的判断，就可以知道这个算法的正确还是错误，

我个人认为，写程序，未必一定要用，英语来表达，
这样会达不到让看的人明白的效果的，  

呵呵，一个没编过程的人，不知道说的对不对，但是我看过LINUX 内核和STL，自认为比别人懂模式。



我确定这个绝对正确，我用了10分钟


然后，将a,b数组合并，成一个数组C，

排序C，
然后将C中的数组

这个时候要看N为奇数还是偶数了 ，分析如图

这样就应该可以了把，



例如；

C数组；123456
那么A，B将取如下图

[ 本帖最后由 banboy 于 2006-11-14 10:10 编辑 ]

billzhou

这样一定不行

windy2335

小弟想到一个算法，，大家给点意见
   定义一个c[2N]数组，将A数组和B数组里面的元素都放到C数组中，然后对C数组小到大排序，排好后在取数，在定义一个的D[N]数组，将C的第一个加上C的第2N个放到D[0]中，C的第二个加上C的第2N-1个放到D[1]中。。。。放好后，再将D数组从小到大排序，在又按照上面的方法，第一个加上最后一个放到另一个数组的第一个中，第2个加到数第二个放到另一个数组的第2个中。。。以这中思路一直排下去，最后得到一个两个元素的数组，那这数组中的两个元素的差应该就是最小的了。。。
这个数组中的两个元素中的每一个都是由N个数加起来的，所以在一开始放数的时候要对这些数进行记录。。。得到后便可以将这2N个数分配给A数组和B数组了.....
     这种方法应该是可行的。。。。高手指点下....

huntrsky

greensky 的算法很不错啊~~~大家看看可否再优化！？

pywj777

QUOTE:
原帖由 zhhui2000 于 2006-11-13 07:54 发表
先各自排序,再交叉存放较大无素
这个基本可行，但不是交叉存放较大元素，而是哪边的和小就一直放大元素，直到n，然后把剩下的扔到另一组中就ok了。

同意，但不应该是哪边小就一直放大元素，直到n， 应该是直到这个组元素的和大于另一组元素和时，再将下一元素放到令一组，若两组之和相等时，将下一元素放到元素最多的那个组，然后以同样的方法继续剩下元素的放置，直到有一个组为n，然后把剩下的放到另一个组。