【c++で楽しく実装!】天井関数





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}

式(\ref{ceil})の証明をしていきます。まず,$a$が$b$で割り切れるとき,つまり$a$が$b$の倍数であるときを考えます。そのとき,$a$は以下のように表せます。

\begin{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}

一方で,式(\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}

次に,$a$が$b$で割り切れないときを考えます。このとき,$a$は以下のように表せます。

\begin{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}

一方で,式(\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}

以上で,式(\ref{ceil})が正しいことを示せました。

ポイント

たた覚えにくい式ですが,基本的には分子に$b$を足した上で,帳尻合わせとして$1$を引くと覚えましょう。

実装

int my_ceil(int a, int b){
  return (a + b - 1) / b;
}
よかったらシェアしてね!
  • URLをコピーしました!

コメント

コメントする

※ Please enter your comments in Japanese to distinguish from spam.

目次