人寿研发9.29编程3【python解法】
题目见：机器人家族划分
思路：
1、分割序列，选择分割点的位置，对于每个子序列进行是否为递增序列子集的检验。因为要划分到最小的家族，从最少的分割点开始遍历，一旦所有子序列满足递增子序列，停止循环。
2、检验是否为递增序列的子序列：
1) 序列排序
2) 子序列长度小于等于2时，自动划分为1个家族
3) 子序列长度为3时，求前两位差和后两位差的最大公约数
求两个值的最大公约数：
用 大值%小值 取模，然后将模作为小值，再用小值作为大值继续取模，直到模为0，则分母即为最大公约数
4) 子序列长度大于3时，依次求相邻差值的最大公约数，最小的数为序列的最大公约数，一旦最大公约数等于1，停止循环，判定为非自增子序列，否则为递增子序列。
from itertools import combinations def max_gys(a,b): #两个数的最大公约数 a,b = max([a,b]),min([a,b]) while b != 0: tmp = a%b a = b b = tmp return a def is_from_dizeng(list0): #是否来自于递增序列的子序列 list0 = sorted(list0) flag = 0 if len(list0)<=2: flag = 0 else: list0 = sorted(list0) max_d = max_gys(list0[1]-list0[0],list0[2]-list0[1]) if max_d == 1: flag = 1 else: for i in range(2,len(list0)-1): cur_d = max_gys(max_d,list0[i+1]-list0[i]) if cur_d == 1: flag = 1 break else: if cur_d < max_d: max_d = cur_d continue if flag == 0: return True else: return False l_test = [4,2,6,8,5,3,1,7]#测试例子 lens = len(l_test) nums = 1 flag = 0 while nums < lens: pos_num = nums - 1 if pos_num == 0: if is_from_dizeng(l_test): flag = 1 break else: pos_list = list(combinations(list(range(0,lens)),pos_num)) for pos_l in pos_list: pos_l = [0]+list(pos_l) for i in range(0,len(pos_l)-1): if is_from_dizeng(l_test[pos_l[i]: pos_l[i+1]]): flag = 1 continue else: flag = 0 break if flag == 1: if is_from_dizeng(l_test[pos_l[-1]:]): flag = 1 break else: flag = 0 if flag == 1: print(nums)#返回家族数目 print(pos_l)#返回分割点位置 break else: nums += 1 if flag == 0: print(nums)
