質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.33%

  • C++

    3768questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

再帰を使わずに再帰のようなことを実現したい

解決済

回答 5

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 520

toshiyan

score 46

[1,1,1,1,1]
[1,1,1,1,2]
...
[1,1,1,1,9]
[1,1,1,2,2]
[1,1,1,2,3]
...
[8,9,9,9,9]
[9,9,9,9,9]

上記のような出力をするC++のプログラムを、再帰を使わずに実現したいです。
どうすればよいでしょうか。

以下は、再帰を使った実装です(一応、丸投げではないアピールです)。

#include <iostream>
#include <vector>

using namespace std;

void recurse(vector<int> *v, int len, int max)
{
    int start;
    int i, j;
    if (v->size() == len) {
        cout << "[";
        for (j = 0; j < len-1; j++) {
            cout << v->at(j) << ",";
        }
        cout << v->at(len-1) << "]" << endl;
        return;
    }
    if (v->size() == 0) {
        start = 1;
    } else {
        start = v->back();
    }
    for (i = start; i <= max; i++) {
        v->push_back(i);
        recurse(v, len, max);
        v->pop_back();
    }
}

int main(void)
{
    vector<int> v;
    recurse(&v, 5, 9);
    return 0;
}

【追記】
長さと最大値は可変にしたいです。最小値は、とりあえずは1で固定です。

【更に追記】
baseballyamaさんの回答を元に書いた、再帰無しのコードです。一応再帰無しで同等の処理が実現できましたので解決済みとします。回答してくださった皆様、ありがとうございました!ただ、僕としては、maxが2桁以上の場合でも正常に動作してほしいですし、再帰処理を再帰無しで記述する「普遍的な」方法を知りたかったです。その方法を知れれば、機械的に再帰無しコードに書き換えられるような…そんなメソッドが知りたかったのです。

#include <iostream>

using namespace std;

void recurse(int len, int max)
{
    // 数値型↔文字型の変換は、0x30を加算・減算することで行う
    string smax = string(5, max + 0x30);
    int imax = stoi(smax);

    for (int i = 1; i <= imax; i++) {
        bool flag = true;
        string s = to_string(i);

        for (int j = 0; j < s.size(); j++) {
            // 要素が1以上max以下の条件を満たさない場合は出力しない
            if (s[j] - 0x30 < 1 || s[j] - 0x30 > max) {
                flag = false;
                break;
            }
            // 左から右に昇順でない場合は出力しない
            if (j > 0 && s[j - 1] > s[j]) {
                flag = false;
                break;
            }
        }

        if (flag) {
            cout << "[";
            for (int j = 0; j < s.size(); j++) {
                cout << s[j];
                if (j < s.size() - 1) {
                    cout << ",";
                }
            }
            cout << "]" << endl;
        }
    }
}

int main(void)
{
    recurse(5, 9);
    return 0;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • iwanote

    2017/12/31 12:58

    これは桁数があらかじめ決まっているものですか?決まっているならfor文で回せばいいですし、決まっていないならプログラム中のprintfのところがおかしいように思われます

    キャンセル

  • toshiyan

    2017/12/31 13:08

    ご指摘ありがとうございます。ご指摘の内容をソースコードに反映しました。配列の長さと最大値は、引数として渡すことを想定しています。

    キャンセル

回答 5

+2

カウンタ変数を1から100,000までカウントアップしていき、各桁を拾えば良いと思います(0である桁があるケースは除外が必要)。各桁を拾うのは10で割った剰余を順に使えば良いです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/12/31 16:59

    回答ありがとうございます。

    キャンセル

  • 2017/12/31 20:25

    9で割ったあまりに1足すとか。

    キャンセル

checkベストアンサー

+1

正月の遊びのつもりで作ってみましたが、出力仕様に合っていますか。

#include <iostream>
#include <vector>

using namespace std;

void init(vector<int> *v, int len) {
    for (int i = 0; i < len; i++) v->push_back(1);
}

void print(vector<int> *v) {
    cout << "[";
    for (int i = 0; i < v->size()-1; i++) cout << v->at(i) << ",";
    cout << v->at(v->size()-1) << "]" << endl;
}

bool checkMax(vector<int> *v, int start, int end, int max) {
    for (int i = start; i <= end; i++) {
        if (v->at(i) < max) return false;
    }
    return true;
}

int main(void)
{
    vector<int> v;
    int len = 5;
    int max = 9;

    init(&v, len);

    while (true) {
        print(&v);

        if (checkMax(&v, 0, len-1, max)) break;

        for (int i = len-1; i >= 0; i--) {
            if (v.at(i) < max) {
                if (i < len-1) {
                    if (checkMax(&v, i+1, len-1, max)) {
                        v.at(i)++;
                    }
                } else {
                    v.at(i)++;
                }
                break;
            } else if (v.at(i) == max) {
                if (i > 0) {
                    if (v.at(i-1) < max) {
                        v.at(i-1)++;
                        if (checkMax(&v, i, len-1, max)) {
                            for (int j = i; j < len; j++) v.at(j) = v.at(i-1);
                        }
                        break;
                    }
                }
            }
        }
    }
    return 0;
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/02 11:14

    私の要件をすべて満たしてくれていますね。ベストアンサーを、こちらの正しいコードに変えさせていただきます。回答ありがとうございました!

    キャンセル

+1

ご質問の内容を正確に把握せずに回答してしまいました。大変申し訳ございません。
再帰処理を使用しないとすると以下のような処理が妥当なのではないかと思いました。
※但し私C++は書いたことがないので、javaをイメージして記載してしまいました。
※なので、不適当なプログラムを記載している部分があるかもしれません。
※コメントを受けて修正しました。

#include <iostream>
#include <stdexcept>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

// char文字を int型 に変換(数字以外が来た場合は -1 を返却)
int ctoi(char c) {
    switch (c) {
    case '0':
        return 0;
    case '1':
        return 1;
    case '2':
        return 2;
    case '3':
        return 3;
    case '4':
        return 4;
    case '5':
        return 5;
    case '6':
        return 6;
    case '7':
        return 7;
    case '8':
        return 8;
    case '9':
        return 9;
    default:
        return -1;
    }
}

// len 文字数の数字を カンマ区切りで出力
// 但し max 以上の数字が入っている場合は出力を実施しない
// 出力例: [2,2,2,2,2]
void printNums(int len, int max) {

    // 出力最大値を取得
    string maxValue = "";
    for (int i = 0; i < len; i++) {
        maxValue = maxValue + std::to_string(max);
    }
    int maxvalue = std::stoi(maxValue);

    // 0 から 出力最大値まで走査
    for (int i = 1; i <= maxvalue; i++) {

        // 出力対象フラグ初期化
        bool printFlag = true;

        // 出力対象の数字を文字列に変換
        std::ostringstream sout;
        sout << std::setfill('0') << std::setw(5) << i;
        std::string str = sout.str();

        // 出力対象に max 以上の数値が含まれている場合は出力処理を実施しない
        for (int j = 0; j < (int) str.size(); j++) {
            if (ctoi(str[j]) > max || ctoi(str[j]) == 0) {
                printFlag = false;
                break;
            }
        }

        // 出力対象の場合は出力を実施
        if (printFlag) {
            cout << "[";
            int length = str.length();
            for (int j = 0; j < length; j++) {
                cout << str[j];
                if (length != (j + 1)) {
                    cout << ", ";
                }
            }
            cout << "]" << endl;
        }

    }

}

// メイン処理
int main() {

    // 5桁で全ての数字が2以下のものを出力
    printNums(5, 2);

    // 結果返却
    return 0;

}

※以下当初の回答
/***************************************************************/

単純に for文 を4重に回すのではダメなのですか?

#include <iostream>
using namespace std;

int main() {

    // 1桁目を 1 から 9 まで走査
    for (int i = 1; i < 10; i++) {

        // 2桁目を 1 から 9 まで走査
        for (int j = 1; j < 10; j++) {

            // 3桁目を 1 から 9 まで走査
            for (int k = 1; k < 10; k++) {

                // 4桁目を 1 から 9 まで走査
                for (int l = 1; l < 10; l++) {

                    // 標準出力 形式:"[i, j, k, l]"
                    cout << "[" << i << ", " << j << ", " << k << ", " << l << "]" << endl;

                }

            }

        }

    }

    // 結果返却
    return 0;

}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/12/31 13:16

    回答ありがとうございます。要素の数は可変にしたいです…。

    キャンセル

  • 2017/12/31 13:59

    そしたら、そのi, j, k, l を引数にしたメソッドを作成し、それをmainから呼べばよいのではないでしょうか。

    キャンセル

  • 2017/12/31 14:10

    すみません。よくわからないので、コードで提示していただけないでしょうか。理解力がなくて申し訳ございません…。

    キャンセル

  • 2017/12/31 15:58

    当初の回答はご質問を正確に理解していないで記載してしまいました。ご質問を再度読み返したのち、再度プログラムを記載させて頂きました。お役に立てたら幸いです。

    キャンセル

  • 2017/12/31 16:42

    丁寧な対応ありがとうございます。嬉しいです。
    私の方でも実装しましたところ、以下のバグが含まれていました。

    ・[1,0,0,0,0]のような配列も出力されてしまう。
    ・[1,1,1,2,1]のような、要素が左から右に昇順になっていないものは、出力したくありません。このプログラムでは出力してしまいます。
    ・maxが2桁以上の場合に対応していない(これは私の伝え忘れです。すみません…)。

    再帰を使って楽に書けるコードを再帰無しで無理に書こうとすると、柔軟性がなくなってしまうものなんですかね…(例えばmaxは一桁の数値にしか対応しない、など)。

    一応、私の方で実装したコードを質問内に載せておきます。

    キャンセル

  • 2017/12/31 16:56

    ・[1,0,0,0,0]のような配列も出力されてしまう。
    ⇒すいません。これは要件を把握できていませんでした。

    ・[1,1,1,2,1]のような、要素が左から右に昇順になって...
    ⇒そうなんですね。了解しました。

    ・maxが2桁以上の場合に対応してい...
    ⇒そうなんですね。了解しました。

    私は再帰処理に抵抗がないので、この場合再帰で書きますが、再帰はわかりづらいという人が一定数いることも事実です。
    ただ、このケースの場合、上記要件も取り込んで再帰なしで実装するとなると、冗長になると思います。

    まずは、上記要件漏れを修正してソースを更新しておきます。

    キャンセル

+1

C++など不要。そう、シェル芸ならね!

$ echo [{1..9},{1..9},{1..9},{1..9}]|tr ' ' '\n'

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/12/31 13:32

    回答ありがとうございます。参考になります。

    キャンセル

  • 2017/12/31 20:16

    https://stackoverflow.com/questions/478898/how-to-execute-a-command-and-get-output-of-command-within-c-using-posix
    C++でコマンドを生成してからそのままシェル芸を投げればいいのですね!

    キャンセル

0

配列に11...11から99...99までの数字全部入れてその条件に当てはまらないものを消していったらどうでしょうか
配列に収まるかはわかりませんが...

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/12/31 16:59

    回答ありがとうございます。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.33%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

  • C++

    3768questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。