免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: forrestgang

华为面试题(8分钟写出代码) [复制链接]

论坛徽章:
0
发表于 2006-11-16 17:24 |显示全部楼层
好啊

论坛徽章:
0
发表于 2006-11-16 17:29 |显示全部楼层
/*
        问题:        有两个数组a,b,大小都为n,数组元素的值任意,无序。

        要求:        通过交换a,b中的元素,使数组a元素的和与数组b元素的
                和之间的差最小。

        思路:        把a, b的数据合并到临时数组c,对c的数据按升序排序。
                选择c里的一对最小数据分别放入a、b,再选择c里的一
                对‘次’小数据。如果a的全部数据之和大于b的全部数
                据之和,则:‘次’小两数据中,小的数据归入a,大的
                归入b,反之小的数据归入b,大的归入a。依次类推。。。

*/


#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <malloc.h>

#define MAX_SIZE        30



void sort(void * C, int size_c);
void split(int A[], int B[], int size_a, int size_b);

int main(int argc, char* argv[])
{
        int i;
        int A[MAX_SIZE], B[MAX_SIZE];


        printf("\n\na[%d]=\n\n", MAX_SIZE);
        for(i=0; i<=MAX_SIZE-1; i++)
        {
                A[i] = rand() % 100;
                printf("\t%d", A[i]);
        }


        printf("\n\nb[%d]=\n\n", MAX_SIZE);
        for(i=0; i<=MAX_SIZE-1; i++)
        {
                B[i] = rand() % 100;
                printf("\t%d", B[i]);
        }


        split(A, B, sizeof(A)/sizeof(int), sizeof(B)/sizeof(int));

     /*        打印a数组的最终结果        */
        printf("\n\n\n\n\n\na[%d]=\n\n", MAX_SIZE); 
        for(i=0; i<=MAX_SIZE-1; i++)
                printf("\t%d", A[i]);

     /*        打印b数组的最终结果        */
        printf("\n\nb[%d]=\n\n", MAX_SIZE);           
        for(i=0; i<=MAX_SIZE-1; i++)
                printf("\t%d", B[i]);


        getch();
        return 0;
}

/*a, b为待交换数据的数组,size_a为a的长度,size_b为b的长度*/
void split(int A[], int B[], int size_a, int size_b){
        int i;       
        int sum_a = 0, sum_b = 0;
       
        int *C = (int*)malloc( (size_a+size_b)*sizeof(int) );


        for(i = 0; i <= size_a; i++)
                *(C+i) = A[i];

        for(i = 0; i <= size_b; i++)
                *(C+size_a+i) = B[i];

        sort(C, size_a+size_b);

        for(i = 0; i < (size_a+size_b)/2; i++)
        {
                A[i] = sum_a > sum_b?C[i*2]:C[i*2+1];
                B[i] = sum_a > sum_b?C[i*2+1]:C[i*2];

                sum_a+=A[i];
                sum_b+=B[i];
        }
}

/*冒泡法升序排序,c为待排序临时数组,size_c为c的长度        */
void sort(void * C, int size_c){
        int i, j, t;

        for(i=size_c; i>0; i--)
                for(j=0; j<i-1; j++)
                        if( *((int*)C+j) > *((int*)C+j+1) )
                        {
                                t = *((int*)C+j+1);
                                *((int*)C+j+1) = *((int*)C+j);
                                *((int*)C+j) = t;
                        }
}

论坛徽章:
0
发表于 2006-11-16 18:01 |显示全部楼层
原帖由 chendreamy 于 2006-11-16 17:29 发表
问题:        有两个数组a,b,大小都为n,数组元素的值任意,无序。

        要求:        通过交换a,b中的元素,使数组a元素的和与数组b元素的
                和之间的差最小。

        思路:        把a, b的数据合并到临时数组c,对c的数据按升序排序。
                选择c里的一对最小数据分别放入a、b,再选择c里的一
                对‘次’小数据。如果a的全部数据之和大于b的全部数
                据之和,则:‘次’小两数据中,小的数据归入a,大的
                归入b,反之小的数据归入b,大的归入a。依次类推。。。


这个算法是错误的。

举一个例子:

a[3] = {14, 13 12};
b[3] = {11, 10, 1};

那么合并之后

c[6] = {14, 13, 12, 11, 10, 1};

按照你的算法组合应该是
a[3] = {1, 12, 14}
b[3] = {10, 11, 13}

suma = 27
sumb = 34

sub = 34 - 27 = 7

但是有另一种组合方式:
a[3] = {1, 13, 14}
b[3] = {10, 11, 12}

suma = 28
sumb = 33

sub = 33 - 28 = 5

这个才是组合后和之差最小的。
而且绝对保证suma或sumb是离sum/2(这里是61/2 = 30.5)最近的。。。

论坛徽章:
0
发表于 2006-11-17 13:34 |显示全部楼层
ccjjhua (贝壳) 的想法不错啊!
原帖由 ccjjhua 于 2006-11-14 10:31 发表
想想2个原始人,他们一起采集了一些土豆2n个,他们之前有一个协议,就是采集到的东西都要平分,最好他们会怎么分,会比较公平呢?土豆不进行切割。你拿一个,我拿一个,个数一样,要求分到的总重量差要最小。那他 ...

论坛徽章:
0
发表于 2006-11-17 14:12 |显示全部楼层
我的想法是错的,
我试图去证明,就证明不了,后来有了一个反例,可以证明我的想法是错的。

a[3]={1 ,1 ,2};
b[3]={5 ,5 ,10};

对c 排序后c[6]={1,1,2,5,5,10}
可以知道把c分成2个和差最小的数组分别是
{1,1,10}和{2,5,5},和差为0
可按我的算法,就应该是
{1,2,10}和{1,5,5},和差是2,所以我的算法是错误。

论坛徽章:
0
发表于 2006-11-17 14:25 |显示全部楼层

回复 116楼 ccjjhua 的帖子

噢,果然有问题,不过这办法还是挺好的,我想改一改就应该可以吧,让他们从大到小拿,谁的轻(或与另一个相等)要继续拿,否则换人拿,(如果有个人一直轻就一直拿下去,直到拿的数量为总数的二分之一时停止!),这样就解决你的问题啦,嘿嘿,再找个反例出来试试!

[ 本帖最后由 绿茶主演 于 2006-11-17 14:28 编辑 ]

论坛徽章:
0
发表于 2006-11-17 14:34 |显示全部楼层
原帖由 ccjjhua 于 2006-11-17 14:12 发表
我的想法是错的,
我试图去证明,就证明不了,后来有了一个反例,可以证明我的想法是错的。

a[3]={1 ,1 ,2};
b[3]={5 ,5 ,10};

对c 排序后c[6]={1,1,2,5,5,10}
可以知道把c分成2个和差最小的数组 ...


将你的算法稍改一下,如何:

1\排序
2\各自取最大,和小者优先;
3\和相等时,已取个数多者占先;

论坛徽章:
0
发表于 2006-11-17 15:13 |显示全部楼层
c[6]={10,8,0,6,6,6}
a[3]={10,8,0},sum(a)=18
b[3]={6,6,6},sum(b)=18
和差为0
按从大向小拿一样存在这样的问题。
a[3]={10,6,0},sum(a)=16
b[3]={8,6,6},sum(b)=18.
和差为2。
也就是说,我们错在凭什么要最大或最小的2个要分开,不能在同一个数组里。所以,这个法子是不可行的。
看来xmyth 兄的解法是唯一的正解了。

论坛徽章:
0
发表于 2006-11-17 15:24 |显示全部楼层
题目没问题吗?

论坛徽章:
0
发表于 2006-11-17 16:20 |显示全部楼层
原帖由 zwylinux 于 2006-11-15 20:14 发表
上面我有发表我的算法,但是有些错误没改过来,现在这个是改进的,应该没什么问题了
#include<stdio.h>
#define SIZE 3
int
sumb (int m[], int n)
{
  int i;
  int sum = 0;
  for (i = 0; i < ...



我的算法怎么没人回应一下啊。如果有错大家指出我也可以改正啊
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP