9

次の問題は、Vazirani らによる動的プログラミングの章からのものです。アル。

[6.6] 3 つのシンボル a に対する乗算演算 (×) を定義しましょう。b; c 次の表に従って：

九九

したがって、 a × a = b 、 a × b = b などです。

bbbbacこれらの記号の文字列 (たとえば ) を調べ、結果の式の値が になるように文字列を括弧で囲むことができるかどうかを判断する効率的なアルゴリズムを見つけてaください。たとえば、入力時bbbbacに、アルゴリズムはyesを返す必要があります((b(bb))(ba))c = a。

これが私のアプローチです：

ここで与えられたブール括弧の数を数える問題にそれをマップします。その問題では、フォームのブール式が与えられます

TまたはFおよびT xor T

そして、true と評価されるように、これを括弧で囲む方法の数を見つける必要があります。

or、and、xorは、特定の規則 (T xor F = T など) に従い、値 T または F を取るオペランドに作用する演算子と考えることができます。

元の問題では、a、b、c をオペランドと見なし、与えられたテーブルでルールを提供するものとして定義されている乗算 (x) を使用できます。

上記のアプローチは理にかなっていますか、それとももっと簡単なアプローチがありますか?

4

3 に答える 3

0

この問題は、動的プログラミング 疑似アルゴリズムによって解決できます。ここで見つけることができます。

/**
* Parenthesizing a string so that expression takes a given value
*/
import java.util.*;
class Solution
{
static boolean func(int[][] matrix, int[] str, int n, int symbol)
{
    Set<Integer>[][] T = new Set[n][n];

    // Assign the value
    for(int i=0; i<n; i++)
    {
        T[i][i] = new HashSet<Integer>();
        T[i][i].add(str[i]);
    }


     for(int gap = 1; gap<n; gap++)
     {
         for( int i = 0, j = gap; j<n; i++, j++)
         {       
             T[i][j] =  new HashSet<Integer>();

             for(int k=i; k < i+gap; k++)
             {
                 Iterator<Integer> outer = T[i][k].iterator();
                 while(outer.hasNext())
                 {
                     int elementOuter = outer.next();
                     Iterator<Integer> inner = T[k+1][j].iterator();
                     while(inner.hasNext())
                     {
                         int elementInner = inner.next();
                         int val = matrix[elementOuter][elementInner];
                         T[i][j].add(val);
                     }
                 }
             }
         }

     }
     if(T[0][n-1].contains(symbol))
         return true;
     return false;
}


public static void main(String args[] ) throws Exception 
{
    int[] stringNew = {1, 1, 1, 1, 0}; // for String "bbbbac"
    int element = 3;
    /**
     * Here a -> 0       
     *      b -> 1
     *      c -> 2
     *      
     *      Table                  Equivalent Table
     *      * a b c         \      * 0 1 2
     *      a b b a    ------\     0 1 1 0
     *      b c b a    ------/     1 2 1 0
     *      c a c c         /      2 0 2 2
     */
    int     matrix[][] = {{1, 1, 0},{2, 1, 0},{0, 2, 2}}; //multiplication table

    System.out.println(func(matrix, stringNew, stringNew.length, 0));
 }
}
于 2015-11-05T16:36:47.790 に答える
0

はい、あなたのアプローチはあなたが言及した問題に似ているはずです。一般に、n個のシンボルがある場合（この問題で言及した3個またはリンクを提供した問題の2個ではなく）、次のようにする必要があります-

#include <stdio.h>
#include <string.h>

#define MAXL 500
#define MAXN 100

int     isPossible[MAXL][MAXL][MAXN];
int     matrix[MAXN][MAXN]; //multiplication table
char    str[MAXN+1];
int     L;

int go(int start, int end, int need) {
    if(start > end) return 0;
    if(isPossible[start][end][need] != -1) return isPossible[start][end][need];

    int i,x,y;
    for(i = start; i < end; i++) {
        for(x = 0; x < MAXN; x++) {//you can optimize these x & y loops by pre-determining which combinations can give you 'need'
            for(y = 0; y < MAXN; y++) if(matrix[x][y] == need) {
                if(go(start, i, x)==1 && go(i+1, end, y)==1 ) {
                    isPossible[start][end][need] = 1;
                    return 1;
                }
            }
        }
    }
    return 0;
}

int main() {
    while(scanf(" %s",str)==1) {
        L = strlen(str);
        memset(isPossible, -1, sizeof(isPossible));
        go(0, L-1, 'a');
    }
    return 0;
}

これは、テスト済みの完全なソース コードではないことに注意してください。

于 2011-12-28T07:38:04.370 に答える