合計がnになる3つの数を見つけるC++プログラム

ある整数 n が与えられたとします。ここで、a + b + c = n を満たし、かつ3つの数 a、b、c のいずれも3の倍数にならないような組み合わせを見つけることを考えます。

例えば、入力が n = 233 の場合、出力は「1, 2, 230」のようになります。実際に確認すると、1 + 2 + 230 = 233 であり、どの数も3の倍数ではありません。

解法のアプローチ

この問題は、以下の手順に従って解くことができます。

if ((n - 2) mod 3 == 0) then:
    return 1, 2, n - 3
otherwise:
    return 1, 1, n - 2

なぜこの方法で正しく動作するのか

(n - 2) が3で割り切れる場合、n - 3 は3で割った余りが2になるため、3の倍数にはなりません。一方、それ以外の場合は n - 2 自体が3の倍数ではないため、そのまま第3の数として利用できます。また、1 は常に3の倍数ではないため、いずれの場合でも条件を満たす組み合わせが得られます。

実装例

理解を深めるために、以下のC++による実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void solve(int n){
    if ((n - 2) % 3 == 0)
        cout << 1 << ", " << 2 << ", " << n - 3;
    else
        cout << 1 << ", " << 1 << ", " << n - 2;
}
int main(){
    int n = 233;
    solve(n);
}

入力

233

出力

1, 2, 230