生成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;
}