華為面試題(8分鐘寫出代碼)

mmx_craft

以下思路如何， 先把a(bǔ),b合成一個(gè)2n的數(shù)組C, 然后按照如下規(guī)則選取。
  1. a[0] = c [2n-1], b[0] = c[2n-2]
  2. 按照suma>sumb, 取剩下的最大的給b，最小的給a； 反之最大的給a，最小的給b。

程序如下：

#include <stdio.h>
#include <stdlib.h>

static int
intcompare(const void *p1, const void *p2)
{
    int i = *((int *)p1);
    int j = *((int *)p2);

    if (i > j)
        return (1);
    if (i < j)
        return (-1);
    return (0);
}

int change(int *a, int *b, int size)
{
    int *c = (int*) malloc(2*size);
    int pos_a,pos_b,pos_c,pos_cend;
    int sum_a,sum_b;
    int i;

    memcpy(c, a, sizeof(int)*size);
    memcpy(c+size, b, sizeof(int)*size);
   
    qsort((void *)c, 2*size, sizeof (int), intcompare);

    pos_a=pos_b=pos_c=0;
    pos_cend = 2*size-1;
    a[pos_a++] = c[pos_cend--];
    b[pos_b++] = c[pos_cend--];
    sum_a = a[0];
    sum_b = b[0];
   
    while (pos_cend > pos_c ) {
        if (sum_a > sum_b) {
            a[pos_a++] = c[pos_c++];
            b[pos_b++] = c[pos_cend--];
            sum_a += a[pos_a-1];
            sum_b += b[pos_b-1];
        } else {
            a[pos_a++] = c[pos_cend--];
            b[pos_b++] = c[pos_c++];
            sum_a += a[pos_a-1];
            sum_b += b[pos_b-1];
        }
    }
}

int main (int argc, char **argv)
{
    int a[6]= {1, 2, 3,4,5,6};
    int b[6]= {7, 8, 9,10,11,12};
    int i;
   
    change(a,b,6);


    printf("a=");
    for(i=0; i <6; i++)
        printf("%d,",a[i]);
    printf("\n");
    printf("b=");
    for(i=0; i< 6; i++)
        printf("%d,", b[i]);
    printf("\n");
}

xmyth

當(dāng)前數(shù)組a和數(shù)組b的和之差為
A = sum(a) - sum(b)

a的第i個(gè)元素和b的第j個(gè)元素交換后，a和b的和之差為
A' = sum(a) - a[i] + b[j] - （sum(b) - b[j] + a[i])
       = sum(a) - sum(b) - 2 (a[i] - b[j])
       = A - 2 (a[i] - b[j])
設(shè)x = a[i] - b[j]

|A| - |A'| = |A| - |A-2x|

假設(shè)A > 0,

當(dāng)x 在 (0,A)之間時(shí)，做這樣的交換才能使得交換后的a和b的和之差變小，x越接近A/2效果越好,

如果找不到在(0,A)之間的x，則當(dāng)前的a和b就是答案。

所以算法大概如下：

在a和b中尋找使得x在(0,A)之間并且最接近A/2的i和j，交換相應(yīng)的i和j元素，重新計(jì)算A后，重復(fù)前面的步驟直至找不到(0,A)之間的x為止。

[[i] 本帖最后由 xmyth 于 2006-11-14 20:45 編輯 [/i]]

flw2

xmyth 快四年一貼啊.

你說(shuō)的我看懂了

cuicp

原帖由 xmyth 于 2006-11-14 17:04 發(fā)表
當(dāng)前數(shù)組a和數(shù)組b的和之差為
A = sum(a) - sum(b)

a的第i個(gè)元素和b的第j個(gè)元素交換后，a和b的和之差為
A' = sum(a) - a + b[j] - （sum(b) - b[j] + a)
       = sum(a) - sum(b) - 2 (a - b[j]) ...

想法很好呀，又有數(shù)學(xué)證明，但是什么時(shí)候會(huì)
找不到（0,A）之間的x呢？
比如：
1，2，3，4，5，12
最佳方案好像是：
4，5，3
1，2，12

那么0<（3－2）<(15-12)

好像不行呀？
是不是要改進(jìn)一下結(jié)束的條件？
我考慮的對(duì)不對(duì)？
高手看看！
謝謝��！

xmyth

這個(gè)結(jié)束條件應(yīng)該是沒有問題的

在你說(shuō)的這個(gè)例子里，已經(jīng)滿足了我所提出的結(jié)束條件

前面我假設(shè)了A>0 (如果A不大于0，對(duì)換一下就好了)

所以這里a = {1,2,12}; b = {4,5,3};

x=a[i]-b[j]

所有的x應(yīng)該都不能滿足（0, 3)的條件了，所以滿足結(jié)束條件了。

exir

真的只有八分鐘嗎？字都打不完啊。

flw2

原帖由 xmyth 于 2006-11-14 20:44 發(fā)表
這個(gè)結(jié)束條件應(yīng)該是沒有問題的

在你說(shuō)的這個(gè)例子里，已經(jīng)滿足了我所提出的結(jié)束條件

前面我假設(shè)了A>0 (如果A不大于0，對(duì)換一下就好了)

所以這里a = {1,2,12}; b = {4,5,3};

x=a-b[j]

所有的x ...

我一眼就感覺你那公式很可能是對(duì)的
這種類似的題很多的
比如100個(gè)紅包，7個(gè)人分，怎么分才最均勻，是不是更頭疼？

flw2

greensky_34

用二重循環(huán)把a(bǔ)中的每個(gè)元素和b中的每個(gè)元素逐個(gè)“嘗試交換”，
如果是差值變小就維持交換，否則就交換回去，也就是不交換，
每有一次交換，“嘗試交換”的二重循環(huán)就重新從頭開始，
直到?jīng)]有任何交換使差值變小為止。
這種方法不是很簡(jiǎn)潔，但的確是可行的。
前邊貼出代碼的算法，有過一次交換后，循環(huán)沒有從頭開始，所以是錯(cuò)誤的。例如a[1]和b[j]交換后，b中的元素改變了，不能再保證a[0]和b[ i ]交換不會(huì)使差值變小，這時(shí)循環(huán)必須從頭開始。

1. 
   
2. #include <stdio.h>
   
3. #include <math.h>
   
4. 
   
5. #define N 10
   
6. 
   
7. void ary_init(int a[], int b[]){ //初始化數(shù)組
   
8.     int i;
   
9.     for (i=0; i<N; i++){
   
10.         a[i] = rand()%10000;
    
11.     }
    
12.     for (i=0; i<N; i++){
    
13.         b[i] = rand()%100;
    
14.     }
    
15.     return;
    
16. }
    
17. long sum(int a[]){ //數(shù)組求和
    
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){ //數(shù)組元素交換
    
27.     int tmp;
    
28.     tmp = *a;
    
29.     *a = *b;
    
30.     *b = tmp;
    
31.     return;
    
32. }
    
33. 
    
34. void prt_ary(int a[], int b[]){ //列印兩數(shù)組元素及各自元素和
    
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. int slove(int a[], int b[]){
    
48.     int i;
    
49.     int j;
    
50.     int is_swap = 0;//是否修交換過數(shù)據(jù)標(biāo)志
    
51.     int ab_diff;
    
52. 
    
53.     ab_diff = abs(sum(a)-sum(b));
    
54.     for (i=0; i<N; i++){
    
55.         for (j=0; j<N; j++){
    
56.             change(a+i, b+j);
    
57.             if (abs(sum(a)-sum(b)) < ab_diff){//判斷是否需要交換元素
    
58.                 is_swap = 1; //置位交換標(biāo)志
    
59.                 ab_diff = abs(sum(a)-sum(b)); //更新差值
    
60.             }
    
61.             else{
    
62.                 change(b+j, a+i);//不交換
    
63. 
    
64.             }
    
65.         }
    
66.     }
    
67.     return is_swap;
    
68. }
    
69. int main(){
    
70. 
    
71.     int a[N];
    
72.     int b[N];
    
73. 
    
74.     ary_init(a,b);//數(shù)組元素初始化
    
75.     prt_ary(a, b);//列印當(dāng)前數(shù)組狀態(tài)
    
76.     while (slove(a, b));//處理數(shù)組
    
77.     prt_ary(a, b);//列印交換后數(shù)組狀態(tài)
    
78.     getch();
    
79. }
    

復(fù)制代碼

[ 本帖最后由 greensky_34 于 2006-11-14 21:20 編輯 ]

cuicp

原帖由 xmyth 于 2006-11-14 20:44 發(fā)表
這個(gè)結(jié)束條件應(yīng)該是沒有問題的

在你說(shuō)的這個(gè)例子里，已經(jīng)滿足了我所提出的結(jié)束條件

前面我假設(shè)了A>0 (如果A不大于0，對(duì)換一下就好了)

所以這里a = {1,2,12}; b = {4,5,3};

x=a-b[j]

所有的x ...

哦，明白了，如果(sum(a) - sum(b)) > (a -b[j]) > 0的話，也就是數(shù)組a的和比數(shù)組b的和大，
而數(shù)組b中有比數(shù)組a中小的元素，如果把a(bǔ)和b[j]交換，就可以把數(shù)組a和數(shù)組b的差縮小，又因?yàn)?br /> (sum(a) - sum(b)) > (a -b[j]) ，所以交換后不會(huì)出現(xiàn)sum(a) < sum(b)的情況。這樣循環(huán)調(diào)整后，
當(dāng)整體上sum(a)  > sum(b))時(shí)，局部上（數(shù)組元素）無(wú)法交換了，也就是無(wú)法找到符合條件的x了。

呵呵，本人天生比較笨，要想一想才能明白！

謝謝xmyth的解釋！