Mr.Tです、こんにちは。
アルゴリズムは、プログラム（マ）になくてはならないのに、プログラマ初心者にとっては、なかなかアルゴリズム自体を
学ぶ機会は少ないです。
アルゴリズムを勉強するのに、実はコンピュータなんかいらないと考えています。
紙と鉛筆さえあれば、学べます。
問題：
毛虫が10メートルの深さの土管の底に落ちました。なんとか、頑張って毛虫は、地上に出たい。
しかし、毛虫は昼間頑張って3メートル上っても、夜になって寝てしまうと2メートルずり落ちます。
毛虫は、何日目に地上に出ることができるでしょう？
ただし、10メートルちょうどでは、地上に出たことにはなりません。
移動速度は一定で、地上にたどりつくまで変化はありません。天候や、環境には、移動には無関係です。
土管を登る際に、障害物はなく、まっすぐ10メートルです。
一日の区切りは、朝の6時から夕方の6時までが昼とし、翌日6時までが夜です。
毛虫が落ちたのは朝6時ちょうどで、そこから日にちを1日と数えるとします。
解き方：
これは、最大最小問題の変形です。
最大値を求めるというアルゴリズムは、比較をどうやって行うか、がミソです。
まずは、何をもとめるのかを見極めます。
ここでは、「何日後に毛虫が地上に出れるか？」が求めるものです。
まずは、問題を整理しましょう。
１）条件を抜き出します。
ここで抜き出すときには、必要な条件なのか、必要じゃないのかは、考えません。
・土管はまっすぐ10メートルの深さ
・昼間3メートル登る
・夜2メートル落ちる
・移動速度は一定
・6時～18時が昼
・18時～翌6時が夜
・落ちた日を1日と数える
２）地上にでた、ということはどういうことなのか？
10メートルちょうど、では地上に出てません。
逆に言えば、10メートル1センチでも地上にでたことになります。
日本語を使えば、「10メートルを超えること」です。
この意味の変換に慣れることが、重要です。
ということは、「毛虫の移動距離が10メートルを超えたら地上にでたことになるので、そのときは何日目か？」
を求める、という問題になります。
３)10メートルを超えるってどういうことだ？
ようやくここで、数字を使います。メートルは邪魔なので、省略しますね。
超えるってのは、数字を使うと、不等号の＜や＞のようにイコールがないものですね。
10 <10.0001 , 10<11
例えば、上のようなときです。 考える時は、適当な数字やサンプルで考えましょう。
４）じゃあ、毛虫は、どのくらい進むんだっけ？
条件を見直しましょう。昼に3メートル進みますが、夜に2メートル戻ってしまいます。
じゃあ、実際に一日ごとに、その動きを追ってみましょう。（ステップで追うということです）
| 日にち | 全体的な移動距離 |
| １ | 1m |
| ２ | 2m |
| ３ | 3m |
| ４ | 4m |
| ５ | 5m |
| ６ | 6m |
| ７ | 7m |
| ８ | 8m |
| ９ | 9m |
はい、これで「なーんだ11日じゃないかぁ」と思った人。
間違いですから。
いいですか？求めるのは、
「毛虫の移動距離が10メートルを超えたら地上にでたことになるので、そのときは何日目か？」
です。求めるゴールは、何度も見直してチェックするんです。
つまり、地上にでるのは常に、昼で動いているときです。10メートルかどうかをチェックするのは
一日でどんだけ動いたか、じゃないんです。
一日目は1mしか進みません。次の日、毛虫の開始場所は、1mからです。
そこから、3m登ります。
で、夜に2m落ちます。
で、2日目は１メートルからの出発で、3メートル登りますから、昼のおしまいには
4メートルの場所にいることになります。
これを踏まえて、表に列を二つ追加します。
| 日にち | 昼間の総合移動距離 | 夜の落ちる距離 | その日の移動距離 |
| １ | 3m | 2m | 1m |
| ２ | 4m | 2m | 2m |
| ３ | 5m | 2m | 3m |
| ４ | 6m | 2m | 4m |
| ５ | 7m | 2m | 5m |
| ６ | 8m | 2m | 6m |
| ７ | 9m | 2m | 7m |
| ８ | 10m | 2m | 8m |
| ９ | 11m | 2m | 9m |
はい、コレで答えがわかりましたね。9日です。
これを文字で、その動きを追っていくようにします。
- 今から登ります。
- まだ、0mです。
- 1日目。
- 昼間3m登る。今は、3mの場所にいます。
- まだ、10mを超えてません
- 夜2m落ちる。
- 合計1m。
- 2日目。
- 昼間3メートル登る。今は、4mの場所にいます。
- まだ、10mを超えてません。
- 夜2m落ちる。
- 合計2m。
- 3日目。
- 昼間3m登る。今は、5mの場所にいます。
- まだ、10mを超えてません。
- 夜2m落ちる。
- 合計3m。
- 4日目。
- 昼間3m登る。今は、6mの場所にいます。
- まだ、10mを超えてません。
- 夜2m落ちる。
- 合計4m。
- 5日目。
- 昼間3m登る。今は、7mの場所にいます。
- まだ、10mを超えてません。
- 夜2m落ちる。
- 合計5m。
- 6日目。
- 昼間3m登る。今は、8mの場所にいます。
- まだ、10mを超えてません。
- 夜2m落ちる。
- 合計6m。
- 7日目。
- 昼間3m登る。今は、9mの場所にいます。
- まだ、10mを超えてません。
- 夜2m落ちる。
- 合計7m。
- 8日目。
- 昼間3m登る。今は、10mの場所にいます。
- まだ、10mを超えてません。
- 夜2m落ちる。
- 合計8m。
- 9日目。
- 昼間3m登る。今は、11mの場所にいます。
- 10メートルを超えました。
これで、ようやく毛虫が地上にでていることがわかります。
長くなったので、次回に続きます。