C++
 Computer >> コンピューター >  >> プログラミング >> C++

C++でnピクセルのディスプレイサイズを求めるアルゴリズム

ある数 n が与えられ、これがディスプレイ上のピクセル総数だとします。このとき、条件を満たす長方形ディスプレイのサイズ（行数と列数）を求めるのが本記事の目的です。

問題の条件

  • 行数 a は列数 b を超えない（a <= b）
  • b − a の差はできるだけ小さくなるようにする

例えば、入力が n = 12 の場合、出力は (3, 4) となります。3 × 4 = 12 ピクセルであり、行数が列数以下で、かつ差が最小になる組み合わせだからです。

解き方の手順

この問題は、n の平方根から始めて、n を割り切れる最大の約数を見つけることで効率的に解けます。手順は以下の通りです。

i := n の平方根
while n mod i が 0 以外の間:
    i を 1 減らす
return (i, n / i)

C++での実装例

実際のコード実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void solve(int n){
    int i = sqrt(n);
    while (n % i)
        i--;
    cout << i << ", " << n / i;
}
int main(){
    int n = 12;
    solve(n);
}

入力

12

出力

3, 4

計算量について

このアルゴリズムは、探索開始点が √n であるため、最悪でも O(√n) の時間計算量で動作します。平方根に近い約数ほど b − a の差が小さくなるため、√n から下向きに探索することで、最初に見つかった約数が必ず最適解となります。

  1. 【C++ STL】multisetのsize()関数をサンプルコードでわかりやすく解説

    このチュートリアルでは、C++ STLにおける multiset の size() 関数について、具体的なプログラム例を交えながら詳しく解説します。size() 関数は、指定されたコンテナ（ここでは multiset）に現在格納されている要素の総数を返すメンバ関数です。multiset は重複した値を許容する連想コンテナであるため、同じ値が複数回挿入された場合も、それぞれが個別の要素としてカウントされる点に注意してください。サンプルコード#include <bits/stdc++.h> using namespace std; int main(){ multiset<

  2. C++でユーザー定義サイズの2次元ベクトル（2D vector）を扱う方法

    C++において、vectorの中にvectorを格納したものは「2次元ベクトル（2D vector）」と呼ばれます。これはいわゆる二次元配列のような使い方ができるデータ構造で、各行の要素数が異なる「ジャグ配列（ギザギザ配列）」としても扱えるのが特徴です。アルゴリズムBegin 2D vector型の変数 v を宣言する。 ベクター v に値を初期化する。 「the 2D vector is:」と出力する。 for (int i = 0; i < v.size(); i++) for (int j = 0; j < v[i].size(); j++