c++ - 在三角矩阵中找到位置

Question

我有以列主要方式存储的对称矩阵。但我只存储矩阵的下半部分以节省空间。

所以我的矩阵看起来像这样:

---

1
2 6 
3 7 10
4 8 11 13
5 9 12 14 15

---

我必须编写代码来根据该矩阵的索引 i(row),j(col) 查找元素在该矩阵中的位置。

我是这样写的:

pos = (n*j) - j*j/2 + (i - j);

pos - 我的元素在矩阵中的位置 - a[pos]n - 矩阵的大小

不幸的是，它总是找不到好的位置。我编写程序来测试它并打印:

1
2 6 
3 7  11
4 8  12 14
5 9  13 15 17
6 10 14 16 18 18

我知道它是这样发生的，因为当我们除以 j*j/2 时，我们得到 int/int。但我不知道该怎么做才能让它正常工作。

请帮忙!

Answer 1

让我们一次检查一列的计算，假设:

i <= j
1 <= i <= n
1 <= j <= n:

然后:

i=1, pos=j
i=2, pos=n+j-1
i=3, pos=n+n-1+j-2
i=4, pos=n+n-1+n-2+j-3
etc...

我们可以从中推导出一个通用公式:

p=n*(i-1)+j-(i-1)*i/2

可以使用简单的 C# 来测试:

using System;
using System.IO;

namespace Stream
{
  class Program
  {
    static void Main (string [] args)
    {
      for (int j = 1 ; j <= 5 ; ++j)
      {
        for (int i = 1 ; i <= 5 ; ++i)
        {
          Console.Write (GetIndex (i, j).ToString ("00 "));
        }
        Console.WriteLine ("");
      }
    }

    static int GetIndex (int in_i, int in_j)
    {
      int
        n = 5,
        i = Math.Min (in_i, in_j),
        j = Math.Max (in_i, in_j);


      return n * (i - 1) + j - (i - 1) * i / 2;
    }
  }
}