posts - 195, comments - 34, trackbacks - 0, articles - 1

生成zigzag序

Posted on 2010-05-03 17:26 小强摩羯座 阅读(265) 评论(0)  编辑  收藏
生成zigzag序,
1、分析关键,在以zigzag序的每一行,以上三角为计算对象分别以i或j的增序排列,因此利用这一点就可以得出结果。
    程序中s即为zigzag行号,而变换则以i和j交替。所以程序很简单。

 

#include<iostream>
#include<iomanip>

using namespace std;

#define M 255

void zigzag(const int N)
{
    int squa = N * N;
    int a[M][M]={0};
    for (int i = 0;i < N; i++)
    {
        for (int j = 0;j < N;j++)
        {
            int s = i + j;
            if ( s < N)
            {
                 a[i][j] = s * (s+1)/2 + ( (s %2 !=0)?i:j);//注意?:的优先级低于+
            }
            else
            {
                int sn = (N-1-i) + (N-1-j);
                a[i][j] = squa - sn * (sn+1)/2 - (N - ( (sn%2 != 0)? i:j));
            }
        }
    }

    for (int i=0; i < N; i++)
    {
        for (int j = 0;j < N;j++)
        {

            cout<<setw(4)<<a[i][j]<<",";
        }
        cout<<endl<<endl;
    }
}

int main()
{
 zigzag(5);
 cout<<endl;
 
 zigzag(8);
 cout<<endl;

    return 0;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void zigzag(int n)
{
int **a =(int**) malloc(n*sizeof(int *)); //分配空间

if(NULL == a)
return ;
int i;
for(i = 0; i < n; i++) {
        if((a[i] =(int*) malloc(n * sizeof(int))) == NULL) {
            while(--i>=0)
                free(a[i]);
            free(a);
            return;
        }
    }

bool flag = false; //这个标志位用来判断是从45度角生成还是225度角生成
int count = 0;
for(i=0; i<n; i++) //生成的上半部分的数据
{

if(flag)
{
   for(int r = 0; r<=i; r++)
   {
    a[r][i-r] = count;
    count++;
   }
   flag = false;
}
else
{
   for(int r = i; r>=0; r--)
   {
    a[r][i-r] = count;
    count++;
   }
   flag = true;
}
}
for(i=n-1; i>=0; i--) //生成的是下半部分的数据
{
// cout<<i<<endl;
if(flag)
{
   for(int r = 0; r<=i-1; r++)
   {
    int r1 = n-i+r;       //代表当前行
    int c1 = 2*n-i-1-r1; //代表当前列
    a[r1][c1] = count;
    count++;
   }
   flag = false;
}
else
{
   for(int r = i-1; r>=0; r--)
   {
    cout<<"ddd"<<endl;
    int r1 = n-i+r;
    int c1 = 2*n-i-1-r1;
//   cout<<r1<<","<<c1<<endl;
    a[r1][c1] = count;
    count++;
   }
   flag = true;
}
}
for(int r = 0; r<n; r++)
{
for(int c=0; c<n; c++)
   cout<<a[r][c]<<",";
cout<<endl;
}
}
int main()
{
int n;
cin>>n;
zigzag(n);
return 0;
}
网上还有一个人写了一个比较巧的算法:
/**
* 得到如下样式的二维数组
* zigzag(jpeg编码里取象素数据的排列顺序)
*
*   0, 1, 5, 6,14,15,27,28,
*   2, 4, 7,13,16,26,29,42,
*   3, 8,12,17,25,30,41,43,
*   9,11,18,24,31,40,44,53,
*   10,19,23,32,39,45,52,54,
*   20,22,33,38,46,51,55,60,
*   21,34,37,47,50,56,59,61,
*   35,36,48,49,57,58,62,63
*/

#include <stdio.h>
int main()
{
    int N;
    int s, i, j;
    int squa;
    scanf("%d", &N);
    /* 分配空间 */
    int **a = malloc(N * sizeof(int *));
    if(a == NULL)
        return 0;
    for(i = 0; i < N; i++) {
        if((a[i] = malloc(N * sizeof(int))) == NULL) {
            while(--i>=0)
                free(a[i]);
            free(a);
            return 0;
        }
    }
    /* 数组赋值 */
    squa = N*N;   
    for(i = 0; i < N; i++)
        for(j = 0; j < N; j++) {
            s = i + j;
            if(s < N)
                a[i][j] = s*(s+1)/2 + (((i+j)%2 == 0)? i : j);
            else {
                s = (N-1-i) + (N-1-j);
                a[i][j] = squa - s*(s+1)/2 - (N - (((i+j)%2 == 0)? i : j));
            }
        }
    /* 打印输出 */   
    for(i = 0; i < N; i++) {
        for(j = 0; j < N; j++)
            printf("%-6d", a[i][j]);
        printf("\n");
    }
    return 0;
}




只有注册用户登录后才能发表评论。


网站导航: