質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

524閲覧

分割統治法による区間の合計値の計算をしているコードでわからないところ

jaogjig

総合スコア21

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2023/01/10 16:40

前提

分割統治法による区間の合計値の計算をしているコードです。
なぜsolve(1,2)とsolve(2,3)は3+1で足すのでしょうか
return s1 + s2;が使われているのでしょうか
しかし、コードを見る限り一番最後に合計を足すだけにreturn s1 + s2;が使われているようにしか見えません。
なぜ3+1をするのかわかりますか

分割統治法による区間の合計値の計算をしているコード

#include <iostream> using namespace std; int N, A[109]; int solve(int l, int r) { if (r - l == 1) return A[l]; int m = (l + r) / 2; // 区間 [l, r) の中央で分割する int s1 = solve(l, m); // s1 は A[l]+...+A[m-1] の合計値となる int s2 = solve(m, r); // s2 は A[m]+...+A[r-1] の合計値となる return s1 + s2; } int main() { // 入力 cin >> N; for (int i = 1; i <= N; i++) cin >> A[i]; // 再帰呼び出し → 答えの出力 int Answer = solve(1, N + 1); cout << Answer << endl; return 0; }

補足情報(FW/ツールのバージョンなど)

C++
ここにより詳細な情報を記載してください。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

episteme

2023/01/10 18:54

配列の 前半部の総和 と 後半部の総和 を加えたら 配列全体の総和 が求まります。 それを再帰的にやってるんですけど...
ALOHAMS

2023/01/11 01:07

入力値を追記していただけますか?
jaogjig

2023/01/11 04:59

N=4、a(3,1,4,1)です。
episteme

2023/01/11 05:14

solve([3,1,4,1]) = solve([3,1]) + solve([4,1]) = ( solve([3]) + solve([1]) ) + ( solve([4]) + solve([1]) ) = ( 3 + 1 ) + ( 4 + 1 ) = 4 + 5 = 9
jaogjig

2023/01/11 05:35

回答ありがとうございます。
guest

回答1

0

ベストアンサー

前提

solve(int l, int r)関数は言ってしまえばデータの集合をトーナメント表式や決定木分類みたいに分割する処理を再帰的に行う関数です。
分かりやすい図を見つけたのでこちらのサイトを見てください。こちらはクイックソートの例ですが分ける部分の図示は全く同じです。
アルゴリズムとデータ構造④

中身の解説

では流れを見てみましょう。

int m = (l + r) / 2; // 区間 [l, r) の中央で分割する int s1 = solve(l, m); // s1 は A[l]+...+A[m-1] の合計値となる int s2 = solve(m, r); // s2 は A[m]+...+A[r-1] の合計値となる

ここがデータの分割の本筋です。データがまだ2個以上あるなら半分に分けるでという処理を行っています。この処理はそれだけです。
そして、データを半分に半分に…としていくと、最終的には1つになります。トーナメントも1:1ですよね。

if (r - l == 1) return A[l];

コード最初のこの一文は 「データが1個になったら中身教えろや!」っていう意味です。 ここでようやく最初の結果が返ってきます。(再帰処理の終端)
ここで終端の一つ手前に戻ってみると、

int s1 = solve(l, m); // 終端到達時はs1=A[l] int s2 = solve(m, r); // 終端到達時はs2=A[m] return s1 + s2;

1:1の隣り合うデータを合計して返してることがわかります。

そして、トーナメント表見ればわかることですが、この分割方法はダブりが発生しないので最終的に左半分データの合計+右半分データの合計という形まで戻ってくることがわかります。

だから最終的にA[1]~A[N]までの総和が結果として帰ってくるのです。
3+1に関してはよくわかりませんが、ご自身でcinで1,3,1みたいに入力したからではないですか?

投稿2023/01/11 01:04

編集2023/01/11 01:08
pig_vba

総合スコア807

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

jaogjig

2023/01/11 05:05

理解できました。(1、3)の関数で戻ってS2の方を処理することを抜け落ちていました。ありがとうございます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問