作者znmkhxrw (QQ)
看板Math
标题[代数] 找两个离散函数的显式
时间Fri Aug 18 01:03:25 2023
请教一下这个问题:
令N为自然数
令S:= N+(N-1)+...+1 = (N+1)*N/2
令i€{1,2,...,S}
我们把S拆成N, N-1, N-2,...,1共N组, 第一组有N个1加起来, 第N组有1个1加起来
即第k组有(N-k+1)个1加起来
因此对於任何i, 我们都能定义一组唯一的数对i=(a_i, b_i)
其中a_i是所在的第几组, b_i是这一组的第几个(照i递增排列)
如下N=4的举例:
S = 10
i€{1,2,...,10}
N=4: i=1 → (a_i,b_i) = (1,1)
=2 = (1,2)
=3 = (1,3)
=4 = (1,4)
N-1=3: i=5 → (a_i,b_i) = (2,1)
=6 = (2,2)
=7 = (2,3)
N-2=2: i=8 → (a_i,b_i) = (3,1)
=9 = (3,2)
N-3=1: i=10 → (a_i,b_i) = (4,1)
我想问对於任何的正整数N, i€{1,..,S}
a_i跟b_i有没有显式公式
(我知道电脑用loop逐次从N开始减, 还有剩就组数加1, 然後继续减N-1
直到即将减的下一个导致负数的时就知道是在当前这组
但是我的需求是a_i与b_i的函数长相通式)
谢谢帮忙~
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.230.137.78 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1692291807.A.7EE.html
1F：推 Vulpix : a_i = ceil( N+0.5 - sqrt( (N+0.5)^2 - 2i ) )08/18 10:21
2F：→ Vulpix : b_i = i - a_i( a_i - 1 )/208/18 10:22
哇V大这怎麽找的啊 这长相难怪我用线性的式都式不出来XDDD 好猛
3F：推 Vulpix : 就解不等式啊:)08/18 18:13
4F：→ Vulpix : 你想想看 a_{k(k+1)/2} 是多少。08/19 01:23
5F：→ Vulpix : 写错了，是 a_{k(2N-k+1)/2}。08/19 01:24
b_i = i - a_i( a_i - 1 )/2
这个代入例子怪怪的? i=9时, a_i=3, b_i=2
但是 b_i = 2
i - a_i( a_i - 1 )/2 = 9 - 3*2/2 = 6
不相等
我是得到 i=(2N-a_i+2)*(a_i-1)/2 + b_i这个等式然後想不到怎麽得到a_i或是b_i
刚刚由你说"不等式"以及看到ceil, 我写出了:
(2N-k+2)*(k-1)/2 < i <= (2N-k+2)*(k-1)/2+N-k+1, 其中k就是a_i
该不会V大你姐的不等式就是这个吧...?
左边跟右边都是k的二次多项式P_L(k), P_R(k), 凹口向下
因此解P_L(k)=i的两根为r_1<=r_2(假设为实根), 因此k<r1或是k>r2
同理解P_R(k)=i的两根为r_3<=r_4(假设为实根), 因此r3<=k<=r4
是解这些东西吗...@@?
※ 编辑: znmkhxrw (123.241.88.179 台湾), 08/19/2023 03:19:41
6F：推 Vulpix : 所以是 b_i = i - a_i(2N-a_i+1)/2，前面写错了。08/19 08:34
7F：→ Vulpix : b_i = i - (a_i-1)(2N-a_i+2)/2，前面又写错了。08/19 08:47
8F：→ Vulpix : 那个……小的 r 应该都是负的。08/19 08:48
了解~我再硬爆出来看看, 谢谢V大~
※ 编辑: znmkhxrw (123.241.88.179 台湾), 08/24/2023 16:12:39