=============================================================================== 2002 年 06 月 19 日(水) 2002 年度「応用数理C3」「計算数学1」 岩瀬順一 =============================================================================== == 020619a.c == #include #include #include #include #define N 26 /* ソートするものの個数 */ #define MAX 99 /* 数値データは 0 ... MAX */ #define swap(I,J) { int tmp = a[(I)]; a[(I)] = a[(J)]; a[(J)] = tmp; } int myrand(int max); void print(int j); void heapsort(void); void downheap(int i, int n); int a[N]; main() { int i; srand((unsigned)time(NULL)); /* 現在時刻で乱数の種を初期化 */ for (i=0; i=0; i--) { /* ヒープの構成(=全体を並べ替えてヒープに)*/ downheap(i, N-1); } print(N); puts("ヒープが完成しました."); for (i=N-1; i>0; i--) { swap(0, i); print(i); printf("%d 項以降は決定しました.\n", i); downheap(0, i-1); /* ヒープの再構成 */ print(i); printf("第 0 項から第 %d 項までをヒープに再構成しました.\n", i-1); } } /* a[i] から a[n] までをヒープにする(←日本語が変かも)。a[i] の子から先の */ /* 世代はすでにヒープになっていると仮定する */ void downheap(int i, int n) { print(n+1); if (2*i+1 > n) { /* 子がないとき */ return; } if (2*i+1 == n) { /* 子が片方のみのとき */ if (a[i] >= a[n]) { /* その子との間の大小関係 OK のとき*/ return; } else { swap(i, n); return; } } /* ここにくるのは両方の子がいるとき */ if (a[2*i+1] <= a[i]) { if (a[2*i+2] <= a[i]) { /* a[i] が最大のとき */ ; } else { /* a[2*i+1] <= a[i] < a[2*i+2] のとき */ swap(i, 2*i+2); downheap(2*i+2, n); } } else { /* a[i] < a[2*i+1] のとき */ if (a[2*i+2] <= a[i] || a[2*i+2] < a[2*i+1]) { swap(i, 2*i+1); downheap(2*i+1, n); } else { /* a[i] < a[2*i+1] <= a[2*i+2] のとき */ swap(i, 2*i+2); downheap(2*i+2, n); } } } == 020619b.c == #include #include /* rand() */ #include /* memcpy() */ #include /* INT_MAX */ #include #define N 26 /* ソートするものの個数 */ #define MAX 99 /* 数値データは 0 ... MAX */ #define min(X,Y) ((X)<(Y)?(X):(Y)) #define swap(I,J) { int tmp = a[(I)]; a[(I)] = a[(J)]; a[(J)] = tmp; } int myrand(int max); void print(void); void mergesort(void); void merge(int *p, int m, int *q, int n, int *r); int a[N]; int b[N]; main() { int i; srand((unsigned)time(NULL)); /* 現在時刻で乱数の種を初期化 */ for (i=0; i void merge(int *p, int m, int *q, int n, int *r); main() { int i; int a[ ] = { 1, 3, 4, 5}; /* 昇順でなければならない */ int b[ ] = { 2, 6 }; /* 同上、そして合わせて 6 個 */ int c[6]; merge(a, sizeof(a)/sizeof(int), b, sizeof(b)/sizeof(int), c); for (i=0; i<6; i++) { printf(" %d", c[i]); } putchar('\n'); } /* p からの m 個と q からの n 個をマージして r からにコピー */ void merge(int *p, int m, int *q, int n, int *r) { /* 課題にしようかと考えているところ */ }