中兴笔试题

Gegung

输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来.编程求解





求大侠支招！！！

folklore

too easy.

Gegung

麻烦一下 说说那个怎么算的  回复 2# folklore


   

cxytz01

1. // ConsoleApplication2.cpp : Defines the entry point for the console application.
   
2. //
   
3. 
   
4. #include <iostream>
   
5. #include <vector>
   
6. 
   
7. void sum(int len, int res) {
   
8.     std::vector<int> arr(len);
   
9. 
   
10.     for (std::vector<int>::size_type ix = 0; ix <= len; ++ix) {
    
11.         arr[ix] = ix;
    
12.     }
    
13. 
    
14.     int sum = 0;
    
15.     for (std::vector<int>::size_type ix = 1; ix <= len; ++ix) {
    
16.         sum = 0;
    
17.         for (std::vector<int>::size_type jx = ix; jx <= len; ++jx) {
    
18.             sum = sum + arr[jx];
    
19.             if (sum < res) continue;
    
20.             else if (sum == res) {
    
21.                 std::cout << "sum = " << sum << std::endl << " ";
    
22.                 for (std::vector<int>::size_type gx = ix; gx <= jx; ++gx) {
    
23.                     std::cout << arr[gx] << " ";
    
24.                 }
    
25.                 std::cout << std::endl;
    
26.                 break;
    
27.             } else if (sum > res) break;
    
28.         }
    
29.     }
    
30. }
    
31. 
    
32. 
    
33. int main(int argc, char* argv[])
    
34. {
    
35.     int n, m;
    
36.     std::cout << "in put n, m: ";
    
37.     std::cin >> n >> m;
    
38. 
    
39.     sum(n+1, m);
    
40. 
    
41.     return 0;
    
42. }
    

复制代码

1. you-ub@you-ub-desktop:~$ ./a.out
   
2. in put n, m: 100 99
   
3. sum = 99
   
4. 4 5 6 7 8 9 10 11 12 13 14
   
5. sum = 99
   
6. 7 8 9 10 11 12 13 14 15
   
7. sum = 99
   
8. 14 15 16 17 18 19
   
9. sum = 99
   
10. 32 33 34
    
11. sum = 99
    
12. 49 50
    
13. sum = 99
    
14. 99
    

复制代码

tc1989tc

回复 4# cxytz01


    明显没有算完。。改算法只列出了连续的相加为n的

Gegung

该算法没算完吧没有列出所有可能情况啊{:3_182:}  回复 4# cxytz01


   

cxytz01

对哦，那就再原有基础上，再加上跳跃性的求和。

Gegung

跳跃性求和？？不懂哎 给代码啊 亲 有c么 c++没学过回复 7# cxytz01


   

cokeboL

笨方法就是遍历

自己搜下组合算法

先遍历1 ~ n求和，算出和为m最多有多少个数 n_max
然后n 取 1 ~ n_max的组合，每个求和，和为m的就是

自己再弄点筛选的条件节约点循环

ilogo1

楼主可以学习一下动态规划的知识了。。。~！算法导论~！