Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这题不用二维数组,直接一个字符一个字符输出的做法

Posted by Eov_Second at 2016-12-15 17:13:38 on Problem 3173 and last updated at 2016-12-15 17:17:28
题目可以等价于把自然数1-N按照三角形向右排开,最后再对9取模(起始值如果不是1,最后加上这个偏移就行了)

1 2 4 7
  3 5 8
    6 9
      10

观察每一行,其实这是一个二阶等差数列(相邻元素的差值构成等差数列)
二阶等差数列记为{A(n)},由于其各项的差构成等差数列,则
A(n+1) - A(n) = A(2)-A(1) + (n-1)d,其中d是对应一阶等差数列的差值,则不难推出
A(n) = A(1) + (n-1)[A(2)-A(1)] + [(n-1)(n-2)/2]*d

各行的A(1)也容易看出来就是自然数前n项和i*(i+1)/2

以第二行为例,A(1)=2*(2+1)/2=3,A(2)-A(1)=2, d = (A3-A2)-(A2-A1) = 1,则其对应的通项为
A(n) = 3 + (n-1)*2 + (n-1)(n-2)/2

各行的通项公式有了,假如起始值为k,则第i行第j个数字为
C(i,j) = (i*(i + 1) / 2 + (j - 1)*i + (j - 1)*(j - 2) / 2 + k - 1) % 9 + 1;

最后附上代码,对公式做了一些优化
int main()
{
    int n, i, j, k, t;
    scanf("%d%d", &n, &k);
    for (i = 0; i < n; i++)
    {
// 先补全行前的空格
        for (j = 0; j < 2 * i; j++)
            putchar(' ');
// 循环中的常数先计算出来
        t = i*(i + 3) / 2 + k - 1;
// 剩下的2n-1 - 2i个字符,是空格和数字交替,所以只要用奇偶性控制就好了
        for (j = 0; j < 2 * (n - i) - 1; j++)
        {
            if (j & 1)
                putchar(' ');
            else
            {
                int m = j / 2;  //实际上m才是真正每行第j个数字
                printf("%d", (t + m * (2 * i + m + 1) / 2) % 9 + 1);
            }
        }
        printf("\n");
    }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator