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

虑而后能得

#include<stdio.h>
#include<stdlib.h>
int cmp ( const void *a , const void *b );
int main(void)
{
        int a[5] = {9,2,5,71,6};
        int b[5] = {9,3,5,8,1};
        int c[10];
        int i,s=1,suma = 0,sumb = 0; //s为sumb=sumb次数标志位；

        for(i = 0;i < 5;i++)
                c = a;
        for(i = 5;i < 10;i++)
                c = b[i - 5];
        qsort(c,10,sizeof(int),cmp);
       
        a[0] = c [9];
        b[0] = c[8];
        i=1;
        while(i<5)
        {
                suma += a[i-1];
                sumb += b[i-1];       
               
                if(suma < sumb)
                {
                        a = c[9-i-s];
                        b = c[i-1];
                }
                else if(suma > sumb)
                {
                        a = c[i-1];
                        b = c[9-i-s];
                }
                else
                {
                        a = c[9-i-s];
                        b = c[9-i-s-1];
                        s += 1;
                }
       
                i++;

        }

        for(i = 0;i < 5;i++)
                printf("%3d",a);
        printf("\n");
        for(i = 0;i < 5;i++)
                printf("%3d",b);
        printf("\n");

        return 0;
       
}


int cmp ( const void *a , const void *b )
{
        return *(int *)a - *(int *)b;

}

[ 本帖最后由 虑而后能得 于 2008-7-7 19:14 编辑 ]

kumbayaco

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

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

这种方法也不行，有可能出现替换多个数据的情况。

kumbayaco

原帖由 虑而后能得 于 2008-7-7 11:26 发表
思想：
a b合并为c【】
c[]排序，取最大的放入a，次大放入b，然后剩下的最大放入b，最小放入a，比较a当前和与b当前和，c中剩下的最大放入和小的，最小放入和大的，。。。。。直到分配完
程序：
#include
# ...

这个ms结果是正确的~~

runforu

1， 合并数组A，B，将AB放入数组C， 清空A、B。
2， x ＝max{Ci, i = 0,1,2....}， 数组D ＝ A， Ci 放入B。       //初始化循化
3， x ＝min{(x-Ci) 的绝对值, i=0,1,2,3....}， cc ＝Ci， cc 放入D，
4， C = C-{cc}
5， 如果D ＝＝ A， 则D＝B 否则D＝A,  
6， 如果C不为空，go to 3.
7， 得出AB

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

gaochang2008

大家为什么要进行排序呢。？  求的是和的差值最小，，排序有什么意义马。？

gaochang2008

原帖由 kumbayaco 于 2008-7-7 16:05 发表



这个ms结果是正确的~~

对的，

runforu

我用动态规划使得每次的差都最小。最终保证全部的差最小。233楼的好像是错的。

runforu

1， 合并数组A，B，将AB放入数组C， 清空A、B。
2， x ＝max{Ci, i = 0,1,2....}， 数组D ＝ A， Ci 放入B。       //初始化循化
3， x ＝min{(x-Ci) 的绝对值, i=0,1,2,3....}， cc ＝Ci， cc 放入D，
4， C = C-{cc}
5， 如果D ＝＝ A， 则D＝B 否则D＝A,  
6， 如果C不为空，go to 3.
7， 得出AB

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

虑而后能得

我的算法好像确实是不对的，在两种情况下完全正确，数组中数据全为正或全为负，其他情况下不能保证正确。
需改正，是看数组的首尾两个数的绝对值大大小
即|c[0]|,|c[n]|; 当|c[0]|>|c[n]|时需要改变策略：如下

（1）  c中最小的数送个a，次小送给b，
（2）  然后比较a与b的当前和，把c中剩下最大的送给a，最小的送给b，比较当前和，剩下的最大送个和较小的，最小的送给和较大的，和相等时（特殊事件）执行（1），直至分配完。

反之方法如上例

呵呵 代码没写。只需改变数组c的排序方式就可以了，主程序不用改动。

[ 本帖最后由 虑而后能得 于 2008-7-8 09:19 编辑 ]

虑而后能得

最好写出代码