2020　島根大学　推薦I総合理工（知能情報デザイン学科）学部MathJax

$m=a_k\times N^k+a_{k-1}\times N^{k-1}+\cdots$$+a_1\times N^1+a_0\times N^0$(1)

の形で表すことができる．ここで，$k$は$k\geqq 0$なる整数，$a_0\text{，}$$a_1\text{，}$$\cdots \text{，}$$a_k$はすべて$0$以上$N-1$以下の整数である．ただし，$a_k\ne 0$である．そこで，式(1)の右辺を${a_k{a}_{k-1}\cdots a_0}_{(N)}$と表す．つまり，

$m={a_k{a}_{k-1}\cdots a_0}_{(N)}$(2)

である．$m$を式(2)の右辺で表したものを$N$進法表記という．例えば，${19}_{(10)}$を$2$進法で表すと$1\times 2^4+0\times 2^3+0\times 2^2+1\times 2^1+1\times 2^0={10011}_{(2)}$である．以下の問に答えよ．ただし，値を求める問は$10$進法で答えよ．

(a)　ある正の整数$x$を$3$進法で表すと${21021}_{(3)}$であるとき，$x$の値を求めよ．

(b)　(a)で求めた$x$を$3$倍して$1$加えた整数を$y$とするとき，$y$を$3$進法で表せ．

(c)　$N$を$4$以上の整数とする．正の整数$m$を$N$進法で表すと${1331}_{(N)}$であるとき，$m$を$(N+1)$進法で表せ．

(d)　$N$を$3$以上の整数とする．${210}_{(N)}={121}_{(N+1)}$を満たす$N$の値を求めよ．ただし，導出過程も述べよ．

(例１)

$A=\{2,5,10,1000\}$

$B=\{1,3,5,7\}$

集合$A$の要素の数を$n(A)$と表し，集合$A$の要素のうち値が小さい順に$i$番目のものを$A_i\text{．}$ただし$i=1\text{，}$$\cdots \text{，}$$n(A)$と表す．例１では$n(A)=4$であり，$A_1=2\text{，}$$A_2=5\text{，}$$A_3=10\text{，}$$A_4=1000$である．$2$つの集合の差集合$A-B$は，$A$に含まれる要素のうち$B$に含まれない要素からなる集合である．例１では$A-B=\{2,10,1000\}$となる．

　次に示すものは，与えられた$2$つの集合$A\text{，}$$B$に関する何らかの計算を行う手順のひな形である．このひな形に従う手順では，ステップ$\text{①}\text{〜}$$\text{⑧}$を実行するにつれて集合$C$が更新されていき，手順が終了した時点で$C$が計算結果となる．

手順のひな形

$\text{①}$　集合$C$を空集合にする．

$\text{②}$　$i$を$1$とし，$j$を$1$とする．

$\text{③}$　$i>n(A)$または$j>n(B)$であればステップ$\text{⑧}$に進む．

$\text{④}$　$A_i$と$B_j$の大小を比較する．

$\text{⑤}$　比較した結果が$A_i=B_j$である場合，$i$と$j$を$1$ずつ増やし，ステップ$\text{③}$に戻る．

$\text{⑥}$　比較した結果が$A_i<B_j$である場合，$i$を$1$増やし，ステップ$\text{③}$に戻る．

$\text{⑦}$　$j$を$1$増やし，ステップ$\text{③}$に戻る．

$\text{⑧}$　$$この手順を終了する．

(a)　ひな形を利用して，$2$つの集合$A\text{，}$$B$の共通部分$A\cap B$を求める手順を作成する．

1)　手順のひな形のステップ$\text{⑤}\text{〜}$$\text{⑦}$の一部の空欄に「$A_i$を$C$に新しい要素として追加し」という語句を入れて，共通部分を求める手順を完成させたい．語句を入れるべきステップの番号をすべて答えよ．

2)　例１の$A\text{，}$$B$を与えてこの手順を行ってステップ$\text{④}$が最初に実行されるとき，比較される$A$と$B$の要素はそれぞれ$A_1$と$B_1$である．この要素の組をその値により$(2,1)$と表記することにする．その後，手順が終了するまでにステップ$\text{④}$の実行で比較される要素の組をこの表記に従ってすべて記せ．

(b)　差集合$A-B$を求める手順を作成する．

1)　手順のひな形のステップ$\text{⑤}\text{〜}$$\text{⑦}$の一部の空欄に「$A_i$を$C$に新しい要素として追加し」という語句を入れた手順を作成し，例１の$A\text{，}$$B$を与えてこの手順を行うと，$C=\{2\}$が得られる．語句を入れるべきステップの番号をすべて答えよ．

2)　1)に加えて，ステップ$\text{⑧}$の空欄に「$i\leqq n(A)$であれば」で始まる内容を補うことで，差集合を求める手順を完成させたい．ステップ$\text{⑧}$の空欄に補う内容を記せ．

　盤面の斜線が入ったマス目は壁や柱を表しており，これらに入ろうとするとロボットが故障する．初期状態でロボットは，$\mathrm{S}$と記入されているマスに北向きに置かれるものとする．例えば図１では，ロボットの初期状態の位置は南西の隅である．図２の$\mathrm{P}$や$\mathrm{Z}$はそれぞれ，汚染されている箇所と，ロボットが通過して汚染が除去された箇所を表している．

　ロボットが受け付けるのは，下表に示す指令を$1$つ以上連ねた「指令列」である．

指令	動作内容
$\mathrm{F}$	今向いている方向に$1$マス進む．
$\mathrm{R}$	今向いている方向の右$90$度に方向を変える．
$\mathrm{L}$	今向いている方向の左$90$度に方向を変える．
数（指令列）	指令列を数で指定された回数繰り返す．数は$2\text{〜}$$9$の整数とする．

図１：屋内の様子を表す盤面の例	図２：図１の状態で「$3\{\mathrm{FRFFLF}\}$」を実行した結果

　ロボットの軌跡を灰色の破線（点線）で示すと，例えば図１の状態で，ロボットに$\text{「}\mathrm{FRFFLFFRFFLFFRFFLF}\text{」}$か$\text{「}3\{\mathrm{FRFFLF}\}\text{」}$あるいは$\text{「}3\{\mathrm{FR}2\{\mathrm{F}\}\mathrm{LF}\}\text{」}$という指令列を与えると，図２に示す結果を得る．

　本問では，指令列に含まれる$\mathrm{F}\text{，}$$\mathrm{R}\text{，}$$\mathrm{L}\text{，}$数の個数を以って指令列の長さとする．例えば$\text{「}\mathrm{FRFFLFFRFFLFFRFFLF}\text{」}$の長さは$18$で，$\text{「}3\{\mathrm{FRFFLF}\}\text{」}$と$\text{「}3\{\mathrm{FR}2\{\mathrm{E}\}\mathrm{LF}\}\text{」}$はともに長さ$7$である．

(a)　解答用紙の1)と2)の$2$つの盤面の初期状態において，ロボットに各々の盤面の上部に記載した指令列を与えたときの軌跡を解答用紙の盤面に実線で描け．ロボットが壁や柱に入ろうとして故障する場合は，その位置が分かるように図に注釈を加えよ．

(b)　解答用紙の盤面の初期状態において，ロボットが汚染されたマスの全てを通過する指令列で，指令列の長さができるだけ短く，ロボットが故障しないものを書け．さらに，指令列を実行したときに，ロボットが通過する軌跡を解答用紙の盤面に実線で描け．

解答用紙の図

(a)

1)　$\text{「}4\{2\{\mathrm{FR}\}2\{\mathrm{FL}\}\}\text{」}$	2)　$\text{「}8\{\mathrm{F}\}\mathrm{R}8\{\mathrm{F}\}\mathrm{R}7\{\mathrm{FRFL}\}\text{」}$

b)