C++でceil()関数を使わずにa/bの切り上げ値(天井値)を求める方法
ここでは、標準ライブラリのceil()関数を使用せずに、a÷b の切り上げ値(天井値)を求める方法を解説します。例えば、a = 5、b = 4 の場合、a/b = 5/4 となり、その切り上げ値は 2 になります。
切り上げ値を求める公式
この問題は、次のシンプルな公式で解くことができます。
ceil(a/b) = (a + b - 1) / b
なぜこの公式が成り立つのか
C++の整数除算では、小数点以下が切り捨てられます。そこで、分子に「b - 1」をあらかじめ加えておくことで、割り切れない場合にのみ結果が1つ上の整数へ繰り上がる仕組みです。割り切れる場合は (a + b - 1) がちょうど b の倍数にならないため結果は変化せず、正しい天井値が得られます。
- 5/4 の場合:(5 + 4 - 1) / 4 = 8 / 4 = 2
- 100/3 の場合:(100 + 3 - 1) / 3 = 102 / 3 = 34
- 49/7 の場合:(49 + 7 - 1) / 7 = 55 / 7 = 7(整数除算により切り捨て)
サンプルコード
#include<iostream>
using namespace std;
int ceiling(int a, int b) {
return (a+b-1)/b;
}
int main() {
cout << "Ceiling of (5/4): " << ceiling(5, 4) << endl;
cout << "Ceiling of (100/3): " << ceiling(100, 3) << endl;
cout << "Ceiling of (49/7): " << ceiling(49, 7) << endl;
}実行結果
Ceiling of (5/4): 2 Ceiling of (100/3): 34 Ceiling of (49/7): 7
注意点
この手法は正の整数同士の除算を前提としています。負の数が含まれる場合、C++の整数除算はゼロ方向への丸め(切り捨て)を行うため、期待した結果にならないことがあります。負の数にも対応させたい場合は、a と b の符号を判定して条件分岐を追加する必要があります。
-
C++ STLのset find()関数の使い方を解説
C++ STLのsetコンテナにおけるfind()関数は、指定した要素を検索し、その要素を指すイテレータを返します。もし要素がセット内に存在しない場合は、最後の要素の直後の位置(つまりend()が返すイテレータ)を指す値が返されます。この関数の計算量はO(log n)であり、setが内部的に平衡二分探索木(赤黒木)で実装されているため、高速な検索が可能です。アルゴリズムBegin セットコンテナの要素を出力するための関数 printS() を定義する。 空のセットコンテナ s を初期化し、いくつかの要素を挿入する。 関数を呼び出して、セットコンテナの要素を出力する。
-
C++で再帰を使って最大公約数(GCD)を求めるプログラム
2つの数の最大公約数(GCD:Greatest Common Divisor)とは、その両方の数を割り切ることができる最大の整数のことです。例として、63と42という2つの数を考えてみましょう。63 = 7 × 3 × 3 42 = 7 × 3 × 2 したがって、63と42のGCDは 21このように、共通する約数は「7」と「3」であり、その積である21が最大公約数となります。ここでは、再帰(リカージョン)を使って2つの数のGCDを求めるC++プログラムを2つの方法で紹介します。方法1:減算による再帰1つ目の方法は、大きい方の数から小さい方の数を引く操作を再帰的に繰り返すアプローチです。これは