首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

一个数学有关问题,希望和大家一起讨论一下。

2013-08-16 
一个数学问题,希望和大家一起讨论一下。。已知:递增数列 an{a1,a2,a3,...an }的函数为:a(n),求递增数列bn{b1

一个数学问题,希望和大家一起讨论一下。。
已知:递增数列 an{a1,a2,a3,...an }的函数为:a(n),
求递增数列bn{b1,b2,b3,...,bn}的函数b(n)
满足:an和bn的交集为空,an和bn的并集为所有正整数
例如:当a(n)=2n的时候,b(n)=2n-1
当a(n)=3n的时候 b(n)=3(n-1)/2+1

最简单的,a(n)=5n
求b(100) 互斥数列
[解决办法]
这个特例有O(1)的办法,b是4个数一组构成mod 5=1,2,3,4的一组。b(100)就应该是5*24+4。
对于一般的a,可以用二分的办法。对于一个数x,如果a(n)<x<a(n+1),那么b(x-n) = x。
[解决办法]
本来就是一个简单的数学题目,数据分类如下:4个b,1个a依次循环,第100个b,之前有24个a,因此结果为100+24=124
[解决办法]
直接用乘除法,显然复杂度是常数
b(n)=n+(n-1)/4  应该就是这样了
[解决办法]

引用:
Quote: 引用:

本来就是一个简单的数学题目,数据分类如下:4个b,1个a依次循环,第100个b,之前有24个a,因此结果为100+24=124


要求算法复杂度为o(1)

那就必须对于每个a都要个别分析。没有通用的办法的。

热点排行