C/C++の宿題のまとめ@Wiki

分割統治法による総和

最終更新:

匿名ユーザー

- view
管理者のみ編集可
238 :デフォルトの名無しさん :2005/11/03(木) 22:50:55
言語:C
[3] 環境
 [3.1] OS: XP Home
 [3.2] コンパイラ名とバージョン: VC6.0
 [3.3] 言語: Cでお願いします
[4] 期限: 2005年11月04日06:00まで
[5] その他の制限: 特になし


次の1~8を埋めよ。
実数値配列の要素の総和を計算する。次の関数sumは、分割統治法を適用して作った。引数l と r とで、a[l]、a[l+1]、・・・、a[r-1]の和を計算することで指定している。
double sum(double a[], int l, int r){
int n= r-l, m= (l+r)/2;
if( n==0 ) return 0.0;
if( n==1 ) return 【 1 】;
return sum(a, l, m)+sum(a,【 2 】,【 3 】); /* (1) */
}
この関数を使うと、 double x[100];と宣言された配列に記録された100個の全要素の値の総和は、
sum(x,【 4 】, 【 5 】) という関数で求めることが出来る。
sum(x, 0, 2)の呼び出しによって(1)と記した行での加算は全部で【 6 】回行われる。
sum(x, 5, 10)の呼び出しによって(1)と記した行での加算は全部で【 7 】回行われる。
一般にsum (x, u, v)の呼出し(0 <= u <= v <= 100)によって(1)と記した行での加算は全部で【 8 】回行われる。

穴埋め問題です。本を見て調べたのですが、よく分からなかったので、宜しくお願いします。

239 :デフォルトの名無しさん :2005/11/03(木) 22:55:47
こりゃ難しい。オレだったら総和は単純ループで計算するよ。

240 :デフォルトの名無しさん :2005/11/03(木) 22:56:53
なんで再帰呼び出ししてんだか
241 :デフォルトの名無しさん :2005/11/03(木) 22:57:26
そうわイカンザキ
243 :デフォルトの名無しさん :2005/11/03(木) 23:03:40
>>238
1:a[l] 2:m+1 3:r 4:0 5:101 6:1 7:4 8:v-u-1
暇だったから解いたがツマラン+間違っててもシラネ
つーか、なんだこの問題。こんなの分割統治にしても
ある程度以上の個数なら関数呼び出しのオーバーヘッドの方がでかいだろうに
クイックソートとか二分探索の方が問題としてもいいと思うがな

244 :デフォルトの名無しさん :2005/11/03(木) 23:08:11
>>243
どうも、有難うございます。4、5は、同感です。1~3を代入してプログラムを動かしてみて、6~8の確認をします。
有難うございます。

245 :デフォルトの名無しさん :2005/11/03(木) 23:10:07
>>243は微妙に間違っている罠。

246 :デフォルトの名無しさん :2005/11/03(木) 23:15:26
>>245
やっぱり間違ってたか
とりあえず半閉区間[l,r)だという事まで考えたところでやる気が尽きたから適当にやったからな
6以降はあんま考えてないし

247 :デフォルトの名無しさん :2005/11/03(木) 23:16:40
>>238
243が答えてしまったがせっかく作ったので
#include <stdio.h>

double sum( double a[], int l, int r )
{
printf( "sum( %x, %d, %d )\n", a, l , r ) ;
int n = r - l ;
int m = ( l + r ) / 2 ;

if( n == 0 ){
printf( "Nullpo\n" ) ;
return 0.0 ;
}
if( n == 1 ){
printf( "Gatt%lf\n", a[ l ] ) ;
return a[ l ] ;
}
return sum( a, l, m ) + sum( a, m, r ) ;
}

int main()
{
double x[] = { 0, 1, 2, 3, 4, 5 } ;

printf( "sum=%lf\n", sum( x, 0, sizeof( x ) / sizeof( x[0] ) ) ) ;
return 0 ;
}
目安箱バナー