簡単な方法 すべてのものを正しい順序で印刷することができれ
ば、不要なifステートメントを簡単に回避し、副作用として数学計算を最適化できます。
ピタゴラスのトリプルを見つけるために、最初の方法を変更したのでsqrt、すべての位置での呼び出しを避けることができます。
#include <stdio.h>
#include <math.h>
// all the loops will test numbers from 1 to 60 included
#define LIMIT 61
int main ( int argc, char * argv[] ) {
int i, j, k, k2, sum;
// print the first line of reference numbers
// start with a space to allign the axes
putchar(' ');
// print every digit...
for ( i = 1; i < LIMIT; ++i )
putchar('0' + i%10);
// then newline
putchar('\n');
// now print every row
for ( i = 1; i < LIMIT; ++i ) {
// first print the number
putchar('0' + i%10);
// then test if the indeces (i,j) form a triple: i^2 + j^2 = k^2
// I don't want to call sqrt() every time, so I'll use another approach
k = i;
k2 = k * k;
for ( j = 1; j < i; ++j ) {
// this ^^^^^ condition let me find only unique triples and print
// only the bottom left part of the picture
// compilers should be (and they are) smart enough to optimize this
sum = i * i + j * j;
// find the next big enough k^2
if ( sum > k2 ) {
++k;
k2 = k * k;
}
// test if the triple i,j,k matches the Pythagorean equation
if ( sum == k2 )
// it's a match, so print a '*'
putchar('*');
else
// otherwise print a space
putchar(' ');
}
// the line is finished, print the diagonal (with a '\\') and newline
printf("\\\n");
// An alternative could be to put the reference numbers here instead:
// printf("%c\n",'0' + i%10);
}
return 0;
}
このプログラムの出力は次のとおりです。
123456789012345678901234567890123456789012345678901234567890
1\
2 \
3 \
4 *\
5 \
6 \
7 \
8 * \
9 \
0 \
1 \
2 * * \
3 \
4 \
5 * \
6 * \
7 \
8 \
9 \
0 * \
1 *\
2 \
3 \
4 * * * \
5 \
6 \
7 \
8 * \
9 \
0 * \
1 \
2 * \
3 \
4 \
5 * \
6 * * \
7 \
8 \
9 \
0 * * \
1 \
2 * \
3 \
4 * \
5 * * \
6 \
7 \
8 * * * \
9 \
0 \
1 \
2 * \
3 \
4 \
5 * \
6 * * \
7 \
8 \
9 \
0 * * * * \
簡単
ではない方法 必要なものを印刷する別の方法を紹介します。
構造体に格納された文字列の配列を描画スペースとして使用することを検討してください。複雑に思えますが、出力手順を単純化して一般化することができます。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
char **img;
int rows;
int cols;
} Image;
Image *init_image( int r, int c, char s ) {
int i;
char *tmp = NULL;
Image *pi = malloc(sizeof(Image));
if ( !pi ) {
perror("Error");
exit(-1);
}
pi->rows = r;
pi->cols = c;
pi->img = malloc(r * sizeof(char*));
if ( !pi->img ) {
perror("Error");
exit(-1);
}
for ( i = 0; i < r; ++i ) {
tmp = malloc(c + 1);
if ( !tmp ) {
perror("Error");
exit(-1);
}
// fill with initial value (spaces) and add the terminating NULL
memset(tmp,s,c);
tmp[c] = '\0';
pi->img[i] = tmp;
}
return pi;
}
void free_image( Image *pi ) {
int i;
if ( !pi || !pi->img ) return;
for ( i = 0; i < pi->rows; ++i ) {
free(pi->img[i]);
}
free(pi->img);
free(pi);
}
void draw_axes( Image *pi ) {
int i;
if ( !pi ) return;
// I use to loops because cols can be != rows, but if it's always a square...
for ( i = 1; i < pi->cols; ++i ) {
pi->img[0][i] = '0' + i%10;
}
for ( i = 1; i < pi->rows; ++i ) {
pi->img[i][0] = '0' + i%10;
}
}
void draw_diagonal ( Image *pi, char ch ) {
int i, m;
if ( !pi ) return;
m = pi->rows < pi->cols ? pi->rows : pi->cols;
for ( i = 1; i < m; ++i ) {
pi->img[i][i] = ch;
}
}
void print_image( Image *pi ) {
int i;
if ( !pi ) return;
for ( i = 0; i < pi->rows; ++i ) {
printf("%s\n",pi->img[i]);
}
}
void draw_triples( Image *pi, char ch ) {
int i, j, k, k2, sum;
for ( i = 1; i < pi->rows; ++i ) {
k = i;
k2 = k * k;
// print only the left bottom part
for ( j = 1; j < i && j < pi->cols; ++j ) {
sum = i * i + j * j;
if ( sum > k2 ) {
++k;
k2 = k * k;
}
if ( sum == k2 ) {
pi->img[i][j] = ch;
// printf("%d %d %d\n",i,j,k);
}
}
}
}
int main(int argc, char *argv[]) {
// Initialize the image buffer to contain 61 strings of 61 spaces
Image *img = init_image(61,61,' ');
// draw the reference numbers at row 0 and column 0
draw_axes(img);
// draw a diagonal with character '\'
draw_diagonal(img,'\\');
// put a '*' if a couple of coordinates forms a Pythagorean triple
draw_triples(img,'*');
// print out the image to stdout
print_image(img);
free_image(img);
return 0;
}
このコードの出力は前のスニペットと同じですが、信じられないかもしれませんが、出力される関数呼び出しの数が少ないため、(少なくとも私のシステムでは) 高速stdoutです。
補遺
話が逸れましたが、前のコードを実際に (グレースケールの 512x512 PGM バイナリ形式のファイルとして) 画像ファイルを出力するように調整するのは楽しかったです。
すべてのピクセルは 16x16 の正方形のブロックに対応し、一致がない場合は黒く、アルゴリズムがブロック内で検出したトリプルの数に応じて明るくなります。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
char *img; // store data in a 1D array this time
int dim;
int samples;
} Image;
Image *init_image( int d, int z );
void free_image( Image *pi );
void add_sample( Image *pi, int r, int c );
void draw_triples_sampled( Image *pi );
void save_image( char *file_name, Image *pi );
int main(int argc, char *argv[]) {
// store the results in a 512x512 image, with each pixel corresponding
// to a 16x16 square, so the test area is 8192x8192 wide
Image *img = init_image(512,16);
draw_triples_sampled(img);
save_image("triples.pgm",img);
free_image(img);
return 0;
}
Image *init_image( int d, int z ) {
Image *pi = malloc(sizeof(Image));
if ( !pi ) {
perror("Error");
exit(-1);
}
pi->dim = d;
pi->samples = z;
pi->img = calloc(d*d,1);
if ( !pi->img ) {
perror("Error");
exit(-1);
}
return pi;
}
void free_image( Image *pi ) {
if ( !pi ) free(pi->img);
free(pi);
}
void add_sample( Image *pi, int r, int c ) {
// each pixel represent a square block of samples
int i = r / pi->samples;
int j = c / pi->samples;
// convert 2D indeces to 1D array index
char *pix = pi->img + (i * pi->dim + j);
++(*pix);
}
void draw_triples_sampled( Image *pi ) {
int i, j, k, k2, sum;
int dim;
char *val;
if ( !pi ) return;
dim = pi->dim * pi->samples + 1;
for ( i = 1; i < dim; ++i ) {
k = i;
k2 = k * k;
// test only bottom left side for simmetry...
for ( j = 1; j < i; ++j ) {
sum = i * i + j * j;
if ( sum > k2 ) {
++k;
k2 = k * k;
}
if ( sum == k2 ) {
add_sample(pi,i-1,j-1);
// draw both points, thanks to simmetry
add_sample(pi,j-1,i-1);
}
}
}
}
void save_image( char *file_name, Image *pi ) {
FILE *pf = NULL;
char v;
char *i = NULL, *end = NULL;
if ( !pi ) {
printf("Error saving image, no image data\n");
return;
}
if ( !file_name ) {
printf("Error saving image, no file name specified\n");
return;
}
pf = fopen(file_name,"wb");
if ( !pf ) {
printf("Error saving image in file %s\n",file_name);
perror("");
return;
}
// save the image as a grayscale PGM format file
// black background, pixels from gray to white
fprintf(pf,"P5 %d %d %d ",pi->dim,pi->dim,255);
end = pi->img + pi->dim * pi->dim;
for ( i = pi->img; i != end; ++i ) {
if ( *i == 0 )
v = 0;
else if ( *i < 10 )
v = 105 + *i * 15;
else
v = 255;
fprintf(pf,"%c",v);
}
close(pf);
}
出力画像は（ここに掲載するために一度PNGに変換したものです）これです。新たなパターンに注意してください。
