小金转呀转不晕矩阵

Time Limit: 1000MS MemoryLimit: 65536KB

Submit Statistic

Problem Description

众所周知，C语言的学习是我们程序设计基础的重点和主要内容。
或是高中、又或是初中，小金学会了使用杨辉三角，同时也了解杨辉三角的由来。他觉得杨辉三角是一个神奇的发现，从中可以发现很多很多神奇的规律。
杨辉三角既是多项式(a+b)^n展开之后的每个项的二次项系数规律，又是二项式系数在三角形中的一种几何排列。
本质特征: 两条斜边都是由数字1构成，而其余的数都是由他肩上的两个数字之和，如下表。
第1行: 1
第2行: 1 1
第3行: 1 2 1
第4行: 1 3 3 1
第5行: 1 4 6 4 1
第....行: .................
小金是一个好奇的孩子，他想知道一个n行的杨辉三角摆在一个矩阵中是什么样子的，又因为小金的脑子因为感冒烧坏了眼睛，看东西都是旋转的，所以他填数的时候是不断旋转杨辉三角去按行填写矩阵，如果杨辉三角旋转完毕之后矩阵还没有满，就在剩余的地方补0，具体情况如下图。

Input

 

多组输入。
每次输入占一行，有一个整数n，代表杨辉三角的行数. (1< =  n  < =  20).

 

Output

输出可填充的最小正矩阵，正矩阵是指长和宽相同的矩阵。
保证数据合法。

Example Input

2

Example Output

1 1
1 0

Hint

Author

2015级期末测试 Casithy


#include<stdio.h>

int  main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int i,a[21][21]={0},k,b[1000]={0};
        a[1][1] = 1;
        for(i=2;i<=n;i++)
        {
            for(k=1;k<=i;k++)
            {
                a[i][k] = a[i-1][k] +a[i-1][k-1];
            }
        }
       /*  for(i=1;i<=n;i++)
        {
            for(k=1;k<=i;k++)
            {
                printf("%d ",a[i][k]);
            }
        }
        printf("\n#\n");*/
        int j,o=n,m=0;
        i = 1;
        j = 0;
        while(1)
        {
            if(o==0)
            {
                break;
            }


            for(k=1;k<=o;k++)
            {
              b[++m] = a[++j][i];
            }
            o--;
            if(o==0)
            {
                break;
            }


            for(k=1;k<=o;k++)
            {
                b[++m] =a[j][++i];
            }
            o--;
            if(o==0)
            {
                break;
            }


            for(k=1;k<=o;k++)
            {
                b[++m] = a[--j][--i];
            }
            o--;


        }
        for(i=1;m>i*i;i++);


         int p = i;




        int u=0;
        for(i=1;i<=p*p;i++)
        {
            u++;
            printf("%d",b[i]);
            if(u%p==0)
            {
                printf("\n");


            }
            else
                printf(" ");
        }


    }




    return 0;

}

正解2：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int data[112][112];
int n;
int ans[112345], tail;

int init()
{
    memset(data,0,sizeof(data));
    memset(ans,0,sizeof(ans));
    tail = 0;
    data[1][1] = 1;
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            data[i][j] = data[i-1][j] + data[i-1][j-1];
//            cout << data[i][j] << ' ';
        }
//        cout << endl;
    }


    int x1 = 1, y1 = 1;
    int x2 = n, y2 = n;
    while (x1 <= x2 && y1 <= y2)
    {
        for (int i = x1; i <= x2; i++)
        {
            ans[tail++] = data[i][y1];
        }

        x1++;
        y1++;
        for (int i = y1; i <= y2; i++)
        {
            ans[tail++] = data[x2][i];
        }

        x2--;
        y2--;
        for (int i = 0; x2-i >= x1 && y2-i >= y1; i++)
        {
            ans[tail++] = data[x2-i][y2-i];
        }

        x1++;
        y2--;
    }
}

int main()
{
    string str;
    while (cin >> n)
    {
        if (n == 1)
        {
            cout << 1 << endl;
            continue;
        }
        init();
        int k;
        for (int i = 0; i < 100; i++)
            if (i*i >= tail)
            {
                k = i;
                break;
            }
        for (int i = 0; i < k*k; i++)
        {
            if (i && i%k == 0)
                cout << endl;
            else if (i)
                cout << ' ';
            cout << ans[i];
        }
        cout << endl;
    }
}