スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[Ruby][アルゴリズム入門]順位付け

第一章「ウォーミングアップ」 目次

1-0 アルゴリズムとは
1-1 漸化式
1-2 写像
1-3 順位付け
1-4 ランダムな順列
1-5 モンテカルロ法
1-6 ユークリッドの互除法
1-7 エラトステネスのふるい

単純な順位付け

テストの点数のデータがあったとき、その特典の順位を求める。

# coding: cp932
score = [56, 25, 67, 88, 100, 61, 55, 67, 76, 56]
juni = Array.new(score.size, 0)

score.each_with_index do |num, i|
  juni[i] = 1
  score.each_with_index do |num2, j|
    if num2 > num
      juni[i] += 1
    end
  end
end

puts "   得点  順位"
score.each_index do |i|
  printf "%6d%6d\n"%[score[i], juni[i]]
end


上記の改良

上記の順位を求めるアルゴリズムではデータがn個の場合、繰り返し回数はn^2となるため、データ数が増えると処理に時間がかかってしまう。そこで、繰り返し回数を減らすようにした順位付けアルゴリズムを考える。

# coding: cp932
score = [56, 25, 67, 88, 100, 61, 55, 67, 76, 56]
juni = Array.new(102, 0)

10.times do |i|
  juni[score[i]] += 1
end

juni[101] = 1
100.downto(0) do |i|
  juni[i] = juni[i] + juni[i + 1]
end

puts "   得点  順位"
score.each_index do |i|
  printf "%6d%6d\n"%[score[i], juni[score[i]+1]]
end


負のデータ版

ゴルフ(Golf)のscoreのように小さい値の方が順位が高い場合の順位付けについて考える。

# encoding: cp932
NUM = 10
MAX = 36
MIN = -20
BIAS = 1 - (MIN) # 最小値を配列要素の1に対応させる

score = [-3, 2, 3, -1, -2, -6, 2, -1, 1, 5]
juni = Array.new(MAX + BIAS + 1, 0)

score.each do |a|
  juni[a + BIAS] += 1
end

juni[0] = 1
((MIN + BIAS) + (MAX + BIAS)).times do |i|
  juni[i] = juni[i] + juni[i - 1]
end

puts " 得点 順位"
NUM.times do |i|
  printf "%6d%6d\n"%[score[i], juni[score[i] + BIAS - 1]]
end

テーマ : プログラミング - ジャンル : コンピュータ

コメント
コメントの投稿
管理者にだけ表示を許可する

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。