经典算法详解(8)数的分组
题目:有10个任意的正整数,将其分为两组A和B,要求组A中每个数据的和与组B中每个数据的和之差的绝对值最小。请设计算法实现数的分组(找出一个答案即可)。
C++版本:
1 #include<iostream> 2 3 using namespace std; 4 5 void get_groupAB(int arr[]) { 6 int sum_a, sum_b; 7 int index, difference=0; 8 int i,i_copy; 9 //数组所有的元素求和给difference赋初值 10 for ( i = 0; i < 10; i++) { 11 difference += arr[i]; 12 } 13 //从0000000000到1111111111,尾数为零时,对应的数组元素划分给a数组,否则划分给b数组 14 for ( i = 0; i < 0x3FF; i++) { 15 sum_a = 0, sum_b = 0; 16 i_copy=i; 17 for (int j = 0; j < 10; j++) { 18 if ((i_copy & 1) == 0) { 19 sum_a += arr[9 - j]; 20 } 21 else { 22 sum_b += arr[9 - j]; 23 } 24 i_copy >>= 1; 25 } 26 if (difference > abs(sum_a - sum_b)) { 27 difference = abs(sum_a - sum_b); 28 index = i; //存储最小值对应的索引 29 } 30 if (difference == 0) { 31 break; 32 } 33 } 34 //存储分组 35 int sub_a[10], sub_b[10]; 36 int count_a=0, count_b=0; 37 for (i = 0; i < 10; i++) { 38 if ((index & 1) == 0) { 39 sub_a[count_a] = arr[9 - i]; 40 count_a++; 41 } 42 else { 43 sub_b[count_b] = arr[9 - i]; 44 count_b++; 45 } 46 index >>= 1; 47 } 48 //输出显示部分 49 cout << "group A:" << endl; 50 for (i = 0; i < count_a; i++) { 51 cout << sub_a[i] << endl; 52 } 53 cout << "group B:" << endl; 54 for (i = 0; i < count_b; i++) { 55 cout << sub_b[i] << endl; 56 } 57 cout << "difference:" << difference << endl; 58 } 59 60 int main(int argc, char *argv[]) { 61 62 int arr[10]; 63 int i=0; 64 while (i < 10) { 65 cin >> arr[i]; 66 i++; 67 } 68 get_groupAB(arr); 69 getchar(); 70 getchar(); 71 return 0; 72 }
思路:可以用一个10位的二进制数表示,对应位置为零时,分给一个组,为1时分给另外一个组;任何一个数都可以分给组A或者组B两种情况,故总的情况共有2^10,即1024种,其中不能全给A,也不能全给B,所以总共1024-2=1022种情况,进行枚举即可。另外如果出现差值为0时可以马上终止循环,因为不可能出现比0小的数了。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Java高级编程细节 模糊数据库database系统
什么是模糊数据库系统 模糊数据库系统指能处理模糊数据的数据库系统。 我们一般遇到的数据库都是具有二值逻辑和精确数据的。但是,在现实中还有很多不确定的模糊不清的事情。我们的大脑也是偏向于处理一些模糊事件,对这些模糊事件更感兴趣。当一件东西太ling清楚地展示在我们面前时,我们大脑就失去了对事物进行探索的欲望。这样就可以把不完全性、不确定性、模糊性引入数据库系统中,从而形成模糊数据库。自1965年美国的L.Z.扎德提出模糊理论以来,人们就对这个领域产生了极大兴趣。模糊理论应用不断扩大,作为流行的数据库更是受到了注意。 随着模糊理论体系的建立,人们可以用数量来描述模糊事件并能进行模糊运算。在数据库系统中,也可以将数学上的这种成果,如不完全性、不确定性、模糊性引入,从而形成模糊数据库。 模糊数据库的研究主要有两方面: 首先是如何在数据库中存放模糊数据,其次是定义各种运算、建立模糊数据上的函数。模糊数据的表示方法主要有模糊区间数、模糊中心数、模糊集合数和隶属函数等。 在模糊数据库中,如果把各记录值视为节点,把关系视为节点间的连线。一个模糊数据库就可以看成是一个复杂的...
- 下一篇
单元测试方法以及实例
为什么要测试? Web程序开发过程一般包括以下几个阶段:[需求分析,设计阶段,实现阶段,测试阶段]。其中测试阶段通过人工或自动来运行测试某个系统的功能。目的是检验其是否满足需求,并得出特定的结果,以达到弄清楚预期结果和实际结果之间的差别的最终目的。 测试的分类: 测试从软件开发过程可以分为: 单元测试 对单独的代码块(例如函数)分别进行测试,以保证它们的正确性 集成测试 对大量的程序单元的协同工作情况做测试 系统测试 同时对整个系统的正确性进行检查,而不是针对独立的片段 在众多的测试中,与程序开发人员最密切的就是单元测试,因为单元测试是由开发人员进行的,而其他测试都由专业的测试人员来完成。所以我们主要学习单元测试。 什么是单元测试? 程序开发过程中,写代码是为了实现需求。当我们的代码通过了编译,只是说明它的语法正确,功能能否实现则不能保证。 因此,当我们的某些功能代码完成后,为了检验其是否满足程序的需求。可以通过编写测试代码,模拟程序运行的过程,检验功能代码是否符合预期。 单元测试就是开发者编写一小段代码,检验目标代码的功能是否符合预期。通常情况下,单元测试主要面向一些功能单一的模块进...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS8编译安装MySQL8.0.19
- Docker安装Oracle12C,快速搭建Oracle学习环境
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- CentOS关闭SELinux安全模块
- CentOS7设置SWAP分区,小内存服务器的救世主
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题