c - 寻找回文

Question

我是编程新手，第一门语言是C（学了一个月左右）。几个小时以来，我一直在尝试解决这个回文问题，但仍然无法提出令人满意的解决方案。问题是 here（来自 SPOJ），这是我的代码：

#include <stdio.h>
#include <string.h>
void plus_one(char *number);
int main(void)
{
    char number[1000001];
    int i, j, m, k, indicator;
    int a;
    scanf("%d", &j);
    for (i = 0; i < j; i++) {
        scanf("%s", number);
        k = 1;
        while (k != 0) {
            plus_one(number);
            a = strlen(number);
            indicator = 1;
            for (m = 0; m < a / 2; m++) {
                if (number[m] != number[a - m - 1]) {
                    indicator = 0;
                    break;
                }
            }
            if (indicator != 0) {
                printf("%s\n", number);
                k = 0;
            }
        }
    }
    return 0;
}

void plus_one(char *number)
{
    int a = strlen(number);
    int i;
    number[a - 1]++;
    for (i = a; i >= 0; i--){
        if (number[i - 1] == ':') {
            number[i - 1] = '0';
            number[i - 2]++;
        }
        else
            break;
    }
    if (number[0] == '0') {
        number[0] = '1';
        strcat(number, "0");
    }
    return;
}

我的想法是检查每个大于输入的数字，直到找到回文，并且它在我的计算机上运行良好。但是 SPOJ 回复了 "time limit exceeded"，所以我想我需要自己找到下一个可能的回文而不是使用蛮力。有人可以给我一个提示，告诉我如何让这一切变得更快吗？谢谢！

Answer 1

既然你要的是提示而不是 C 代码（我是出了名的不擅长），我会这样做：

确定数字 k 的位数是偶数还是奇数，将其存储在名为 odd 的布尔值中。
取数字k的前半部分，如果odd为真，则包括中间数字，并将其存储在名为half.
的变量中 808 -> 80
2133 -> 21
镜像 half 变量，如果 odd 为真，请注意不要重复中间数字，并将其存储在名为 mirror.
的变量中 80 -> 808
21 -> 2112
检查是否 mirror > k
- 如果为真：您找到了结果
- 如果为假：递增 half 并从第 3 步重新开始。
  （在最多增加一个增量后，您一定会找到您的结果。）
  80 -> 81 -> 818
  21 -> 22 -> 2222

这里有一个 JavaScript 实现供您参考：

const palin = (k) => {
  const mirror = (half, odd) => half + Array.from(half).reverse().join('').substring(odd);
  
  const s = k.toString();
  const odd = s.length % 2;
  const half = s.substring(0, Math.floor(s.length / 2) + odd);
  
  let mirrored = mirror(half, odd);
  
  if (+mirrored <= k) {
    mirrored = mirror((+half + 1).toString(), odd);
  }
  
  return mirrored;
}

console.log(palin(5));
console.log(palin(808));
console.log(palin(2133));

Answer 2

欢迎访问本网站。对于只使用 C 一个月的人来说，您发布的内容值得称赞！无论如何......我认为你的怀疑是正确的。使用 'brute force' 查找下一个回文可能是不可行的方法。

这个问题既是关于算法设计的，也是关于 C 的。尽管如此，您如何处理 char[] C 中整数的表示是有趣且相关的。 FWIW，我的尝试粘贴在下面。

它接受数字 (n) 和位数 (k) 的 char[] 表示作为参数，并且 returns 1成功或 0 失败（需要另一遍）。

static int next_palindrome(char *n, size_t k) {
    unsigned i = 0, carry = 0;
    char tmp = 0;
    int finished = 1;

    for (i = 0; i < k; i++) {
        if (carry) {
            finished = 0;
            *(n + k - i - 1) = *(n + k - i - 1) + 1;
            if (*(n + k - i - 1) == 10) {
                *(n + k - i - 1) = 0;
                carry = 1;
            } else
                carry = 0;
            continue;
        }
        if (i >= k / 2) continue;
        if (*(n + k - i - 1) == *(n + i)) continue;
        tmp = *(n + k - i - 1);
        *(n + k - i - 1) = *(n + i);
        if (tmp > *(n + i)) {
            carry = 1;
        }
    }

    return finished;
}

到目前为止，我只在小于 64 位的数字上测试过它，但没有理由相信它会在更大的数字上失败。

示例用法：http://codepad.org/3yyI9wEl

c - 寻找回文

c - find palindrome

c

palindrome