提问人：konxanth 提问时间：11/18/2023 最后编辑：Vlad from Moscowkonxanth 更新时间：11/19/2023 访问量：164
C 中的回文数
Palindromic number in C
问：
因此，假设我们在 C 语言中有这个程序来检查一个数字是否是回文的，而根本不使用任何数组（所以不要用任何使用数组的答案来响应）
#include <stdio.h>
#include <math.h>
int NumOfDigits(long long x) {
int sum = 1;
while (x / 10 != 0) {
sum ++;
x = x / 10;
}
return sum;
}
int isPal(long long x) {
int f, c, front, back, sum;
sum = NumOfDigits(x);
c = round(pow(10,(sum-2)));
front = x / round(pow(10,(sum - 1)));
back = x % 10;
f = 1;
while (x != 0 && f == 1 && c != 0) {
if (front == back) {
x = (x / 10) % c;
c /= 100;
sum -=2;
front = x / round(pow(10,(sum-1)));
back = x % 10;
} else {
f = 0;
}
}
if (f) {
return 1;
} else {
return 0;
}
}
int main() {
int f;
long long x;
scanf("%lld", &x);
f = isPal(x);
if (f) {
printf("yes");
} else {
printf("no");
}
printf("\n");
}
所以基本上这个算法每次都会检查第一个和最后一个数字，然后将 NumOfDigits 减少 2，所以如果我们有345543，首先是 345543，然后是 4554、55 等。这个程序的要点是，例如，给定数字900075181570009它说它不是回文的，但这是因为计算机擦除了数字左侧的 0。因此，当它0007518157000它基本上是7518157000，这不是一个回文数。那么，我们如何在不使用数组的情况下修改算法以达到预期的结果呢？
答：
1赞
Sachin Mirajkar
11/18/2023
#1
在代码中，该值被错误地声明为 .cint
#include <stdio.h>
#include <math.h>
int main()
{
int c ;
c = round(pow(10,13));
printf("%ld",c);
return 0;
}
当我们运行上述程序时，我们收到溢出警告：
main.c: In function ‘main’:
main.c:14:9: warning: overflow in conversion from ‘double’ to ‘int’ changes value from ‘1.0e+13’ to ‘2147483647’ [-Woverflow]
14 | c = round(pow(10,13));
| ^~~~~
2147483647
因此，只需更改即可解决问题，并且工作正常。int cunsigned long int c
0赞
Fe2O3
11/18/2023
#2
首先，在处理整数值时不需要该解决方案。<math.h>
NumOfDigits()在错误启动时关闭。这意味着被比较的值将被视为数组（具有单个元素）。
下面是一个解决方案。 打印正在检查的两个值的 base10 表示形式，以验证函数是否使用整数，而不是数组。isPal()
数组用于 （外部 ） 中的测试对集合，仅用于演示如何在测试用例中表示带有前导/尾随零的值。（注意：通过规避 C 编译器对前导零的解释转换的数字字符串在源代码中预示着八进制或十六进制值。main()isPal()atoi())
#include <stdio.h>
char *isPal( uint32_t a, uint32_t b) {
uint32_t rev = 0;
printf( "isPal( %u, %u ) - ", a, b );
for( ; b; b /= 10 )
rev = rev * 10 + b % 10;
for( ; rev <= a; rev *= 10 )
if( rev == a )
return "yes";
return "no";
}
int main( void ) {
char *vals[][2] = {
{ "123", "321" },
{ "121", "321" },
{ "00070", "07000" },
{ "50060", "06005" },
{ 0 } // terminate
};
for( size_t i = 0; vals[i][0]; i++ )
printf( "%s & %s - %s\n", vals[i][0], vals[i][1],
isPal( atoi( vals[i][0]), atoi( vals[i][1] ) ) );
return 0;
}
结果：
isPal( 123, 321 ) - 123 & 321 - yes
isPal( 121, 321 ) - 121 & 321 - no
isPal( 70, 7000 ) - 00070 & 07000 - yes
isPal( 50060, 6005 ) - 50060 & 06005 - yes
当别人说某事是不可能的时，相信他们是不健康的......
警告：在更简单的领域中，该值可以表示（在一个字节中），其反转不能...检测和避免数字溢出是 OP 的练习。unsigned char128821if( value >= UtypeMAX / 10 ) /* do not attempt to multiply by 10 */)
编辑：在展示了概念证明之后，这里有一个不那么生硬的版本，它处理一个数字和它自己的栅栏：
#include <stdio.h>
char *isPal( uint32_t a ) {
uint32_t b = a, rev = 0;
printf( "isPal( %u ) - ", a );
for( ; b; b /= 10 )
rev = rev * 10 + b % 10;
for( ; rev <= a; rev *= 10 )
if( rev == a )
return "yes";
return "no";
}
int main( void ) {
char *vals[] = {
"12321",
"12345",
"00000700",
"031300",
"50050",
0 // terminate
};
for( size_t i = 0; vals[i]; i++ )
printf( "%s - %s\n", vals[i], isPal( atoi( vals[i] ) ) );
return 0;
}
结果：
isPal( 12321 ) - 12321 - yes
isPal( 12345 ) - 12345 - no
isPal( 700 ) - 00000700 - yes
isPal( 31300 ) - 031300 - yes
isPal( 50050 ) - 50050 - yes
1赞
chux - Reinstate Monica
11/18/2023
#3
OP 的第一个问题不是由于前导零，而是由于失败，因为 是 an 而不是 .c = round(pow(10,(sum-2)));cintlong long
如果代码想要处理前导零，请考虑使用 来记录扫描的偏移量。"%n"
int n1, n2;
if (scanf(" %n%lld%n", &n1, &x, &n2) != 1) {
Handle_BadInput(); // TBD code
}
int digit_count = n2 - n1;
这仍然会被输入（如或范围之外的值）所愚弄。"-123"long long
考虑用于处理所有 19 位数字和一些 20 位数字的值。unsigned long long
[编辑 2023/11/18]
尝试完全反转一个数字的问题之一是反转的数字可能超出了数字范围。对于最小有效数字大于最高有效数字的大值，很容易发生这种情况。
一种解决方案是只反转数字的最高有效一半，同时形成反转的最低有效部分。然后比较值。这样，就不会发生溢出。它还执行更少的计算。
示例代码和测试工具。测试代码使用数组来形成反向值，但这是用于测试的。 是无阵列的（一旦删除了调试。isPal_without_array()printf()
#include <stdio.h>
int isPal_without_array(unsigned long long x) {
unsigned long long forward = x;
unsigned long long reverse = 0;
unsigned long long tens = 10;
while (forward >= tens) {
printf("f:%20llu r:%20llu\n", forward, reverse);
unsigned digit = forward % 10;
forward /= 10;
reverse = reverse * 10 + digit;
tens *= 10;
}
printf("f:%20llu r:%20llu\n", forward, reverse);
if (forward >= tens / 10) {
forward /= 10;
}
return forward == reverse;
}
#include <assert.h>
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
/*
* Test palindrome 2 ways:
* Return 0 on match, 1 on mis-match.
*/
int isPal_test(unsigned long long x) {
char forward[50];
char reverse[50];
int len = sprintf(forward, "%llu", x);
for (int i = 0; i < len; i++) {
reverse[i] = forward[len - 1 - i];
}
reverse[len] = '\0';
int cmp0 = (strcmp(forward, reverse) == 0);
int cmp1 = isPal_without_array(x);
if (cmp0 != cmp1) {
printf("%20llu %20s %d %d FAIL\n", x, reverse, cmp0, cmp1);
return 1;
}
printf("%20llu %20s %d %d\n\n", x, reverse, cmp0, cmp1);
return 0;
}
#include <limits.h>
int main() {
isPal_test(18446744073709551615u); // ULLONG_MAX
isPal_test(18446740733704764481u);
return 0;
isPal_test(67899876);
isPal_test(3443);
isPal_test(121);
for (unsigned i = 0; i <= 1000; i++) {
isPal_test(i);
}
for (unsigned long long i =0; i < 10000000; i++) {
isPal_test(ULLONG_MAX - i);
}
puts("Done");
}
输出接近 '
f:18446744073709551615 r: 0
f: 1844674407370955161 r: 5
f: 184467440737095516 r: 51
f: 18446744073709551 r: 516
f: 1844674407370955 r: 5161
f: 184467440737095 r: 51615
f: 18446744073709 r: 516155
f: 1844674407370 r: 5161559
f: 184467440737 r: 51615590
f: 18446744073 r: 516155907
f: 1844674407 r: 5161559073
18446744073709551615 51615590737044764481 0 0
f:18446740733704764481 r: 0
f: 1844674073370476448 r: 1
f: 184467407337047644 r: 18
f: 18446740733704764 r: 184
f: 1844674073370476 r: 1844
f: 184467407337047 r: 18446
f: 18446740733704 r: 184467
f: 1844674073370 r: 1844674
f: 184467407337 r: 18446740
f: 18446740733 r: 184467407
f: 1844674073 r: 1844674073
18446740733704764481 18446740733704764481 1 1
评论
0赞
chux - Reinstate Monica
11/20/2023
@Bob__ 看起来不错！
0赞
Vlad from Moscow
11/18/2023
#4
该函数是错误的，至少因为在此语句中由于整数除法isPal
x = (x / 10) % c;
前导零可能会丢失。
你不应该改变 suzh 的方式。此外，使用返回双精度值的函数是不安全和多余的。xpow
此外，按照建议使用字符串会打破不允许使用数组的规则，因为字符串实际上包含在字符数组中。
我可以提出以下解决方案。
#include <stdio.h>
unsigned long long max_divisor( unsigned long long x )
{
const unsigned long long int Base = 10;
unsigned long long divisor = 1;
while (!( x / divisor < Base ))
{
divisor *= Base;
}
return divisor;
}
int is_palindrome( unsigned long long x )
{
const unsigned long long Base = 10;
unsigned long long int left_divisor = max_divisor( x );
unsigned long long int right_divisor = 1;
int palindrome = 1;
while (palindrome && right_divisor < left_divisor)
{
unsigned long long int left_digit = x / left_divisor % Base;
unsigned long long int right_digit = x % ( Base * right_divisor ) / right_divisor;
if (( palindrome = left_digit == right_digit ))
{
left_divisor /= Base;
right_divisor *= Base;
}
}
return palindrome;
}
int main( void )
{
printf( "is_palindrome( 1 ) is %s\n", is_palindrome( 1 ) ? "true" : "false" );
printf( "is_palindrome( 11 ) is %s\n", is_palindrome( 11 ) ? "true" : "false" );
printf( "is_palindrome( 12 ) is %s\n", is_palindrome( 12 ) ? "true" : "false" );
printf( "is_palindrome( 121 ) is %s\n", is_palindrome( 121 ) ? "true" : "false" );
printf( "is_palindrome( 1221 ) is %s\n", is_palindrome( 1221 ) ? "true" : "false" );
printf( "is_palindrome( 12321 ) is %s\n", is_palindrome( 12321 ) ? "true" : "false" );
printf( "is_palindrome( 900075181570009 ) is %s\n", is_palindrome( 900075181570009 ) ? "true" : "false" );
}
程序输出为
is_palindrome( 1 ) is true
is_palindrome( 11 ) is true
is_palindrome( 12 ) is false
is_palindrome( 121 ) is true
is_palindrome( 1221 ) is true
is_palindrome( 12321 ) is true
is_palindrome( 900075181570009 ) is true
0赞
NoDakker
11/18/2023
#5
在测试代码时，我确实注意到900075181570009被指定为不是回文的结果是变量是整数的问题，因此在某些情况下太小而无法包含适当的 10 次幂。当我将其指定为“long long”变量时，数字900075181570009被指定为回文。
关于测试具有前导零（和尾随零）的数字，似乎是一个必要的函数，即重复将数字除以 10，直到所有尾随零都被清除，然后执行回文测试。以下是重构后的代码。首先是附加功能，用于从候选号码中删除尾随零。
#include <stdio.h>
#include <math.h>
long long lagging(long long z)
{
long long work = z;
while (1)
{
if ((work % 10) != 0)
break;
work /= 10;
}
return work;
}
接下来是重构的回文测试函数，其中变量“c”被放大，以及测试值的初始清理。
int isPal(long long x) {
int f,front, back, sum;
long long c;
x = lagging(x); /* One off call to additional scrubbing if needed */
sum = NumOfDigits(x);
在测试示例中记录的各种数字时，以下是终端的测试输出。
craig@Vera:~/C_Programs/Console/PalInteger/bin/Release$ ./PalInteger
Enter a number: 900075181570009
yes
craig@Vera:~/C_Programs/Console/PalInteger/bin/Release$ ./PalInteger
Enter a number: 0007518157000
yes
craig@Vera:~/C_Programs/Console/PalInteger/bin/Release$ ./PalInteger
Enter a number: 345543
yes
craig@Vera:~/C_Programs/Console/PalInteger/bin/Release$ ./PalInteger
Enter a number: 7518157000
yes
一个是您评估的思路。
评论
1赞
Bob__
11/18/2023
为什么你会认为 7518157000（或除 0 以外的任何数字）是回文？OP没有，在他们的问题中：“所以当它去0007518157000它基本上是7518157000，这不是一个回文数”。
0赞
chux - Reinstate Monica
11/18/2023
NoDakker，谨慎使用，因为这是一个无限循环。lagging(0)
0赞
chux - Reinstate Monica
11/18/2023
“变量是整数的问题”比“变量是整数的问题”更好。
0赞
NoDakker
11/18/2023
@chux - 是的，这些都是需要进一步澄清的好点。
0赞
Vlad from Moscow
11/19/2023
@NoDakker 实际上，数字7518157000不是回文。0 不等于 7。所以你的解决方案是不正确的。
2赞
Simon Goater
11/18/2023
#6
您可以将数字反转，然后将其与原始值进行比较。适用于 0 <= xinit < 10^19。
int isPal(uint64_t xinit) {
uint64_t x = xinit;
uint64_t xrev = 0;
while(x) {
xrev = 10*xrev + (x % 10);
x /= 10;
}
return (xrev == xinit);
}
评论
0赞
Simon Goater
11/18/2023
@chux-恢复莫妮卡公平点。不过，它适用于所有非负有符号多头，这是 OP 函数的输入范围，通常适用于任何小于 10^19 的正整数。
0赞
Simon Goater
11/18/2023
@chux-恢复莫妮卡 这就是我通常使用 stdints 的原因。
评论
numOfDigits()x00000