「分割統治法による総和」の編集履歴(バックアップ)一覧はこちら
「分割統治法による総和」(2005/11/07 (月) 06:20:55) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
<dl>
<dt>238 :<font color="green"><b>デフォルトの名無しさん</b></font>
:2005/11/03(木) 22:50:55</dt>
<dd>言語:C<br>
[3] 環境<br>
[3.1] OS: XP Home<br>
[3.2] コンパイラ名とバージョン: VC6.0<br>
[3.3] 言語: Cでお願いします<br>
[4] 期限: 2005年11月04日06:00まで<br>
[5] その他の制限: 特になし<br>
<br>
<br>
次の1~8を埋めよ。<br>
実数値配列の要素の総和を計算する。次の関数sumは、分割統治法を適用して作った。引数l
と r
とで、a[l]、a[l+1]、・・・、a[r-1]の和を計算することで指定している。<br>
double sum(double a[], int l, int r){<br>
int n= r-l, m= (l+r)/2;<br>
if( n==0 ) return 0.0;<br>
if( n==1 ) return 【 1 】;<br>
return sum(a, l, m)+sum(a,【 2 】,【 3 】); /* (1) */<br>
}<br>
この関数を使うと、 double
x[100];と宣言された配列に記録された100個の全要素の値の総和は、<br>
sum(x,【 4 】, 【 5 】)
という関数で求めることが出来る。<br>
sum(x, 0,
2)の呼び出しによって(1)と記した行での加算は全部で【 6 】回行われる。<br>
sum(x, 5,
10)の呼び出しによって(1)と記した行での加算は全部で【 7 】回行われる。<br>
一般にsum (x, u, v)の呼出し(0 <= u <= v <=
100)によって(1)と記した行での加算は全部で【 8 】回行われる。<br>
<br>
穴埋め問題です。本を見て調べたのですが、よく分からなかったので、宜しくお願いします。<br>
<br></dd>
<dt>239 :<a href="mailto:sage"><b>デフォルトの名無しさん</b></a>
:2005/11/03(木) 22:55:47</dt>
<dd>
こりゃ難しい。オレだったら総和は単純ループで計算するよ。<br>
<br></dd>
<dt>240 :<a href="mailto:sage"><b>デフォルトの名無しさん</b></a>
:2005/11/03(木) 22:56:53</dt>
<dd>なんで再帰呼び出ししてんだか</dd>
<dt>241 :<a href="mailto:sage"><b>デフォルトの名無しさん</b></a>
:2005/11/03(木) 22:57:26</dt>
<dd>そうわイカンザキ</dd>
<dt>243 :<a href="mailto:sage"><b>デフォルトの名無しさん</b></a>
:2005/11/03(木) 23:03:40</dt>
<dd><a href="http://pc8.2ch.net/test/read.cgi/tech/1130431335/238" target=
"_blank">>>238</a><br>
1:a[l] 2:m+1 3:r 4:0 5:101 6:1 7:4 8:v-u-1<br>
暇だったから解いたがツマラン+間違っててもシラネ<br>
つーか、なんだこの問題。こんなの分割統治にしても<br>
ある程度以上の個数なら関数呼び出しのオーバーヘッドの方がでかいだろうに<br>
クイックソートとか二分探索の方が問題としてもいいと思うがな<br>
<br></dd>
<dt>244 :<font color="green"><b>デフォルトの名無しさん</b></font>
:2005/11/03(木) 23:08:11</dt>
<dd><a href="http://pc8.2ch.net/test/read.cgi/tech/1130431335/243" target=
"_blank">>>243</a><br>
どうも、有難うございます。4、5は、同感です。1~3を代入してプログラムを動かしてみて、6~8の確認をします。<br>
有難うございます。<br>
<br></dd>
<dt>245 :<a href="mailto:sage"><b>デフォルトの名無しさん</b></a>
:2005/11/03(木) 23:10:07</dt>
<dd><a href="http://pc8.2ch.net/test/read.cgi/tech/1130431335/243" target=
"_blank">>>243</a>は微妙に間違っている罠。<br>
<br></dd>
<dt>246 :<a href="mailto:sage"><b>デフォルトの名無しさん</b></a>
:2005/11/03(木) 23:15:26</dt>
<dd><a href="http://pc8.2ch.net/test/read.cgi/tech/1130431335/245" target=
"_blank">>>245</a><br>
やっぱり間違ってたか<br>
とりあえず半閉区間[l,r)だという事まで考えたところでやる気が尽きたから適当にやったからな<br>
6以降はあんま考えてないし<br>
<br></dd>
<dt>247 :<font color="green"><b>デフォルトの名無しさん</b></font>
:2005/11/03(木) 23:16:40</dt>
<dd><a href="http://pc8.2ch.net/test/read.cgi/tech/1130431335/238" target=
"_blank">>>238</a><br>
243が答えてしまったがせっかく作ったので<br>
#include <stdio.h><br>
<br>
double sum( double a[], int l, int r )<br>
{<br>
printf( "sum( %x, %d, %d )\n", a, l , r ) ;<br>
int n = r - l ;<br>
int m = ( l + r ) / 2 ;<br>
<br>
if( n == 0 ){<br>
printf( "Nullpo\n" ) ;<br>
return 0.0 ;<br>
}<br>
if( n == 1 ){<br>
printf( "Gatt%lf\n", a[ l ] ) ;<br>
return a[ l ] ;<br>
}<br>
return sum( a, l, m ) + sum( a, m, r ) ;<br>
}<br>
<br>
int main()<br>
{<br>
double x[] = { 0, 1, 2, 3, 4, 5 } ;<br>
<br>
printf( "sum=%lf\n", sum( x, 0, sizeof( x ) / sizeof( x[0] ) ) ) ;<br>
return 0 ;<br>
}<br></dd>
</dl>
表示オプション
横に並べて表示:
変化行の前後のみ表示: