[AOJ] 色々な言語で降順ソート

12251 ワード
Python SQLite3 C++ CommonLisp PHP Python テキストリンク

AIZU ONLINE JUDGE という会津大学提供のプログラミング問題提出＆採点サイトを見つけて楽しくなったので、色々な言語で問題を解いてみることにした。

言語は C++, python, php, sqlite3, common lisp の5つを選択。
普段使っている言語は C++ で、その他の言語はネットなどで調べながら書いた。

今回は 0001 List of Top 3 Hills という問題。

問題

List of Top 3 Hills

山の高さをメートル単位の整数で表した 10 個のデータがあります。その 10 個のデータを読み込んで、その中で、高い順から３つ出力して終了するプログラムを作成して下さい。

Input

山の高さ１（整数）　
山の高さ２（整数）　
.
.
山の高さ１０（整数）　

Constraints

0 ≤ 山の高さ ≤ 10000

Output

最も高い山の高さ
２番目に高い山の高さ
３番目に高い山の高さ

Sample Input

1819
2003
876
2840
1723
1673
3776
2848
1592
922

Output for the Sample Input

3776
2848
2840

とりあえずサンプル入力に対して正しい答えを返すものを書く。
どの言語でもソートは標準で入っているので自分でアルゴリズム書く必要は無かった。

回答

C++


#include <iostream>
#include <set>
using namespace std;

int main() {

  typedef std::multiset<int> MySet;
  MySet heightSet;

  for(int i = 0; i < 10; ++i)
  {
    int val;
    cin >> val;
    // set に要素を挿入すると自動的にソートされる
    heightSet.insert(val);
  }

  // 大きい順にアクセスするために reverse_iterator を使う
  MySet::reverse_iterator rit = heightSet.rbegin();
  for(int i = 0; i < 3; ++i)
  {
    cout << *rit << endl;
    ++rit;
  }
  return 0;
}

STL の multiset コンテナを使うと要素挿入の際に自動ソートされるのでちょっとサボれる。

python


# 配列を作成
n = list()

for var in range(0, 10):
  # 標準入力から一行読み込み
  # int にキャスト
  n.append( int(raw_input()) )

# 配列を降順ソート
n.sort(reverse = True)

for var in range(0, 3):
  print n[var]

python だと短く書けるなと感動。

PHP


<?php
$hi = fopen('php://stdin', "r");
$ho = fopen('php://stdout', "w");

# 空の配列を作成
$arr = array();

# 標準入力からデータをセット
for($i = 0; $i < 10; $i++)
{
    fscanf($hi, "%d", $arr[]);
}

# 降順ソート
rsort($arr);

# 出力
for($i = 0; $i < 3; $i++)
{
    fwrite($ho, sprintf("%d\n", $arr[$i]));
}

fclose($ho);
fclose($hi);

変数に $ をつけるところを除けば c 言語に近い感覚。

sqlite3


-- テーブルの作成
create table tbl(height integer);

-- テキストファイルからデータを読み込む
.import data.txt tbl

-- 'tbl' から 'height' フィールドで降順ソートして 3 行読み込む
select * from tbl order by height desc limit 3;

sqlite3 で標準入力からレコードに情報を入れる方法が判らなかったのでファイルから読んでます。

Common Lisp


;; 標準入力から n 回受け取ってリストに追加
(defun input (lst n)
    (cond
        ((eq (length lst) n)
            lst
        )
        (t
            (input (append lst (list (read)) ) n )
        )
    )
)

;; リストの先頭 n 要素の部分配列を作成
(defun gettop (lst n)
    (if (or (= n 0) (null lst))
        nil
        (cons (car lst)
            (gettop (cdr lst) (- n 1))
        )
    )
)

(mapcar #'(lambda (x) (format t "~A~%" x))  ; リストの要素を改行区切りで出力する
    (gettop
        (sort (input () 10) #'>)    ; 標準入力からリストを作り降順ソートする
        3                           ; 先頭3つのリストを作成
    )
)

CommonLisp は手続き型に慣れた身からすると異質過ぎて凄い手間取った。

Ruby openssl生成証明書
RVMとRubyのインストール