c - 为什么我的 C 代码给出下一个回文的错误输出

Question

我有一个 C 代码(找到 next smallest palindrome )，当我在我的本地 Mac(osx:10.11.4)和 ideone 中运行时，对于相同的输入它会给出错误的结果。它不会对所有输入给出错误，但对某些输入给出错误。

例如这里由ideone运行:http://ideone.com/T4tqak

这是我对相同输入的结果:

在本地输入:

8
97795375756122352572879826552151654387112262
1892388497169516734992356528466
19891859448286167812
47737795782241879811566697829238862994263278849942632926438725
857751275744476297149515661
699
5119783738665448121162642286
4177118624313412937235746451

本地输出:

97795375756122352572877827525322165757359779
1892388497169516159617948832981
19891859444495819891
47737795782241879811566697829233292879666511897814228759773774
857751275744474447572157758
707
5119783738665445668373879115
4177118624313443134268117714

C代码供引用:

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

int all_nine(char* input){
  int result = 1, i;
  for(i = 0; i < strlen(input); ++i){
    if(input[i] != '9')
      return 0;
  }
  return result;
}

char* increase_one(char* input){
  int i;
  for(i = strlen(input) - 1; i >= 0; --i) {
    if(input[i] < '9'){
      input[i] += 1;
      break;
    }
    else{
      input[i] = '0';
    }
  }
  return input;
}


char* increase_make_palin(char* input){
  int input_len = strlen(input);
  int half_len = input_len%2 ? input_len/2 : input_len/2 - 1;
  int carry = 1, i;
  for(i = half_len; i >= 0; --i) {
    int cur_val = input[i] - '0';
    carry = (cur_val + carry) / 10;
    int new_val = (cur_val + carry) % 10;
    input[i] = input[input_len - 1 - i] = '0' + new_val;
  }
  return input;
}
char* next_palin_for_me(char* input){
    int input_len = strlen(input);
    int half_len = input_len/2  - 1, i;
    for(i = half_len; i >= 0; --i) {
      if(input[i] > input[input_len - 1 - i]){
        input[input_len - 1 - i] = input[i];
      } else {
        return increase_make_palin(input);
      }
    }
    return input;
}

char* next_palin(char* input){
  int input_len = strlen(input);
  if(all_nine(input)){
    return next_palin_for_me(increase_one(input));
  }
  if(input_len == 1){
    input[0] += 1;
    return input;
  }
  input = increase_one(input);
  return next_palin_for_me(input);
}

int main() {
  int n, i;
  scanf("%d", &n);
  char input[1000010];
  for(i = 0 ; i < n ; i++){
    scanf("%s", input);
    char* result = next_palin(input);
    printf("%s\n", result);
  }
  return 0;
}

Answer 1

问题出在这里:

char* increase_make_palin(char* input){
    ...
    carry = (cur_val + carry) / 10;
    int new_val = (cur_val + carry) % 10;
    ...
}

请注意，您在使用 carry 之前更改了它。颠倒这两行的顺序，您的代码将按预期工作。

您可以使用 8799 作为测试输入，看看它是如何工作的。您本可以自己发现这一点，方法是使用调试器单步执行，或者将失败案例简化为更简单的案例。

至于为什么在ideone上给出了错误代码的正确答案(如果确实是这样；我没试过)，我只能猜测可能是那里数字的编码不同，这会造成麻烦用你的“-'0'”方法。

编辑:

char* increase_make_palin(char* input){
  int input_len = strlen(input);
  int half_len = input_len%2 ? input_len/2 : input_len/2 - 1;
  int carry = 1, i = half_len;
  while(i > 0){
    if(input_len%2 == 0){
      if(input[i] == input[input_len - 1 - i]) {
        i--;
        continue;
      }
      if(input[i] > input[input_len - 1 - i]) {
        carry = 0;
        break;
      }
      else{
        break;
      }
    }
    if(input_len%2){
      if(input[i-1] == input[input_len - i]){
        i--;
        continue;
      }
      if(input[i-1] > input[input_len - i]){
        carry = 0;
        break;
      }
      else{
        break;
      }
    }
  }
  for(i = half_len; i >= 0; --i) {
    int cur_val = input[i] - '0';
    int new_val = (cur_val + carry) % 10;
    carry = (cur_val + carry) / 10;
    input[i] = input[input_len - 1 - i] = '0' + new_val;
  }
  return input;
}