C++で隣接セルの数を加算するとフィボナッチ数になる行列内のセルの個数を求める方法

問題概要

row × col のサイズを持つ行列 matrix[ ][ ] が与えられます。この問題のゴールは、次の条件を満たす行列内のセルの個数を求めることです。

セルの値 matrix[i][j] ＋ そのセルに隣接するセルの数 ＝ フィボナッチ数

フィボナッチ数列は次のとおりです。0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ……

例を使って理解しよう

入力

matrix[row][col] = {{1, 4, 1}, {2, 0, 1}, {5, 1, 1}}

出力

隣接セルの数を加算するとフィボナッチ数になる行列内のセルの個数：4

解説

      0    1   2

0    1    4    1

1    2    0    1

2    5    1    1

Cell(0,0) → 1＋2＝3（隣接セルは (1,0) と (0,1) の2つ）

Cell(0,2) → 1＋2＝3

Cell(1,0) → 2＋3＝5

Cell(2,2) → 1＋2＝3

入力

matrix[row][col] = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}

出力

隣接セルの数を加算するとフィボナッチ数になる行列内のセルの個数：9

解説

      0    1   2

0    0    0    0

1    0    1    0

2    0    0    0

Cell(0,0) → 0＋2＝2（隣接セルは (1,0) と (0,1) の2つ）。同様に (0,2)、(2,2)、(2,0) も該当します。

Cell(0,1) → 0＋3＝3（隣接セルは (0,0)、(0,2)、(1,1) の3つ）。同様に (1,0)、(1,2)、(2,1) も該当します。

Cell(1,1) → 1＋4＝5

この結果、9個すべてのセルが条件を満たします。

プログラムで使用するアプローチ

任意の行列において、セルのタイプは実質的に3種類しかありません。すなわち、隣接セルが2つの「角のセル」、隣接セルが3つの「端のセル」、そして隣接セルが4つの「内部のセル」です。それぞれのセルの値に2、3、または4を加算し、その合計が関数 check_fibonacci(int num) を使ってフィボナッチ数かどうかを判定します。

• 行列 matrix[][] を用意して初期化します。
• 関数 check_square(long double num) は、引数として受け取った数が完全平方数であれば true を返します。
• 関数 check_fibonacci(int num) は、num がフィボナッチ数であれば true を返します。
• check_square(5 * num * num + 4) または check_square(5 * num * num − 4) が true を返せば、num はフィボナッチ数であると判定できます（フィボナッチ数の数学的性質を利用）。
• 関数 Fibonacci_cells(int matrix[row][col]) は、隣接セルの数を加算したときにフィボナッチ数となる行列内のセルの個数を返します。
• カウント用変数 count を 0 で初期化します。
• for ループを使って i＝0 から i＜row、j＝0 から j＜col の範囲で走査し、total = matrix[i][j] とします。
• セルの位置に応じて、total に 2、3、または 4 を加算します。
• 新しい total がフィボナッチ数であれば check_fibonacci(total) が true を返すので、count をインクリメントします。
• すべての for ループが終了したら、count を結果として返します。

実装例

#include <bits/stdc++.h>
using namespace std;
#define row 3
#define col 3

bool check_square(long double num) {
    long double val = sqrt(num);
    return ((val - floor(val)) == 0);
}
bool check_fibonacci(int num) {
    return check_square(5 * num * num + 4) || check_square(5 * num * num - 4);
}
int Fibonacci_cells(int matrix[row][col]) {
    int count = 0;

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            int total = matrix[i][j];
            if ((i == 0 && j == 0) || (i == row - 1 && j == 0) || (i == 0 && j == col - 1) || (i == row - 1 && j == col - 1)) {
                total = total + 2;
            } else if (i == 0 || j == 0 || i == row - 1 || j == col - 1) {
                total = total + 3;
            } else {
                total = total + 4;
            }
            if (check_fibonacci(total)) {
                count++;
            }
        }
    }
    return count;
}
int main() {
    int matrix[row][col] = {{1, 4,1},{2,0,1},{5,1,1}};
    cout << "隣接セルの数を加算するとフィボナッチ数になる行列内のセルの個数: " << Fibonacci_cells(matrix);
    return 0;
}

上記のコードを実行すると、次のような出力が得られます。

出力

隣接セルの数を加算するとフィボナッチ数になる行列内のセルの個数: 4