- ベストアンサー
マージソートについて
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
- ベストアンサー
この関数自体が、配列の要素数を知らないのでスタート位置とソートする個数を教えてやっているのです。 簡単な例でトレースしてみましょう。 最初に x[0],x[1],x[2],…,x[10],x[11] という配列があったとします。 関数を呼び出すときは mergsort(12,x); のようになるはずです。 呼び出された側はx[0]から12個に処理をします。 m=n/2; でmが6になりますよね？ そこで、 mergsort(m,x); を考えると、x[0]から6個(x[0],x[1],x[2],x[3],x[4],x[5])処理をすることになります。 また、 mergsort(n-m,x+m); を考えると、n-mは6、x+mはx[6]を表しますからx[6]から6個(x[6],x[7],x[8],x[9],x[10],x[11])処理することになります。 判りますか？ 因みに、n-mとしているのは割り切れなかったときのことを考えての事です。 最初にnが11だったら、 m=n/2 は、5になりますから前半部分はx[0]から5個(x[0],x[1],x[2],x[3],x[4])、後半部分は11-5=6でx[5]から6個(x[5],x[6],x[7],x[8],x[9],x[10])処理することになります。
その他の回答 (1)
＃１です。 配列を変えるのではなく、x[5]から始まる配列を1つの配列と認識しているんだと思います。 受け取った側は何番から始まるかは関係ないので（エラーにならない限り）、送る側で「次はここからここまでをよろしく～」と渡しているだけですね。
関連するQ&A
- マージソートのプログラム
↓が自分の作ったマージソートのプログラムなのですが、コンパイルするとエラーが起きてしまいます。 mergesort()にポインタを引数として渡してる、引数の数が足りない、ということが書いてありますが…。 ちゃんとint型を渡してるし、引数の数も合ってるように思います。 どこがおかしいのでしょう？ #include<stdio.h> #include<stdlib.h> #include<time.h> #define Max 255 int A[Max]; main(){ int n,k; n=inputdata(); int w=1; mergesort(w,n); printdata(n); return(0); } inputdata(){ //配列に乱数を要素として入れていく int n,i; printf("n= "); scanf("%d",&n); //使用者にいくつの要素を入れるか指定してもらう srand(time(NULL)); for(i=1; i<=n; i++){ A[i]=1+rand()%30; } printf("A[%d]={%d,",n,A[1]); for(i=2;i<n;i++) printf("%d,",A[i]); printf("%d}\n",A[n]); return(n); } void mergesort(int p, int r){ int q; if(p<r){ q=(p+r)/2; mergesort(p,q); mergesort(q+1,r); merge(p,q,r); } } void merge(int p, int q, int r){ int i,j,k,B[Max]; i=p; j=q+1; for(k=p;k<=r;k++){ if((j>r) || ((i<=q)&&(A[i]<=A[j]))){ B[k]=A[i]; i++; }else{ B[k]=A[j]; j++; } } for(k=p; k<=r; k++) A[k]=B[k]; } printdata(int n){ int i; printf("A[%d]={%d,",n,A[1]); for(i=2; i<n; i++) printf("%d,",A[i]); printf("%d}\n",A[n]); } ・エラーメッセージ merge1.c: In function ‘main’: merge1.c:12: warning: passing argument 1 of ‘mergesort’ makes pointer from integer without a cast merge1.c:12: error: too few arguments to function ‘mergesort’ merge1.c: At top level: merge1.c:31: error: conflicting types for ‘mergesort’ /usr/include/stdlib.h:294: error: previous declaration of ‘mergesort’ was here merge1.c:41: warning: conflicting types for ‘merge’ merge1.c:37: warning: previous implicit declaration of ‘merge’ was here
- ベストアンサー
- C・C++・C#
- マージソート
マージソートの実行時間を測定するプログラムを書いています。 コンパイルの時にはエラーが出ないのですが、実行するとコマンドプロンプトが強制終了されます。 どこが悪いか、どう直せばいいのか指摘していただけないでしょうか？ よろしくお願いします。 ～qtime.c～ //マージソート実行用プログラム //bcc32 mtime.c merge.c m1.c sfmt.c #include <stdio.h> #include <stdlib.h> #include <time.h> #include "sfmt.h" #define MAX 5000 void merge_sort(int a[], int start, int end); main() { int i , x[MAX] , n; time_t start , end ; int sn; printf("適当な数字の入力 : "); scanf("%d", sn); init_gen_rand(sn); for(i=0; i<MAX; i++) x[i]= (gen_rand32()% MAX);; n=MAX; start = clock(); //測定対象プログラム merge_sort(x, 0, n-1); end = clock(); printf("sort\n"); for(i =0 ; i < n ; i++ ) if ( i == i/100*100) printf("%d\n" , x[i]); printf ("実行時間: %f sec\n" , (double)(end-start) /CLOCKS_PER_SEC); return 0; } ～merge.c～ int b[100]; void merge_array(int x[], int start, int end) { int mid, i, j, k; mid = (start + end) /2; i = start; j = mid + 1; for(k = start; k <= end; k++){ if(x[i] > x[j] && j <= end || i > mid){ b[k] = x[j]; j++; } else{ b[k] = x[i]; i++; } } for(k = start; k <= end; k++){ x[k] = b[k]; } } ～m1.c～ void merge_array(int x[], int start, int end); void merge_sort(int a[], int start, int end); void merge_sort(int a[], int start, int end) { int mid; if(start >= end) return; mid = (start + end) / 2; merge_sort(a, start, mid); merge_sort(a, mid + 1, end); merge_array(a, start, end); }
- ベストアンサー
- C・C++・C#
- 数独を解くアルゴリズム
バックトラック法で解いているのですが、どこがおかしいのか見当もつかないので教えてください。 コンパイルエラーはありません。 表示の関数は省いてあります。 よろしくお願いします。 #include <stdio.h> #define M 3 //小さいブロックのサイズ #define N M*M //全体のサイズ #define MTX N*N //全体のマス数 int sudoku[N][N]={ {0,2,4,5,0,0,6,0,0}, {0,0,6,3,2,0,0,0,4}, {0,0,5,0,9,0,0,8,3}, {0,0,8,4,0,3,0,0,1}, {0,6,1,9,0,0,4,3,0}, {7,0,0,1,0,0,5,0,0}, {8,3,0,0,4,0,9,0,0}, {4,0,0,0,3,5,8,0,0}, {0,0,7,0,0,9,3,4,0} }; /* 候補がOKかどうかチェック */ int OKkouho(int x, int y, int k) { int i,j; int p,q; for(i=0; i < N; i++){ //その行に候補は入るか if(sudoku[y][i] == k) return 0; } for(j=0; j < N; j++){ //その列に候補は入るか if(sudoku[j][x] == k) return 0; } p = x/M*M; q = y/M*M; //そのブロックに候補は入るか for(j = q; j < q+M; j++){ for(i = p; i < p+M; i++){ if(sudoku[j][i] == k) return 0; } } return 1; } void Solve(int level) { int k; int x,y; if(level >= MTX){ printf("OK"); return; } x = level%N; y = level/N; if(sudoku[y][x]) Solve(level+1); else{ for(k = 1; k <= N; k++){ if(OKkouho(x,y,k)){ sudoku[y][x] = k; Solve(level+1); sudoku[y][x] = 0; } } } } int main(void) { Solve(0); return 0; }
- 締切済み
- C・C++・C#
- Ｃプログラムで１５パズルを作ってみたのですがうまく動作しません。何処が
Ｃプログラムで１５パズルを作ってみたのですがうまく動作しません。何処が間違っているのかずっと考えているのですがいまだに解決策が見つかりません。ヒントでもいいのでお願します。 #include <stdio.h> int init(void); void show(void); int chk_cmp(void); char input(void); int move(char cmd); #define N 4 int panel[N][N] = { { 1, 2, 3, 4}, { 5, 6, 7, 8}, { 9, 10, 11, 0}, {13, 14, 15, 12} }; int x, y; int main(void) { printf("これは15パズルです。\n" "左上から右に向かって「1」から「15」が並ぶよう，\n" "「0」を動かしてください。\n" "操作はテンキーで行います。（ 8(上),4(左),6(右),2(下) ）\n"); if( !init() ) { printf("パネルの初期化に失敗しました。「0」のパネルがありません。\n"); return 1; } while(1) { show(); if( chk_cmp() ) { printf("完成です！\n"); break; } while(1) { if( move(input()) ) { break; } else { printf("そっちには動かせません。\n"); } } } return 0; } int init(void) { int i,j; for(i=0;i<=N-1;i++){ for(j=0;j<=N-1;j++){ if(panel[i][j]==0){ x=j; y=i; return 1; } } } return 0; } void show(void) { int i,j; printf("---------------\n"); for(i=0;i<=N-1;i++){ for(j=0;j<=N-1;j++){ printf("%3d",panel[i][j]); } printf("\n"); } printf("---------------\n\n"); } int chk_cmp(void) { int i,j; for(i=0;i<=N-1;i++){ for(j=0;j<=N-1;j++){ if(i==N-1&&j==N-1){ if(panel[i][j]!=0){ return 0; } }else{ if(panel[i][j]!=N*i+j+1){ return 0; } } } } return 1; } char input(void) { int comand; while(1){ scanf("%d",&comand); if(comand==8||comand==4||comand==6||comand==2){ break; } printf("8(上),4(左),6(右),2(下)を入力してください。"); } return comand; } int move(char cmd) { int dx=0, dy=0; if(cmd==8){dy=-1;}//上 if(cmd==4){dx=-1;}//左 if(cmd==6){dx=1;}//右 if(cmd==2){dy=1;}//下 if(x+dx>=0&&x+dx<=N-1&&y+dy>=0&&y+dy<=N-1){ panel[y][x]==panel[y+dy][x+dx]; panel[y+dy][x+dx]==0; y+=dy; x+=dx; return 1; } else{return 0;} }
- ベストアンサー
- C・C++・C#
- クイックソート
今クイックソートのプログラム作成をしていますが、分からない箇所が幾つかあります。下は、作成した時のプログラムリストです。 class QuickSort{ static int compare = 0; static int copy = 0; static int swap = 0; static void swap(int a[], int i, int j){ int tmp; tmp = a[i];copy++; a[i] = a[j];copy++; a[j] = tmp;copy++; swap++;} static void showArray(int a[], int l, int r){//配列の内容を表示するメソッドで、動作:部分配列a[l]～a[r]の要素を表示。これが分かりません。 int a[l] = {1,2,3,4,5,6,7,8,9,10}; int a[r] = {11,12,13,14,15,16,17,18,19,20};} static void initArray(int a[], int N){ int i; a[0]=0; for(i=1;i<N;i++) a[i] = i; for(i=1;i<N;i++){ int j,k; j = (int)(java.lang.Math.random()*(N-1)) + 1; k = (int)(java.lang.Math.random()*(N-1)) + 1; swap(a,j,k);}} public static void (int a[],int l, int r) { if (r+1-l <= 1) return; int e = (l+r+1)/2; int c = 0; return a[c]; } static int partition(int a[], int l, int r, int pivot){// 配列の分割を行うメソッドです。そのあと分割に要した比較回数(=iの増加分+jの減少分)を変数compareに加算し、iの値を戻り値として返さないといけませんが、そこんとこが分かりません。 while (true) { while (a[l] < pivot) l = l + 1; while (a[r] >= pivot) r = r - 1; if (l > r) return l; swap(a, l, r); } } static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } int i=0; int j=0; return i; } static void quicksort(int[] a, int l, int r){//(カットオフなしで)再帰的にクイックソートを行うメソッドです。paritionメソッドを用い、a[l]～a[r]を分割値a[r]で分割するのが条件ですが、ここも全然分かりません。 if(l < r){ int i = l; int j = r; int x = a[(i+j)/2]; do{ while(a[i]<x) i++; while(a[j]>x) j--; if(i<=j) { swap(a,i,j); i++; j--; } }while(i<=j); quickort(a,l,j); quicksort(a,i,r); } } static void swap(int[] a, int s, int t){ int temp = a[s]; a[s] = a[t]; a[t] = temp; return; int i,pivot; } public static void main(String args[]){ //上で作ったメソッドを用いて、ソート過程を表示しながらクイックソートを実行 //手順は次のようになる。 1.要素を(20個もつ)整数型配列aを宣言 2.整数型変数Nに配列aの要素数を保存 3.initArrayメソッドを用いて配列aを初期化 4.showArrayメソッドを用いてソート前の配列aの内容を表示 5.変数compare,copyの値を0に初期化 6.quickSortメソッドを用いて配列aを選択ソート 7.showArrayメソッドを用いてソート後の配列aの内容を表示 8.ソートにかかった比較・コピーの回数を表示 //これも分かりません。 } 分かる人がいましたら教えて下さい。お願いします。
- 締切済み
- Java
- C言語＜素数を求めるプログラム＞
#include<stdio.h> int j; int prime(int n) { int i; if(n < 2) return 0; if(n == 2) return 1; if(n%2 == 0) return 0; for(i = 3; i*i<= n; i += 2){ if(n%i == 0) return 0; } return 1; } int main(void) { int n; for(n=1; n <= 1000; n++) { if(prime(n)){ printf("%d\n",n); j++; } } printf("素数の個数は全部で %d 件見つかりました。\n",j); return 0; } このプログラムは1から1000までの素数のみを表示させるプログラムでありますが、このアルゴリズムが全くわかりません。 int prime(int n)の中身のアルゴリズムがどういう仕組みになっているのかお分かりになりますでしょうか？
- ベストアンサー
- C・C++・C#
- クイックソートについて
クイックソートのプログラムなんですが、 セグメンテーション違反で実行出来ません。 どこがおかしいのでしょうか？ int main(void) { FILE *fp; int a[10],b=0,n; clock_t start; double jikan; if( (fp = fopen ("quicksort.txt","r") ) == NULL ) { printf("ファイルが見つかりません : quicksort.txt\n"); exit(1); } while( fscanf(fp, "%d", &a[b]) != EOF ) { b++; } start = clock(); quick_sort(a,n); jikan = clock() - start; for(n = 0; n < b ; ++n) { printf("%d ",a[n]); } printf("計算時間 %.3f 秒 \n", jikan/CLOCKS_PER_SEC); return 0; } int partition(int a[], int l, int r) { int i,j,pivot,t; i = l-1; j = r; pivot = a[r]; for(;;) { while( a[++i] < pivot ) ; while( i < --j && pivot < a[j] ) ; if( i >= j ) break; t=a[i]; a[i]=a[j]; a[j]=t; } t=a[i]; a[i]=a[r];a[r]=t; return i; } void quick_sort_1(int a[],int l,int r) { int v; if( l >= r ) return; v = partition( a, l, r); if( l < v-1 ) quick_sort_1( a, l, v-1); if( v+1 < r ) quick_sort_1( a, v+1, r); } void quick_sort(int a[],int n) { quick_sort_1( a, 0, n-1); }
- ベストアンサー
- C・C++・C#
- 再帰呼び出しの計算量
再帰呼び出しを用いた関数の計算量を求める方法がわからないので質問させていただきます． xのn乗を再帰呼び出しを用いて求める関数に関して，計算量を求める問題なのですが，どのような方針で求めればよいのでしょうか？ int exponent(int x, int n) { if(n == 0){ return 1; }else{ return x * exponent(x, n-1); } } exponentがn回呼ばれるからO(n)というのは間違いでしょうか？
- ベストアンサー
- C・C++・C#
- 再帰関数とユークリッドの互除法を用いて最大公約数を求める
学校の課題で、再帰関数とユークリッドの互除法を用いて１０～１０００００までの最大公約数を求めるという問題が出て自分でプログラムを作ってみたのですが無限ループに入ったり、関数が使えてないみたいでできません。プログラムを見て頂いて、どこを改善したらいいかを教えてください。 #include <stdio.h> /* 正整数 n, m の最大公約数を計算する */ int gcd(int n, int m) { int res; res = n % m; if (res == 0) return m; /* 最大公約数が求まった */ return gcd(m, res); /* 再帰呼び出し */ } int main(void) { int i,j; for(i=10000;i>=10;i--){ for(j=10;j=10000;j++){ printf("%d to %d no saidaikouyakusuu ha %d \n", i, j, gcd(i, j)); } } return (0); } です。期限が今日の夜までで、ぎりぎりなんですがよろしくお願いします。
- ベストアンサー
- C・C++・C#
- 並べ替え
次のようなプログラムを作れ。 1.数値を次々に読み込んで配列に1番目から順に格納する。 2.配列に格納されている数値を逆の順番に並べ換える (最後に読み込んだ数値が配列の1番目に入る)。 3.その配列の内容を1番目から順番に画面に出力する。読み込み、逆転、出力の部分はそれぞれ関数にすること。 という課題をやっています。下のように作ってみたんですが 上手くいかなくて・・・ 何処が悪いか教えて下さい。 #include <stdio.h> #define MAX 100 void reve(int *, int *); void read(int *, int *); void write(int *,int *); int main () { int x[MAX]; int n=0; read(&n, x); reve(&n, x); write(&n, x); return; } void read(int *n, int x[]) { while(scanf("%d", &x[n]) == 1 ) { n += 1; } return; } void reve(int *n, int x[]) { int i, j, y; for(i = 0, j = n-1; i <j; i++, j--) { y = x[j]; x[j] = x[i]; x[i] = y; } return; } void write(int *n, int x) { int i; for(i = n; i = 0; i--) { printf("x[%d] = %d\n", i, x[i]); } return; }
- 締切済み
- C・C++・C#
補足
プログラムを追うため少しプログラムを変えてみました。 void mergesort(int n,int x[]) { int m,s; for(s=0;s<n;s++) { printf("%d\n",x[s]); } puts("小休止"); if(n<=1) return; m=n/2; mergesort(n-m,x+m); } これの実行結果は 12345678910 小休止678910 小休止8910 小休止910 小休止10 小休止 でした。 これはx+mは配列の中を（もしmが５であったら、x[5]以降のみに）変えるということと解釈してよいのでしょうか？