流れ図について

質問

次(添付)の流れ図は、
最大値選択法によって値を大きい順に整列するものである。
＊印の処理(比較)が実行される回数を表す式は、どれか。

正解
n(n-1)/2
4+3+2+1=10(下記参照)を満たすものを探します。

n=5でトレースしています。
仮のデータを3,8,2,4,6として下さい。

自力で解釈しようとしたのですが、
添付した流れ図のトレースの仕方が分かりません。
お手数ですがトレースの仕方を詳しく教えて下さい。

仮のデータとは、何処で使っているのですか。
数式での回数とは、どういうことですか。

ご説明して頂ける方おられましたら、ご教授お願いします。

以上、よろしくお願い致します。

回答No.2

jjon-com · ベストアンサー

> 仮のデータとは、何処で使っているのですか。

　X(1) X(2) X(3) X(4) X(5)
＋――＋――＋――＋――＋――＋
｜　３｜　８｜　２｜　４｜　６｜
＋――＋――＋――＋――＋――＋

> 数式での回数とは、どういうことですか。

具体例としてｎ＝５でトレースすると，

ｉ＝１のとき，ｊは２，３，４，５と「４回ループ」
　　ｎ＝５なので「ｎ－１回ループ」と，変数ｎを用いた数式で表現できる

以下同様に，
ｉ＝２のとき，ｊは３，４，５と「３回ループ」（「ｎ－２回ループ」）
ｉ＝３のとき，ｊは４，５と「２回ループ」（「ｎ－３回ループ」）
ｉ＝４のとき，ｊは５と「１回ループ」（「ｎ－４回ループ」）

よって比較処理が実行される総回数は，
ｎ＝５の場合は，４回＋３回＋２回＋１回 ＝ 10回。

変数ｎで表すならば，(ｎ－１)＋(ｎ－２)＋(ｎ－３)＋……＋３＋２＋１。
ガウスの計算公式より，
(１ ＋ (ｎ－１))×(ｎ－１)÷２ ＝ ｎ×(ｎ－１)／２
http://www.t-tsushin.net/kaihou/kei/p4.html
http://blog.chugaku-juken.net/article/135769894.html

> 添付した流れ図のトレースの仕方が分かりません。
> お手数ですがトレースの仕方を詳しく教えて下さい。

かなり手間がかかるので，私はパスします。

お礼

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

ご丁寧に説明して頂いたので、理解することが出来ました。
また情報のURLを添付して頂き、ありがとうございます。

まだ全てをトレースした訳ではありませんが、あとは自力で頑張ってみます。

以上、ありがとうございました。

回答No.1

osamuy

添付図みたままでは。

＞ 仮のデータとは、何処で使っているのですか。

プログラム中の配列Xかと。

＞ 数式での回数とは、どういうことですか。

n=5としているから、4ならn-1、3ならn-2ということかと。

この問題は、たぶん計算量についての勉強かと思われますので、
配列要素の数と比較回数との関連に気付いてほしいという願いが込められてるのでしょう。
あてずっぽうですが。

なので、分からないことがあったら、先生に聞いたほうが効率的かと。

お礼

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

お陰様で仮のデータを使う場所が分かりました。
あとは自力でトレースしてみようと思います。

以上、ありがとうございました。