面试问题，递归+回溯
这个问题是关于递归/回溯的面试题，涉及IT技术。假设我们有两个布尔数组：bool* source 和 bool* target，它们都有相同的长度n（source/target/n作为参数给出）。问题的目标是使用操作 switch将source转换为target。 如果有多个变换：请给出其...
你能在纯Prolog中写出between/3吗？
我一直在尝试理解如何通过Prolog谓词回溯生成一系列值。内置的谓词between/3会在回溯时逐个生成范围内的所有整数，因此一个实现该谓词的示例可能对我有所帮助。 我寻找了现有Prolog系统中的实现，但GNU Prolog的between/3实现是一个C函数，其中的技巧在于它调用另一个C...
我该如何解决《编程挑战（编程竞赛培训手册）》中所提出的“Crypt Kicker”练习？
"Programming Challenges (The Programming Contest Training Manual)" 可能是关于算法最好的练习书之一。 我已经解决了前11个问题，但现在卡在了 "Crypt Kicker" 问题上： Crypt Kicker 加密文本...
编程练习（安装管道）的回溯解决方案
我正在审查一道来自本地编程竞赛的编程问题。 您可以在此处下载这个问题（pdf文件）。虽然是荷兰语，但图片会帮助理解。 输入一个m * m的网格，其中有些地方有管道，有些地方缺失（用问号表示）。 剩下的管道必须被放置在网格中，以便与其他管道连接起来。 每个管道都表示为一个字母（请参见第2页...
编写一个高效解决纵横字谜的程序。
我有一个填字游戏和一个可以用来解决它的单词列表（单词可以被放置多次或者甚至一次都不放）。对于给定的填字游戏和单词列表，总是存在解决方案。 我搜索了一些关于如何解决这个问题的线索，发现它是NP-Complete问题。我的填字游戏的最大尺寸是250乘250，单词列表的最大长度（可以用来解决游戏的...
在Python中实现Prolog Unification算法？回溯
我正在尝试实现统一，但遇到了问题。虽然已经有了许多例子，但它们只是使问题更加混乱。我感到越来越困惑而不是受到启发： http://www.cs.trincoll.edu/~ram/cpsc352/notes/unification.html https://www.doc.ic.ac.uk...
正则表达式模式——灾难性回溯问题
我在旧的Java系统中使用了下面展示的正则表达式，最近它导致回溯问题。很多时候回溯线程会导致机器的CPU达到上限，直到应用程序重新启动才恢复正常。 有没有人能建议一种更好的重写这个模式的方法或一个可以帮助我做到这一点的工具？ 模式：^\[(([\p{N}]*\]\,\[[\p{N}]*)*...
Atomic groups clarity
考虑这个正则表达式。a*b 在输入 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac 时，这段代码将会失效。 在调试器中，运行这段代码需要 67 步才会失效。 现在考虑以下正则表达式。(?>a*)b 在出现 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
正则表达式中的(a?)*是否具有指数增长？
我正在研究一些正则表达式的问题，当对某个输入进行匹配时，它们可能会以指数级的时间运行。例如，(a*)*和(a|a)*在与字符串aaaaab匹配时可能会出现'灾难性回溯'的情况——对于匹配字符串中每一个额外的'a'，尝试匹配该字符串所需的时间就加倍。只有引擎使用回溯/NFA方法在失败之前尝试树中...
如何使用选择单子（Select monad）来解决 N 皇后问题？
我正在试图理解Select单子的工作原理。显然，它是Cont的近亲，可用于回溯搜索。 我有一个基于列表的解决n皇后问题的方案：-- All the ways of extracting an element from a list. oneOf :: [Int] -> [(Int,[In...