zuka
天井関数を実装するよ。
本記事では,天井関数の簡単な解説と実装例をお伝えしていきます。使用言語はc++です。その他の競技プログラミング関連の記事は,以下の目次をご覧ください。
目次
本記事の概要
天井関数はstd::ceil
が利用できますが,勉強のために今回は自前で実装したいと思います。とは言っても,実装は一行で終わります。
今回おさえるべき内容
天井関数の定式化を確認する
天井関数を実装する
定式化
正の整数$a$,$b$に対して,天井関数は以下のように計算できます。
\begin{align}
\left\lceil\frac{a}{b}\right\rceil &= \left\lfloor\frac{a+b-1}{b}\right\rfloor \label{ceil}
\end{align}
\left\lceil\frac{a}{b}\right\rceil &= \left\lfloor\frac{a+b-1}{b}\right\rfloor \label{ceil}
\end{align}
式(\ref{ceil})の証明をしていきます。まず,$a$が$b$で割り切れるとき,つまり$a$が$b$の倍数であるときを考えます。そのとき,$a$は以下のように表せます。
\begin{align}
a &= qb
\end{align}
a &= qb
\end{align}
ただし,$q$は正の整数です。すると,式(\ref{ceil})の左辺は以下のように計算できます。
\begin{align}
\left\lceil\frac{a}{b}\right\rceil &= \left\lceil\frac{qb}{b}\right\rceil \\
&= q
\end{align}
\left\lceil\frac{a}{b}\right\rceil &= \left\lceil\frac{qb}{b}\right\rceil \\
&= q
\end{align}
一方で,式(\ref{ceil})の右辺は以下のように計算できます。
\begin{align}
\left\lfloor\frac{a+b-1}{b}\right\rfloor &= \left\lfloor\frac{bq+b-1}{b}\right\rfloor \\
&= q + 1 - 1\\
&= q
\end{align}
\left\lfloor\frac{a+b-1}{b}\right\rfloor &= \left\lfloor\frac{bq+b-1}{b}\right\rfloor \\
&= q + 1 - 1\\
&= q
\end{align}
次に,$a$が$b$で割り切れないときを考えます。このとき,$a$は以下のように表せます。
\begin{align}
a &= qb + r
\end{align}
a &= qb + r
\end{align}
ただし,$r$は$b$より小さい正の整数です。すると,すると,式(\ref{ceil})の左辺は以下のように計算できます。
\begin{align}
\left\lceil\frac{a}{b}\right\rceil &= \left\lceil\frac{qb+r}{b}\right\rceil \\
&= q + 1
\end{align}
\left\lceil\frac{a}{b}\right\rceil &= \left\lceil\frac{qb+r}{b}\right\rceil \\
&= q + 1
\end{align}
一方で,式(\ref{ceil})の右辺は以下のように計算できます。
\begin{align}
\left\lfloor\frac{a+b-1}{b}\right\rfloor &= \left\lfloor\frac{bq + r + b - 1}{b}\right\rfloor \\
&= q + 1 +1 - 1\\
&= q + 1
\end{align}
\left\lfloor\frac{a+b-1}{b}\right\rfloor &= \left\lfloor\frac{bq + r + b - 1}{b}\right\rfloor \\
&= q + 1 +1 - 1\\
&= q + 1
\end{align}
以上で,式(\ref{ceil})が正しいことを示せました。
ポイント
たた覚えにくい式ですが,基本的には分子に$b$を足した上で,帳尻合わせとして$1$を引くと覚えましょう。
実装
int my_ceil(int a, int b){
return (a + b - 1) / b;
}
コメント