[已解决]在n个数中取其中n/2个数，使这n/2个数和为某指定值

chenlifeng

例如有一个数组a[8]={4,5,10,12,13,14,15,16}
我想找其中某4个数的和为44，
像这种类型的问题应该怎么解决呀？

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2021-10-30 22:31:19

chenlifeng 发表于 2021-10-30 22:27
我开始学习c语言不久，c++还没有学呢，告诉我高效率解法估计我都看不懂

那么先用暴力解法吧，4 个 for() 循环：

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.     int a[8] = {4, 5, 10, 12, 13, 14, 15, 16}, target = 44;
   
6.     for(int i = 0; a[i]; i++){
   
7.         for(int j = 0; a[j]; j++){
   
8.             for(int k = 0; a[k]; k++){
   
9.                 for(int l = 0; a[l]; l++){
   
10.                     if(i != j && j != k && k != l && l != i && i != k && j != l && (a[i] + a[j] + a[k] + a[l] == target)){
    
11.                         printf("%d+%d+%d+%d = %d\n", a[i], a[j], a[k], a[l], target);
    
12.                     }
    
13.                 }
    
14.             }
    
15.         }
    
16.     }
    
17.     return 0;
    
18. }

复制代码

跳转到最佳答案楼层

傻眼貓咪

4 个 for() 循环

chenlifeng

傻眼貓咪 发表于 2021-10-30 22:09
4 个 for() 循环

那如果这个n是从键盘输入的一个2到20的整数，怎么办呀，比如我输入n=20,就要在20个数中找10个数和为某指定值了

jackz007

        我先来个笨办法的：

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         int a[8] = {4,5,10,12,13,14,15,16} , c , d , e , f , m ;
   
6.         for(m = c = 0 ; c < 8 ; c ++) {
   
7.                 for(d = 0 ; d < 8 ; d ++) {
   
8.                         if(d != c) {
   
9.                                 for(e = 0 ; e < 8 ; e ++) {
   
10.                                         if(e != c && e != d) {
    
11.                                                 for(f = 0 ; f < 8 ; f ++) {
    
12.                                                         if(f != c && f != d && f != e) {
    
13.                                                                 if(a[c] + a[d] + a[e] + a[f] == 44) {
    
14.                                                                         m ++                                                                ;
    
15.                                                                         printf("%3d : %d + %d + %d + %d\n" , m , a[c] , a[d] , a[e] , a[f]) ;
    
16.                                                                 }
    
17.                                                         }
    
18.                                                 }
    
19.                                         }
    
20.                                 }
    
21.                         }
    
22.                 }
    
23.         }
    
24. }

复制代码

        编译、运行实况：

1. D:\00.Excise\C>g++ -o x x.c
   
2. 
   
3. D:\00.Excise\C>x
   
4.   1 : 4 + 10 + 14 + 16
   
5.   2 : 4 + 10 + 16 + 14
   
6.   3 : 4 + 12 + 13 + 15
   
7.   4 : 4 + 12 + 15 + 13
   
8.   5 : 4 + 13 + 12 + 15
   
9.   6 : 4 + 13 + 15 + 12
   
10.   7 : 4 + 14 + 10 + 16
    
11.   8 : 4 + 14 + 16 + 10
    
12.   9 : 4 + 15 + 12 + 13
    
13. 10 : 4 + 15 + 13 + 12
    
14. 11 : 4 + 16 + 10 + 14
    
15. 12 : 4 + 16 + 14 + 10
    
16. 13 : 5 + 10 + 13 + 16
    
17. 14 : 5 + 10 + 14 + 15
    
18. 15 : 5 + 10 + 15 + 14
    
19. 16 : 5 + 10 + 16 + 13
    
20. 17 : 5 + 12 + 13 + 14
    
21. 18 : 5 + 12 + 14 + 13
    
22. 19 : 5 + 13 + 10 + 16
    
23. 20 : 5 + 13 + 12 + 14
    
24. 21 : 5 + 13 + 14 + 12
    
25. 22 : 5 + 13 + 16 + 10
    
26. 23 : 5 + 14 + 10 + 15
    
27. 24 : 5 + 14 + 12 + 13
    
28. 25 : 5 + 14 + 13 + 12
    
29. 26 : 5 + 14 + 15 + 10
    
30. 27 : 5 + 15 + 10 + 14
    
31. 28 : 5 + 15 + 14 + 10
    
32. 29 : 5 + 16 + 10 + 13
    
33. 30 : 5 + 16 + 13 + 10
    
34. 31 : 10 + 4 + 14 + 16
    
35. 32 : 10 + 4 + 16 + 14
    
36. 33 : 10 + 5 + 13 + 16
    
37. 34 : 10 + 5 + 14 + 15
    
38. 35 : 10 + 5 + 15 + 14
    
39. 36 : 10 + 5 + 16 + 13
    
40. 37 : 10 + 13 + 5 + 16
    
41. 38 : 10 + 13 + 16 + 5
    
42. 39 : 10 + 14 + 4 + 16
    
43. 40 : 10 + 14 + 5 + 15
    
44. 41 : 10 + 14 + 15 + 5
    
45. 42 : 10 + 14 + 16 + 4
    
46. 43 : 10 + 15 + 5 + 14
    
47. 44 : 10 + 15 + 14 + 5
    
48. 45 : 10 + 16 + 4 + 14
    
49. 46 : 10 + 16 + 5 + 13
    
50. 47 : 10 + 16 + 13 + 5
    
51. 48 : 10 + 16 + 14 + 4
    
52. 49 : 12 + 4 + 13 + 15
    
53. 50 : 12 + 4 + 15 + 13
    
54. 51 : 12 + 5 + 13 + 14
    
55. 52 : 12 + 5 + 14 + 13
    
56. 53 : 12 + 13 + 4 + 15
    
57. 54 : 12 + 13 + 5 + 14
    
58. 55 : 12 + 13 + 14 + 5
    
59. 56 : 12 + 13 + 15 + 4
    
60. 57 : 12 + 14 + 5 + 13
    
61. 58 : 12 + 14 + 13 + 5
    
62. 59 : 12 + 15 + 4 + 13
    
63. 60 : 12 + 15 + 13 + 4
    
64. 61 : 13 + 4 + 12 + 15
    
65. 62 : 13 + 4 + 15 + 12
    
66. 63 : 13 + 5 + 10 + 16
    
67. 64 : 13 + 5 + 12 + 14
    
68. 65 : 13 + 5 + 14 + 12
    
69. 66 : 13 + 5 + 16 + 10
    
70. 67 : 13 + 10 + 5 + 16
    
71. 68 : 13 + 10 + 16 + 5
    
72. 69 : 13 + 12 + 4 + 15
    
73. 70 : 13 + 12 + 5 + 14
    
74. 71 : 13 + 12 + 14 + 5
    
75. 72 : 13 + 12 + 15 + 4
    
76. 73 : 13 + 14 + 5 + 12
    
77. 74 : 13 + 14 + 12 + 5
    
78. 75 : 13 + 15 + 4 + 12
    
79. 76 : 13 + 15 + 12 + 4
    
80. 77 : 13 + 16 + 5 + 10
    
81. 78 : 13 + 16 + 10 + 5
    
82. 79 : 14 + 4 + 10 + 16
    
83. 80 : 14 + 4 + 16 + 10
    
84. 81 : 14 + 5 + 10 + 15
    
85. 82 : 14 + 5 + 12 + 13
    
86. 83 : 14 + 5 + 13 + 12
    
87. 84 : 14 + 5 + 15 + 10
    
88. 85 : 14 + 10 + 4 + 16
    
89. 86 : 14 + 10 + 5 + 15
    
90. 87 : 14 + 10 + 15 + 5
    
91. 88 : 14 + 10 + 16 + 4
    
92. 89 : 14 + 12 + 5 + 13
    
93. 90 : 14 + 12 + 13 + 5
    
94. 91 : 14 + 13 + 5 + 12
    
95. 92 : 14 + 13 + 12 + 5
    
96. 93 : 14 + 15 + 5 + 10
    
97. 94 : 14 + 15 + 10 + 5
    
98. 95 : 14 + 16 + 4 + 10
    
99. 96 : 14 + 16 + 10 + 4
    
100. 97 : 15 + 4 + 12 + 13
     
101. 98 : 15 + 4 + 13 + 12
     
102. 99 : 15 + 5 + 10 + 14
     
103. 100 : 15 + 5 + 14 + 10
     
104. 101 : 15 + 10 + 5 + 14
     
105. 102 : 15 + 10 + 14 + 5
     
106. 103 : 15 + 12 + 4 + 13
     
107. 104 : 15 + 12 + 13 + 4
     
108. 105 : 15 + 13 + 4 + 12
     
109. 106 : 15 + 13 + 12 + 4
     
110. 107 : 15 + 14 + 5 + 10
     
111. 108 : 15 + 14 + 10 + 5
     
112. 109 : 16 + 4 + 10 + 14
     
113. 110 : 16 + 4 + 14 + 10
     
114. 111 : 16 + 5 + 10 + 13
     
115. 112 : 16 + 5 + 13 + 10
     
116. 113 : 16 + 10 + 4 + 14
     
117. 114 : 16 + 10 + 5 + 13
     
118. 115 : 16 + 10 + 13 + 5
     
119. 116 : 16 + 10 + 14 + 4
     
120. 117 : 16 + 13 + 5 + 10
     
121. 118 : 16 + 13 + 10 + 5
     
122. 119 : 16 + 14 + 4 + 10
     
123. 120 : 16 + 14 + 10 + 4
     
124. 
     
125. D:\00.Excise\C>

复制代码

chenlifeng

jackz007 发表于 2021-10-30 22:17
我先来个笨办法的：

        编译、运行实况：

啊这

傻眼貓咪

chenlifeng 发表于 2021-10-30 22:20
啊这

4 个 for() 循环是暴力解法，我是有 C++ 高效率解法，但是应该不是你想要的

chenlifeng

傻眼貓咪 发表于 2021-10-30 22:24
4 个 for() 循环是暴力解法，我是有 C++ 高效率解法，但是应该不是你想要的

我开始学习c语言不久，c++还没有学呢，告诉我高效率解法估计我都看不懂

傻眼貓咪

chenlifeng 发表于 2021-10-30 22:27
我开始学习c语言不久，c++还没有学呢，告诉我高效率解法估计我都看不懂

那么先用暴力解法吧，4 个 for() 循环：

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.     int a[8] = {4, 5, 10, 12, 13, 14, 15, 16}, target = 44;
   
6.     for(int i = 0; a[i]; i++){
   
7.         for(int j = 0; a[j]; j++){
   
8.             for(int k = 0; a[k]; k++){
   
9.                 for(int l = 0; a[l]; l++){
   
10.                     if(i != j && j != k && k != l && l != i && i != k && j != l && (a[i] + a[j] + a[k] + a[l] == target)){
    
11.                         printf("%d+%d+%d+%d = %d\n", a[i], a[j], a[k], a[l], target);
    
12.                     }
    
13.                 }
    
14.             }
    
15.         }
    
16.     }
    
17.     return 0;
    
18. }

复制代码

chenlifeng

傻眼貓咪 发表于 2021-10-30 22:31
那么先用暴力解法吧，4 个 for() 循环：

那我就先这么干了感谢！

chenlifeng

傻眼貓咪 发表于 2021-10-30 22:31
那么先用暴力解法吧，4 个 for() 循环：

我突然想到一种方法，我可以用一个数组index[4],然后用随机数为它赋值，然后计算sum=a[index[0]]+a[index[1]]+a[index[2]]+a[index[3]],然后与我指定的值反复比较,这样就不用套很多层了，你觉得怎么样

傻眼貓咪

chenlifeng 发表于 2021-10-31 10:12
我突然想到一种方法，我可以用一个数组index[4],然后用随机数为它赋值，然后计算sum=a]+a]+a]+a],然后与 ...

这也是个办法，不过时间复杂度要么O(1)要么无限，看运气。而且假设答案不止一个，就好象你的题目一样多个，重复性极高啊～

jhq999

(n*(n-1)*(n-2)*......*(n/2+1))/(1*2*3*......*n/2)这么多个组合
8个就是（8×7×6×5）/（1×2×3×4）=70个组合

chenlifeng

傻眼貓咪 发表于 2021-10-31 10:20
这也是个办法，不过时间复杂度要么O(1)要么无限，看运气。而且假设答案不止一个，就好象你的题目一样多个 ...

也对哦