CodeIQ/トグルスイッチ問題
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
トグル問題
この問題はCodeIQで結城浩先生から出題されたトグル問題につ...
-トグル問題の詳細は[[こちら>https://codeiq.jp/ace/yuki_hi...
-結城浩先生のCodeIQのページは[[こちら>http://www.hyuki.co...
-トグル問題のポイントは以下の2点
--すべてのトグルスイッチの状態を指定しなくてはいけない
--同じトグルスイッチの状態を指定してはいけない
-この状態で「トグルスイッチを変化させる最大の回数」を求め...
*見方を変えて [#a914035c]
-トグルスイッチの状態は、立方体として考えることができる
-例えば、トグルスイッチ3個の状態は立方体で表すことができる
#ref(立方体の図.png)
-この図だと、
--それぞれの軸に位が割り当てられており
--立方体=3軸あるので、3桁のトグルスイッチの状態を表すのに...
-こう見立てると、トグル問題はすべての頂点を移動する問題に...
--ただし、問題になるのは送信ボタンを押す際のトグルスイッ...
*更に見方を変えて [#vc631f7b]
-この問題、できることなら、なるべく多くのスイッチを変更し...
-1度に送信できる最大のスイッチ変化数は、トグルスイッチの...
--先の例で言えば3トグル、問題となるのは10トグルである
-トグルスイッチ3個の場合で言えば、1例としてこの状態の遷移...
000 <- -> 111
-この例では3トグル、1回の送信で得られる
-同様に、トグルスイッチの状態は、それぞれ真逆の状態とも言...
000 <- -> 111
001 <- -> 110
010 <- -> 101
011 <- -> 100
-少なくとも、「最大」を目標とするならば、ここに示した経路...
-その上で、
--このペア間をつなぐトグルコストが最大になる
--同じ経路を2度通らないことが保証される
-アルゴリズムを考えなくてはならない
-前述したように、3トグル変化する場合は、同じ状態に戻るだ...
-例題に書かれている様に、下記の様に遷移すると、3→2→3→2…の...
*最大の変化のために最小の変化を考える [#xb198363]
-なんとなく見えてきたと思うけれど、前述の遷移図を見るに、...
-なので、左側に並んでる数値の配列が、トグルスイッチ1個の...
終了行:
トグル問題
この問題はCodeIQで結城浩先生から出題されたトグル問題につ...
-トグル問題の詳細は[[こちら>https://codeiq.jp/ace/yuki_hi...
-結城浩先生のCodeIQのページは[[こちら>http://www.hyuki.co...
-トグル問題のポイントは以下の2点
--すべてのトグルスイッチの状態を指定しなくてはいけない
--同じトグルスイッチの状態を指定してはいけない
-この状態で「トグルスイッチを変化させる最大の回数」を求め...
*見方を変えて [#a914035c]
-トグルスイッチの状態は、立方体として考えることができる
-例えば、トグルスイッチ3個の状態は立方体で表すことができる
#ref(立方体の図.png)
-この図だと、
--それぞれの軸に位が割り当てられており
--立方体=3軸あるので、3桁のトグルスイッチの状態を表すのに...
-こう見立てると、トグル問題はすべての頂点を移動する問題に...
--ただし、問題になるのは送信ボタンを押す際のトグルスイッ...
*更に見方を変えて [#vc631f7b]
-この問題、できることなら、なるべく多くのスイッチを変更し...
-1度に送信できる最大のスイッチ変化数は、トグルスイッチの...
--先の例で言えば3トグル、問題となるのは10トグルである
-トグルスイッチ3個の場合で言えば、1例としてこの状態の遷移...
000 <- -> 111
-この例では3トグル、1回の送信で得られる
-同様に、トグルスイッチの状態は、それぞれ真逆の状態とも言...
000 <- -> 111
001 <- -> 110
010 <- -> 101
011 <- -> 100
-少なくとも、「最大」を目標とするならば、ここに示した経路...
-その上で、
--このペア間をつなぐトグルコストが最大になる
--同じ経路を2度通らないことが保証される
-アルゴリズムを考えなくてはならない
-前述したように、3トグル変化する場合は、同じ状態に戻るだ...
-例題に書かれている様に、下記の様に遷移すると、3→2→3→2…の...
*最大の変化のために最小の変化を考える [#xb198363]
-なんとなく見えてきたと思うけれど、前述の遷移図を見るに、...
-なので、左側に並んでる数値の配列が、トグルスイッチ1個の...
ページ名: