C语言 递归代码如何确定回文是否工作?

Question

我有一个问题和下面的代码片段。片段已经填满了，因为我找到了解决方案，但我不明白为什么是这样的。你能帮我解释一下密码是怎么工作的吗?

问题:十个贴图上都有1到4个字母的字符串(在下面的代码中硬编码)。这个问题的目标是完成下面的代码，这样它就可以计算所有瓷砖可以放置的不同顺序的数量，以便它们形成的字符串创建一个回文(一个向前和向后读取相同的单词)。所有main，以及函数eval它决定了瓷砖的特定顺序是否形成回文。你可以在函数go中调用这个函数。完成递归函数(命名为go)来完成解。

片段代码:

#include <stdio.h>
#include <string.h>
#define N 10
#define MAXLEN 5
int go(int perm[], int used[], int k, char tiles[N][MAXLEN]);
int eval(int perm[], char tiles[N][MAXLEN]);
char MYTILES[N][MAXLEN] = {
"at", "ta", "g", "cc", "ccac", "ca", "cc", "gag", "cga", "gc"
};
int
main(void)
{
int perm[N];
int used[N];
for (int i = 0; i < N; i++)
used[i] = 0;
int res = go(perm, used, 0, MYTILES);
printf("Number of tile orderings that create palindromes is %dn", res);
return 0;
}
int
go(int perm[], int used[], int k, char tiles[N][MAXLEN])
{
if (k == N)
return eval(perm, tiles);
int res = 0;
for (int i = 0; i < N; i++) {
if (used[i])
continue;
used[i] = 1;
perm[k] = i;
res += go(perm, used, k + 1, tiles);
used[i] = 0;
}
return res;
}
int
eval(int perm[], char tiles[N][MAXLEN])
{
char tmp[N * MAXLEN];
int idx = 0;
for (int i = 0; i < N; i++) {
int len = strlen(tiles[perm[i]]);
for (int j = 0; j < len; j++)
tmp[idx++] = tiles[perm[i]][j];
}
tmp[idx] = '';
for (int i = 0; i < idx / 2; i++)
if (tmp[i] != tmp[idx - 1 - i])
return 0;
return 1;
}

谢谢。我感谢所有的帮助!!

Answer 1

要理解这段代码，将以下行添加到eval()的开头:

for( int j = 0; j < N; j++ ) printf( "%d ", perm[j] ); putchar('n');

go()中的for()循环导致深度为10的递归，最终生成10!(~ 360万)从0到9的10个指数的排列。按顺序，使用这些排列中的每一个将'令牌'(短的ACTG变体)连接到一个字符串中，然后通过' eval()'

测试该字符串是否为回文字符串。这被称为"蛮力"。搜索可能性空间

下面我修改了代码，使其稍微紧凑一些，增加了两个&;printf调试&;报告程序正在做什么的行(标记为"/**/")。如果您希望看到数以百万计的0到9的排列滚动，或者只是注释掉该行并重新编译，则需要一些耐心。我还打乱了一些东西，让这两个有趣的数组成为全局数组，而不是"破坏堆栈"。通过递归向上/向下传递它们。代码越少越好。这个程序是"单一目的"的。由此获得的清晰度证明了在本例中使用全局变量是合理的。

更有趣的是报告回文序列的附加puts()行。

#include <stdio.h>
#include <string.h>
#define N 10
#define MAXLEN 5
char MYTILES[N][MAXLEN] = { "AT","TA","G","CC","CCAC","CA","CC","GAG","CGA","GC" };
int perm[N], used[N] = { 0 };
int go( int k ) {
if (k == N) {
// At extent of recursion here.
/**/    for( int j = 0; j < k; j++ ) printf( "%d ", perm[j] ); putchar('n');
// Make a string in this sequence
char tmp[N*MAXLEN] = {0};
for( int i = 0; i < N; i++ )
strcat( tmp, MYTILES[ perm[ i ] ] );
// Test string for being palidromic
for( int l = 0, r = strlen( tmp ) - 1; l <= r; l++, r-- )
if( tmp[l] != tmp[r] )
return 0; // Not palidrome
/**/    puts( tmp );
return 1; // Is palidrome
}
// recursively generate permutations here
int res = 0;
for( int i = 0; i < N; i++ )
if( !used[i] ) {
used[i] = 1;
perm[k] = i;
res += go( k+1 );
used[i] = 0;
}
return res;
}
int main( void ) {
printf( "Palindromic tile orderings: %dn", go( 0 ) );
return 0;
}

一个直接的"加速"将是测试第0个字符串的第一个字母是否匹配第9个字符串的最后一个字母…如果从一开始就不可能使用回文，就不要费心连接。其他优化留给读者作为练习…

顺便说一句:可以复制代码并添加自己的print语句，以便程序报告它正在做什么，当…或者，您可以单步通过调试器…

添加了一个10x10矩阵的初步生成来"gate"生成要作为回文检查的字符串的工作量，使用10个OP提供的字符串，事实证明，72%的这些操作从一开始就注定要失败。在360万"蛮力"中对这个预先生成的矩阵的快速引用阻止了大约260万次攻击。

让代码更高效是值得尝试的。

更新# 2:
在尝试改进"蛮力"后，执行中仍然有很多"脂肪";用一种简单的方式，我重做了一些代码。

使用一些额外的全局变量(处理状态)，下面的代码现在做了一些"准备"。在main()中，然后进入递归。在这个版本中，一旦由片段组装的字符串超过了一半(长度)，就会从"中间"开始检查。如果它符合回文的条件。如果是，则每个附加的片段都会导致重新测试。如果字符串永远不会变成回文，递归就会"备份"并尝试另一种"味道"的排列。这极大地减少了可能性空间(并真正加快了执行速度)。

char *Tiles[] = { "AT","TA","G","CC","CCAC","CA","CC","GAG","CGA","GC" };
const int nTiles = sizeof Tiles/sizeof Tiles[0];
int used[ nTiles ];
char buildBuf[ 1024 ], *cntrL, *cntrR; // A big buffer and 2 pointers.
int fullLen;
int cntTested, goCalls; // some counters to report iterations
uint32_t factorial( uint32_t n ) { // calc n! (max 12! to fit uint32_t)
uint32_t f = 1;
while( n ) f *= n--;
return f;
}
int hope() { // center outward testing for palindromic characteristics
int i;
for( i = 0; cntrL[ 0 - i ] == cntrR[ 0 + i ]; i++ ) ; // looping
return cntrR[ 0 + i ] == '';
}
int go( int k ) {
goCalls++;
if( k == nTiles ) { // at full extent of recursion here
// test string being palindromic (from ends toward middle for fun)
cntTested++;
for( int l = 0, r = fullLen - 1; l <= r; l++, r-- )
if( buildBuf[l] != buildBuf[r] )
return 0; // Not palindrome
/**/    puts( buildBuf );
return 1; // Is palindrome
}
// recursively generate permutations here
// instead of building from sequence of indices
// this builds the (global) sequence string right here
int res = 0;
char *at = buildBuf + strlen( buildBuf );
for( int i = 0; i < nTiles; i++ )
if( !used[i] ) {
strcpy( at, Tiles[ i ] );
// keep recursing until > half assembled and hope persists
if( at < cntrL || hope() ) {
used[i] = 1;
res += go( k+1 ); // go 'deeper' in the recursion
used[i] = 0;
}
}
return res;
}
int main( void ) {
for( int i = 0; i < nTiles; i++ )
fullLen += strlen( Tiles[i] );
if( fullLen % 2 == 0 ) // even count
cntrR = (cntrL = buildBuf + fullLen/2 - 1) + 1; // 24 ==> 0-11 & 12->23
else
cntrR = cntrL = buildBuf + fullLen/2; // 25 ==> 0-12 & 12->24
printf( "Palindromic tile orderings: %dn", go( 0 ) );
printf( "Potential: %dn", factorial( nTiles ) );
printf( "Calls to go(): %dn", goCalls );
printf( "Actual: %dn", cntTested );
return 0;
}

ATCCACGAGCCGCCGAGCACCTA
ATCCACGAGCCGCCGAGCACCTA
ATCCACGCCGAGAGCCGCACCTA
ATCCACGCCGAGAGCCGCACCTA
ATCACCGAGCCGCCGAGCCACTA
ATCACCGCCGAGAGCCGCCACTA
ATCACCGAGCCGCCGAGCCACTA
ATCACCGCCGAGAGCCGCCACTA
TACCACGAGCCGCCGAGCACCAT
TACCACGAGCCGCCGAGCACCAT
TACCACGCCGAGAGCCGCACCAT
TACCACGCCGAGAGCCGCACCAT
TACACCGAGCCGCCGAGCCACAT
TACACCGCCGAGAGCCGCCACAT
TACACCGAGCCGCCGAGCCACAT
TACACCGCCGAGAGCCGCCACAT
CCACATGAGCCGCCGAGTACACC
CCACATGAGCCGCCGAGTACACC
CCACATGCCGAGAGCCGTACACC
CCACATGCCGAGAGCCGTACACC
CCACTAGAGCCGCCGAGATCACC
CCACTAGAGCCGCCGAGATCACC
CCACTAGCCGAGAGCCGATCACC
CCACTAGCCGAGAGCCGATCACC
CACCATGAGCCGCCGAGTACCAC
CACCATGCCGAGAGCCGTACCAC
CACCTAGAGCCGCCGAGATCCAC
CACCTAGCCGAGAGCCGATCCAC
CACCATGAGCCGCCGAGTACCAC
CACCATGCCGAGAGCCGTACCAC
CACCTAGAGCCGCCGAGATCCAC
CACCTAGCCGAGAGCCGATCCAC
Palindromic tile orderings: 32
Potential: 3628800
Calls to go(): 96712
Actual: 32

更新# 3(玩得开心)
当有太多的代码和低效的算法时，很容易迷失方向，很难弄清楚发生了什么。

下面的产生与上面完全相同的结果，但是从执行中删除了一些操作。简而言之，go()被递归地调用，直到至少有1/2的候选字符串被构建。在这一点上，hope()被要求求值字符串从中间，到。只要满足回文(从中心向外)的条件，则随着字符串(通过递归)增长到最大范围，该计算将重复进行。这是"早期纾困"。这使得这个版本比OP版本更有效率。

一个进一步的"细化"是在没有额外调用的情况下找到递归的底部。一旦有了递归和置换的概念，这一切都应该是直截了当的…

char *Tiles[] = { "AT", "TA", "G", "CC", "CCAC", "CA", "CC", "GAG", "CGA", "GC" };
const int nTiles = sizeof Tiles/sizeof Tiles[0];
int used[ nTiles ];
char out[ 1024 ], *cntrL, *cntrR;
int hope() { // center outward testing for palidromic characteristics
char *pL = cntrL, *pR = cntrR;
while( *pL == *pR ) pL--, pR++;
return *pR == '';
}
int go( int k ) {
int res = 0;
char *at = out + strlen( out );
for( size_t i = 0; i < nTiles; i++ )
if( !used[i] ) {
strcpy( at, Tiles[ i ] );
if( at >= cntrL && !hope() ) // abandon this string?
continue;
if( k+1 == nTiles ) { // At extent of recursion here.
puts( out );
return 1;
}
used[i] = 1, res += go( k+1 ), used[i] = 0;
}
return res;
}
int main( void ) {
int need = 0;
for( size_t i = 0; i < nTiles; i++ )
need += strlen( Tiles[ i ] );
cntrL = cntrR = out + need/2; // odd eg: 25 ==> 0-12 & 12->24
cntrL -= (need % 2 == 0 ); // but, if even eg: 24 ==> 0-11 & 12->23
printf( "Palindromic tile orderings: %dn", go( 0 ) );
return 0;
}