如何证明递归算法的正确性？
private static void swap(char[] str, int i, int j){
char tmp = str[i];
str[i] = str[j];
str[j] = tmp;
}
public static void permute(String str){
permute(str.toCharArray(), 0, str.length());
}
private static void permute(char[] str, int low, int high){
if(low == high){
System.out.println(str);
} else {
for(int i = low; i < high; i++){
swap(str, low, i);
permute(str, low+1, high);
swap(str, low, i);
}
}
}我实现了一个字符串置换的递归方法。但我有一个问题:如何使用归纳来证明此代码的正确性？我真的不知道。
回答 1
Stack Overflow用户
发布于 2013-07-29 14:02:05
首先，您必须具体说明您所说的正确性是什么意思(即，您希望检查代码所依据的规范；另请参阅https://stackoverflow.com/a/16630693/476803 )。让我们假设这里的正确性意味着
permute的每个输出都是给定字符串的排列。
然后，我们可以选择执行归纳的自然数。对于递归函数permute，我们可以在low或high之间进行选择，也可以选择它们的组合。
在读取实现时，很明显，输出字符串的某个前缀的元素不会发生变化。此外，该前缀的长度在递归期间增加，因此长度为high - low的剩余后缀减少。所以让我们在high - low上进行归纳(假设low <= high，这是合理的，因为我们最初使用0作为low，将一些字符串的长度用于high，并且递归在low == high之后立即停止)。也就是说，我们展示了
事实：
permute(str, low, high)的每个输出都是str的最后一个high - low字符的排列。
假设情况：假设high - low = 0。则该语句完全正确，因为它必须保持最后的0字符(即，对于none).
- Step情况:假设为
high - low = n + 1。此外，作为归纳假设(IH)，我们可以假设这一陈述对n是正确的。从high - low = n + 1我们得到了high - (low + 1) = n(因为high必须严格大于low，high - low = n + 1才能保持)。因此，通过IH，permute(str, low+1, high)的每个输出都是str的最后一个high - (low + 1)字符的排列。
现在到了我们必须要证明的时候了。也就是说，通过在permute(str, low+1, high)生成的输出中将str的low-th字符与low (直到high)之后的任何字符进行交换，我们生成low和high之间的字符排列。这一步(我在这里省略，因为我只是想演示如何在原则上使用归纳法)结束了证明。
最后，通过使用用于low的0和用于high的str.length来实例化上述事实，我们得到了非递归permute的每个输出都是str的置换。
注：上面的证明只表明每一个输出都是一个排列。然而，知道实际上所有的排列都是打印出来的，这可能也是很有趣的。
https://stackoverflow.com/questions/15361097
复制相似问题
腾讯云开发者
