递归函数寻找回文

Question

也许你能告诉我方法，至少我可以开始。我只会用C语言。该任务有非常具体的限制，我无法以任何方式打破它们。任务是：

编写检查字符串是否为回文的递归函数。
只能在函数中使用strlen()一次。
不能使用任何循环或基于循环的函数。
在递归函数中只能使用一个转换。
可以更改字符串，但前提是它会在结束时返回函数。
函数声明为：int palindrom(char* str);

开始写了，但是没有想法了：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

int palindrom(char* str)
{
    int len = strlen(str);
    if (str[0] != str[len - 1]) return 0;

}

int main(void)
{
    char string1[] = "ROTATOR";
    char string2[] = "8536358";
    char string3[] = "Palindrome";
    if (palindrom(string1)) printf("%s is Palindrome\n", string1);
    else printf("%s is not Palindrome\n", string1);
    if (palindrom(string2)) printf("%s is Palindrome\n", string2);
    else printf("%s is not Palindrome\n", string2);
    if (palindrom(string3)) printf("%s is Palindrome\n", string3);
    else printf("%s is not Palindrome\n", string3);
    return 0;
}

Answer 1

这样的东西行得通吗？

Something like this will work ?

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

bool palindrom_helper(char* str, int first, int last)
{
    if(first >= last)
        return true;
    if (str[first] != str[last]) 
        return false;
    return (palindrom(str, first+1, last-1));

}

bool palindrom(char* str)
{
    return palindrom_helper(str, 0, strlen(str)-1);
}

int main(void)
{
    char string1[] = "ROTATOR";
    char string2[] = "8536358";
    char string3[] = "Palindrome";
    if (palindrom(string1)) printf("%s is Palindrome\n", string1);
    else printf("%s is not Palindrome\n", string1);
    if (palindrom(string2)) printf("%s is Palindrome\n", string2);
    else printf("%s is not Palindrome\n", string2);
    if (palindrom(string3)) printf("%s is Palindrome\n", string3);
    else printf("%s is not Palindrome\n", string3);
    return 0;
}

您应该只使用一次 strlen 函数。所以你不能在被递归调用的函数中使用它。

我在这里所做的是将 first 和 last 初始化为 0 和 len-1，然后使用 (first+1, last-1) 进行递归。

即使函数找到一对不匹配的字母，它也会 return 错误。否则它会一直持续到它们一起到达中心（奇数长度的字符串）或相互交叉（偶数长度的字符串）然后 return true （因为那意味着它们在路径上没有看到任何不匹配的字母）

另外，我不明白递归函数中的单一转换是什么意思？

Answer 2

如何解决的线索在限制中：可以更改字符串，但前提是它会在函数结束时返回。通过打印检查该条件结果。

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

int palindrom(char* str)
{
    size_t len = strlen(str);
    int res;
    if(len < 2) {
        return 1;                   // cannot shorten: must be success
    }
    if(str[0] != str[len - 1]) {    // make palindrome test
        return 0;
    }

    str[len - 1] = '[=10=]';            // shorten the string at the back
    res = palindrom(str + 1);       // recurse woth string shortened at the front
    str[len - 1] = str[0];          // replace last char (we know it's the same)
    return res;
}

int main(void)
{
    char string1[] = "ROTATOR";
    char string2[] = "8536358";
    char string3[] = "Palindrome";
    char string4[] = "A";
    char *wrd[] = { "not ", "" };

    printf("%s is %sa Palindrome\n", string1, wrd[ palindrom(string1) ]);
    printf("%s is %sa Palindrome\n", string2, wrd[ palindrom(string2) ]);
    printf("%s is %sa Palindrome\n", string3, wrd[ palindrom(string3) ]);
    printf("%s is %sa Palindrome\n", string4, wrd[ palindrom(string4) ]);

    return 0;
}

程序输出：

ROTATOR is a Palindrome
8536358 is a Palindrome
Palindrome is not a Palindrome
A is a Palindrome

递归函数寻找回文

Recursive function finding Palindrome

c

recursion

palindrome