セグメンテーションフォルトについて。

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら

トピックに返信する


答えを正確にご入力ください。答えられるかどうかでスパムボットか否かを判定します。

BBCode: ON
[img]: ON
[flash]: OFF
[url]: ON
スマイリー: OFF

トピックのレビュー
   

展開ビュー トピックのレビュー: セグメンテーションフォルトについて。

Re: セグメンテーションフォルトについて。

#7

by 初心者です » 4年前

@かめのこのこのこ さん
ここまで深く考察してくださるとは……。
本当にありがとうございます!
たしかに、複数回無駄に計算してしまっていることで処理に時間がかかっているようでした…。
期限まではもう少し時間があるので、もう少し考えてみます!(^▽^)/
また コマンドライン引数に1以上の値を指定したときに何も出ないという件に関しては、

コード:

int from=atoi(argv[1]);
int to=atoi(argv[1]);
と修正することで1以上の値でも出力されるようになりました!
ご指摘ありがとうございました!

Re: セグメンテーションフォルトについて。

#6

by かめのこのこのこ » 4年前

課題の期限が過ぎてしまったかもしれませんが、計算回数の謎に対してある程度考察してみたので..

フィボナッチ数列を初心者です さんのように単純な再帰関数で実装したとき、
その関数呼び出し回数は
漸化式 an = an-1 + an-2 + 1, a0 = a1 = 1

一般項 an = 2 * Sqrt(5) / 5 * (sn+1 - tn+1) - 1, s = {1 + Sqrt(5)} / 2, t = {1 - Sqrt(5)} / 2
であり、実行例に提示された回数 (n * 2, n = 0 のとき 2) にほど遠いことがわかります。

そこで実行回数を図示してみたのですが、
図1.png
n = 4 では、f(2) (ピンク色) の再計算を 2回
n = 5 では、f(3) (緑色) の再計算を 3回,
と複数回無駄に計算してしまっていることがわかります。

ここで、計算の途中に f(2), f(3) などの値を保存しておき、その計算結果を再利用することで
(図は作ったけど1つまでしか添付できないみたいだから省略)
関数呼び出し回数を
漸化式 an = an-1 + 2, a0 = a1 = 1

一般項 an = 2 * n - 1
まで抑えることができます。
(一回分足りないのは最初に余分な関数でも挟めばどうにかなる)

あとは、計算の途中にどのように計算結果を再利用するか、ここが腕の見せ所になるのではないのでしょうか。
ヒントはここまで、実装頑張ってみてください、応援しています :-)
オフトピック
組んでみたソースコードがあってここで提示しない私意地悪だなぁ..

Re: セグメンテーションフォルトについて。

#5

by 初心者です » 4年前

@かめのこのこのこさん
リンクありがとうございます!大変参考になります。
早速目を通してみます。
たしかに、確認してみると1以上の値の場合何も出ませんね…。
0 や 3と6 だったりすると値は出力されますが…。

Re: セグメンテーションフォルトについて。

#4

by かめのこのこのこ » 4年前

横槍失礼します。
フィボナッチ数列の動的計画法を用いた実装はあるみたいですね。
以下に「フィボナッチ数列 動的計画法」で検索した結果へのリンクを貼っておきますね。https://www.google.com/search?q=%E3%83% ... B%E6%B3%95
オフトピック
コマンドライン引数に1以上の値を指定したときに何も出ない気がするのは気のせいなのでしょうか..

Re: セグメンテーションフォルトについて。

#3

by 初心者です » 4年前

@かずまさん
コードありがとうございます。大変参考になります。
無事出力されました。
トップダウンの動的計画法については説明できないです、すみません…。
関数呼出し回数の表示方法が分からなかったため2を入れていましたが、f_cの存在を忘れていました…。
ありがとうございます!
下記のように修正し、なんとか単純実装までは持ち込めましたが、このコードのままでは
0を入力するとf(0)=0 [1 times]と出力されてしまいます。
実行例ではf(0)=0 [2 times]と2回呼び出されていますが、なぜ2回呼び出されているのかが分かりません…。

コード:

#include <stdio.h>
#include <stdlib.h>
long int f(int n);
long int f_c;
long int r;

int main(int argc, char *argv[]){

  if(argc==1) return 0;

int i;

int from=atoi(argv[1]);
int m = 0;
	if (argc > 2) m = atoi(argv[2]);
  for(i=from; i<=m; i++){

 
    printf("f(%d)=%ld ",i,f(i));
    printf("[%ld times]\n",f_c);

}
return 0;
}


long int f(int n){
    f_c++;
    
    
    if( n<=1 ) return n;
    return f(n-1)+f(n-2);
}

Re: セグメンテーションフォルトについて。

#2

by かずま » 4年前

コマンドラインで引数が 1つだけの時、
argc = 2, argv[1] = "0", argv[2] = NULL となります。
int to=atoi(argv[2]); がセグメンテーションフォールトの原因です。

次のようにすればよいでしょう。

コード:

	int to = 0;
	if (argc > 2) to = atoi(argv[2]);
ところで、f(0)=0 [2 times] はおかしくないですか?
f(0) の場合、関数 f の呼び出しは 1回だけのはずです。
呼び出し回数を数える変数 f_c を表示していませんね。
f_c のカウントアップは f(i) を呼び出した後に行われますから、
printf の中で f(i) の呼び出しと f_c の参照を同時に行ってはいけません。

3 から 6 までは、f の単純実装では、次のようになります。
f(3)=2 [5 times]
f(4)=3 [14 times]
f(5)=5 [29 times]
f(6)=8 [54 times]

問題には、「再帰呼出しを使って実装したものに
トップダウンの動的計画法を適用した場合を考える。」とあります。
トップダウンの動的計画法とは何か説明できますか?

私が改良すると、次のようになりました。
f(3)=2 [5 times]
f(4)=3 [8 times]
f(5)=5 [11 times]
f(6)=8 [14 times]

セグメンテーションフォルトについて。

#1

by 初心者です » 4年前

はじめまして!
c言語初心者ですが、よろしくお願いいたします。
今回は課題の期限が間近に迫ってきているため、投稿させていただきました。
下記の問題について、実行例と実行結果が異なる点があります。
【問題】
フィボナッチ数を計算する関数
long int f(int n)
を再帰呼出しを使って実装したものにトップダウンの動的計画法を適用した場合を考える。与えられた非負整数 n を引数とする関数呼出し f(n) を行なったときに生じる関数呼出し( f 自身の呼出し、および、そこから(直接に/再帰的に)呼び出される関数の呼出し)の回数を数え、 計算されたフィボナッチ数とともにその回数を標準出力に書き出すプログラムを作れ。
プログラムの仕様はつぎの通りとする。
コマンドライン引数に非負整数値が1個または2個与えられる。  
1個与えられた場合、その値 n を引数として呼出し f(n) を行う。
2個与えられた場合、それらの値を m1、m2 とすると m 1 ≦ n ≦ m 2 である全ての値 n について小さい方から順に関数呼出し f(n) を行う。 m1>m2 のときは関数呼出しは何も行わずに実行を終了する。
出力は、関数呼出し f(n) を行うごとにその結果をつぎの形式で1行として標準出力に書き出す。
f(n)=v [c times]
v はフィボナッチ数の値、 c はその関数呼出し回数
v と [ の間、c と times の間には、それぞれ空白1文字をおくこと。
【実行例】
コマンドライン入力
0
標準出力
f(0)=0 [2 times]

コマンドライン入力
6 3
標準出力

コマンドライン入力
3 6
標準出力
f(3)=2 [6 times]
f(4)=3 [8 times]
f(5)=5 [10 times]
f(6)=8 [12 times]


上記の問題について、下記のようなコードを作成したのですが、
コマンドラインに、0など値を"1つだけ"入力すると、セグメンテーションフォルトが発生してしまいます。
値が1つだけ与えられた場合や、値が2つ与えられた場合でも、セグメンテーションフォルトを発生させずに値を回すために、どう修正すれば良いのでしょうか。

コード:

#include <stdio.h>
#include <stdlib.h>

long int f(int n);
long int f_c;

long int r;

int main(int argc, char *argv[]){

 if(argc==1) return 0;

int i;

int from=atoi(argv[1]);
int to=atoi(argv[2]);

  for(i=from; i<=to; i++){

  if(i==0){
     printf("f(%d)=%ld [%d times]\n",i,f(i),2); 
}

  if(i>0){
    printf("f(%d)=%ld [%d times]\n",i,f(i),i*2);

}
}
return 0;
}


long int f(int n){
    f_c++;
    
    if( n<=1 ) return n;
    return f(n-1)+f(n-2);
}

ページトップ