今日のお題は「ピタゴラス数を求める」です。
Ｃプログラミング専門課程の準備 ■アルゴリズムの格差でいきなり、お題として挙げられている例ですが、せっかくなので自分で解いてみようと。
ま、日曜プログラミングですから（^^;
ピタゴラスの定理って言ったら、直角三角形の斜辺の長さの二乗は他の辺の二乗を足した値に等しい・・・ですが、その中でも例えば、3:4:5と6:8:10は公約数の関係にあるので、そういう数を省いたモノがピタゴラス数になる・・・です。
上記を式で表すと、斜辺の長さをZ、他をX,Yと表すと
Z^2 = X^2 + Y^2
です。
そのまま、XYZの値を代入して調べる方法もあるのですが、
ピラゴラス数でググルとこんなページに辿り着きました。
m>n
mとnの和は奇数になる。
という条件で、
X = m^2 - n^2
Y = 2 * m * n
Z = m^2 + n^2
という式を使うと、かなり簡略化出来ると。
#include <stdio.h>
#include <stdlib.h>
#define SAIDAI 10000
typedef struct PITA {
struct PITA *back;
long m;
long n;
long x;
long y;
long z;
struct PITA *next;
}_PITA;
struct PITA *save_pita(struct PITA *,long ,long , long , long , long);
void print_pita(struct PITA *);
struct PITA *pita_slow();
struct PITA *pita_fast();
int main (int argc, const char * argv[]) {
char choice;
unsigned long sTime, eTime;
printf("ピタゴラス数を求める\n");
printf("選択せよ(1=低速、2=高速）");
if(scanf("%c%*c", &choice) == EOF) {
return -1;
}
switch(choice) {
case '1' :
print_pita(pita_slow());
break;
case '2' :
print_pita(pita_fast());
break;
default :
return -1;
}
return 0;
}
/***********************************
ピタゴラス数を表示する
**********************************/
void print_pita(struct PITA *pita) {
struct PITA *q;
int count = 0;
while(pita != NULL) {
count++;
q = pita;
printf("%5ld (%d, %d) = (%d, %d, %d)\n", count, pita->m, pita->n, pita->x, pita->y, pita->z);
free(pita);
pita = q->back;
}
}
/***********************************
ピタゴラス数を保存する
**********************************/
struct PITA *save_pita(struct PITA *old,long m,long n, long x, long y, long z){
struct PITA *new;
new = NULL;
if((new = (struct PITA *)malloc(sizeof(struct PITA))) == NULL) {
printf("memory allocation error.¥n");
exit(EXIT_FAILURE);
}
new->m = m;
new->n = n;
new->x = x;
new->y = y;
new->z = z;
new->back = old;
new->next = NULL;
if(old != NULL) {
old->next = new;
}
return new;
}
/***********************************
ピタゴラス数を求める（低速版）
**********************************/
long gcm(long a, long b) {
long c;
if(a<b) return gcm(b,a);
c = a % b;
if(c == 0) return b;
return gcm(b, c);
}
struct PITA *pita_slow() {
long a, b, c, d;
struct PITA *pita;
pita = NULL;
for(c=1; c<=SAIDAI; ++c) {
for(b=1; b<c; ++b) {
if(gcm(c,b) != 1) continue;
for(a=1; a<b; ++a) {
d= a*a + b*b - c*c;
if(d>0) break;
if(d==0) {
pita = save_pita(pita, 0, 0, a, b, c);
}
}
}
}
return pita;
}
/***********************************
ピタゴラス数を求める（高速版）
**********************************/
struct PITA *pita_fast() {
long m, n;
long x, y, z;
struct PITA *pita;
pita = NULL;
for(m=SAIDAI; m>0; m--) {
for(n=m; n>0; n--) {
x = m*m - n*n;
y = 2*m*n;
z = m*m + n*n;
if(x > 0 && y > 0 && z > 0) {
if(((m + n) % 2) == 1) {
if((x*x + y*y) == z*z) {
// ピタゴラス数
pita = save_pita(pita, m, n, x, y, z);
}
}
}
}
}
return pita;
}
お題通りにトライしてみましたが、確かに全然速度が違います。
今ではちょっとしたアルゴリズムの改善で高速化するのと、機械を買い換えて高速化するのではどちらが良いのか？という話もありますが、ここまで高速化できるとなれば、やはり考えざるを得ないでしょう。
という事を考えたり、考えなかったり。
ところで、Visual Studioで同じコードをデバッグで実行させると、free()で異様に時間が掛かります。
（Xcodeとか、gccでは問題ないのに）
これは何故なのか？という事はちょっと解明できずじまいですが。
コメント