给出一些词,例如香蕉,猫,狗,大象,类型,中间,湖
找到这样的序列
(1)每个单词都在序列上
(2)任何相邻的单词不能有相同的字符。
如果找不到seq,则返回false。 否则,返回true和seq。
没有重复。 没有单词的排列。
我的想法:
设置图形,并使用哈密顿路径查找seq。
但是,这是一个完整的NP。
如何避免汉密尔顿路径?
还有更好的想法?
谢谢
请注意,如果您构建了一个部分序列,那么只有最后一个单词才能确定您可以继续使用哪个其他单词。 例如,如果你选择了“香蕉”和“狗”,你可以继续“类型”或“湖”(“湖”与“香蕉”碰撞并不重要,因为“湖”将与“狗”)。 由于你必须按照它们出现的顺序使用这些单词(如果我理解你的描述正确),你可以使用动态编程来解决问题“我能用最后一个词结束的最长的单词序列是什么?”
我的方法将涉及一个结构:
struct node{ char c1, c2; char* str; int used; int ind; std::vector valid; };
c1将是str中的第一个字符,c2将是最后一个字符。 我会循环输入数组并为每个项生成一个节点,并可能将它们放入std :: vector中。 然后在每个节点上,push_back()引用所有可以有效放置在该节点前面的节点。 然后我会递归寻找路径。 刚开始使用第一个节点,使用标签,导航到第一个有效索引,重复该节点,然后当控制返回到该点时,转到下一个有效节点,执行相同操作,然后从此处返回时,重置所有节点中的已使用值。 如果未找到匹配项,则返回false。
这是一些代码。 它确保每个单词的第一个和最后一个字母不匹配。 修改符合条件的表达式以满足您的需要。
#include #include #include struct node{ char c1, c2; char* str; int used; int ind; std::vector valid; }; int ispath_rec( std::vector &nodes, int depth, int* returnarray ); int ispath( char** value, int valuec, int* returnarray ){ std::vector 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 &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]] ); } } }
以上就是c/c++开发分享给定一些单词,找到一个序列,使得seq的任何相邻单词不能具有相同的字符相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/522515.html