読者です 読者をやめる 読者になる 読者になる

せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【アルゴリズム】【Ruby】アルゴリズムのいろいろ

まずは基本中の基本である
ソートはおさえたほうがいいよ
各種のソートの概要と計算量
んで、有名なソートのいくつか
バブル、クイックくらいは実装できるようにしたほうがいいよ

その後、リスト、グラフを理解すれば大体はいけるかな

という師匠の雷に対処すべく

バブル、クイックくらいは実装できるようにした

のが昨日。

どうやって進めるべか、と思っていたところ、

「アルゴリズム 練習問題」で検索したらヒットする、
アルゴリズムに関して書いてあるサイト

が良さそうだったので、まずはこれを読んでから

各種のソートの概要と計算量

に戻ることにしよう。


 
さくさく読む。
知らなかったことまとめ。

 

case文は、フローチャートの種類が違う

3つ以上の異なった処理の中から、条件にあった処理を行うことを多方向分岐と言う

言われたら確かに、if文とは、フローチャートの書き方が異なるわ。
アルゴリズムが別だから、

アセンブリ言語などこのようなアルゴリズムを サポートしていない言語もある。

のか。なるほど。

ネストを深く書いちゃいがち

1文字入力し、大文字('A'~'Z')ならば"大文字と、小文字('a'~'z')ならば "小文字"と表示せよ。

http://www5c.biglobe.ne.jp/~ecb/algorithm/3_7a.html

多重分岐で書いちゃった。
プログラミングだったら、解答の通りかけるけど、
こういう風に出されたらスマートにチャートがかけないって事は
「プログラミングのtips」として知ってるだけで、
そもそもアルゴリズムがどうとか、考えたことないからだろうなあ。。
気をつけよう。

問題も解く

4桁以内の正の整数を2つ以上入力し、入力された数の最大値、最小値を求め、 さらに何件目の入力かを表示せよ。ただし5桁以上もしくは負の数が入力 されたら終了とする。

http://www5c.biglobe.ne.jp/~ecb/algorithm/4_9b.html
a =(0...10000).to_a
a =( a.sample(4) << -1).sample(5)
p a

min = 10000
max = -1
min_doko = 0
max_doko = 0
kaisu = 0

a.each_with_index do |int, i|

  if int<0 or int>9999
  break

  else
    if min >int
      min = int
      min_doko = i
    end
    if max < int
      max = int
      max_doko = i
    end
    kaisu += 1
  end
end

if kaisu == 0
  p "だめな数しか入ってない"
  exit
end

p "min" + min.to_s
p "max" + max.to_s
p "min_doko" + min_doko.to_s
p "max_doko" + max_doko.to_s

■実行結果

[4683, 9054, 1362, 861, -1]
"min861"
"max9054"
"min_doko3"
"max_doko1"

解答とネストの深さが一緒だから、まあ大きくイケてないこともなさそう。
もっと良く書けるのかな。


each_with_indexメソッド。
「ブロック中でindexを取れるメソッドは絶対あるはず!」
と思いつつ、探してもなかなか分からなかった。
便利だな。
Arrayの公式ガイドもちゃんと読もう。

「素数を求めよう」まで読んでタイムアップ。
http://www5c.biglobe.ne.jp/~ecb/algorithm/5_5.html