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

虑而后能得

最好写出代码

runforu

我觉得代码不重要，所以就直接把算法写了。

blackuhlan

int proc( int []a, int []b, int cnt) {         int changed;         int mis = sum(a,cnt)-(b,cnt);         while(1)         {                 changed=0;                 for( int i=0; i< cnt; i++)                 {                         for( int j=0; j<cnt;j++)                         {                                 if( ( mis>0 && a[ i] > b[j] ) ||                                     ( mis < 0 && a[ i] < b[j] ) )                                 {                                         mis -=a[ i]-b[j];                                         change(a[ i], b[j]):                                         changed=1;                                         break;                                 }                         }                         if( changed == 1 || mis == 0 )break;                 }                 if( ( i== cnt && j == cnt ) || mis == 0 ) break;         }         return 0; } void change( int &a, int &b) {         int c;         c=*a;         *a=*b;         *b=c; } int sum( int []a, int cnt) {         int num=0;         for( int i=0; i< cnt; i++)         {                 num+=a[ i];         }         return num; }

应该是在8分钟之内写出来的，所以，没有编译，没有测试

[ 本帖最后由 blackuhlan 于 2008-7-14 22:18 编辑 ]

blackuhlan

靠，发出来a 怎么变成a，后面的全变斜体了？

silverzi

回复244楼：

原帖由 blackuhlan 于 2008-7-14 22:12 发表
int proc( int []a, int []b, int cnt)
{
        int changed;
        int mis = sum(a,cnt)-(b,cnt);
        while(1)
        {
                changed=0;
                for( int i=0; i< cnt ...

之前楼层太多，估计看不来，所以就不看了。还是就近讨论吧。

上面的算法很明显不是a,b并集两分后和差最小的充分条件。
因为两分后集合的组合情况有

C(2n,n) = (2n)! / (2(n!)) = n * (2n-1) * (2n-2) * ... * (n+2) * (n+1)

种，而该算法最多只检查了n种情况，可谓相去甚远啊。:wink:

----------------

8分钟的话，题没有规定算法效率，我觉得可以先穷举C(2n,n)种组合实现功能 ，然后再优化。

[ 本帖最后由 silverzi 于 2008-7-16 14:07 编辑 ]

runforu

我以前的算法是错误的，楼上的求组合的算法是目前唯一正确的。

w_cannon

#include <stdio.h>
#include <math.h>
#include <time.h>

#define NUM 100

void ary_init(int a[], int b[])
{ //初始化数组
    int i;
        srand(time(NULL));
    for (i=0; i<NUM; i++)
        {
        a = rand()%10000;
    }
    for (i=0; i<NUM; i++)
        {
        b = rand()%100;
    }
    return;
}
long sum(int a[])
{ //数组求和
    int i;
    int s;
    for (s=0,i=0; i<NUM; i++)
        {
        s += a;
    }
    return s;
}

int                swap_times;
int                sum_a, sum_b;

void change(int *a, int *b)
{ //数组元素交换
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
        swap_times++;
    return;
}

void prt_ary(int a[], int b[])
{ //列印两数组元素及各自元素和
    int i;
    for(i=0; i<NUM; i++)
        {
        printf("%5d   ", a);
    }
    printf("\n";
    for(i=0; i<NUM; i++)
        {
        printf("%5d   ", b);
    }
    printf("\n";
    printf("diff=%d sum_a=%d sum_b=%d all=%d\n", abs(sum_a-sum_b), sum_a, sum_b, sum_a+sum_b);
}


void slove(int a[], int b[])
{
    int i;
    int j;
    int ab_diff, sum_aa, sum_bb, diff;

        for(;
        {
CONT:
                ab_diff = abs(sum_a-sum_b);
                for (i=0; i<NUM; i++)
                {
                        for (j=0; j<NUM; j++)
                        {
                                diff= a-b[j];
                                sum_aa= sum_a-diff;
                                sum_bb= sum_b+diff;
                                diff= sum_aa-sum_bb;
                                if (abs(diff) < ab_diff)
                                {//判断是否需要交换元素
                                        change(a+i, b+j);
                                        sum_a= sum_aa;
                                        sum_b= sum_bb;
                                        if(diff==0)
                                                return;
                                        goto CONT;
                                }
                        }
                }
                break;
        }
}


int main()
{

    int a[NUM];
    int b[NUM];
        time_t        stime, etime;

    ary_init(a,b);//数组元素初始化
        sum_a= sum(a);
        sum_b= sum(b);
    prt_ary(a, b);//列印当前数组状态
        stime= time(NULL);
    slove(a, b);//处理数组
        etime= time(NULL);
    prt_ary(a, b);//列印交换后数组状态
        printf("\n";
        printf("swap_times=%d, spend_time=%d secs\n", swap_times, etime-stime);

    getch();
}


在前面兄弟(对不起,忘了是哪位兄弟了)的代码基础上进行了尽量优化,效率提高了很多.算法从逻辑上很容易理解,如果经过NxN次的扫描没有找到更小的差值,那结果应该是没有问题的.

[ 本帖最后由 w_cannon 于 2008-7-16 14:48 编辑 ]

runforu

错的。 你试试9 8 7 5 4 1这个序列放入两个数组，成功了再试试9 8 7 5 4 3

silverzi

想了一段时间，以我目前的水平，优化搞不定，放弃了。

PS：
题目要求的是最小值，而不是近似最小值，能起到最大效果的随机划分之类的算法都满足不了要求。
如果是华为的话，我感觉这算法相关的应用应该只要求近似值就行了吧，穷举是完全没有应用价值的，估计拿来测试都不行，太慢了。

[ 本帖最后由 silverzi 于 2008-7-16 15:40 编辑 ]

runforu

楼上的代码提醒了我，我一直钻牛角尖，想找个快捷的算法。以下代码是我经过验证的。

void EqualizeArray(int * A, int * B, int count)
{
    int sum_A = 0;
    for (int m = 0; m < count; m++)
        sum_A += A[m];  
   
    int sum_B = 0;
    for (int n = 0; n < count; n++)
        sum_B += B[n];     

    int diff_AB = sum_A - sum_B;

    for ( int i = 0; diff_AB && i < count; i++)
    {
        for ( int j = 0; diff_AB && j < count; j++)
        {
            int diff = A - B[j];
            if(  abs( diff_AB - 2 * diff ) < abs( diff_AB ) )
            {   
                int tmp = A;
                A = B[j];
                B[j] = tmp;
                diff_AB -= 2 * diff;
            }
        }
    }
}

[ 本帖最后由 runforu 于 2008-7-16 15:39 编辑 ]