与えた条件を満たす候補 in C DouKaku?

与えた条件を満たす候補

['and', 'or', 'not', 'and']
のような入力が与えられた場合に、
式 x1 and x2 or not x3 and x4 の値が
Trueとなるような、x1～x4の組み合わせを全て
出力するプログラムを作成してください。
x1～x4には真と偽の2通りの値だけが入るものとします。

Pythonであれば上の入力に対し、
(True, True, True, True)
(True, True, False, True)
(True, False, False, True)
(False, True, False, True)
(False, False, False, True)
と出力します。

andとorの優先順位は同じで左結合性、
つまりa and b or c and dは
(((a and b) or c) and d)
という順番で評価されるものとします。

参考：
d.y.d.

キミならどう書く2.0の小町算問題と似てますが。

このお題はmorchinさんの投稿をもとに作成しました。ご投稿ありがとうございました。
元ネタの充足可能性問題 - Wikipedia は、同じリテラル(x1とかnot x2とか)が複数回出てくることを想定しているので、今回の問題のようにそれぞれ別の変数でだと乗法標準形 - Wikipediaにした場合に、答えが…と色々悩みどころでした。

post comment

Posted feedbacks - C

総当たりがうまく思いつかなかったのでビット配列に変換してしまいました。。。

NOTの計算がやっつけぽくてあまり好ましくないですがまぁ、いっか(笑
gcc -std=c99 -Wall doukaku43.c -o a

#include <stdio.h>
#include <memory.h>

int dec2bin(char *buf, size_t bufsize, int n)
{
    memset(buf, '\0', bufsize);
    while( bufsize > 0 )
    {
        buf[bufsize-1] = n & 1;
        bufsize --;
        n >>= 1;
    }
    return 0;
}

int solver(const char *op[], size_t nop)
{
    int bits = nop + 1;
    int result ;
    int n,k,m;

    for( k=0; k<nop; k++ )
    {
        /* NOTは右辺のみなので値無し */
        if( strcmp(op[k], "not") == 0 ) bits --;
    }
    char x[bits];

    bits = 1 << bits;
    for( n=bits; n>0; n--)
    {
        dec2bin(x, sizeof(x), n); /* ビット配列に変換 */
        result  = x[0] ;
        if( strcmp(op[0], "not") == 0 ) result = (~x[0] & 1);
        for( m=0,k=0; k<nop; k++,m++ )
        {
            if( k<nop-1 )
            {
                /* NOTの場合は先に計算する */
                if( strcmp(op[k+1], "not") == 0 ) x[m+1] = (~x[m+1] & 1);
            }

            if( strcmp(op[k], "not") == 0 ) m--; /* 計算済みなので次も同じ値を使用する */
            else if( strcmp(op[k], "and") == 0 ) result &= x[m+1];
            else if( strcmp(op[k], "or") == 0 )  result |= x[m+1];
            else if( strcmp(op[k], "xor") == 0 ) result = (result ^ x[m+1]) & 1;
            else
            {
                printf("invalid opration:[%s]\n",op[k]);
                return -1;
            }
        }
        if( result == 1 )
        {
            /* 結果出力 */
            dec2bin(x, sizeof(x), n);
            printf("(");
            for( m=0; m<sizeof(x)-1; m++ )
            {
                printf("%s, ", (x[m])?"True":"False");
            }
            printf("%s)\n", (x[m])?"True":"False");
        }
    }
    return 0;
}

int main(int argc, char *argv[])
{
    solver( (const char *[]){"and","or","not","and"}, 4);
    return 0;
}

DouKaku?

与えた条件を満たす候補

Posted feedbacks - C

Index

Feed

Other

Link

Pathtraq