OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

基数整列法について教えてください(後編)

  • すぐに回答を!
  • 質問No.211606
  • 閲覧数92
  • ありがとう数1
  • 気になる数0
  • 回答数1
  • コメント数0

お礼率 65% (36/55)

基数整列法について教えてください(前編)の続きです。
長文につき1投稿では入りきらないため、2回にわけております。

回答はこちら(後編)のほうにお願いいたします。

ちゃりお
--------------------------------------------------------------------

【流れ図】
端子:開始

処理:3→桁数

ループ始端:桁ループ(桁数=1、桁数)


 ループ始端:山数クリア(山番号=0,9)
 │
 処理:0→山数(山番号)
 │
 ループ終端:山数クリア
 │
 │
 ループ始端:分類ループ(番号=1、件数)
 │
 処理:ユーザ関数(番号、桁)→山番号・・・桁の数字を山番号に設定
 │
 処理:山数(山番号)+1→山数(山番号)/ データ(番号)→山(山番号、山数(山番号))
 │
 ループ終端:分類ループ
 │
 │
 処理:0→番号
 │
 │
 ループ始端:統合ループ(山番号=0,9)
 │
 │
  ループ始端:転送ループ(数=1、山数(山番号))
  │
  処理:番号+1→番号/ 山(山番号、数)→データ(番号)
  │
  ループ終端:転送ループ
 │
 │
 ループ終端:統合ループ


ループ終端:桁ループ

端子:終了

関連URL: http://oshiete1.goo.ne.jp/kotaeru.php3?q=211604
通報する
  • 回答数1
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.1
レベル7

ベストアンサー率 46% (6/13)

>整列の様子は理解できるのですが
ということなのでいきなり流れ図の説明からします

まず変数の使われかたから

データ(n):
 元々のデータが入っています
 整列後のデータもここに格納されます

山(山番号、山のデータ数):
 整列のためにデータを分類する場所です
 例えば、1桁目の数字で分類時の312は1桁目が2である数の3番目なので
 (いわば「2組の出席番号3番、312君」)
 
 山(2、3)=312
 
 となるわけです。

山番号:
 そのデータがどの山に入ればいいかを示す変数です

山数:
 それぞれの山にデータがいくつ入っているかを示しています
 つまり新しいデータを入れるときには
 
 山数(山番号)+1→山数(山番号)
 と、山数を一つ増やし
 
 データ(番号)→山(山番号、山数(山番号))
 と、そこにデータを入れればいいわけです

番号:
 データ(n)の何番目を処理中かを示す数です。



では流れ図を見ていきましょう

まず全体が
//////////////////////////////////////
処理:3→桁数

ループ始端:桁ループ(桁数=1、桁数)
//////////////////////////////////////
ループ終端:桁ループ
//////////////////////////////////////
の二つに挟まれています。
これは1桁目・2桁目・3桁目と同じ処理をしているだけです。


次にこの内部の先頭部分
////////////////////////////////////////////////////////////////
ループ始端:山数クリア(山番号=0,9)
 処理:0→山数(山番号)
ループ終端:山数クリア

ループ始端:分類ループ(番号=1、件数)
 処理:ユーザ関数(番号、桁)→山番号・・・桁の数字を山番号に設定
 処理:山数(山番号)+1→山数(山番号)
 処理:データ(番号)→山(山番号、山数(山番号))
ループ終端:分類ループ
////////////////////////////////////////////////////////////////
は、データ(n)に入っている数値を全て山に移し替える作業をしています。
山数クリアループは分類ループの前処理として存在します。
これは山数を0にする事により(実際にはデータが残っていたとしても)
山の内部を空にします。

分類ループは全データに対して同じ処理をするループです。
「全データに対し」
「まずユーザ関数でどの山に入ればいいかを求め」
「その山の定員を1増やし」
「最後尾に入れてやる」
「…」
と読んでください。


次に後半部分
/////////////////////////////////////////////////////////////
処理:0→番号

ループ始端:統合ループ(山番号=0,9)
 ループ始端:転送ループ(数=1、山数(山番号))
  処理:番号+1→番号
  処理:山(山番号、数)→データ(番号)
 ループ終端:転送ループ
ループ終端:統合ループ
//////////////////////////////////////////////////////////////
は、山の値を全てデータ(n)に戻す作業をします。
さっきと同じように番号を0にする事によってデータ(n)は空になりました。

こんどの6行は
「それぞれの山に対して」
「山の先頭から順番に」
「データ(n)の末尾の一個となりに」
「値を書き込んでいく」
「…」
「…」
と読んでください。
補足コメント
chaz

お礼率 65% (36/55)

minimumさん、

流れ図の解説、感謝いたします。理解をさらに深めることが出来ました。

4時間理解とトレースで格闘した挙句まだ行き詰まってしまいました(^^;どこで考え違いを犯しているのか、指摘いただけないでしょうか?

[データ]6件 ※トレース用にデータ数を若干減らしてあります
(1) (2) (3) (4) (5) (6)
423 121 231 232 253 312

[分類ループ]
桁ループ 分類ループ ユーザ関数 山数   山
桁数   番号    山番号   (山番号)(山番号、山数(山番号))
=====================================================================
1    1     3     1    423 → 山(3,1)
     2     1     2    121 → 山(1,2)
     3     1     3    231 → 山(1,3)
     4     2     4    232 → 山(2,4)
     5     3     5    253 → 山(3,5)
     6     2     6    312 → 山(2,6)

[統合ループ&転送ループ]
統合ループ 転送ループ 番号 山(山番号、数)→データ番号
山番号   数
=====================================================================
0     1     1  山(0,1) → データ (1)該当なし
      2     2  山(0,2) → データ (2)該当なし
      3     3  山(0,3) → データ (3)該当なし
      4     4  山(0,4) → データ (4)該当なし
      5     5  山(0,5) → データ (5)該当なし
      6     6  山(0,6) → データ (6)該当なし
1     1     7  山(1,1) → データ (7)該当なし
      2     8  山(1,2) → データ (8)121
      3     9  山(1,3) → データ (9)231
      4    10  山(1,4) → データ(10)該当なし
      5    11  山(1,5) → データ(11)該当なし
      6    12  山(1,6) → データ(12)該当なし
投稿日時 - 2002-02-08 22:54:05
お礼コメント
chaz

お礼率 65% (36/55)

minimumさん、

配列のスケールをずっと小さくして(213、132、321)トレースしたら、並べ替えが成功しました。とりあえず補足でのやり方でいいんですね。たいへん助かりました。ありがとうございます。

ちゃりお
投稿日時 - 2002-02-10 02:59:05
-PR-
-PR-
このQ&Aのテーマ
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ