華為面試題(8分鐘寫出代碼)

greensky_34

原帖由 s5unty 于 2006-11-13 22:43 發(fā)表


不行阿，我理解后用c實(shí)現(xiàn)，結(jié)果不正確，可能是我理解有問題？

1. 
   
2. #include <iostream>
   
3. 
   
4. using namespace std;
   
5. 
   
6. void change(int* a, int* b) {
   
7.     int t = *b;
   
8.     *a = t;
   
9.     *b = * ...

復(fù)制代碼

完整的程序是這樣的，可以參考一下

1. 
   
2. #include <stdio.h>
   
3. #include <math.h>
   
4. 
   
5. #define N 10
   
6. 
   
7. void ary_init(int a[], int b[]){ //初始化數(shù)組
   
8.     int i;
   
9.     for (i=0; i<N; i++){
   
10.         a[i] = rand()%100;
    
11.     }
    
12.     for (i=0; i<N; i++){
    
13.         b[i] = rand()%100;
    
14.     }
    
15.     return;
    
16. }
    
17. long sum(int a[]){ //數(shù)組求和
    
18.     int i;
    
19.     int s;
    
20.     for (s=0,i=0; i<N; i++){
    
21.         s += a[i];
    
22.     }
    
23.     return s;
    
24. }
    
25. 
    
26. void change(int *a, int *b){ //數(shù)組元素交換
    
27.     int tmp;
    
28.     tmp = *a;
    
29.     *a = *b;
    
30.     *b = tmp;
    
31.     return;
    
32. }
    
33. 
    
34. void prt_ary(int a[], int b[]){ //列印兩數(shù)組元素及各自元素和
    
35.     int i;
    
36.     for(i=0; i<N; i++){
    
37.         printf("%5d   ", a[i]);
    
38.     }
    
39.     printf("\n");
    
40.     for(i=0; i<N; i++){
    
41.         printf("%5d   ", b[i]);
    
42.     }
    
43.     printf("\n");
    
44.     printf("%d\n", sum(a));
    
45.     printf("%d\n", sum(b));
    
46. }
    
47. 
    
48. int main(){
    
49.     int i;
    
50.     int j;
    
51.     int a[N];
    
52.     int b[N];
    
53.     int a_sum;
    
54.     int b_sum;
    
55.     int tmp;
    
56.     int ab_diff;
    
57. 
    
58.     ary_init(a,b);//初始化
    
59.     prt_ary(a, b);//列印當(dāng)前數(shù)組狀態(tài)
    
60.     ab_diff = abs(sum(a)-sum(b));
    
61.     for (i=0; i<N; i++){//交換數(shù)組元素
    
62.         for (j=0; j<N; j++){
    
63.             change(a+i, b+j);
    
64.             if (abs(sum(a)-sum(b)) > ab_diff){
    
65.                 change(b+j, a+i);
    
66.             }
    
67.             else{
    
68.                 ab_diff = abs(sum(a)-sum(b));
    
69.             }
    
70.         }
    
71.     }
    
72.     prt_ary(a, b);//列印交換后數(shù)組狀態(tài)
    
73.     getch();
    
74. }
    

復(fù)制代碼

[ 本帖最后由 greensky_34 于 2006-11-14 00:30 編輯 ]

小帥哥飛飛

比如說總共加起來為數(shù)組：1，2，3，4，5，6

如果算6-5，4-3，2-1（12樓的算法），然后求和結(jié)果最小差是3

但我可以這樣分組（1，6）一組，（2，5）一組，4，3分到兩個(gè)組，結(jié)果最小差才是1

jinjianlee

首先可以用窮舉的方式來實(shí)現(xiàn)該方法
在此基礎(chǔ)上再優(yōu)化算法（即排除沒有必要的計(jì)算），最后必然可以得到想要的結(jié)果

pinyin

原帖由 mill888 于 2006-11-13 17:29 發(fā)表
8分鐘就能寫出正確方法的人，建議就不要去華為了，應(yīng)當(dāng)去更好的公司。
招聘中，建議華為公司應(yīng)當(dāng)定好自己的位。

共鳴

天山峰右

可以用背包算法

輪流取數(shù)、按差值取數(shù)都不能保證正確性

比如對于原始數(shù)組：
a[]={1,2,3}
b[]={4,10,20}

或者：
a[]={1,29,30}
b[]={50,90,100}

banboy

首先看圖片信息-------這個(gè)題不一定就能交叉，你們能確定交叉就對嗎，不對的，這也是我剛開始錯(cuò)誤的思路，哈哈
我很就沒寫程序了，我是個(gè)做網(wǎng)頁的，現(xiàn)在也不知道用哪種語言表達(dá)了，希望寫程序比較好的朋友，把程序?qū)懗鰜戆�，就一個(gè)函數(shù)，我認(rèn)為就能解決這個(gè)問題，

你們的程序中只要不區(qū)分當(dāng)N為奇數(shù)還是偶數(shù)的情況，你們的算法就是錯(cuò)誤的，我可以這么肯定的說，

你們只需要看N的判斷，就可以知道這個(gè)算法的正確還是錯(cuò)誤，

我個(gè)人認(rèn)為，寫程序，未必一定要用，英語來表達(dá)，
這樣會(huì)達(dá)不到讓看的人明白的效果的，  

呵呵，一個(gè)沒編過程的人，不知道說的對不對，但是我看過LINUX 內(nèi)核和STL，自認(rèn)為比別人懂模式。



我確定這個(gè)絕對正確，我用了10分鐘


然后，將a,b數(shù)組合并，成一個(gè)數(shù)組C，

排序C，
然后將C中的數(shù)組

這個(gè)時(shí)候要看N為奇數(shù)還是偶數(shù)了 ，分析如圖

這樣就應(yīng)該可以了把，



例如；

C數(shù)組；123456
那么A，B將取如下圖

[ 本帖最后由 banboy 于 2006-11-14 10:10 編輯 ]

billzhou

這樣一定不行

windy2335

小弟想到一個(gè)算法，，大家給點(diǎn)意見
   定義一個(gè)c[2N]數(shù)組，將A數(shù)組和B數(shù)組里面的元素都放到C數(shù)組中，然后對C數(shù)組小到大排序，排好后在取數(shù)，在定義一個(gè)的D[N]數(shù)組，將C的第一個(gè)加上C的第2N個(gè)放到D[0]中，C的第二個(gè)加上C的第2N-1個(gè)放到D[1]中。。。。放好后，再將D數(shù)組從小到大排序，在又按照上面的方法，第一個(gè)加上最后一個(gè)放到另一個(gè)數(shù)組的第一個(gè)中，第2個(gè)加到數(shù)第二個(gè)放到另一個(gè)數(shù)組的第2個(gè)中。。。以這中思路一直排下去，最后得到一個(gè)兩個(gè)元素的數(shù)組，那這數(shù)組中的兩個(gè)元素的差應(yīng)該就是最小的了。。。
這個(gè)數(shù)組中的兩個(gè)元素中的每一個(gè)都是由N個(gè)數(shù)加起來的，所以在一開始放數(shù)的時(shí)候要對這些數(shù)進(jìn)行記錄。。。得到后便可以將這2N個(gè)數(shù)分配給A數(shù)組和B數(shù)組了.....
     這種方法應(yīng)該是可行的。。。。高手指點(diǎn)下....

huntrsky

greensky 的算法很不錯(cuò)啊~~~大家看看可否再優(yōu)化��？

pywj777

QUOTE:
原帖由 zhhui2000 于 2006-11-13 07:54 發(fā)表
先各自排序,再交叉存放較大無素
這個(gè)基本可行，但不是交叉存放較大元素，而是哪邊的和小就一直放大元素，直到n，然后把剩下的扔到另一組中就ok了。

同意，但不應(yīng)該是哪邊小就一直放大元素，直到n， 應(yīng)該是直到這個(gè)組元素的和大于另一組元素和時(shí)，再將下一元素放到令一組，若兩組之和相等時(shí)，將下一元素放到元素最多的那個(gè)組，然后以同樣的方法繼續(xù)剩下元素的放置，直到有一個(gè)組為n，然后把剩下的放到另一個(gè)組。