最近遇到了一道这样的算法题:
有这样一类定时器,每个定时器都每过 7 天,一个就会变两个。
但不是每个定时器都从 7 天开始倒数,比如有的定时器只剩下 2 天就会变两个,有的剩下 4 天就会变两个。
且如果是新分裂的定时器,得从 8 开始,因为新的得有 2 天的 “成长“ 期它才能开始分裂。
如果分裂了,那么原本的定时器计数会重置为 6,然后新分裂出来的定时器重置为 8 (为什么这样呢?因为 0 是算在里面的,所以重置为 6 就能保证再过第 7 天的时候,6 -> -1,然后重置为 6,产生新的;而新的又变成 8,是因为题目要求新的定时器得过 2 天才能开始它的第一轮分裂)。
因此根据上面的条件,比如有一个为 3 开始的定时器(当然也可以是 1,也可以是 5,算法要能满足 <= 8 开始即可):
经过 1 天:定时器值变 2
经过 1 天:变 1
经过 1 天:变 0
经过 1 天:变 6,8 两个,总共过了 4 天
经过 7 天:变 6,8,1 三个,总共过了 11 天
经过 2 天:变 4,6,6,8 四个,总共过了 13 天
经过 5 天:变 6,8,1,1,3 五个,总共过了 18 天
...
以此类推。(定时器为 6 的过 7 天分裂;定时器为 8 的过 9 天分裂,但分裂一次后按重置为 6 处理)
问:如果从最开始经过了 256 天,此时共有多少个定时器?
这道题目是传统的指数增长的变形,一般的题目包括第一次分裂,就每次固定都是经过多少天就分裂一次,这样只要算出天数内分裂了多少次,再 2 的 N 次方就能算出终态有多少个。但这个题目第一次分裂的剩余天数并不固定(3 只是示例,也可以是 1,也可以是 5),且分裂后新旧定时器首次运作时还有区别(老的重置为 6 继续运转,而新的从 8 开始,且分裂当天不扣减定时器,当然这个“新的”定时器一旦出生就不再新了,后续经过 9 天分裂,然后重置为 6 继续分裂工作)
例题给出的案例和最终答案是:
如最开始有 3,4,3,1,2 这 5 个定时器,
经过 256 天后将会变成 26984457539 个定时器。
例题中虽然给出了多定时器开始和最终答案,但并没有给出算法过程。其实只要解决了一个定时器的演化,其他的也都是一样的规律,那么第一个定时器按照上述规则,有没有什么算法思路可以计算出几百天后此时共有多少个定时器呢?(除了用链表一天天模拟之外)