你如何找到一个数字属于弗洛伊德三角中的哪一行和哪一列

Question

你如何找到一个数字在弗洛伊德三角中属于哪一行和哪一列？ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

例如，

33在第8行第5列（输入33→输出第8行第5列）
46 在第 10 行第 1 列
27在第7行第6列

在此先感谢您！

Answer 1

注意第 n 行 ends with value n*(n+1)/2。所以你可以制作二次方程并求解它以获得给定数字 k

的行号

n*(n+1)/2 = k
n^2 + n - 2*k = 0
D = 1 + 8*k
n_row = Ceil((-1 + Sqrt(D)) / 2)   //round float value up

例如，对于 k=33，您可以计算

   n_row = Ceil((-1 + Sqrt(265)) / 2) = 
           Ceil(7.639) =
           8

有n_row，找到上一行的最后一个数字和k在当前行的位置

  n_Column = 33 - n_row * (n_row - 1) / 2 = 
            33 - 28 = 
            5

行查找的替代方法的伪代码：

 sum = 0
 row = 0
 while sum < k do
      row++  
      sum = sum + row

Answer 2

我认为这种方法在某种程度上更自然：

       #include <iostream>
       size_t getRow(size_t n)
       { // just count the rows, and when you meet the number, return the row
           size_t row(0), k(1);
           for (row = 1; row <= n; row++)
           {
               for (size_t j = 1; j <= row; j++)
               {
                   if (k == n)
                   {
                       goto end;
                   }
                   k++;
               }
           }
           end:return row;
       }
       size_t getCol(size_t n)
       { /* well, we have already found the row, so now knowing that every n-th row starts
       with n(n-1)/2+1 and ends with n(n+1)/2, just count the columns and when you
       meet the number (and that surely will happen), just return the column and you're done*/
           size_t col(1);
           size_t r = getRow(n);
           for (size_t j = r * (r - 1) / 2+1; j <= r*(r+1)/2; j++)
           {
               if (j == n)
               {
                   break;
               }
               col++;
           }    
           return col;
       }
       int main()
       {
           size_t n;
           std::cin >> n;
           std::cout << "Number " << n << " lies in row " << getRow(n) << ", column " << getCol(n) << " of the Floyd's triangle.\n";

           return 0;
       }

Answer 3

在 python 中看起来像这样（如果您不想使用 sqrt）：

def rc(n):
    # rc(1) = (1, 1); rc(33) -> (8, 5)
    assert n > 0 and int(n) == n
    sum = 0
    row = 0
    while sum < n:
        row += 1
        sum += row
    col = n - sum + row
    return row, col

你如何找到一个数字属于弗洛伊德三角中的哪一行和哪一列

How do you find which row and column a number belongs to in Floyd Triangle

algorithm

math

triangular

pascals-triangle