0

いくつかの単語が与えられた場合、たとえば、バナナ、猫、犬、象、タイプ、中間、湖

となる数列を見つける

(1) すべての単語がシーケンス上にある

(2) 隣接する単語に同じ文字を含めることはできません。

seq が見つからない場合は、false を返します。それ以外の場合は、true と seq を返します。

重複なし。単語の順列はありません。

私の考え:

グラフを設定し、ハミルトニアン パスを使用して seq を見つけます。

でも、NPコンプリートです。

ハミルトニアンパスを回避するには?

より良いアイデアはありますか？

ありがとう

4

2 に答える 2

1

部分シーケンスを構築した場合、シーケンスを継続できる他の単語を決定するのは最後の単語だけであることに注意してください。たとえば、「バナナ」と「犬」を選択した場合は、「タイプ」または「湖」に進むことができます (「湖」は「バナナ」に隣接するため、「湖」が「バナナ」と衝突しても問題ありません)。 "犬"）。表示される順序で単語を使用する必要があるため (説明が正しく理解されている場合)、動的計画法を使用して、「 i番目の単語で終わる、生成できる単語の最長シーケンスは?」という問題を解決できます。

于 2012-01-06T17:57:41.037 に答える
0

私のアプローチには構造体が含まれます。

struct node{
    char c1, c2;
    char* str;
    int used;
    int ind;
    std::vector<struct node*> valid;
};

c1はstrの最初の文字であり、c2は最後の文字です。入力配列をループして各アイテムのノードを生成し、おそらくそれらをstd::vectorに配置します。次に、各ノードで、そのノードの前に有効に配置できるすべてのノードへの参照をpush_back（）して有効にします。次に、パスを再帰的に探します。最初のノードから始めて、使用したラベルを付け、有効な最初のインデックスに移動し、そのノードに対して繰り返します。次に、制御がそのポイントに戻ったら、有効な次のノードに移動し、同じことを行い、ここから戻るときに、すべてのノードで使用されている値をリセットします。一致するものが見つからない場合は、falseを返します。

ここに少しのコードがあります。各単語の最初と最後の文字が一致しないようにします。ニーズに合わせて修飾式を変更します。

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

struct node{
    char c1, c2;
    char* str;
    int used;
    int ind;
    std::vector<struct node*> valid;
};

int ispath_rec( std::vector<node*> &nodes, int depth, int* returnarray );

int ispath( char** value, int valuec, int* returnarray ){
    std::vector<node*> nodes;
    for( int i = 0; i < valuec; i ++ ){
        node* a = new node;
        nodes.push_back(a);
        a->used = 0;
        a->str = value[i];
        a->c1 = value[i][0];
        a->c2 = value[i][strlen(value[i])-1];
        a->ind = i;
    }
    for( int i = 0; i < valuec; i ++ ){
        node* a = nodes[i];
        for( int j = 0; j < valuec; j ++ ){
            node* b = nodes[j];
            if( b->c1 != a->c2 && b != a ) /*b->c1 != a->c2 is the qualifying expression*/
                a->valid.push_back( b );
        }
    }
    return ispath_rec( nodes, valuec, returnarray );
}

int ispath_rec( std::vector<struct node*> &nodes, int depth, int* returnarray ){
    if( depth <= 0 )
        return 1;
    for( int i = 0; i < nodes.size(); i ++ ){
        if( nodes[i]->used == 0 ){
            nodes[i]->used = 1;
            *returnarray = nodes[i]->ind;
            if( ispath_rec( nodes[i]->valid, depth-1, returnarray + 1 ) == 1 )
                return 1;
            nodes[i]->used = 0;
        }
    }
    return 0;
}

int main(){
    char* tmp[] = {"hello","oeyh","aol", "loks", "sol"};
    int rets[5];
    if( ispath( tmp, 5, rets ) ){
        for( int i = 0; i < 5; i ++ ){
            printf(" %s ", tmp[rets[i]] );
        }
    }
}
于 2012-01-06T21:51:13.593 に答える