C++で学ぶ再帰処理:N未満の数値から「1」と「3」のみで構成される数をすべて出力する方法

概要

正の整数値が格納された整数変数Nが与えられます。この記事の課題は、与えられた値N未満の数値のうち、1、3、またはその両方のみで構成されるすべての数値を、再帰処理を用いて出力することです。

入出力シナリオの例

入力 − int num = 40

出力 − N未満の数値のうち、1または3のみで構成される数値は次のとおり: 33 31 13 11 3 1

説明 − 変数numには正の整数値40が格納されています。1と3(またはその両方)のみで構成される数値を再帰的に探索すると、40未満の該当する数値は1、3、11、13、31、33であることが分かります。

入力 − int num = 5

出力 − N未満の数値のうち、1または3のみで構成される数値は次のとおり: 3 1

説明 − 変数numには正の整数値5が格納されています。1、3、またはその両方のみで構成される数値のうち、5未満のものは1と3だけです。

入力 − int num = 1

出力 − 不正な入力(Wrong Input)

説明 − 変数numには正の整数値1が格納されています。1未満の非負整数は0のみですが、0は条件を満たさないため、該当する数値は存在しません。したがって、出力は不正な入力となります。

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

• 整数変数numを入力として受け取り、その値を引数として関数Recursive_Numbers(num)に渡します。

• 関数Recursive_Numbers(num)の内部では、以下の手順で処理を行います。

  • bool型の変数checkを宣言し、1(true)で初期化します。

  • numが0より大きい場合、whileループを開始します。ループは「temp > 0 かつ check == 1」の間継続され、変数digitにtemp % 10(最下位桁の値)を代入します。

  • digitが1でも3でもない場合、checkを0(false)に設定します。その後、temp = temp / 10として上位の桁へ処理を進めます。

  • checkが1のまま残っていれば、そのnumは条件を満たすため出力します。

  • 最後にRecursive_Numbers(num − 1)を再帰的に呼び出し、より小さい数値に対して同じ判定を繰り返します。

このアルゴリズムの計算量は、Nから1まで各数値について桁ごとの判定を行うため、おおよそO(N × 桁数)となります。

コード例

#include <iostream>
using namespace std;
void Recursive_Numbers(int num){
   bool check = 1;
   int temp = num;
   if(num > 0){
      while(temp > 0 && check == 1){
         int digit = temp % 10;
         if (digit != 1 && digit != 3){
            check = 0;
         }
         temp = temp / 10;
      }
      if(check == 1){
         cout<< num << " ";
      }
      Recursive_Numbers(num - 1);
   }
}
int main(){
   int num = 40;
   if(num <= 1){
      cout<<"Wrong input";
   }
   else{
      cout<<"Recursive program to print all numbers less than N which consist of digits 1 or 3 only are: ";
      Recursive_Numbers(num);
   }
   return 0;
}

出力結果

上記のコードを実行すると、以下の出力が生成されます。

Recursive program to print all numbers less than N which consist of digits 1 or 3 only are: 33 31
13 11 3 1