【C言語】合計がNになるように、0と1のみで構成される数を出力するプログラム

問題概要

整数 n が与えられたとき、0と1のみで構成される数を組み合わせて、その合計がちょうど n になるような組み合わせを出力するのが課題です。

0と1だけで表現できる数には「1」「10」「11」などがあります。これらの数を足し合わせて合計が n と等しくなるように、該当する数を順番に出力します。

たとえば n = 31 を入力した場合、「10 + 10 + 11」または「10 + 10 + 10 + 1」といった組み合わせが答えになります。

入力例と出力例

Input: 31
Output: 10 10 10 1

アルゴリズム

残りの値に応じて「10」「11」「1」を選びながら合計を組み立てていくシンプルな手法です。

int findNumbers(int n)
START
STEP 1: 変数 m = n % 10、a = n を宣言して代入する
STEP 2: a > 0 の間、以下の処理を繰り返す
   IF a/10 > 0 かつ a > 20 ならば、
     a から 10 を引いた値を a に代入し直す
     "10 " を出力する
   ELSE IF a - 11 == 0 ならば、
     a から 11 を引いた値を a に代入し直す
     "11 " を出力する
   ELSE
     "1 " を出力する
     a を 1 減らす
   END IF
END LOOP
STOP

処理のポイント

残りの値 a が 21 以上あるうちは、できるだけ大きな「10」を使って合計に近づけます。残りがちょうど 11 になった時点で「11」を一度に出力することで、出力する個数を抑えられます。それ以外の場合は「1」を一つずつ加算していきます。

C言語での実装例

#include <stdio.h>
// 数を出力する関数
int findNumbers(int n) {
   int m = n % 10, a = n;
   while (a > 0) {
      if (a / 10 > 0 && a > 20) {
         a = a - 10;
         printf("10 ");
      }
      else if (a - 11 == 0) {
         a = a - 11;
         printf("11 ");
      }
      else {
         printf("1 ");
         a--;
      }
   }
}
// ドライバーコード
int main() {
   int N = 35;
   findNumbers(N);
   return 0;
}

実行結果

上記のプログラムを実行すると、次のような出力が得られます。

10 10 1 1 1 1 11

N = 35 の場合、「10 + 10 + 1 + 1 + 1 + 1 + 11 = 35」となり、すべて 0 と 1 だけで構成された数の合計が N と一致していることが確認できます。