programing sisters 姉

プログラミングを学習するブログです

独学プログラマー22章読んでみた:アルゴリズム

 

この章以降はプログラマーとして働くのに必要な知識や心がけなどが書いてあるので、独学プログラマーの更新はおそらくこれで最後です。だいぶ時間かかったな。。。もっとハイスピードで勉強しないと卒論に全然間に合わないなぁと思ってます。ハイ。他人事の感じがやばいですね。

 

この章ではアルゴリズムについてでした。

アルゴリズム:特定の問題を解決するための再現可能な一連の手順

ということで何個かの問題の解決方法が載っていました。

 

 

FizzBuzz

 

これは1から100までの数字を出力するのに、3の倍数はFizz、5の倍数はBuzz、そして3と5の倍数はFizzBuzzと出力させるというものです。

f:id:yoshinon444:20181204173601p:plain

このように書けます。ここでポイントは3,5の倍数の処理を先に書くといことです。上から処理していくから順番大切!という感じです。次!

 

 

線形探索

 

探索アルゴリズムとは、データ構造の中から欲しいデータを探す処理です。
線形探索とは、要素を1つ1つ見ていくシンプルな探索アルゴリズムです。

ssという関数で探している要素があるかどうか調べて、あればその数字を出力しTrueを返します。なければそのままFalseを返します。

f:id:yoshinon444:20181204174906p:plain

breakはfor文を終わらせるものだから、if文の列と同じ並びかなと思ってたんですけど、もう一個下げなきゃいけないみたいで「??」と思った。

 

誰か教えて?

 

 

回文

 

ある文が回文か回文でないかを判定するプログラムです。

回文考える人ってすごいですよね。。どんな脳みそしてるんだろう。

f:id:yoshinon444:20181204175912p:plain

lower()することで大文字小文字を関係なく処理するためです。word[::-1]と書くことで文字列を逆転させることができるらしい。知らなかった。逆転させた文字列が元の文字列と同じなら回文なのでTrueとなり、違ければFalseを出力してくれます。

 

 

アナグラム

 

アナグラムとは、単語の文字を入れ替えて違う文字を作ることです。

pythonではソート(並べ替え)が簡単にできます。sorted()という組み込み関数があるからです。数字だと小さい順に並べ替えてくれ、文字だとabc順に並べ替えてくれます。なので二つの文字がアナグラムかどうか検証するプログラムがすごく簡単にかけます!

f:id:yoshinon444:20181102142344p:plain

たったのこれだけで書けちゃいました!ここでもlower()が活躍。

 

 

出現する文字列を数える

 

渡された文字列にどの文字が何回出現したかを数えるものをプログラミングします。辞書を使って、1文字づつループを回して実装しました。

f:id:yoshinon444:20181102144342p:plain

もし辞書の中にある文字がすでにあるならば+1をして、まだないなら1を代入するという流れです。このように要素の集まり(コレクション)を扱うのは頻繁にあるらしく、pythonの組み込みモジュールcollectioonsで提供されているらしいです。せっかくなのでこれを使っても書いてみました。

 

f:id:yoshinon444:20181102144700p:plain

これはcollectionsの中にあるdefaultdictというものを使っています。さっきより短くかけました!

 

f:id:yoshinon444:20181102144753p:plain

これはcollectionsの中にあるCounterというものを使っていて同じ動作をするのですが、関数すら自分で書く必要もなくなりました。簡単になりすぎてびっくりしました笑。

 

組み込みモジュールを自分で見つける能力が必要になってくるなと思いました。みんなが欲しいアルゴリズムならば組み込みモジュールにある確率が高いから、自分で0から書くよりもそっちを探す方が最終的には楽で速いかも。。

 

ここで不思議だったのは、出力が以下のようになり毎回合ってはいるんですけど順番がバラバラなんですよね。。なんで??

 

{'i': 1, 'e': 1, 'u': 1, 'a': 1, 'o': 4}

{'u': 1, 'a': 1, 'e': 1, 'o': 4, 'i': 1}

{'o': 4, 'u': 1, 'e': 1, 'a': 1, 'i': 1} etc...

 

わかる人教えてください~。

 

 

再帰問題

 

再帰:大きい問題を小さい問題に分割して解決する分割統治法で使われる手法

 反復法は手順を繰り返すことで問題を解決し、再帰法はその関数自身を呼び出します。反復法で解決できる問題ならば、全て再帰法でも解決できるらしい。再帰関数は無限に呼び出し続けられることを避けるために再帰終了条件を持たなければならないらしい。再帰終了条件とは、関数自身の呼び出しを終了する条件です。

 

再帰は守らなければいけないルールがあるそうです。

  1. 再帰終了条件を持つ
  2. 状態を変えながら再帰終了条件に進む
  3. 再帰的に関数自身を呼び出す

というルールです。

本では"99 Bottles of Beer on the Wall"という曲の歌詞を再帰法を使って出力してたんですけど、私は99本もビール飲めないので、7本にしておきました。

f:id:yoshinon444:20181204182153p:plain

 

出力

f:id:yoshinon444:20181204182257p:plain

こんな感じです。7本くらいなら飲めるので次の日のことも考えて、7本にしておきました。 numが1以下になるともうビールないよって出力してreturnで終わります。numが1より大きい時は、1つ引いて残りのビールの本数出力して、bottles_of_beer関数を再帰的に呼び出します。ちゃんと再帰終了条件あって、終わりに向かってるので上の3つのルール満たしてます!

 

 

終わり!

だいぶ前に途中まで書いてほったらかしてたけど折角書いてたからあげます。

さ、卒論のことはほっといてビール飲みにいくかな〜白目