设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › C\C++交流 › 在n个数中取其中n/2个数，使这n/2个数和为某指定值
返回列表 发新帖
查看: 1212|回复: 12

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

[复制链接]
chenlifeng
发表于 2021-10-30 22:00:13 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
例如有一个数组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() 循环：
#include <stdio.h>

int main()
{
    int a[8] = {4, 5, 10, 12, 13, 14, 15, 16}, target = 44;
    for(int i = 0; a[i]; i++){
        for(int j = 0; a[j]; j++){
            for(int k = 0; a[k]; k++){
                for(int l = 0; a[l]; l++){
                    if(i != j && j != k && k != l && l != i && i != k && j != l && (a[i] + a[j] + a[k] + a[l] == target)){
                        printf("%d+%d+%d+%d = %d\n", a[i], a[j], a[k], a[l], target);
                    }
                }
            }
        }
    }
    return 0;
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

傻眼貓咪
发表于 2021-10-30 22:09:25 | 显示全部楼层
4 个 for() 循环
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

chenlifeng
 楼主| 发表于 2021-10-30 22:17:17 | 显示全部楼层
傻眼貓咪 发表于 2021-10-30 22:09
4 个 for() 循环

那如果这个n是从键盘输入的一个2到20的整数，怎么办呀，比如我输入n=20,就要在20个数中找10个数和为某指定值了
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

jackz007
发表于 2021-10-30 22:17:46 | 显示全部楼层
        我先来个笨办法的：
#include <stdio.h>

int main(void)
{
        int a[8] = {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[c] + a[d] + a[e] + a[f] == 44) {
                                                                        m ++                                                                ;
                                                                        printf("%3d : %d + %d + %d + %d\n" , m , a[c] , a[d] , a[e] , a[f]) ;
                                                                }
                                                        }
                                                }
                                        }
                                }
                        }
                }
        }
}
        编译、运行实况：
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>
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

chenlifeng
 楼主| 发表于 2021-10-30 22:20:52 | 显示全部楼层
jackz007 发表于 2021-10-30 22:17
我先来个笨办法的：

        编译、运行实况：

啊这
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

傻眼貓咪
发表于 2021-10-30 22:24:01 | 显示全部楼层
chenlifeng 发表于 2021-10-30 22:20
啊这

4 个 for() 循环是暴力解法，我是有 C++ 高效率解法，但是应该不是你想要的
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

chenlifeng
 楼主| 发表于 2021-10-30 22:27:49 | 显示全部楼层
傻眼貓咪 发表于 2021-10-30 22:24
4 个 for() 循环是暴力解法，我是有 C++ 高效率解法，但是应该不是你想要的

我开始学习c语言不久，c++还没有学呢，告诉我高效率解法估计我都看不懂
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

傻眼貓咪
发表于 2021-10-30 22:31:19 | 显示全部楼层    本楼为最佳答案   
chenlifeng 发表于 2021-10-30 22:27
我开始学习c语言不久，c++还没有学呢，告诉我高效率解法估计我都看不懂

那么先用暴力解法吧，4 个 for() 循环：
#include <stdio.h>

int main()
{
    int a[8] = {4, 5, 10, 12, 13, 14, 15, 16}, target = 44;
    for(int i = 0; a[i]; i++){
        for(int j = 0; a[j]; j++){
            for(int k = 0; a[k]; k++){
                for(int l = 0; a[l]; l++){
                    if(i != j && j != k && k != l && l != i && i != k && j != l && (a[i] + a[j] + a[k] + a[l] == target)){
                        printf("%d+%d+%d+%d = %d\n", a[i], a[j], a[k], a[l], target);
                    }
                }
            }
        }
    }
    return 0;
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

chenlifeng
 楼主| 发表于 2021-10-30 22:34:32 | 显示全部楼层
傻眼貓咪 发表于 2021-10-30 22:31
那么先用暴力解法吧，4 个 for() 循环：

那我就先这么干了感谢！
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

chenlifeng
 楼主| 发表于 2021-10-31 10:12:42 | 显示全部楼层
傻眼貓咪 发表于 2021-10-30 22:31
那么先用暴力解法吧，4 个 for() 循环：

我突然想到一种方法，我可以用一个数组index[4],然后用随机数为它赋值，然后计算sum=a[index[0]]+a[index[1]]+a[index[2]]+a[index[3]],然后与我指定的值反复比较,这样就不用套很多层了，你觉得怎么样
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

傻眼貓咪
发表于 2021-10-31 10:20:33 | 显示全部楼层
chenlifeng 发表于 2021-10-31 10:12
我突然想到一种方法，我可以用一个数组index[4],然后用随机数为它赋值，然后计算sum=a]+a]+a]+a],然后与 ...

这也是个办法，不过时间复杂度要么O(1)要么无限，看运气。而且假设答案不止一个，就好象你的题目一样多个，重复性极高啊～
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

jhq999
发表于 2021-10-31 10:58:10 | 显示全部楼层
本帖最后由 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个组合
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

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

也对哦
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-9-22 19:38

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表