【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※返信付き投稿の削除は禁止!
 ※マルチポスト(多重投稿)は慎んで!

 詳しくはこちら


本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール掲示板2こちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.21575

再帰を使った分割統治法で最大値と最小値を求めるプログラム
投稿者---素浪人108世(2005/06/23 06:29:22)


再帰をつかって分割統治法のプログラムをつくってみたのですが、
結果が最大値はちゃんと出てくるのですが、最小値がうまく出てきません。
ソースを見ていただければ分かると思いますが、
最小値は1が出るべきだと思うのですが・・・
使用したデータファイル名:
  最大値 = 10
  最小値 = 3
実行時間 = 0.00000000 sec

関数Divide_and_Conquerでまだ工夫が必要だと思うのですが
再帰の仕方を変えればいいのか、最大値、最小値の判定の仕方が違うのか、
考えたのですがわかりません。

どこを修正すればいいのでしょうか?

OS: Windows98 SE
コンパイラ:Borland C++ Compilar

以下、書きかけのソースです(コンパイルは通ります)。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

#define MAT_MAX 50000
#define MAX -50000
#define MIN 50000
#define NOT_FOUND -1

void Divide_and_Conquer(int a[],int n);
void Output();

int a[]={1,4,2,7,9,6,7,10,5,3};
int datasize=10;
int Bmax[MAT_MAX],Bmin[MAT_MAX];
int max,min;
char fname1[100],fname2[100];   /* ファイル名 */
FILE *fp,*fp1,*fp2;

clock_t start,finish;                        /* 実行開始、終了のCPU時間 */
double Time = 0.0;                                      /* 平均実行時間 */
int count=1;                                                /* 実行回数 */

int main(){
     int l;
     
     printf("出力テキストファイル(*.txt *.TXT) => ");
     scanf("%s",fname2);

     l = strlen(fname2);
     /* datファイルを指定が違うか、拡張子.txt(.TXT)を入れていなければエラー */
     if(fname2[l-4]!='.'&&fname2[l-3]!='t'&&fname2[l-2]!='x'&&fname2[l-1]!='t'){
         printf("\nError:出力ファイルの拡張子は .txt(.TXT) にすること\n");
         exit(1);
     }else if(fname2[l-4]!='.'&&fname2[l-3]!='T'&&fname2[l-2]!='X'&&fname2[l-1]!='T'){
         printf("\nError:出力ファイルの拡張子は .txt(.TXT) にすること\n");
         exit(1);
     }
     fclose(fp1);

     printf("分割統治法で最大値、最小値の探索中...\n\n");
     max = MAX;   min = MIN;
     Divide_and_Conquer(a,datasize);
     Output();
     return 0;
}

void Divide_and_Conquer(int x[],int n){
     int i,halfsize;

     if(n==1) return;
     halfsize = n/2;
     for(i=0; i<halfsize; i++){
            if(x[2*i] >= x[2*i+1]){Bmax[i]=x[2*i];  Bmin[i]=x[2*i+1];}
        else if(x[2*i] < x[2*i+1]){Bmax[i]=x[2*i+1];  Bmin[i]=x[2*i];}
     }

     Divide_and_Conquer(Bmax,halfsize);
     Divide_and_Conquer(Bmin,halfsize);
     
     for(i=0; i<halfsize; i++){
        if(max < Bmax[i]) max = Bmax[i];
        if(min > Bmin[i]) min = Bmin[i];
     }
}

void Output(){
     int i=0;
     fp2 = fopen(fname2,"w");
     fprintf(fp2,"使用したデータファイル名:");
     while(fname1[i]!='\0'){
         fputc(fname1[i],fp2); i++;
     }
     fprintf(fp2,"\n");
     fprintf(fp2,"  最大値 = %d\n",max);
     fprintf(fp2,"  最小値 = %d\n",min);
     fprintf(fp2,"実行時間 = %.8lf sec\n",Time);
     fclose(fp2);
     /* 改めて結果を出力する */
     printf("結果をファイルに書込みました.\n");
     printf("実行時間  : %.8lf sec\n",Time);
}





この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:再帰を使った分割統治法で最大値と最小値を求めるプログラム 21576 επιστημη 2005/06/23 08:42:49
<子記事> Re:再帰を使った分割統治法で最大値と最小値を求めるプログラム 21577 REE 2005/06/23 10:21:31
<子記事> Re:再帰を使った分割統治法で最大値と最小値を求めるプログラム 21580 かずま 2005/06/23 10:33:57
<子記事> Re:再帰を使った分割統治法で最大値と最小値を求めるプログラム 21599 素浪人108世 2005/06/24 07:01:55


No.21576

Re:再帰を使った分割統治法で最大値と最小値を求めるプログラム
投稿者---επιστημη(2005/06/23 08:42:49)


>再帰をつかって分割統治法のプログラムをつくってみたのですが、
>結果が最大値はちゃんと出てくるのですが、最小値がうまく出てきません。

んー…デタラメに並んだデータからmin/maxを探すのに分割統治が有効だろうか?
アタマから順に舐めてくだけで求まるんだから、線形検索がもっとも簡単かつ高速じゃないのかしら?



この投稿にコメントする

削除パスワード

No.21577

Re:再帰を使った分割統治法で最大値と最小値を求めるプログラム
投稿者---REE(2005/06/23 10:21:31)


>どこを修正すればいいのでしょうか?

下記のような問題点があります。

・要素数が奇数の時に出る端数要素が考慮されていない。
・BMax、BMinが、自身を呼んだときに破壊されてしまう。
・最大値、最小値を得るのに再帰が全く生かされていない。



この投稿にコメントする

削除パスワード

No.21580

Re:再帰を使った分割統治法で最大値と最小値を求めるプログラム
投稿者---かずま(2005/06/23 10:33:57)


ファイル入出力や、時間計測などは後回しにして、主要部分(最大値、最小値
を求める部分)だけを作ってみましょう。

#include <stdio.h>

int a[] = { 1, 4, 2, 7, 9, 6, 7, 10, 5, 3 };
int datasize = sizeof(a) / sizeof(a[0]);

void Divide_and_Conquer(int x[], int n, int *max, int *min)
{
    int max1, min1, max2, min2, halfsize = n / 2;

    if (n == 1) { *max = *min = x[0]; return; }
    Divide_and_Conquer(x, halfsize, &max1, &min1);
    Divide_and_Conquer(x + halfsize, n - halfsize, &max2, &min2);
    *max = (max1 > max2) ? max1 : max2;
    *min = (min1 < min2) ? min1 : min2;
}

int main()
{
     int max, min;
     
     Divide_and_Conquer(a, datasize, &max, &min);
     printf("max = %d, min = %d\n", max, min);
     return 0;
}



この投稿にコメントする

削除パスワード

No.21599

Re:再帰を使った分割統治法で最大値と最小値を求めるプログラム
投稿者---素浪人108世(2005/06/24 07:01:55)


皆様ありがとうございます。
本当に参考になりました。


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧