华为面试题，求答案？

bruceteen

1. #include <stdio.h>
   
2. #include <assert.h>
   
3. 
   
4. int main()
   
5. {
   
6.     const int arr[] = { 43, 72, 12, 32, 19, 9, 2, 14 };
   
7.     const unsigned N = sizeof(arr)/sizeof(arr[0]);
   
8. 
   
9.     assert( N < sizeof(N)*8 );
   
10.     for( unsigned i=1; i!=(1u<<N); ++i ) // i不从0开始，是为了剔除『一个都没选择』的情况
    
11.     {
    
12.         if( (i&(i-1)) == 0 ) // 剔除『只选择了一个』的情况
    
13.             continue;
    
14. 
    
15.         // 输出
    
16.         for( unsigned j=0; j!=N; ++j )
    
17.             if( i&(1u<<j) )
    
18.                 printf( "%d%c", arr[j], "+\n"[(i&((~0u)<<(j+1)))==0] );
    
19. 
    
20.     }
    
21.     return 0;
    
22. }

复制代码

udb6688

回复 10# koolcoy


    0 1 2 3 3 4 5 6 4 5 6 7 7 8 9 10 5 6 7 8 8 9 10 11 9 10 11 12 12 13 14 15 6 7 8 9 9 10 11 12 10 11 12 13 13 14 15 16 11 12 13 14 14 15 16 17 15 16 17 18 18 19 20 21 7 8 9 10 10 11 12 13 11 12 13 14 14 15 16 17 12 13 14 15 15 16 17 18 16 17 18 19 19 20 21 22 13 14 15 16 16 17 18 19 17 18 19 20 20 21 22 23 18 19 20 21 21 22 23 24 22 23 24 25 25 26 27 28 8 9 10 11 11 12 13 14 12 13 14 15 15 16 17 18 13 14 15 16 16 17 18 19 17 18 19 20 20 21 22 23 14 15 16 17 17 18 19 20 18 19 20 21 21 22 23 24 19 20 21 22 22 23 24 25 23 24 25 26 26 27 28 29 15 16 17 18 18 19 20 21 19 20 21 22 22 23 24 25 20 21 22 23 23 24 25 26 24 25 26 27 27 28 29 30 21 22 23 24 24 25 26 27 25 26 27 28 28 29 30 31 26 27 28 29 29 30 31 32 30 31 32 33 33 34 35 36
这样的结果似乎不对耶

koolcoy

回复 12# udb6688

基本就这么个意思，调试一下就能找到哪里不对了
   

koolcoy

我那个代码应该没有错，这么改一下就很清晰了：

1. 
   
2. #include <stdio.h>
   
3. 
   
4. int main() {
   
5.         unsigned long input[8] = {1, 10, 100, 1000, 10000, 100000, 1000000,
   
6.                 10000000};
   
7.         unsigned long sum[256];
   
8. 
   
9.         sum[0] = 0;
   
10.         sum[1] = input[0];
    
11. 
    
12.         int idx = 2;
    
13.         for (int i = 1; i < 8; ++i, idx *= 2) {
    
14.                 for (int j = 0; j < idx; ++j) {
    
15.                         sum[idx + j] = input[i] + sum[j];
    
16.                 }
    
17.         }
    
18.         for (int i = 0; i < 256; ++i) {
    
19.                 printf("%08lu\n", sum[i]);
    
20.         }
    
21.         return 0;
    
22. }
    

复制代码

udb6688

回复 14# koolcoy


    还没有细研究，发觉打印0，就认为不对了。

udb6688

回复 14# koolcoy


    idx=2是什么意思？

koolcoy

回复 16# udb6688

因为sum[0]和sum[1]已经赋值了，所以就从sum[2]开始算起
   

lichmama

这样吗？

1+2 1+3 1+4 1+5 1+6 1+7 1+8
1+2+3 1+2+4 1+2+5 1+2+6 1+2+7 1+2+8
1+2+3+4 1+2+3+5 1+2+3+6 1+2+3+7 1+2+3+8
1+2+3+4+5 1+2+3+4+6 1+2+3+4+7 1+2+3+4+8
1+2+3+4+5+6 1+2+3+4+5+7 1+2+3+4+5+8
1+2+3+4+5+6+7 1+2+3+4+5+6+8
1+2+3+4+5+6+7+8

2+3 2+4 2+5 2+6 2+7 2+8
2+3+4 2+3+5 2+3+6 2+3+7 2+3+8
2+3+4+5 2+3+4+6 2+3+4+7 2+3+4+8
2+3+4+5+6 2+3+4+5+7 2+3+4+5+8
2+3+4+5+6+7 2+3+4+5+6+8
2+3+4+5+6+7+8

3+4 3+5 3+6 3+7 3+8
3+4+5 3+4+6 3+4+7 3+4+8
3+4+5+6 3+4+5+7 3+4+5+8
3+4+5+6+7 3+4+5+6+8
3+4+5+6+7+8

4+5 4+6 4+7 4+8
4+5+6 4+5+7 4+5+8
4+5+6+7 4+5+6+8
4+5+6+7+8

5+6 5+7 5+8
5+6+7 5+6+8
5+6+7+8

6+7 6+8
6+7+8

7+8


   

sig13

我用递归写了一个，但是也没有解决有重复输入的问题，即输入1,1,1,1这样的情况。

1. #include <stdio.h>
   
2. 
   
3. int b[16];
   
4. 
   
5. int d(int in)
   
6. {
   
7.     static int cnt=0;
   
8.     int i;
   
9. 
   
10.     printf("%4d: ", cnt++);
    
11. 
    
12.     if (in > 0) printf("%d", b[0]);
    
13. 
    
14.     for (i=1; i<in; i++) printf("+%d", b[i]);
    
15. 
    
16.     printf("\n");
    
17. 
    
18.     return 0;
    
19. }
    
20. 
    
21. int p(int a[], int n, int m, int in);
    
22. 
    
23. int p(int a[], int n, int m, int in)
    
24. {
    
25.     int i;
    
26. 
    
27.     //printf("n=%d, m=%d, in=%d\n", n, m, in);
    
28. 
    
29.     if (m < 0) return 0;
    
30.     if (m == 0) return d(in);
    
31. 
    
32.     if (m == n)
    
33.     {
    
34.         for(i=0; i<n; i++) b[in+i] = a[i];
    
35.         return d(in+n);
    
36.     }
    
37. 
    
38.     for(i=0; i<n; i++)
    
39.     {
    
40.         b[in] = a[i];
    
41.         p(a+(i+1), n-(i+1), m-1, in+1);
    
42.     }
    
43. 
    
44.     return 0;
    
45. }
    
46. 
    
47. int main(int argc, char* argv[])
    
48. {
    
49.     int a[]={1, 2, 3, 4, 5, 6, 7, 8};
    
50. 
    
51.     p(a, 8, 2, 0);
    
52.     p(a, 8, 3, 0);
    
53.     p(a, 8, 4, 0);
    
54.     p(a, 8, 5, 0);
    
55.     p(a, 8, 6, 0);
    
56.     p(a, 8, 7, 0);
    
57.     p(a, 8, 8, 0);
    
58. 
    
59.     return 0;
    
60. }
    

复制代码

vbs100

#include<iostream>
#include<vector>
#include<string>  
#include<iterator>  
using namespace std;
using std::iterator;
void CombineRescure(vector<int> &num,vector<int>::iterator pNum,vector<int> &result,int count);
void Combine(vector<int> num,int n)
{
        if(num.empty())
                return;
        vector<int> result;
        CombineRescure(num,num.begin(),result,n);
}
void CombineRescure(vector<int> &num,vector<int>::iterator pNum,vector<int> &result,int count)
{
        if(count==0)
        {
                for(int i=0;i<result.size();i++)
                {
                        cout<<result[i];
                        if(i!=result.size()-1)
                                cout<<"+";
                }
                cout<<",";
                return;
        }
        if(pNum!=num.end())
        {
                result.push_back(*pNum);
                CombineRescure(num,pNum+1,result,count-1);
                result.erase(result.end()-1);
                CombineRescure(num,pNum+1,result,count);
        }
}
int main()
{
        vector<int> num;
        for(int i=1;i<=8;i++)
        {
                num.push_back(i);
        }

        for(int i=1;i<=num.size();i++)
        {
                Combine(num,i);
                cout<<endl;
        }
        return 0;
}