js 如图,求算法
这是一个有趣的题目,我更为好奇的是,题中罗列一众太阳系的星星,为何没有地球呢???
不过没有关系,先给出答案:
运行结果如下:
拿星球来组合着玩儿是个新奇趣致又气势恢宏磅礴的想法,颇为值得仔细玩味。题目没有明确是需要排列,还是组合,事实上这会导致两种不同的可能性,因为在数学上“排列”和“组合”两者是有明确区别的。
依照题目所示,条件有两个:
(1) 七颗星星任意选取n个合并为1组,每种选择中至少一颗星星,最多七颗。
(2) 每组的结果不能重复。
但是——
题目没有指出是否需要“有顺序”,排列是指任意选取n个合并为一个组,不同顺序的组视为2个各不相同的组,例如:[金、木、水] 和 [金、水、木],在排列的情况下,它们是两个组,然而在组合的情况下,他们则是相同的组合。组合是指这3个星星在不同顺序下,它们只要个数相同,组中元素也相同,则认为两组是一样的,不看顺序,只论有无。它们同时存在则代表两者重复。
不论排列还是组合,我们先来计算两种方式它们各自能够合并成组的总数。
按排列公式计算7颗星星的所有组(注意不是组合)的可能性总数,假设为 A,则:
A = 7!/(7-7)! + 7!/(7-6)! + 7!/(7-5)! + 7!/(7-4)! + 7!/(7-3)! + 7!/(7-2)! + 7!/(7-1)!
= 5040 + 5040 + 2520 + 840 + 210 + 42 + 7
= 13699
以排列的方式将会产生13699种可能的组。
然而按组合公式来计算的话,可能性的组的总数将会少很多,假设组合方式的组的总数为C,则:
C = 7!/(7!*0!) + 7!/(6!*1!) + 7!/(5!*2!) + 7!/(4!*3!) + 7!/(3!*4!) + 7!/(2!*5!) + 7!/(1!*6!)
= 1 + 7 + 21 + 35+ 35 + 21 + 7
= 127
以组合的方式将会产生127种可能的组,它也正好等于 2^7 - 1,即2的7次方减1,这使人容易想到2进制编码,假设我们如下图这样看待每颗星星:
将每颗星星想象成一个位,7颗星星则有7位(如果有8位最好,刚好凑成2个字节),7位可以表达的正整数刚好是128,全部位0则代表某个组合内没有任何星星,假设空组合没有意义,所以减去1。
假设为1代表在组合中,0则不在,那么上图的组合结果就是:[日、金、木、土]
按排列的方式多达1.3万多种可能性,数量庞大,犹如置身于浩瀚而深邃、虚无而飘渺般的茫茫宇宙中使人彷徨失措。
所幸题主仅需其中的28种,当真是弱水三千,只取一瓢饮。
故此,使用组合方式可以骤然缩减组合的总数,区区百余个,使人轻松舒畅,仿佛等到黎明前漆黑的夜空中静悄悄地迎来天边的第一缕曙光。
选择是烦恼的根源,迷茫的因由。
巧之又巧,为何题主偏偏要、刚刚好、恰恰是28种组合?不偏不倚,不多不少,这让我颇费思量,为何对28这个数字这般执着?
不过后来发现,28 = 7 + 6 + 5 + 4 + 3 + 2 + 1,刚好是一个阶梯求和的结果。编写成程序仅需一个双重循环: