様式９ +-------------------------------------+----------------+----------------------+ | ｼｽﾃﾑ名(ｺｰﾄﾞ): ＡＬＧＯＰＡＫ | | システム報告書概要 | +-------------------------------------+ +----------------------+ | ﾓｼﾞｭｰﾙ名(ｺｰﾄﾞ): REPSORT(A219) | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者･学生番号: 増沢善子21SS1159 | 文書作成者･学生番号: 増沢善子21SS1159 | +-------------------------------------+---------------------------------------+ | 作成期間: 62/01/ ー / / | 文書作成期間: 62/02/ ー / / | +-------------------------------------+---------------------------------------+ | 親モジュール: ＡＬＧＯＳ | 子モジュール: | +-------------------------------------+---------------------------------------+ | 講義名・課題名: 卒業研究 | 参考文献(著者名、書名、出版社、発行年)| +-------------------------------------+ | | 開発形態: 移植 | SARA BAASE,COMPUTER ALGORITHMS | +-------------------------------------+ | | 形式: サブルーチン | ADDITION WESLEY 1981 | +-------------------------------------+---------------------------------------+ | 利用対象者: 一般 | 格納ﾒﾃﾞｨｱ形式: フロッピーディスク | +-------------------------------------+---------------------------------------+ | 目的（問題解説、機能解説−制限事項）| 格納ﾒﾃﾞｨｱ番号、ﾌｧｲﾙ名: | | マ−ジソ−トのための連の作成 +---------------------------------------+ | | 記述言語・走行ＯＳ: TURBO PASCAL　　 | | +---------------------------------------+ | | 走行条件（ハードウェア、ソフトウェア）| | | ＰＣ−９８０１ | | | | | | ＭＳ−ＤＯＳ | +-------------------------------------+---------------------------------------+ | キーワード（適用分野、手法など） ： | 分類コード（ＣＲコードを使用） ： | | REPLACEMENT SELECTION | | +-------------------------------------+---------------------------------------+ | 呼び出し法: REPSORT(VAR INFILE,OUTFILE:TEXT; LEN:INTEGER); | | | +-----------------------------------------------------------------------------+ | 操作手順(ｺﾝﾌﾟﾘｰﾄﾌﾟﾛｸﾞﾗﾑ(ﾒｲﾝﾌﾟﾛｸﾞﾗﾑ)の場合:1.システム起動手順､2.データ入出力 | | 手順と形式､3.終了手順) | | (ｻﾌﾞﾙｰﾁﾝの場合:1.呼び出し形式-引き数の並べ方-､2.親ルーチン､3.子ルー | | チン､4.その他) | | infile :入力ファイル | | | | outfile:出力ファイル | | | | len :内部バッファの大きさ | | | | 1 呼び出し形式 | | | | repsort(infile,outfile,len) | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 注. システム１つにつき１枚作成 必要な場合モジュール１つにつき１枚作成(ｲﾝﾀｰﾌｪｰｽ仕様書-様式１-に追加) 様式７ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | 問題解説 | +-------------------------------------+ +----------------------+ | モジュール名: REPSORT-1 | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 三村晶子 20SS1143 | 文書作成者: 三村晶子 20SS1143 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/09/ ー 61/01/ | 文書作成期間: 61/01/ ー 61/01/ | +-------------------------------------+---------------------------------------+ | | | ＲＥＰＬＡＣＥＭＥＮＴ ＳＥＬＥＣＴＩＯＮ | | | | 併合による整順列化では, なるべく少ない数の連から出発する方が全体の手数が | | 少なくてすむ｡ つまり初期連をできるだけ長くした方がよい｡ 限られた内部記憶を | | 用いて長い連を作り出すにはどうすればよいか｡ | | すぐ思いつく方法は, 入力ファイルからできるだけ多くの記録を内部記憶に読み | | 込み, クイックソ−トなどの内部整列法で整順列とし, これを出力する方法である | | ｡ この方法の利点は, 最後の連は別として初期連の長さが一定であるから, プログ | | ラムを少しだけ簡単にできることである｡ | | ところで, 内部記憶にＭ個の記録しか収まらないとき, Ｍより長い連を作れない | | だろうか｡ 下図のような, ２桁の整数の列が与えられたとき, これをＭ＝３の内部 | | | | 入力ファイル 78,45,72,59,20,43,85,33,92,81,34,85,16,49,61,･･･ | | 内部記憶の変化 78 *45 72 | | Ｍ＝３. * 印を出 78 *59 72 | | 力し, そこに入力 78 20 *72 | | *78 20 43 | | *85 20 43 | | ------------ 第１の連の終わり | | 33 *20 43 | | *33 92 43 | | 81 92 *43 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式７ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | 問題解説 | +-------------------------------------+ +----------------------+ | モジュール名: REPSORT-2 | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 三村晶子 20SS1143 | 文書作成者: 三村晶子 20SS1143 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/09/ ー 61/01/ | 文書作成期間: 61/01/ ー 61/01/ | +-------------------------------------+---------------------------------------+ | 一番重い所からは一番軽い方へと巡回的に出力していく模様と類似している｡ この | | 運転が定常的になっているとする｡ 入力が一様であれば出力位置の移動は等速度と | | なり, 溜まっている油の量の分布は, 今取り出そうとしている点から１周期の間, | | 一定勾配で減少している｡ さて, １周期で出力する量（即ち連の長さ）は, 現在量 | | 全部と, １周期中に入る量の半分すなわち現在量に等しい量である｡ TUMARI, 現在 | | 量の２倍, 分溜塔の容量の２倍が１周期の出力である｡ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: REPSORT-1 | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 三村晶子 20SS1143 | 文書作成者: 三村晶子 20SS1143 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/09/ ー 61/01/ | 文書作成期間: 61/01/ ー 61/01/ | +-------------------------------------+---------------------------------------+ | ++-------++ +-----+ ++-------++ +--------!! +---------+ | | !!MODULE !! +TYPE + !!HEAP-BU!! !PACKED !! !INTEGER ! | | !!REPSORT!!-+-+ +---!!FF !!--!ARRAY !!--! ! | | !! !! ! + + !! !! ![1..20] !! ! ! | | ++-------++ ! +-----+ ++-------++ +--------++ +---------+ | | ! ++-------++ +-----+ +-------+ +---------+ | | ! !!PROCEDU!! +PARAMET+ + X,Y + !INTEGER ! | | +-!!RE !!-+-+ ER +--! !--! ! | | ! !!SWAP !! ! + + + + ! ! | | ! ++-------++ ! +-----+ +-------+ +---------+ | | ! ! +-----+ +-------+ +---------+ | | ! ! + VAR + + Z + !INTEGER ! | | ! +-+ +--! !--! ! | | ! ! + + + + ! ! | | ! ! +-----+ +-------+ +---------+ | | ! ! +---------+ | | ! ! !Z:=X,X:=Y! | | ! +-!Y:=Z ! | | ! ! ! | | ! +---------+ | | ! +---------+ | | ! !REPS ! | | +-+---------+ | | ! ! | | +---------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: REPSORT-2 | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 三村晶子 20SS1143 | 文書作成者: 三村晶子 20SS1143 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/09/ ー 61/01/ | 文書作成期間: 61/01/ ー 61/01/ | +-------------------------------------+---------------------------------------+ | +---------+ ++-------++ +-----+ +-------+ +---------+ | | !REPS ! !!PROCEDU!! +PARAMET+ +INFILE, + !TEXT ! | | +---------+--!!RE !!-+-+ ER +-+-!OUTFILE !--! ! | | ! ! !!REPSORT!! ! + + ! + + ! ! | | +---------+ ++-------++ ! +-----+ ! +-------+ +---------+ | | ! ! +-------+ +---------+ | | ! ! +LEN + !INTEGER ! | | ! +-! !--! ! | | ! + + ! ! | | ! +-------+ +---------+ | | ! +-----+ +-------+ +---------+ | | ! + VAR + +BUFF + !HEAP-BUFF! | | +-+ +-+-! !--! ! | | ! + + ! + + ! ! | | ! +-----+ ! +-------+ +---------+ | | ! ! +-------+ +---------+ | | ! ! +DATA,I, + !INTEGER ! | | +-------------+ +-!TAIL,LAST!--! ! | | ! +-DATA + ! ! | | ! +-------+ +---------+ | | ! ++-------++ +---------+ | | ! !!PROCEDU!! ! I:=0 ! | | +--!!RE FIRS!!--! ! | | ! !!T-READ !! ! ! | | ! ++-------++ +---------+ | | ! ! | | ! +--------++ +---------+ | | ! !REPEAT !! !I:=I+1 ! | | ! ! !!--! ! | | ! ! !! ! ! | | ! +--------++ +---------+ | | ! ! ! | | +---------+ ! +---------+ | | !LAST-OUT ! ! +READ + | | +---------+ ! +(INFILE, + | | ! ! ! +DATA + | | +---------+ ! +---------+ | | ! ! | | ! +---------+ | | ! !BUFF[I] ! | | ! !:=DATA ! | | ! ! ! | | ! +---------+ | | ! +--------+ +---------+ | | ! !UNTIL EOF+ !EXIT ! | | +------!(INFILE)OR+--! ! | | !(I:=LEN) + ! ! | | +--------+ +---------+ | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: REPSORT-3 | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 三村晶子 20SS1143 | 文書作成者: 三村晶子 20SS1143 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/09/ ー 61/01/ | 文書作成期間: 61/01/ ー 61/01/ | +-------------------------------------+---------------------------------------+ | +---------+ ++-------++ +-----+ +-------+ +---------+ | | !LAST ! !!PROCEDU!! +PARAMET+ +TAIL + !INTEGER ! | | +---------+--!!RE LAST!!-+-+ ER +--! !--! ! | | ! ! !!-OUT !! ! + + + + ! ! | | +---------+ ++-------++ ! +-----+ +-------+ +---------+ | | ! ! +--------++ ++-------++ | | ! ! !REPEAT !! !!MAKEHEA!! | | ! +-! !!--!!P !! | | ! ! ! !! !! !! | | ! ! +--------++ ++-------++ | | ! ! ! ! | | ! ! ! +---------+ | | ! ! ! +WRITE(OUT+ | | ! ! ! +FILE,BUFF+ | | ! ! ! +[1]) + | | ! ! ! +---------+ | | +---------+ ! ! ! | | !TAIL:=LEN! ! ! +-----------+ | | ! ! ! ! !BUFF[1]:=BU! | | ! ! ! ! !FF[TAIL],TA! | | +---------+ ! ! !IL:=TAIL-1 ! | | ! ! ! +-----------+ | | ++-------++ ! ! +-------+ +---------+ | | !!FIRST-R!! ! ! !UNTIL + !EXIT ! | | !!EAD !! ! +-------!TAIL=0 +--! ! | | !! !! ! ! + ! ! | | ++-------++ ! +-------+ +---------+ | | ! ! | | +---------+ ! +---------+ | | !LAST-2 ! ! +WRITELN + | | +---------+ +---+(OUTFILE)+ | | ! ! + + | | +---------+ +---------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 様式６ +-------------------------------------+----------------+----------------------+ | システム名: ＡＬＧＯＰＡＫ | | アルゴリズム流れ図 | +-------------------------------------+ +----------------------+ | モジュール名: REPSORT-4 | ﾗｲﾌﾞﾗﾘ-登録番号: | +-------------------------------------+---------------------------------------+ | 作成者: 三村晶子 20SS1143 | 文書作成者: 三村晶子 20SS1143 | +-------------------------------------+---------------------------------------+ | 作成期間: 60/09/ ー 61/01/ | 文書作成期間: 61/01/ ー 61/01/ | +-------------------------------------+---------------------------------------+ | +---------+ | | !LAST-2 ! | | +---------+ | | ! ! | | +---------+ | | ! +-------+ ++-------++ | | ! !IF + !!LAST-OU!! | | +--!I crepsort | | | | buffer size? 6 | | | | A> | | | | 注） 下線部は，システム側からの応答 | | | | | | | | | | | | | | | | | | | +-----------------------------------------------------------------------------+ 注. システム１つにつき１枚作成 必要な場合モジュール１つにつき１枚作成(ｲﾝﾀｰﾌｪｰｽ仕様書-様式１-に追加)