ページ 11

アルゴリズム

Posted: 2007年10月07日(日) 00:37
by
#include <stdio.h>
#define MAX 5001                            /* 配列の大きさ */
#define DIGIT 7500                          /* n の最大値 */

void print_box(int [/url]);                     /* 配列の中身を表示する */
void copy_box(int [/url], int [/url]);              /* 配列をコピーする */
void addition(int [/url], int [/url], int [/url]);      /* 足し算 */
void subtraction(int [/url], int [/url], int [/url]);   /* 引き算 */
void division(int [/url], int, int [/url]);         /* 配列 ÷ 整数 */
void division_int(int, int, int [/url]);        /* 整数 ÷ 整数 */

int pi[MAX], ans1[MAX], ans2[MAX];
int tmp[MAX], a[MAX], b[MAX], c[MAX];


int main()
{
  int i, n;

  /*-----------*/
  /*     5     */
  /*-----------*/
  division_int(16, 5, ans1);      
  copy_box(ans1, tmp);

  for( i=1, n=0 ; n+2 <= DIGIT ; i++ ){
    n = 2 * i + 1;                
    division(tmp, 5*5, a);        
    copy_box(a, tmp);             /* ○ ÷ 5^2 の値を退避 */
    division(a, n, b);            /* ○ ÷ n */
    if( i % 2 == 0 )              /* i: 偶数なら */
      addition(ans1, b, c);       /* + */
    else                          /* i: 奇数なら  */
      subtraction(ans1, b, c);    /* - */
    copy_box(c, ans1);
  }

  /*-----------*/
  /*    239    */
  /*-----------*/
  division_int(4, 239, ans2);
  copy_box(ans2, tmp);

  for( i=1, n=0 ; n+2 <= DIGIT ; i++ ){
    n = 2 * i + 1;
    division(tmp, 239*239, a);
    copy_box(a, tmp);
    division(a, n, b);
    if( i % 2 == 0 )
      addition(ans2, b, c);
    else
      subtraction(ans2, b, c);
    copy_box(c, ans2);
  }

  /*----------*/
  /*    π    */
  /*----------*/  
  subtraction(ans1, ans2, pi);    
  print_box(pi);                  

  return 0;
}

void print_box(int box[/url])
{
  int i;

  printf("%5d.", box[0]);         

  for( i=1 ; i < MAX ; i++ )      
    printf("%d", box);         

  printf("\n");
}

void copy_box(int from[/url], int to[/url]){
  int i;

  for( i=0 ; i < MAX ; i++ )      
    to = from;              
}

void addition(int x[/url], int y[/url], int answer[/url])  
{
  int i, carry=0;

  for( i=MAX-1 ; i > 0 ; i-- ){
    answer = (x + y + carry) % 10;    
    carry = (x + y + carry) / 10;        
  }
  answer[0] = x[0] + y[0] + carry;             
}

void subtraction(int x[/url], int y[/url], int answer[/url])
{
  int i;

  for( i=MAX-1 ; i > 0 ; i-- ){
    if( x >= y ){            
      answer[i] = x[i] - y[i];     
    }else{                         
      x[i-1] = x[i-1] - 1;         
      answer[i] = x[i] + 10 - y[i];
    }
  }
  answer[0] = x[0] - y[0];
}

void division(int x[/url], int y, int box[/url])
{
  int i, surplus=0;

  for( i=0 ; i < MAX ; i++ ){
    box[i] = (surplus * 10 + x[i]) / y;
    surplus = (surplus * 10 + x[i]) % y;  
  }
}

void division_int(int x, int y, int box[/url])
{
  int i, surplus;

  box[0] = x / y; 
  surplus = x % y;

  for( i=1 ; i < MAX ; i++ ){
    box[i] = surplus * 10 / y;
    surplus = surplus * 10 % y;
  }
}



上のプログラムの簡単なアルゴリズムを教えていただけないでしょうか?
ちなみに、「πをマーチンの公式を使って7500桁(この場合)求める」プログラムです

Re:アルゴリズム

Posted: 2007年10月07日(日) 00:46
by 管理人
ご質問が2通りに受け取れるのですが、

上のプログラムをもっと簡単にするアルゴリズムを知りたいのでしょうか。

それともどこかから出された、あるいはどこかでみかけたこのプログラムの意味がわからないので、その手続きを手短かに教えてほしいという事でしょうか。

Re:アルゴリズム

Posted: 2007年10月07日(日) 15:09
by
管理人さんが言う、2通りのうちの後者のほうです
できれば、どちらとも教えて欲しいのです。

自分でここは無駄なんじゃないかと思うのは、
配列に値が1つしか入ってないところだと思うのですが。

Re:アルゴリズム

Posted: 2007年10月07日(日) 15:44
by box
> 自分でここは無駄なんじゃないかと思うのは、
> 配列に値が1つしか入ってないところだと思うのですが。

どこのことでしょうか?

Re:アルゴリズム

Posted: 2007年10月07日(日) 16:53
by
>どこのことでしょうか?

感覚的なんですが、
void print_box(int box[/url])
{
int i;

printf("%5d.", box[0]);

for( i=1 ; i < MAX ; i++ )
printf("%d", box);

printf("\n");
}

のところはそうなっていそうなんですが。

Re:アルゴリズム

Posted: 2007年10月07日(日) 17:05
by 管理人
厳しい事を言うようですが、聞いてください。

これは学校の課題でしょうか。学校から提示されたものですか?

まず質問する姿勢として、自分はどこまで理解したのか、どの部分が知りたいのか明確にしてもらう事を規約にしています。
また、自分がプログラムが理解出来ず困っている時は、簡単に説明してもらうより、詳しく説明してほしいと思うはずだと思います。
どこまで理解したのか、自分はどれ位知識があるか全く示さず、誰かこのプログラムの意味を手短に教えて欲しいというのはいかがなものでしょうか。

自分がわからない部分をはっきり示し、その部分について詳しい解説を要求した方が問題解決になると思います。

プログラムが全部わから無いという事は無いと思います。自分の理解出来ない箇所を示してください。
もし全く理解出来ないなら自分はどの位で躓いているのか教えてください。

Re:アルゴリズム

Posted: 2007年10月07日(日) 17:12
by box
> 自分でここは無駄なんじゃないかと思うのは、
> 配列に値が1つしか入ってないところだと思うのですが。

box[/url]の各要素に1桁分しか入っていない、ということですか?

であれば、box[/url]の各要素に複数の桁を格納できるよう、
プログラムを修正することにチャレンジしてみてはいかがでしょうか。

Re:アルゴリズム

Posted: 2007年10月07日(日) 23:27
by
特に学校とかは通ってなくて、独学でやってるものなんです。
つい最近はじめたばかりなので、知識はかなり浅いほうだと思います。

ちょっと質問の仕方に悪いところが多かったみたいですね。
管理人さんの言うとおりに、質問をしなおしてみます。
かなり基本的なことを質問するかもしれませんが、よろしく御願いします

☆自分が分からない点

●1●
void copy_box(int from[/url], int to[/url]){
int i;

for( i=0 ; i < MAX ; i++ )
to = from;
}

の部分で、なぜ配列をコピーするのかということ。

●2●
copy_box(a, tmp); /* ○ ÷ 5^2 の値を退避 */

の部分で、5^2の値を退避することによって、どのようなメリットがあるのかということ


以上の2つです。

ネットで勉強してるので、かなり基礎的なことができてないところがありまして。


追伸
box様
いちおう、配列に4桁格納できるようにはしてみました。
しかし、勉強不足なので修行しなおしてきます

Re:アルゴリズム

Posted: 2007年10月09日(火) 17:38
by やそ
マーチンの公式を級数展開して求めているプログラムでは?

PI=16*arctan(1/5)-4*arctan(1/239)

この公式を元にじっくりプログラムを眺めて処理を追ってみると良いでしょう。