• 締切済み

多層マージソートが分かりません

(1)テープを4本用いる多層マージソートでは初期連を3本のテープに 　どう分配すればよいでしょうか？ (2)テープ3本のとき（ｐ＝２） 　F0＝０　F1＝１　Fn+1＝Fn＋Fn-1（ｎ≧１） 　総数　ｔn＝２Fn＋Fn-1を 　Fn/tn：（Fn＋Fn-1）/tnに分配すればよく、 　この比はｎ→大のとき0.382：0.618に近づきます。 　この収束の様子を観察するにはどのようなプログラムを 　書けばよいでしょうか？ (3)また、ｐ＝３のとき 　F0＝F1＝０　F2＝１　Fn+1＝Fn＋Fn-1＋Fn-2（ｎ≧２） 　総数　ｔn＝３Fｎ＋２Fn-1＋Fn-2を 　Fn/tn：（Fn＋Fn-1）/tn：（Fn＋Fn-1＋Fn-2）/tn 　に分配すればよいです。 　これを、一定精度に収束するｎまで計算するには、 　どのようなプログラムを書けばよいでしょうか？ まだプログラムに不慣れですがプログラムしなければ ならなくなって困っています。 また多層マージソートについて分かりやすく詳しく説明 しているサイトがありましたら教えてください。

みんなの回答

  • f272
  • ベストアンサー率46% (7998/17100)
回答No.1

(1) 自分で(3)で言ってると思うが... (2) 前回の質問でエクセルを使って収束の様子を観察するにはどうするかを言ったと思うが，何か分からないことがあるのか？ (3) p=2のときと全く同じこと。収束の様子を観察していればどこまで計算すればよいかは自明でしょ。

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • 多層マージソート

    (1)テープを4本用いる多層マージソートでは初期連を3本のテープに 　どう分配すればよいでしょうか？ (2)テープ3本のとき（ｐ＝２） 　F0＝０　F1＝１　Fn+1＝Fn＋Fn-1（ｎ≧１） 　総数　ｔn＝２Fn＋Fn-1を 　Fn/tn：（Fn＋Fn-1）/tnに分配すればよく、 　この比はｎ→大のとき0.382：0.618に近づきます。 　この収束の様子を観察するにはどのようなプログラムを 　書けばよいでしょうか？ (3)また、ｐ＝３のとき 　F0＝F1＝０　F2＝１　Fn+1＝Fn＋Fn-1＋Fn-2（ｎ≧２） 　総数　ｔn＝３Fｎ＋２Fn-1＋Fn-2を 　Fn/tn：（Fn＋Fn-1）/tn：（Fn＋Fn-1＋Fn-2）/tn 　に分配すればよいです。 　これを、一定精度に収束するｎまで計算するには、 　どのようなプログラムを書けばよいでしょうか？

  • マージソート

    マージソートの実行時間を測定するプログラムを書いています。 コンパイルの時にはエラーが出ないのですが、実行するとコマンドプロンプトが強制終了されます。 どこが悪いか、どう直せばいいのか指摘していただけないでしょうか？ よろしくお願いします。 ～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); }

  • マージソートのプログラム

    ↓が自分の作ったマージソートのプログラムなのですが、コンパイルするとエラーが起きてしまいます。 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

  • 極限の問題です

    f(x)＝e^π/2×cosπ/2の代n次導関数をfn(x)とする n＝1~∞Σf２n(0)の収束発散を調べ収束するなら収束値を調べよ 数学的帰納法によりfn(x)＝(1/√2×e^－π/4)^n×f(x＋nπ/2)を調べさせる問題が前問で、 それを利用して、Ｓ2n＋２とＳ2nを求めようと思ったんですがそれが出来ません 方針ミスでしょうか

  • 関数列の収束について

    [0,1]で定義された連続な関数g,hに対して距離dを導入します． すると，({[0,1]で定義された連続な関数},d)は，距離空間になると思います． ここで，[0,1]で定義された連続な関数の列(fn)(n=1,2,...)について，(fn)が，{[0,1]で定義された連続な関数}に収束するかどうかを判定したいときに疑問が生じました． まず，与えられた(fn)が，直感的にF=[1(x=0),0(0<x≦1)]の形に近づきそうだと思いました． そこで，(fn)がFに収束するなら，(fn)は{[0,1]で定義された連続な関数}には収束しない，と判定できると考えました． しかし，このFは，[0,1]で定義された連続関数ではありません． 距離が定義されていない空間に属する関数Fに収束しそうな関数列(fn)について，どのように収束判定を行えばよいのでしょうか？ ご回答よろしくお願いします．

  • 一様収束しないことの証明

    ∑xe^-(nx)が0<x<1で一様収束しないことを示せ。 ∑は0～∞です。 sup|fn(x)-f(x)|=1/ne →0(n→∞)なので、一様収束していませんか？

  • 配列の中に、リストが入っているものをボトムアップ形式でマージソートして

    配列の中に、リストが入っているものをボトムアップ形式でマージソートしています。 リストは、空のノードの次に文字列が入ったノード、というものです。 sizeは、配列の要素数となっています。 merge_listは、リスト２つをマージするものです。 ２つのリストをマージして、ひとつになったリストを最初のリストが入っていた配列に入れる。 もう片方はＮＵＬＬにする。 順に繰り返していき、配列の要素が１つのみになったらそれを返す・・・ といったアルゴリズムなのですが、うまく配列の中のリストが指定できません。 調べたところ、おそらくプログラム中の矢印があるところに問題があってprintfが実行できないようなんですが、原因がわかりません。 同じ原因によりmerge_listに、マージしたいリストが入っていないようなんですが・・・。 説明下手ですいませんが、どうかよろしくお願いします。 typedef struct list * word_list; struct list { char* word; word_list rest; }; word_list _mergesort(word_list* word_lists, int size) { int i=0, j; while(1){ while(1){ while(word_lists[i] =NULL) //配列に一つ目の要素が見つかるまで回す <-　原因 i++; j = i+1; while(word_lists[j] =NULL)　//配列に二つ目の要素が見つかるまで回す<-　原因 　 j++; 　　　　　　if(j == size) //マージする要素が後ろになかったら終了 　break; //printf("%d,%d\n",i, j); printf("%s\n",word_lists[i] ->rest ->word);　　＜－ここでエラー printf("%s\n",word_lists[j] ->rest ->word); word_lists[i] =merge_list(word_lists[i], word_lists[j]); word_lists[j] =NULL; printf("%s",word_lists[i]->rest ->word); i = j+1; } if(i !=0){ i = 0; }else{ break;　　　　//要素がひとつしかなかったら終了 } } return word_lists[0]; }

  • 積分の問題

    [0,1]上の皮膚連続関数f(x)に対して、[0,1]上の関数列{Fn(x)}n≧0を以下により定める。 F0(x)=f(x), Fn(x)=∫0 x Fn-1(t)dt (n≧1) この時次の問いに答えなさい。 (1) f(x)=xとおいたとき、Fn(x)を具体的に求めなさい。 (2) n≧1の時、Fn(x)は単調非減少な微分可能関数であることと、不等式 Fn+1(1/2)≦ Fn+1(1)/2が成り立つことをそれそれ示しなさい。 (3)n≧1の時、各x∈[0,1]に対して不等式Fn+1(x)≦ Fn(x)xが成り立つことを示しなさい。 (4)n≧2の時、Fn+1(1)≦ 3Fn(1)/4を示しなさい。（ヒント：積分区間を[0,1/2]と[1/2,1]に分けて評価する） (5){Fn(x)}は[0,1]で0に一様収束することを示しなさい。 これらの問題です。 (1)は帰納的に求めていきたいです。 教えていただけませんか？お願いします。

  • ソートプログラム

    ファイルから10個の整数が 29 45 11 2 86 91 33 62 77 59 のように一行に1個の形式で格納されている。このファイルから10個の整数を読み込み、選択法でソートし、この数字を小さい順に表示するプログラムを作成したのですが、ソート部分がうまくできません。どなたかどうすれば改善できるか教えてください。 <プログラム> #include<stdio.h> #include<stdlib.h> #define MAXN 100 int A[MAXN]; main() { ＿inputdata(); ＿selectionsort(1,10); ＿printdata(); } selectionsort(p,q) ＿＿＿int p, q; { ＿int i, j, cmin, temp; ＿for(j = p; j <= q; j++){ ＿＿cmin = j; /* A[cmin]が現在の最小値 */ ＿＿for(i = j+1; i <= q; i++) ＿＿＿if(A[cmin] > A[i]) cmin = i; ＿＿/* A[j]とA[cmin]との入れ換え操作 */ ＿＿swap(j, cmin); ＿} } swap(int x, int y) { ＿int temp; ＿temp = x; ＿x = y; ＿y = temp; } inputdata() { ＿FILE *fp; ＿if((fp=fopen("integers10.dat", "r"))==NULL) { ＿＿printf("ファイルが見つかりません: integers10.dat\n"); ＿＿exit(EXIT_FAILURE); ＿} ＿printf("データを入力\n"); ＿while(fscanf(fp, "%s", A)!=EOF) { ＿＿＿＿printf("%s\n",A); ＿} ＿fclose(fp); } <コンパイル→実行> % gcc -o sort1 sort1.c % ./sort1 データを入力 29 45 11 2 86 91 33 62 77 59 ソート済みデータ 0 0 0 0 0 0 0 0 0 0 %

  • ２変数関数の極限について

    D：ｆの定義域 有限な極限値limf(P) (P→P_0）が存在するための条件は、P_0に収束するどんな点列｛P_n｝（ただし、P_n∈D、P_n≠P）に対しても、数列{ｆ（P_n）}が収束することである。 これを示してください。 よろしくお願いします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する