在n个数中取其中n/2个数，使这n/2个数和为某指定值
例如有一个数组a={4,5,10,12,13,14,15,16}我想找其中某4个数的和为44，
像这种类型的问题应该怎么解决呀？
{:9_241:} 4 个 for() 循环 傻眼貓咪 发表于 2021-10-30 22:09
4 个 for() 循环
那如果这个n是从键盘输入的一个2到20的整数，怎么办呀，比如我输入n=20,就要在20个数中找10个数和为某指定值了
{:9_241:} 我先来个笨办法的：
#include <stdio.h>
int main(void)
{
int a = {4,5,10,12,13,14,15,16} , c , d , e , f , m ;
for(m = c = 0 ; c < 8 ; c ++) {
for(d = 0 ; d < 8 ; d ++) {
if(d != c) {
for(e = 0 ; e < 8 ; e ++) {
if(e != c && e != d) {
for(f = 0 ; f < 8 ; f ++) {
if(f != c && f != d && f != e) {
if(a + a + a + a == 44) {
m ++ ;
printf("%3d : %d + %d + %d + %d\n" , m , a , a , a , a) ;
}
}
}
}
}
}
}
}
}
编译、运行实况：
D:\00.Excise\C>g++ -o x x.c
D:\00.Excise\C>x
1 : 4 + 10 + 14 + 16
2 : 4 + 10 + 16 + 14
3 : 4 + 12 + 13 + 15
4 : 4 + 12 + 15 + 13
5 : 4 + 13 + 12 + 15
6 : 4 + 13 + 15 + 12
7 : 4 + 14 + 10 + 16
8 : 4 + 14 + 16 + 10
9 : 4 + 15 + 12 + 13
10 : 4 + 15 + 13 + 12
11 : 4 + 16 + 10 + 14
12 : 4 + 16 + 14 + 10
13 : 5 + 10 + 13 + 16
14 : 5 + 10 + 14 + 15
15 : 5 + 10 + 15 + 14
16 : 5 + 10 + 16 + 13
17 : 5 + 12 + 13 + 14
18 : 5 + 12 + 14 + 13
19 : 5 + 13 + 10 + 16
20 : 5 + 13 + 12 + 14
21 : 5 + 13 + 14 + 12
22 : 5 + 13 + 16 + 10
23 : 5 + 14 + 10 + 15
24 : 5 + 14 + 12 + 13
25 : 5 + 14 + 13 + 12
26 : 5 + 14 + 15 + 10
27 : 5 + 15 + 10 + 14
28 : 5 + 15 + 14 + 10
29 : 5 + 16 + 10 + 13
30 : 5 + 16 + 13 + 10
31 : 10 + 4 + 14 + 16
32 : 10 + 4 + 16 + 14
33 : 10 + 5 + 13 + 16
34 : 10 + 5 + 14 + 15
35 : 10 + 5 + 15 + 14
36 : 10 + 5 + 16 + 13
37 : 10 + 13 + 5 + 16
38 : 10 + 13 + 16 + 5
39 : 10 + 14 + 4 + 16
40 : 10 + 14 + 5 + 15
41 : 10 + 14 + 15 + 5
42 : 10 + 14 + 16 + 4
43 : 10 + 15 + 5 + 14
44 : 10 + 15 + 14 + 5
45 : 10 + 16 + 4 + 14
46 : 10 + 16 + 5 + 13
47 : 10 + 16 + 13 + 5
48 : 10 + 16 + 14 + 4
49 : 12 + 4 + 13 + 15
50 : 12 + 4 + 15 + 13
51 : 12 + 5 + 13 + 14
52 : 12 + 5 + 14 + 13
53 : 12 + 13 + 4 + 15
54 : 12 + 13 + 5 + 14
55 : 12 + 13 + 14 + 5
56 : 12 + 13 + 15 + 4
57 : 12 + 14 + 5 + 13
58 : 12 + 14 + 13 + 5
59 : 12 + 15 + 4 + 13
60 : 12 + 15 + 13 + 4
61 : 13 + 4 + 12 + 15
62 : 13 + 4 + 15 + 12
63 : 13 + 5 + 10 + 16
64 : 13 + 5 + 12 + 14
65 : 13 + 5 + 14 + 12
66 : 13 + 5 + 16 + 10
67 : 13 + 10 + 5 + 16
68 : 13 + 10 + 16 + 5
69 : 13 + 12 + 4 + 15
70 : 13 + 12 + 5 + 14
71 : 13 + 12 + 14 + 5
72 : 13 + 12 + 15 + 4
73 : 13 + 14 + 5 + 12
74 : 13 + 14 + 12 + 5
75 : 13 + 15 + 4 + 12
76 : 13 + 15 + 12 + 4
77 : 13 + 16 + 5 + 10
78 : 13 + 16 + 10 + 5
79 : 14 + 4 + 10 + 16
80 : 14 + 4 + 16 + 10
81 : 14 + 5 + 10 + 15
82 : 14 + 5 + 12 + 13
83 : 14 + 5 + 13 + 12
84 : 14 + 5 + 15 + 10
85 : 14 + 10 + 4 + 16
86 : 14 + 10 + 5 + 15
87 : 14 + 10 + 15 + 5
88 : 14 + 10 + 16 + 4
89 : 14 + 12 + 5 + 13
90 : 14 + 12 + 13 + 5
91 : 14 + 13 + 5 + 12
92 : 14 + 13 + 12 + 5
93 : 14 + 15 + 5 + 10
94 : 14 + 15 + 10 + 5
95 : 14 + 16 + 4 + 10
96 : 14 + 16 + 10 + 4
97 : 15 + 4 + 12 + 13
98 : 15 + 4 + 13 + 12
99 : 15 + 5 + 10 + 14
100 : 15 + 5 + 14 + 10
101 : 15 + 10 + 5 + 14
102 : 15 + 10 + 14 + 5
103 : 15 + 12 + 4 + 13
104 : 15 + 12 + 13 + 4
105 : 15 + 13 + 4 + 12
106 : 15 + 13 + 12 + 4
107 : 15 + 14 + 5 + 10
108 : 15 + 14 + 10 + 5
109 : 16 + 4 + 10 + 14
110 : 16 + 4 + 14 + 10
111 : 16 + 5 + 10 + 13
112 : 16 + 5 + 13 + 10
113 : 16 + 10 + 4 + 14
114 : 16 + 10 + 5 + 13
115 : 16 + 10 + 13 + 5
116 : 16 + 10 + 14 + 4
117 : 16 + 13 + 5 + 10
118 : 16 + 13 + 10 + 5
119 : 16 + 14 + 4 + 10
120 : 16 + 14 + 10 + 4
D:\00.Excise\C>
jackz007 发表于 2021-10-30 22:17
我先来个笨办法的：
编译、运行实况：
{:9_239:}啊这 chenlifeng 发表于 2021-10-30 22:20
啊这
4 个 for() 循环是暴力解法，我是有 C++ 高效率解法，但是应该不是你想要的 傻眼貓咪 发表于 2021-10-30 22:24
4 个 for() 循环是暴力解法，我是有 C++ 高效率解法，但是应该不是你想要的
我开始学习c语言不久，c++还没有学呢，告诉我高效率解法估计我都看不懂
{:10_266:} chenlifeng 发表于 2021-10-30 22:27
我开始学习c语言不久，c++还没有学呢，告诉我高效率解法估计我都看不懂
那么先用暴力解法吧，4 个 for() 循环：#include <stdio.h>
int main()
{
int a = {4, 5, 10, 12, 13, 14, 15, 16}, target = 44;
for(int i = 0; a; i++){
for(int j = 0; a; j++){
for(int k = 0; a; k++){
for(int l = 0; a; l++){
if(i != j && j != k && k != l && l != i && i != k && j != l && (a + a + a + a == target)){
printf("%d+%d+%d+%d = %d\n", a, a, a, a, target);
}
}
}
}
}
return 0;
} 傻眼貓咪 发表于 2021-10-30 22:31
那么先用暴力解法吧，4 个 for() 循环：
那我就先这么干了{:10_282:}感谢！ 傻眼貓咪 发表于 2021-10-30 22:31
那么先用暴力解法吧，4 个 for() 循环：
我突然想到一种方法，我可以用一个数组index,然后用随机数为它赋值，然后计算sum=a]+a]+a]+a],然后与我指定的值反复比较,这样就不用套很多层了，你觉得怎么样{:10_254:} chenlifeng 发表于 2021-10-31 10:12
我突然想到一种方法，我可以用一个数组index,然后用随机数为它赋值，然后计算sum=a]+a]+a]+a],然后与 ...
这也是个办法，不过时间复杂度要么O(1)要么无限，看运气。而且假设答案不止一个，就好象你的题目一样多个，重复性极高啊～ 本帖最后由 jhq999 于 2021-10-31 11:00 编辑
(n*(n-1)*(n-2)*......*(n/2+1))/(1*2*3*......*n/2)这么多个组合
8个就是（8×7×6×5）/（1×2×3×4）=70个组合 傻眼貓咪 发表于 2021-10-31 10:20
这也是个办法，不过时间复杂度要么O(1)要么无限，看运气。而且假设答案不止一个，就好象你的题目一样多个 ...
也对哦{:10_243:}
页:
[1]