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

cjaizss

哦，这不是典型的背包,典型的背包不是分为相同数量的两块，hoho

tianshanxue2005

不知道这样行不行，建立数组c[n][n]
c[j] = a[j] - b
两个数组的差值delt
将delt与c[j]比较，小于则更换

#include    <unistd.h> #include    <stdio.h> #include    <stdlib.h> #include    <time.h> #include    <math.h> #define    NUM  200 #define LIMIT 1000000 struct sign{     int    a;     int    b;     int    delt; }; int main(void){     srand(time(NULL));     int    a[NUM];     int    b[NUM];     int    c[NUM][NUM];     int    i, j;     int    delt = 0;     int    temp;     struct    sign s;     s.a=0; s.b=0; s.delt=0;     for(i=0; i<NUM; i++)     {         a[i] = (rand())%LIMIT;         b[i] = (rand())%LIMIT;         delt +=(a[i] - b[i]);         printf("a is %i; b is %i; delt is %i\n", a[i], b[i], delt);     }     for(i=0; i<NUM; i++)         for(j=0; j<NUM; j++)         {             c[i][j] = a[j] - b[i];         }     s.delt = delt;     if(delt == 0)         return 0;     for(i = 0; i<NUM; i++)     {         printf("%5.i", a[i]);     }     printf("\n");     for(i = 0; i<NUM; i++)     {         printf("%5.i", b[i]);     }     printf("\n");     while(1)     {         for(i=0; i<NUM; i++)             for(j=0; j<NUM; j++)             {                 temp = s.delt - 2*c[i][j];                 if( abs(temp) < abs(delt) && abs(temp)< abs(s.delt) )                 {    s.a = j;                     s.b = i;                     s.delt = temp;                 }             }         if(delt == s.delt)             break;         delt = s.delt;         printf("delt is %i\n", delt);         temp = a[s.a];         a[s.a] = b[s.b];         b[s.b] = temp;         if(delt == 0)             break;         for(i=0; i<NUM; i++)         {             c[i][s.a] = a[s.a] - b[i];             c[s.b][i] = a[i] - b[s.b];         }     }     int tempa=0, tempb=0;     for(i = 0; i<NUM; i++)     {         printf("%5.i", a[i]);         tempa += a[i];     }     printf("%10.i\n",tempa);     for(i = 0; i<NUM; i++)     {         printf("%5.i", b[i]);         tempb += b[i];     }     printf("%10.i\n", tempb);     printf("delt is %i", delt);     return 0; }

[ 本帖最后由 tianshanxue2005 于 2007-8-29 18:56 编辑 ]

NewCore

想到一个方法，因为是求和，其实无所谓负数还是正数，没有关系。

我的办法是：

两个数组和得差要最小，理想的情况就是sum(a)=sum(b)；而2N个数的和为total=sum(a)+sum(b)，求其算术平均为avg=total+1/2N。同理，avgab=total+1/2，这是a,b的各自和的理想值。其实，选取的策略就是使调整后的sum(a)=sum(b)=avgab。
采取这样地选取算法：
1）从2N-k个数中取出与avg的差的绝对值最小的整数，作为ak。其中,k为已经选出的a中的元素的个数。
2）重新计算avgab=avgab-ak，（total前面已经计算了，所以这里不用再算了，直接使用就可以了）。同时计算avg = avgab+1-a1/N-k，然后再重复1）。
3）直道选出N个数，选出的数作为a中元素，剩下的数即是数组b中的元素了。

很明显的是，理想情况下，这样选出来的sum(a)=sum(b)。在非理想情况下，这样选出来的也是满足条件的a和b。

[ 本帖最后由 NewCore 于 2007-8-30 00:24 编辑 ]

tom_xx_hu@yahoo

所有用了“排序”的都应该是错的。
求和只要开始时做一遍，以后随时订正。
遍历两个数组的元素，如果交换能降低两个数组和之差，就交换，同时订正数组和。
如此反复，直到任何这样两个不同数组的元素交换都只能增加或不改变数组和之差。

[ 本帖最后由 tom_xx_hu@yahoo 于 2007-8-30 02:14 编辑 ]

gldamao

首先整体排序，然后两个数组分别成对交替前后顺序的取数。不置可否。

jackyshi3333

我贴一个,当数目比较小的时候运行还比较快.
在VC中开发.

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include "Windows.h"

void quicksort(int *p, int from ,int to)
{
        int i,j,pivot,temp;

        if(from >= to)
        {
                return;
        }
        i = from + 1;
        j = to;
        pivot = *(p + from);
        while(i <= j)
        {
                while (*(p + i) <= pivot)
                {
                        i++;
                }
                while(*(p + j) > pivot)
                {
                        j--;
                }
                if(i < j)
                {
                        temp = *(p+i);
                        *(p+i) = *(p+j);
                        *(p+j) = temp;
                }
        }

        temp = *(p+j);
        *(p+j) = pivot;
        *(p+from)=temp;

        quicksort(p,from,j-1);
        quicksort(p,j+1,to);
}

//高位右移时，低位向左移动
void move_left_zero(int *p, int num)
{
        int i,j,n;
        if(num == 0)
        {
                return;
        }

        for(i = 0; i < num-1; i++)
        {
                if((*(p+i) == 0) &&(*(p+i+1) == 1))
                {
                        break;
                }
        }

        if( i == num-1)
        {               
        }
        else
        {
                for(j = 0; j < num-1-i; j++)
                {
                        *(p+j) = *(p+j+i+1);
                }

                for(n = 0; n < i+1; n++)
                {
                        *(p+j+n) = 0;
                }
        }

        return ;
}
int combine_incre(int *p, int num)
{
        int i;

        for(i = 0; i < num-1; i++)
        {
                if((*(p+i) == 1) && (*(p+i+1) == 0))
                {
                        *(p+i) = 0;
                        *(p+i+1) = 1;

                        move_left_zero(p,i);
                        break;
                }
        }

        if(i == num-1)
        {
                return false;
        }
        else
        {
                return true;
        }
}

void prepare_combine(int **p, int size, int num)
{
        int i;
        *p = (int*)malloc(size*sizeof(int));
        memset(*p,0,size*sizeof(int));

        for(i = 0; i < num ;i++)
        {
                *(*p + i) = 1;
        }
}

//size = 12;
//测试组合数运行，组合
int combine_test(int size,int num)
{
        int i;
        int count = 0;
        int *p;       

        prepare_combine(&p,size,num);
        count++;
        for(i = 0; i < size; i++)
        {
                printf("%d,",p);
        }
        printf("\r\n");

        while(combine_incre(p,size))
        {
                count++;
                for(i = 0; i < size; i++)
                {
                        printf("%d,",p);
                }
                printf("\r\n");
        }

        return 0;
}

int main(int argc, char* argv[])
{
        int i,size;
        int a[1000];
        long midsum;
        long minsum;
        long temp;
        int count = 0;
        int *p;
        int *result;

        size = 30;
        for(i = 0; i < size; i++)
        {
                a = rand();
                Sleep(100);
        }
        temp = minsum = midsum = 0;
        quicksort(a,0,size-1);
       
        for(i = 0; i < size-1; i++)
        {
                printf("%d,",a);
        }
        printf("\r\n");

        //combine_test(size,size/2);
       
        prepare_combine(&p,size,size/2);
        prepare_combine(&result,size,size/2);
        count++;
        for(i = 0; i < size; i++)
        {
                if(*(p+i) == 1)
                {
                        minsum += a;                       
                }

                midsum += a;
        }

        midsum /= 2;

        printf("the min sum is:%d; mid sum is:%d\r\n",minsum,midsum);

        while(combine_incre(p,size))
        {
                temp = 0;
                for(i = 0; i < size; i++)
                {
                        if(*(p+i) == 1)
                        {
                                temp += a;                       
                        }
                }

                if(temp == midsum)
                {
                        for(i = 0; i < size; i++)
                        {
                                result = p;
                        }
                        break;
                }
                else if(temp < midsum)
                {
                        if(temp > minsum)
                        {
                                minsum = temp;

                                for(i = 0; i < size; i++)
                                {
                                        result = p;
                                }                               
                        }
                }
        }

        printf("the sum is:%d:",minsum);
        for(i = 0; i < size; i++)
        {
                printf("%d,",result);
        }
        printf("\r\n");

        getchar();

        return 0;
}

omiga2

从头到尾看了一遍，赞同zwylinux，tom_xx_hu的方法。看了xmyth的推理让我想起了高中的数学，很有味道，十几年都没有感受了。

foolishx

原帖由 namtso 于 2006-11-13 17:16 发表
我相信，这个题在8分钟内能写出代码来的人，绝对是大大的牛人。

我觉得应该这样：
a和b 分别求出累加和，得出累加和的差c1，然后循环查找找a中的某个元素a，使得a与b中的某个元素b[j]交换之后，得出一个新的 ...

我也是这个想法。顶个

jackyshi3333

单一的元素交换很多时候不是最优的,
如果出现这种情况,有可能两个元素一起交换,导致两组数的差最小.
因此最优的情况,应该是从2n个数中取n个数,进行穷举.

tom_xx_hu@yahoo

原帖由 omiga2 于 2007-9-13 19:57 发表
从头到尾看了一遍，赞同zwylinux，tom_xx_hu的方法。看了xmyth的推理让我想起了高中的数学，很有味道，十几年都没有感受了。

不容易。4年3帖，一帖顶了在下（当然还有zwylinux），荣幸之至。
3帖得11分，按平均每帖得分衡量，在CU一定名列前茅。赞！