Help us understand the problem. What is going on with this article?

bcコマンドを使わないで小数を表せるか

More than 1 year has passed since last update.

目的

BashでAtCoder Beginner Contest 003 - Cの問題を解きます。
ただし、小数の計算がありますがbcコマンドを使いません

bcコマンドとは

ざっくり言うと数値計算をするためのコマンドです。例えば echo 3+1 | bc とやると4と返してくれるみたいな。
シェルで小数計算といえばこれらしいのですが、今回は別の方法を模索します。ゴリ押しとも言います。

今回やりたい計算

double m=0.0;
for(i=0;i<k;i++) m=(m+r[i])/2.0;
return m;

準備

Bashで四則演算をしようとすると、例えば

m=$(((m+r[i])/2))

といったように\$(())で囲んで計算する方法があります。単に筆者が浅学なのでこれくらいしか知らないだけですが。
しかし、これでは小数点以下が切り捨てられます。int型にキャストされる、といった感じですかね。
今回認められるのは$10^{-6}$までの誤差なので、このままやっては大変なことになります。

10^n倍→10^{-n}倍

そこで今回使ったのは、すべて整数で計算するという方法です。今回は$10^{-6}$までの制度で計算できればいいので、求める値を$10^6$倍して計算すれば解決という寸法。
つまり、

#m=$(((m+r[i])/2))         #最終的に求めたい値
 m=$(((m+r[i]*1000000)/2)) #仮に求める値

として、最後にmを$10^{-6}$倍すれば答えが出ます。何倍するかを調整すればさらに細かい精度で計算できますが、桁数が大変なことになっていくので難しいところ。

暫定的なプログラム

この問題を解くにあたっては配列のソートとかいった計算が事前に必要になってくるのですが、小数の計算をすることが今回の主題なので割愛します。

#!bin/bash
read n k
r=(`sed 's/ /\n/g' | sort -n | tail -$k | sed 'N;s/\n/ /g'`)
# ここからが今回やりたい計算
m=0
for i in `seq 0 $((k-1))`
do
m=$(((m+r[i]*1000000)/2))
done
echo $m #1000000倍した値

ということで、$10^6$倍した値の出力はこんな感じになっています。

本題

整数部

整数部を求めるのは簡単で、そもそも\$(())で計算すると小数点以下が切り捨てられますから、素直に\$((m/1000000))とするだけです。

小数部の表現(失敗例)

では、小数部は\$((m%1000000))と剰余を求めればいいのではないか? と思いましたが、それでは自分にとって少々問題がありました。
例えば、m=1000001を$10^{-6}$倍することを考えると、\$((m%1000000))=1となることから、そのまま繋げると1.1になってしまいます。0-paddingをしないといけませんね。
が、

小数部の表現(一部成功例)

折角なので、今回は正規表現を使って置換したいと思います。
整数部は既に計算済みで(m1とします)、それが当然先頭にあるわけですから、次のように置換すれば小数部が表現できますね。

echo $m | sed "s/^$m1/$m1\./"

「整数部」を「整数部.」に変更するだけですが、これで見た目は完全に小数となります。

例外処理 - 整数部が0の場合

中々に盲点ですが、整数部が0の場合の処理を考える必要があります。
整数部m1が0の場合、普通は$10^6$倍された値mの先頭に0がついていません。つまり、sedによる置換がこのままでは出来ないということです。

これは素直にif文を使って分岐させたほうが分かりやすいかも、ということで。

if ((m1==0))
then echo "0."$m
else echo $m | sed "s/^$m1/$m1\./"
fi

まとめ

冒頭に出た問題のAC解はこのようになりました。

#!bin/bash
read n k
r=(`sed 's/ /\n/g' | sort -n | tail -$k | sed 'N;s/\n/ /g'`)
m=0
for i in `seq 0 $((k-1))`
do
m=$(((m+r[i]*1000000)/2)) #10^6倍で計算する
done
m1=$((m/1000000)) #整数部を取り出す
if ((m1==0))
then echo "0."$m #整数部が0なら"0."を頭につける
else echo $m | sed "s/^$m1/$m1\./" #整数部が1以上なら整数部の後に"."をつける
fi

つまり、

  • 最初は精度を満たせるように整数で計算する
  • 整数部と小数部を分けて表示する

だけでしたね。言われてみれば当たり前のことでした。もっと考えればより簡単に表現できるかもしれません。
また、m自体が小数になったわけではないので、さらに計算を進めるときにはまた色々考える必要があると思います。

まあ、結局bcコマンドは便利だぜってことでこの話は終わりにいたします。初学者の記事にここまでお付き合いいただきありがとうございました。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away