python求两序列的和最小差值序列,python最小差值序列,有两个序列a,b,大小都
python求两序列的和最小差值序列,python最小差值序列,有两个序列a,b,大小都
有两个序列a,b,大小都为n,序列元素的值任意整形数,无序;
要求:通过交换a,b中的元素,使[序列a元素的和]与[序列b元素的和]之间的差最小。
算法
将两序列合并为一个序列,并排序,为序列Source拿出最大元素Big,次大的元素Small在余下的序列S[:-2]进行平分,得到序列max,min将Small加到max序列,将Big加大min序列,重新计算新序列和,和大的为max,小的为min。python实现代码def mean( sorted_list ): if not sorted_list: return (([],[])) big = sorted_list[-1] small = sorted_list[-2] big_list, small_list = mean(sorted_list[:-2]) big_list.append(small) small_list.append(big) big_list_sum = sum(big_list) small_list_sum = sum(small_list) if big_list_sum > small_list_sum: return ( (big_list, small_list)) else: return (( small_list, big_list))tests = [ [1,2,3,4,5,6,700,800], [10001,10000,100,90,50,1], range(1, 11), [12312, 12311, 232, 210, 30, 29, 3, 2, 1, 1] ]for l in tests: l.sort() print print "Source List:\t", l l1,l2 = mean(l) print "Result List:\t", l1, l2 print "Distance:\t", abs(sum(l1)-sum(l2)) print '-*'*40
输出结果
Source List: [1, 2, 3, 4, 5, 6, 700, 800]Result List: [1, 4, 5, 800] [2, 3, 6, 700]Distance: 99-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*Source List: [1, 50, 90, 100, 10000, 10001]Result List: [50, 90, 10000] [1, 100, 10001]Distance: 38-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*Source List: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]Result List: [2, 3, 6, 7, 10] [1, 4, 5, 8, 9]Distance: 1-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*Source List: [1, 1, 2, 3, 29, 30, 210, 232, 12311, 12312]Result List: [1, 3, 29, 232, 12311] [1, 2, 30, 210, 12312]Distance: 21-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
相关内容
- python实现Bogo排序算法,pythonbogo排序,Bogo算法定义下面是
- python set 使用介绍,pythonset,Set是简单对象的无需集
- python读写zip格式文件,python读写zip,Python自带模块zi
- python字符串str和字节数组相互转化,pythonstr,# bytes obj
- python使用正则表达式验证ip地址,python正则表达式,pyt
- webpy 实现301永久重定向的方法,webpy301重定向,webpy内置
- django做301,302重定向代码,django302,下面代码是django实
- python的问号表达式,python问号表达式,python中没有c语言
- Python实现将Html转换为UBB,pythonhtml转换ubb,python实现htm
- python使用PyPDF解析PDF文件,pythonpypdf解析pdf,pyPDF模块提供
评论关闭