作者etrexetrex (moonet)
看板Prob_Solve
标题Re: [问题] 上三角矩阵循序储存公式推导
时间Sat Jun 7 20:32:30 2008
※ 引述《jones86723 (jones)》之铭言：
: 其实这问题不知道要Po哪，所以想请教大大这简单的原理
: 假设有一个上三角矩阵式是
: 1 1 1 1
: 1 1 1 0
: 1 1 0 0
: 1 0 0 0
: 则A32是第9个
: 那麽这个9的公式是
: loc = n*(i-1) - i*(i-1)/2 + j
: loc=9;
: 我是想知道要如何反推这个公式
: 拜托~~~~
1 2 3 4
1 1 2 3 4
2 5 6 7
3 8 9
4 10
1 2 3 4
1 0+1 0+2 0+3 0+4
2 4+1 4+2 4+3
3 7+1 7+2
4 9+1
a1 a2 a3 a4 (j=0)
0 4 7 9
a1 = 1+2+3+4 - 1+2+3+4
a2 = 1+2+3+4 - 1+2+3
a3 = 1+2+3+4 - 1+2
a4 = 1+2+3+4 - 1
ai = (1+n)*n/2 - (1+n-i+1)*(n-i+1)/2
= (2in - i^2 - 2n + 3i - 2)/2
loc(i,0) = (2in - i^2 - 2n + 3i - 2)/2
求函数
loc = (2in - i^2 - 2n + 3i - 2)/2
f(i) = (2in - i^2 - 2n + 3i - 2)/2 = loc
求反函数
i = (n + 3/2) - sqrt(n^2 + n + 1/4 - 2loc)
f'(loc) = (n + 3/2) - sqrt(n^2 + n + 1/4 - 2loc) = i
验证
1 = (4 + 3/2) - sqrt(4^2 + 4 + 1/4 - 2*0) = 5.5 - 4.5 = 1
2 = (4 + 3/2) - sqrt(4^2 + 4 + 1/4 - 2*4) = 5.5 - 3.5 = 2
3 = (4 + 3/2) - sqrt(4^2 + 4 + 1/4 - 2*7) = 5.5 - 2.5 = 3
4 = (4 + 3/2) - sqrt(4^2 + 4 + 1/4 - 2*9) = 5.5 - 1.5 = 4
建表
i j
loc f'(loc-1) [f'(loc-1)](取高斯) f(i) loc - f(i)
1 1 1 0 1
2 1点多 1 0 2
3 1点多 1 0 3
4 1点多 1 0 4
5 2 2 4 1
6 2点多 2 4 2
7 2点多 2 4 3
8 3 3 7 1
9 3点多 3 7 2
10 4 4 9 1
解
f(i) = (2in - i^2 - 2n + 3i - 2)/2
f'(loc) = (n + 3/2) - sqrt(n^2 + n + 1/4 - 2loc)
i = [f'(loc-1)]
j = loc - f(i)
= loc - f([f'(loc-1)])
弄了一个半小时反函数一直算错 = =
--
blog:
http://etrex.blogspot.com/
site:
http://web.ntust.edu.tw/~B9409041/
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.120.112.49
※ 编辑: etrexetrex 来自: 122.120.112.49 (06/07 20:43)