如何在 C 编程中使用递归反转整数数字的顺序？
How do I reverse the order of the digits of an integer using recursion in C programming?
问题陈述：
Given a 32-bit signed integer, reverse digits of an integer.
Note: Assume we are dealing with an environment that could only store
integers within the 32-bit signed integer range: [ −2^31, 2^31 − 1]. For
the purpose of this problem, assume that your function returns 0 when
the reversed integer overflows.
我正在尝试实现递归函数 reverseRec()，它适用于较小的值，但对于边缘情况来说是一团糟。
int reverseRec(int x)
{
if(abs(x)<=9)
{
return x;
}
else
{
return reverseRec(x/10) + ((x%10)*(pow(10, (floor(log10(abs(x)))))));
}
}
我已经实现了工作正常的非递归函数:
int reverse(int x)
{
long long val = 0;
do{
val = val*10 + (x%10);
x /= 10;
}while(x);
return (val < INT_MIN || val > INT_MAX) ? 0 : val;
}
这里我使用long long类型的变量val来检查MAX和MIN[=28的结果=] signed int type 但是问题的描述中特别提到我们需要在32位整数范围内处理，虽然不知何故它被接受了但我只是好奇 如果有办法仅使用 int 数据类型实现递归函数 ?
还有一件事，即使我考虑使用 long long，我也无法在递归函数 reverseRec() 中实现它。
我假设通过反转整数你的意思是将 129 变成 921 或者 120 变成 21。
您需要一个初始化方法来初始化您的递归函数。
您的递归函数必须计算出您的整数使用了多少位小数。这可以通过对值使用以 10 为底的对数然后将结果转换为整数来找到。
- log10 (103) 大约。 2.04 => 2
将初始值乘以 10 得到个位并将其存储在名为 temp 的变量中
从初始值中减去个位并将其存储在名为 newStart 的变量中。
- 将此值除以 10
从小数位减一并存储在另一个名为 newDecimal 的变量中。
Return个位乘以10的小数次方，加入函数中，初值为newStart，decimalPlace为newDecimal
#include <stdio.h>
#include <math.h>
int ReverseInt(int startValue, int decimalPlace);
int main()
{
int i = -54;
int positive = i < 0? i*-1 : i;
double d = log10(positive);
int output = ReverseInt(positive,(int)d);
int correctedOutput = i < 0? output*-1 : output;
printf("%d \n",correctedOutput);
return 0;
}
int ReverseInt(int startValue, int decimalPlace)
{
if(decimalPlace == 0)
{
return startValue;
}
int temp = startValue % 10;
int newStart = (startValue -temp)/10;
int newDecimal = decimalPlace -1;
int value = temp*pow(10,decimalPlace);
return value + ReverseInt(newStart,newDecimal);
}
很晚了，我没有想到更好的了。没有浮动计算。当然，整数必须足够大以容纳结果。否则就是UB。
int rev(int x, int partial, int *max)
{
int result;
if(x / partial < 10 && (int)(x / partial) > -10)
{
*max = partial;
return abs(x % 10) * partial;
}
result = rev(x, partial * 10, max) + abs(((x / (int)(*max / partial)) % 10) * partial);
return result;
}
int reverse(int x)
{
int max;
return rev(x, 1, &max) * ((x < 0) ? -1 : 1);
}
int main(void){
printf("%d", reverse(-456789));
}
unsigned rev(unsigned x, unsigned partial, unsigned *max)
{
unsigned result;
if(x / partial < 10)
{
*max = partial;
return (x % 10) * partial;
}
result = rev(x, partial * 10, max) + (x / (*max / partial) % 10) * partial;
return result;
}
unsigned reverse(unsigned x)
{
unsigned max;
return rev(x, 1, &max);
}
int main(void){
printf("%u", reverse(123456));
}
当使用 long long 存储结果时，所有可能的整数都可以反转
long long rev(int x, long long partial, long long *max)
{
long long result;
if(x / partial < 10 && (int)(x / partial) > -10)
{
*max = partial;
return abs(x % 10) * partial;
}
result = rev(x, partial * 10, max) + abs(((x / (int)(*max / partial)) % 10) * partial);
return result;
}
long long reverse(int x)
{
long long max;
return rev(x, 1, &max) * ((x < 0) ? -1 : 1);
}
int main(void){
printf("%d reversed %lld\n", INT_MIN, reverse(INT_MIN));
printf("%d reversed %lld\n", INT_MAX, reverse(INT_MAX));
}
If there is a way to implement a recursive function using only int datatype ?
(and) returns 0 when the reversed integer overflows
是的。
对于此类 +/- 问题，我喜欢将 int 值折叠到一侧并根据需要取反。折叠到一侧（- 或 +）简化了溢出检测，因为只有一侧需要测试
我更喜欢弃牌到负面，因为负面多于正面。 （对于 32 位 int，这个问题确实没有任何区别。）
由于代码形成反转值，在执行之前测试以下r * 10 + least_digit是否可能溢出
一个int唯一的递归解决方案来反转int。溢出 returns 0.
#include <limits.h>
#include <stdio.h>
static int reverse_recurse(int i, int r) {
if (i) {
int least_digit = i % 10;
if (r <= INT_MIN / 10 && (r < INT_MIN / 10 || least_digit < INT_MIN % 10)) {
return 1; /// Overflow indication
}
r = reverse_recurse(i / 10, r * 10 + least_digit);
}
return r;
}
// Reverse an int, overflow returns 0
int reverse_int(int i) {
// Proceed with negative values, they have more range than + side
int r = reverse_recurse(i > 0 ? -i : i, 0);
if (r > 0) {
return 0;
}
if (i > 0) {
if (r < -INT_MAX) {
return 0;
}
r = -r;
}
return r;
}
测试
int main(void) {
int t[] = {0, 1, 42, 1234567890, 1234567892, INT_MAX, INT_MIN};
for (unsigned i = 0; i < sizeof t / sizeof t[0]; i++) {
printf("%11d %11d\n", t[i], reverse_int(t[i]));
if (t[i] != INT_MIN) {
printf("%11d %11d\n", -t[i], reverse_int(-t[i]));
}
}
}
输出
0 0
0 0
1 1
-1 -1
42 24
-42 -24
1234567890 987654321
-1234567890 -987654321
1234567892 0
-1234567892 0
2147483647 0
-2147483647 0
-2147483648 0
In trying to learn C programming I programed this question and get some correct results and some incorrect. I don't see the reason for the difference.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h> // requires adding link to math -lm as in: gcc b.c -lm -o q11
int ReverseInt(int startValue, int decimalPlace)
{
if(decimalPlace == 0) // if done returns value
{
return startValue;
}
int temp = startValue % 10; // gets units digit
int newStart = (startValue -temp)/10; // computes new starting value after removing one digit
int newDecimal = decimalPlace -1;
int value = temp*pow(10,decimalPlace);
return value + ReverseInt(newStart,newDecimal); // calls itself recursively until done
}
int main()
{
int x, decimalP, startValue;
printf("Input number to be reversed \n Please note number must be less than 214748364 :");
scanf("%d", &x);
if (x > 214748364)
{
printf("Input number to be reversed \n Please note number must be less than 214748364 :");
scanf("%d", &x);
}
decimalP = round(log10(x)); // computes the number of powers of 10 - 0 being units etc.
startValue = ReverseInt(x, decimalP); // calls function with number to be reversed and powers of 10
printf("\n reverse of %d is %d \n", x, startValue);
}
Output is: reverse of 1234 is 4321 but then reverse of 4321 is 12340
您可以添加第二个参数：
int reverseRec(int x, int reversed)
{
if(x == 0)
{
return reversed;
}
else
{
return reverseRec(x/10, reversed * 10 + x%10);
}
}
并调用传递 0 作为第二个参数的函数。如果你想要负数，你可以检查之前的符号并将绝对值传递给这个函数。
问题陈述：
Given a 32-bit signed integer, reverse digits of an integer.
Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [ −2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
我正在尝试实现递归函数 reverseRec()，它适用于较小的值，但对于边缘情况来说是一团糟。
int reverseRec(int x)
{
if(abs(x)<=9)
{
return x;
}
else
{
return reverseRec(x/10) + ((x%10)*(pow(10, (floor(log10(abs(x)))))));
}
}
我已经实现了工作正常的非递归函数:
int reverse(int x)
{
long long val = 0;
do{
val = val*10 + (x%10);
x /= 10;
}while(x);
return (val < INT_MIN || val > INT_MAX) ? 0 : val;
}
这里我使用long long类型的变量val来检查MAX和MIN[=28的结果=] signed int type 但是问题的描述中特别提到我们需要在32位整数范围内处理，虽然不知何故它被接受了但我只是好奇 如果有办法仅使用 int 数据类型实现递归函数 ?
还有一件事，即使我考虑使用 long long，我也无法在递归函数 reverseRec() 中实现它。
我假设通过反转整数你的意思是将 129 变成 921 或者 120 变成 21。
您需要一个初始化方法来初始化您的递归函数。 您的递归函数必须计算出您的整数使用了多少位小数。这可以通过对值使用以 10 为底的对数然后将结果转换为整数来找到。
- log10 (103) 大约。 2.04 => 2
将初始值乘以 10 得到个位并将其存储在名为 temp 的变量中 从初始值中减去个位并将其存储在名为 newStart 的变量中。
- 将此值除以 10
从小数位减一并存储在另一个名为 newDecimal 的变量中。
Return个位乘以10的小数次方，加入函数中，初值为newStart，decimalPlace为newDecimal
#include <stdio.h>
#include <math.h>
int ReverseInt(int startValue, int decimalPlace);
int main()
{
int i = -54;
int positive = i < 0? i*-1 : i;
double d = log10(positive);
int output = ReverseInt(positive,(int)d);
int correctedOutput = i < 0? output*-1 : output;
printf("%d \n",correctedOutput);
return 0;
}
int ReverseInt(int startValue, int decimalPlace)
{
if(decimalPlace == 0)
{
return startValue;
}
int temp = startValue % 10;
int newStart = (startValue -temp)/10;
int newDecimal = decimalPlace -1;
int value = temp*pow(10,decimalPlace);
return value + ReverseInt(newStart,newDecimal);
}
很晚了，我没有想到更好的了。没有浮动计算。当然，整数必须足够大以容纳结果。否则就是UB。
int rev(int x, int partial, int *max)
{
int result;
if(x / partial < 10 && (int)(x / partial) > -10)
{
*max = partial;
return abs(x % 10) * partial;
}
result = rev(x, partial * 10, max) + abs(((x / (int)(*max / partial)) % 10) * partial);
return result;
}
int reverse(int x)
{
int max;
return rev(x, 1, &max) * ((x < 0) ? -1 : 1);
}
int main(void){
printf("%d", reverse(-456789));
}
unsigned rev(unsigned x, unsigned partial, unsigned *max)
{
unsigned result;
if(x / partial < 10)
{
*max = partial;
return (x % 10) * partial;
}
result = rev(x, partial * 10, max) + (x / (*max / partial) % 10) * partial;
return result;
}
unsigned reverse(unsigned x)
{
unsigned max;
return rev(x, 1, &max);
}
int main(void){
printf("%u", reverse(123456));
}
当使用 long long 存储结果时，所有可能的整数都可以反转
long long rev(int x, long long partial, long long *max)
{
long long result;
if(x / partial < 10 && (int)(x / partial) > -10)
{
*max = partial;
return abs(x % 10) * partial;
}
result = rev(x, partial * 10, max) + abs(((x / (int)(*max / partial)) % 10) * partial);
return result;
}
long long reverse(int x)
{
long long max;
return rev(x, 1, &max) * ((x < 0) ? -1 : 1);
}
int main(void){
printf("%d reversed %lld\n", INT_MIN, reverse(INT_MIN));
printf("%d reversed %lld\n", INT_MAX, reverse(INT_MAX));
}
If there is a way to implement a recursive function using only
intdatatype ?
(and) returns 0 when the reversed integer overflows
是的。
对于此类 +/- 问题，我喜欢将 int 值折叠到一侧并根据需要取反。折叠到一侧（- 或 +）简化了溢出检测，因为只有一侧需要测试
我更喜欢弃牌到负面，因为负面多于正面。 （对于 32 位 int，这个问题确实没有任何区别。）
由于代码形成反转值，在执行之前测试以下r * 10 + least_digit是否可能溢出
一个int唯一的递归解决方案来反转int。溢出 returns 0.
#include <limits.h>
#include <stdio.h>
static int reverse_recurse(int i, int r) {
if (i) {
int least_digit = i % 10;
if (r <= INT_MIN / 10 && (r < INT_MIN / 10 || least_digit < INT_MIN % 10)) {
return 1; /// Overflow indication
}
r = reverse_recurse(i / 10, r * 10 + least_digit);
}
return r;
}
// Reverse an int, overflow returns 0
int reverse_int(int i) {
// Proceed with negative values, they have more range than + side
int r = reverse_recurse(i > 0 ? -i : i, 0);
if (r > 0) {
return 0;
}
if (i > 0) {
if (r < -INT_MAX) {
return 0;
}
r = -r;
}
return r;
}
测试
int main(void) {
int t[] = {0, 1, 42, 1234567890, 1234567892, INT_MAX, INT_MIN};
for (unsigned i = 0; i < sizeof t / sizeof t[0]; i++) {
printf("%11d %11d\n", t[i], reverse_int(t[i]));
if (t[i] != INT_MIN) {
printf("%11d %11d\n", -t[i], reverse_int(-t[i]));
}
}
}
输出
0 0
0 0
1 1
-1 -1
42 24
-42 -24
1234567890 987654321
-1234567890 -987654321
1234567892 0
-1234567892 0
2147483647 0
-2147483647 0
-2147483648 0
In trying to learn C programming I programed this question and get some correct results and some incorrect. I don't see the reason for the difference.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h> // requires adding link to math -lm as in: gcc b.c -lm -o q11
int ReverseInt(int startValue, int decimalPlace)
{
if(decimalPlace == 0) // if done returns value
{
return startValue;
}
int temp = startValue % 10; // gets units digit
int newStart = (startValue -temp)/10; // computes new starting value after removing one digit
int newDecimal = decimalPlace -1;
int value = temp*pow(10,decimalPlace);
return value + ReverseInt(newStart,newDecimal); // calls itself recursively until done
}
int main()
{
int x, decimalP, startValue;
printf("Input number to be reversed \n Please note number must be less than 214748364 :");
scanf("%d", &x);
if (x > 214748364)
{
printf("Input number to be reversed \n Please note number must be less than 214748364 :");
scanf("%d", &x);
}
decimalP = round(log10(x)); // computes the number of powers of 10 - 0 being units etc.
startValue = ReverseInt(x, decimalP); // calls function with number to be reversed and powers of 10
printf("\n reverse of %d is %d \n", x, startValue);
}
Output is: reverse of 1234 is 4321 but then reverse of 4321 is 12340
您可以添加第二个参数：
int reverseRec(int x, int reversed)
{
if(x == 0)
{
return reversed;
}
else
{
return reverseRec(x/10, reversed * 10 + x%10);
}
}
并调用传递 0 作为第二个参数的函数。如果你想要负数，你可以检查之前的符号并将绝对值传递给这个函数。