26年春のアルゴリズムについて

26年春のアルゴリズムについて [1677]

icemanさん(No.1)

空き領域についてのアルゴリズムなのですが、他の問題と比べとても難しく感じました。iを添え字として用いるところなどは解説を読んでも理解でしません。皆さんから見てこの問題は普通なのでしょうか？また、もし可能でしたらご教授お願いします。

2019.02.20 10:40

名無しさん(No.2)

IPAの講評を見ると設問1の正答率は平均的で、設問2,3は低かったそうです
・問題文が長い
・設問数が3つありいずれも思考を要する
・パズルのような問題で混乱しやすい
という理由で私もかなり苦戦しました
解説は、youtubeに解説動画があったかと思います

私も勉強中なので、間違っていたらごめんなさい
添字Iは空きリストの番号です
この時、添字は0ではなく1から始まります
これは問題文にある図を見ながら考えれば分かりやすいと思います

空きリストの説明(2)の図で説明すると、
空きリストIは始点[I], 終点[I]なので、
空きリスト1は始点[1] -∞, 終点[1] 0
空きリスト2は始点[2] 3, 終点[2] 7
空きリスト3は始点[3] 9, 終点[3] +∞
となっています

要は空きリストを配列で管理してるんです
紛らわしいですがAlloc関数の引数である始点P, 終点Pはただの変数なので配列とは関係ないです
Alloc関数における始点P, 終点Pは確保したいメモリ領域の始点と終点を指定するものです

ついでに設問2のeも少し触れますね
これは添字が手掛かりになっています
・始点[L+1] ← 始点[L]
よくある配列の箱をイメージして欲しいのですが、右(末尾方向)へずらすと言う処理になってます
例えば、L=1なら始点[2]に始点[1]を代入します
当然何も工夫しなければ始点[2]を始点[1]が上書きしてしまいますので、それを避けるために先頭ではなく末尾からこの処理を行う必要があります

2019.02.20 15:45

スレッドの先頭へ»

その他のスレッド

»[1676] 勉強時間投稿数:3
»[1675] 午後試験のデータベースの勉強法について投稿数:3
»[1674] 【17年秋】問4のアルゴリズムについて投稿数:3

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの投稿はできません。