三角螺旋阵

三角螺旋阵

时间： 1ms        内存：128M

描述：

方阵的主对角线之上称为“上三角”。
请你设计一个用于填充n阶方阵的上三角区域的程序。填充的规则是：使用1，2，3….的自然数列，从左上角开始，按照顺时针方向螺旋填充。

输入：

程序运行时，从标准输入获得整数n（3~20）

输出：

程序输出：方阵的上三角部分。
要求格式：每个数据宽度为4，右对齐。

示例输入：

3

示例输出：

   1   2   3
   6   4
   5

提示：

参考答案（内存最优[752]）：

/*三角螺旋阵*/
#include<stdio.h>  
int main()  
{     
    int low,i,j,hi,n;     
    int a[80][80];    
    while(scanf("%d",&n)!=EOF)//输入行数  
    {  
        low=0;  
        hi=n;  
        for(j=1;j<=n*(n+1)/2;low++)//n行螺旋共有n*(n+1)/2个数,将1~n*(n+1)/2依次填入到对应位置           
        {  
            for(i=low;i<hi-low;i++) 
                a[low][i]=j++;  
            for(i=low+1;i<hi-low;i++)  
                a[i][hi-i-1]=j++;  
            for(i=(hi-low)-2;i>low;i--)  
                a[i][low]=j++;  
            hi--;  
        } 
        for(i=0;i<n;i++) 
        { 
            for(j=0;j<n-i;j++) 
                printf("%4d",a[i][j]);  
            printf("\n");  
        } 
    } 
    return 0;  
} 

参考答案（时间最优[0]）：

#include<stdio.h>
#include<string.h>
#include <iostream>
using namespace std;  
//输入n，输出n行的上三角螺旋阵
//如n=3时，输出为：
//1 2 3
//6 4
//5
  
typedef struct _pos 
{
    int rows;
    int cols;
}pos;
  
void output(int * A,int n)
{
    int index = 0;
    //一共打印n行
    for(int i=n;i>=1;i--)//每行需要打印的元素个数
    {
        for(int j=1;j<=i;j++)
        {
            printf("%4d",A[index]+1);
            index ++;
        }
        printf("\n");
    }
}
  
  
void puttriangle(int n)
{
    int * A = NULL;
    pos * posN = NULL;
    int m = n*(n+1)/2;
    A = new int[m];
    posN = new pos[m];
    int currow , curcol ,curiter, curnum;
  
    currow = 0;
    curcol = -1;
    curiter = 0;
    curnum = 0;//实际从1开始
  
    //共需要迭代n次
    for(int i=n;i>=1;i--)//每次迭代的元素个数
    {
        curiter ++;
        for(int j=1;j<=i;j++)
        {
  
            if(curiter % 3 == 1)//从左到右横向产生序列
            {       
                curcol ++;
            }
            else
            if(curiter % 3 == 2)//沿对角线方向向下产生序列
            {
                currow ++;
                curcol --;
            }
            else//从下到上纵向产生序列
            {
                currow --;
            }
              
            posN[curnum].rows = currow;
            posN[curnum].cols = curcol;
            curnum ++;
  
        }
  
    }
  
  
    memset(A,0,sizeof(A));
  
    //根据得到的位置信息重新调整序列
    for(int k=0;k<m;k++)//每次迭代的元素个数
    {
        int startidx = 0;
        for(int s=0;s<posN[k].rows;s++)
            startidx += (n-s);
        int index = startidx + posN[k].cols;
        A[index] = k;
    }
      
    output(A,n);
      
    delete [] A;
    delete [] posN;
      
}
  
  
int main()
{
    int n ;
		scanf("%d",&n);
    puttriangle(n);
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。