-1

サブシーケンスの考え方は、この投稿で非常によく説明されています:サブシーケンスの生成

しかし、私は初心者なので、その質問の答えがわかりませんでした。

私が知りたかったのは、関数を使用せずにシンプルで理解しやすい状態に保ちながら、C プログラムをより効率的にすることができるかどうかです。

#include <stdio.h>
#define NUM 123456

int main(void) {

    int i,num=NUM,x,y,mask,digits=0,max=1;

    while ( num != 0 ) {  //calculate digits
        num /= 10;
        digits++;
    }

    for ( i = 1; i <= digits; i++ ) {  //calculate max number of subsequences
        max *= 2;     
    }
    max=max-2;

    printf("Subsequences are:\n");
    for ( i = 1; i <= max ; i++ ) {
        mask = i;     //digit selector
        x = 1;        //multiplier
        num = NUM;
        y=0;          //subsequence value

        while ( num != 0 ) {
            if ( mask % 2 == 1 ) {
                y += num % 10 * x;
                x *= 10; 
            }
            num /= 10;
            mask /= 2;
        }
        printf("%d \n" , y);
    } 

    return 0;
}

NUM を 5111 や 100 などの数値として定義すると、一部のサブシーケンスが 2 回表示されることに注意してください。それを修正する簡単な方法はありますか？ありがとう！

4

2 に答える 2

0

この問題は、(1) 数字の配列のすべてのサブシーケンスを見つける、(2) 整数を数字にパックおよびアンパックするという 2 つのタスクに分けることができます。

array のサブシーケンスを考えてみましょう{a, b, c}。配列を左から右にたどって生成し、2 つのパス (現在の要素をサブシーケンスに含めるパスと含めないパス) をたどることで、それらを生成できます。

これは、ツリーとして表すことができる再帰的なアプローチにつながります。

                  {}
               /      \
         {}               {a}
       /    \           /     \
    {}        {b}     {a}      {ab}
   /  \      /   \   /   \    /    \
  {}  {c}  {b} {bc} {a} {ac} {ab} {abc}

左に分岐すると現在の要素をスキップし、右に分岐するとその要素を含めます。要素自体はツリーの深さです。最初のレベルでは要素を扱い、次のレベルaとb最後のレベルでは要素を扱いますc。

一番下の行にはすべてのサブシーケンスがあります。これには、不要な空のシーケンスと完全なシーケンスが含まれます。しかし、今のところそれらを含めましょう。(一番下の行の配列は、通常、べき乗集合と呼ばれます。これは、Web で検索可能な便利な用語です。)

再帰関数を伴う再帰について言及しましたが、関数はアウトです。

したがって、別の方法で問題に取り組む必要があります。木を横向きにしましょう。ダッシュは、要素がスキップされたことを示します。右側の表記は別の表記を使用しています:0要素がスキップされたことを1意味し、要素が含まれたことを意味します:

- - -        000
- - c        001
- b -        010
- b c        011
a - -        100
a - c        101
a b -        110
a b c        111

右のコードに見覚えがあるといいのですが、これは から000まで111を 2 進数で数える方法です。これは、要素を列挙する良い方法です。ここで、各数値でどのビットが設定されているかを知る方法が必要です。

数が奇数の場合、右端のビットが設定されます。他のビットについては、数値を 2 で繰り返し割ることによって確認できます。これは、2 進法では右にシフトし、右端のビットを破棄します。

元の数字から数字を抽出する方法は？その数は 10 進数です。ビット 0 と 1 は 2 進数であるため、2 進数のビットを見つけるのと同じアプローチを使用できます。

番号から始めます。最後の桁は、10 で割った余りをとった結果です。次に、数値がゼロになるまで 10 で割ります。このコードは、右から左に数字を生成します。ビットを見つけるためのコードもそうです。つまり、ビットが設定されているかどうかと、単一のループで出力する桁を見つけ、常に右端のビットを取得し、設定されている場合は元の数値の右端の数字を出力します。

空のサブシーケンスと完全なサブシーケンスは、列挙の最初と最後の項目です。不要な場合はスキップしてください。

数字に数字が繰り返されている場合、重複したサブシーケンスの問題が残ります。とにかくサブシーケンスを作成し、後でそれがすでに印刷されているかどうかを確認するというuser3629249の提案を除いて、これを解決する簡単な方法はわかりません。

これを行う簡単な方法は、サブシーケンスの配列を保持することです。その配列にはmaxエントリがあります。その配列を埋めたら、並べ替えてから出力しますが、前のエントリと等しいエントリはスキップします。

元の数値を毎回分解する必要がないように、数字の配列を使用する実装例を次に示します。qsortのソート関数を使用しますが<stdlib.h>、これにはソート関数が必要です。

#include <stdlib.h>
#include <stdio.h>

#define NUM 412131

typedef unsigned int uint;

int uintcmp(const void *pa, const void *pb)
{
    const uint *a = pa;
    const uint *b = pb;

    return (*a > *b) - (*a < *b);
}

int main(void)
{
    uint digit[20];             // array of digits
    size_t ndigit = 0;          // length of array
    uint num = NUM;
    uint max = 1;
    size_t i;

    while (num) {
        digit[ndigit++] = num % 10;
        num /= 10;
        max *= 2;
    }

    uint res[max];              // array of subsequences

    for (i = 0; i < max; i++) {
        uint mask = i;          // mask for bit detection
        uint j = ndigit;        // index into digit array
        uint s = 0;

        while (j--) {
            if (mask % 2) s = s*10 + digit[j];
            mask /= 2;
        }

        res[i] = s;
    }

    qsort(res, max, sizeof(*res), uintcmp);

    for (i = 1; i < max - 1; i++) {
        if (res[i] != res[i - 1]) printf("%u\n", res[i]);
    }

    return 0;
}
于 2015-11-12T07:18:47.963 に答える