免费注册 查看新帖 |

Chinaunix

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

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

论坛徽章:
0
发表于 2006-11-17 16:39 |显示全部楼层
原我犯了很多数人一样的错误

主观一定认为最大的两个数一定要分开

[ 本帖最后由 lih928 于 2006-11-17 16:46 编辑 ]

论坛徽章:
0
发表于 2006-11-17 17:34 |显示全部楼层
  1. 原帖由 [i]xmyth[/i] 于 2006-11-14 17:04 发表
  2. 当前数组a和数组b的和之差为
  3. A = sum(a) - sum(b)

  4. a的第i个元素和b的第j个元素交换后,a和b的和之差为
  5. A' = sum(a) - a[i] + b[j] - (sum(b) - b[j] + a[i])
  6.        = sum(a) - sum(b) - 2 (a[i] - b[j]) ...
复制代码

当x 在 (0,A)之间时,做这样的交换才能使得交换后的a和b的和之差变小,x越接近A/2效果越好, 如果找不到在(0,A)之间的x,则当前的a和b就是答案。


当这样的X不存在时,并不能结束算法。还可能存在如下情形,可以得到更小的差值:
例如: A={3, 5, 6, 7, 13, 14}
       B={1, 3, 7, 8, 10, 17}
此时有,sum(A) - sum(B) = 2 ,并且不存在(0, 2)之间的x值。
但将A中的5和6与B中的3和7同时交换,得到
       A={3, 3, 7, 7, 13, 14}
       B={1, 5, 6, 8, 10, 17}
此时有:sum(A) - sum(B) = 0,此时的数组才是解。

我觉得这个算法难在如何有效寻找a(i)]和b[j]上

[ 本帖最后由 tyc611 于 2006-11-17 23:54 编辑 ]

论坛徽章:
0
发表于 2006-11-17 17:38 |显示全部楼层
>为啥上边的回复后部分斜了呢

  1. 知道了,原来是a[i]中的[i]在作祟:em02:
复制代码

[ 本帖最后由 tyc611 于 2006-11-17 23:58 编辑 ]

论坛徽章:
0
发表于 2006-11-17 18:19 |显示全部楼层
建2各数组,把那些数从大到小,分别放入数组就成把.   放的时候判断一下就行了.
if (sum(a)>sunm(b))
  a.push_back(num)
else
  b.push_back(num)

论坛徽章:
0
发表于 2006-11-17 19:07 |显示全部楼层
xmyth 兄从事什么专业?
能够快速的把实际问题模式化,并行成正确的数学思维,论证严谨.
而且整个模型具有智能的味道,佩服佩服
令我收益非浅那~~

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

  1. int abs(int n)
  2. {
  3.         return n >= 0 ? n : -n;
  4. }

  5. int sum(int *array, int count)
  6. {
  7.         int sum = 0;
  8.         for (int i = 0; i < count; i++)
  9.                 sum += array[i];
  10.         return sum;
  11. }

  12. void exchange(int *array1, int *array2, int count)
  13. {
  14.         int sum1 = sum(array1, count);
  15.         int sum2 = sum(array2, count);
  16.         if (sum1 == sum2)
  17.                 return;
  18.                
  19.         int diff = abs(sum1 - sum2);
  20.         for (int i = 0; i < count; i++) {
  21.                 for (int j = 0; j < count; j++) {
  22.                         int s1 = sum1 + array2[j] - array1[i];
  23.                         int s2 = sum2 + array1[i] - array2[j];
  24.                         if (abs(s1 - s2) < diff) {
  25.                                 int tmp = array1[i];
  26.                                 array1[i] = array2[j];
  27.                                 array2[j] = tmp;
  28.                                 sum1 = s1;
  29.                                 sum2 = s2;
  30.                                 diff = abs(sum1 - sum2);
  31.                                 if (diff == 0)
  32.                                         return;
  33.                         }
  34.                 }
  35.         }
  36. }
复制代码

[ 本帖最后由 svenwang 于 2006-11-17 23:41 编辑 ]

论坛徽章:
0
发表于 2006-11-18 11:09 |显示全部楼层
先把数据放到一个临时数组中,排序且求和sum;用背包算法,尽量是一个数组大小为n的存放的数字和为sum/2

论坛徽章:
0
发表于 2006-11-18 11:19 |显示全部楼层
原帖由 slsl8460 于 2006-11-17 19:09 发表
先把数据放到一个临时数组中,排序且求和sum;用背包算法,尽量是一个数组大小为n的存放的数字和为sum/2


原题说了数组里面元素的值任意,背包算法的效率线性于最大容积K,这里就是sum/2,如果这个数字可以任意,那背包算法也没什么意义了。

论坛徽章:
0
发表于 2006-11-18 17:53 |显示全部楼层
关注....

论坛徽章:
0
发表于 2006-11-18 22:21 |显示全部楼层
搞一个数组C   包含了全部a  b  的数据   并排序(再生成C的时候就排序)
然后在C里面  选1个 放到A  第2n个放到B  第2个放到A  第2n-1个放到B。。。。。。。

[ 本帖最后由 geba168 于 2006-11-18 22:23 编辑 ]
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP