Skip to content

Yanoh sample quiz2#1

Open
yanoh wants to merge 4 commits into
developfrom
yanoh-sample-quiz2
Open

Yanoh sample quiz2#1
yanoh wants to merge 4 commits into
developfrom
yanoh-sample-quiz2

Conversation

@yanoh

@yanoh yanoh commented Aug 3, 2013

Copy link
Copy Markdown
Member

近藤さんから聞いたクイズ（その２）を解いてみました。

お題

任意の数値列から、

  1. 最小値
  2. 最大値
  3. 最小値と最大値
    を効率よく抽出せよ。

アプローチ

1 と 2 に関しては、どちらも愚直に全要素を比較してます。
3 は、リストの先頭から 2 要素ごとに比較し、その結果から最大値 / 最小値を更新することで、比較を 2n 回から 3n / 2 + 1 回に抑えています。

3 の具体例

'(3 5 2 1 4) の場合
    3 < 5 -> 3 < min, max < 5
    2 < 1 -> 1 < min, max < 2
          -> 4 < min, max < 4

'(1 2 3 4 5) の場合
    1 < 2 -> 1 < min, max < 2
    3 < 4 -> 3 < min, max < 4
          -> 5 < min, max < 5

'(5 4 3 2 1) の場合
    5 < 4 -> 4 < min, max < 5
    3 < 2 -> 2 < min, max < 3
          -> 1 < min, max < 1

yanoh
yanoh reviewed Aug 7, 2013
View reviewed changes
Comment thread quiz2.lisp Outdated

@yanoh yanoh Aug 7, 2013

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

お題のデータとして 0..299 をランダムに並べ替えたものを設定してます。

yanoh added 2 commits August 23, 2013 13:11
@yanoh
Fix dumb min/max/minmax algorithm
1a8d264
@yanoh
Refine order function to return a cons-cell instead of a list and add…
8ba96a8 
… precondition check in order not to die when an empty list is passed to min/max/minmax function
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@yanoh @keisen