将输入读入动态大小的 int?
Read input into a dynamic sized int?
我需要从标准输入中读取大量数据,这是我目前的代码:
int main() {
int x;
int* n1;
scanf("%d", &x); // I get the number of digits the integer will have
n1 = malloc(x * sizeof(int)); // I resize the integer pointer
}
所以我的问题是如何从标准输入中读取这个可能很大的整数?
int x;
int* n1;
int i;
scanf("%d", &x);
n1 = malloc(x * sizeof(int));
for(i = 0; i < x; ++i){
scanf("%1d", &n1[i]);//Read (unsigned) one digit
}
for(i = 0; i < x; ++i){
printf("%d", n1[i]);
}
puts("");
按照您现在的设计方式,您将有一个指向 int
的指针,换句话说:一个整数数组。可以存储数字的最大整数类型是 long long
(其大小取决于机器,在 64 位机器上通常为 8 个字节)。
您还可以考虑将数字存储在字符串中(在分配 char*
之后),或者如您所写,存储在 int
的数组中,其中每个数组元素将持有任意数量的数字(然后我建议使用 getchar()
和 atoi()
函数而不是 scanf()
)。
C 中没有 "dynamic sized int" 这样的东西。正如其他人所建议的,根据您的用例,您可能需要将数字读取为字符串。 (如果为此使用 scanf
,请注意缓冲区溢出。)
如果您需要对数字进行算术运算,您可能希望使用现有的库,例如 libgmp,以便从现有的问题解决方案中获益。您也可以自己重新实现 libgmp 的功能,但除非您将此作为学习练习,否则没有理由这样做。
处理非常大的数字的最可靠方法是使用 'bignum.c',可在以下位置找到:http://www3.cs.stonybrook.edu/~skiena/392/programs/bignum.c
引用的代码是一个完整的程序,。但是函数和结构可以免费使用。
你会在那里找到什么:
/* bignum.c
Implementation of large integer arithmetic: addition, subtraction,
multiplication, and division.
begun: February 7, 2002
by: Steven Skiena
*/
/*
Copyright 2003 by Steven S. Skiena; all rights reserved.
Permission is granted for use in non-commerical applications
provided this copyright notice remains intact and unchanged.
This program appears in my book:
"Programming Challenges: The Programming Contest Training Manual"
by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003.
See our website www.programming-challenges.com for additional information.
This book can be ordered from Amazon.com at
http://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/
*/
#include <stdio.h>
#define MAXDIGITS 100 /* maximum length bignum */
#define PLUS 1 /* positive sign bit */
#define MINUS -1 /* negative sign bit */
typedef struct {
char digits[MAXDIGITS]; /* represent the number */
int signbit; /* 1 if positive, -1 if negative */
int lastdigit; /* index of high-order digit */
} bignum;
print_bignum(bignum *n)
{
int i;
if (n->signbit == MINUS) printf("- ");
for (i=n->lastdigit; i>=0; i--)
printf("%c",'0'+ n->digits[i]);
printf("\n");
}
int_to_bignum(int s, bignum *n)
{
int i; /* counter */
int t; /* int to work with */
if (s >= 0) n->signbit = PLUS;
else n->signbit = MINUS;
for (i=0; i<MAXDIGITS; i++) n->digits[i] = (char) 0;
n->lastdigit = -1;
t = abs(s);
while (t > 0) {
n->lastdigit ++;
n->digits[ n->lastdigit ] = (t % 10);
t = t / 10;
}
if (s == 0) n->lastdigit = 0;
}
initialize_bignum(bignum *n)
{
int_to_bignum(0,n);
}
int max(int a, int b)
{
if (a > b) return(a); else return(b);
}
/* c = a +-/* b; */
add_bignum(bignum *a, bignum *b, bignum *c)
{
int carry; /* carry digit */
int i; /* counter */
initialize_bignum(c);
if (a->signbit == b->signbit) c->signbit = a->signbit;
else {
if (a->signbit == MINUS) {
a->signbit = PLUS;
subtract_bignum(b,a,c);
a->signbit = MINUS;
} else {
b->signbit = PLUS;
subtract_bignum(a,b,c);
b->signbit = MINUS;
}
return;
}
c->lastdigit = max(a->lastdigit,b->lastdigit)+1;
carry = 0;
for (i=0; i<=(c->lastdigit); i++) {
c->digits[i] = (char) (carry+a->digits[i]+b->digits[i]) % 10;
carry = (carry + a->digits[i] + b->digits[i]) / 10;
}
zero_justify(c);
}
subtract_bignum(bignum *a, bignum *b, bignum *c)
{
int borrow; /* has anything been borrowed? */
int v; /* placeholder digit */
int i; /* counter */
initialize_bignum(c);
if ((a->signbit == MINUS) || (b->signbit == MINUS)) {
b->signbit = -1 * b->signbit;
add_bignum(a,b,c);
b->signbit = -1 * b->signbit;
return;
}
if (compare_bignum(a,b) == PLUS) {
subtract_bignum(b,a,c);
c->signbit = MINUS;
return;
}
c->lastdigit = max(a->lastdigit,b->lastdigit);
borrow = 0;
for (i=0; i<=(c->lastdigit); i++) {
v = (a->digits[i] - borrow - b->digits[i]);
if (a->digits[i] > 0)
borrow = 0;
if (v < 0) {
v = v + 10;
borrow = 1;
}
c->digits[i] = (char) v % 10;
}
zero_justify(c);
}
compare_bignum(bignum *a, bignum *b)
{
int i; /* counter */
if ((a->signbit == MINUS) && (b->signbit == PLUS)) return(PLUS);
if ((a->signbit == PLUS) && (b->signbit == MINUS)) return(MINUS);
if (b->lastdigit > a->lastdigit) return (PLUS * a->signbit);
if (a->lastdigit > b->lastdigit) return (MINUS * a->signbit);
for (i = a->lastdigit; i>=0; i--) {
if (a->digits[i] > b->digits[i]) return(MINUS * a->signbit);
if (b->digits[i] > a->digits[i]) return(PLUS * a->signbit);
}
return(0);
}
zero_justify(bignum *n)
{
while ((n->lastdigit > 0) && (n->digits[ n->lastdigit ] == 0))
n->lastdigit --;
if ((n->lastdigit == 0) && (n->digits[0] == 0))
n->signbit = PLUS; /* hack to avoid -0 */
}
digit_shift(bignum *n, int d) /* multiply n by 10^d */
{
int i; /* counter */
if ((n->lastdigit == 0) && (n->digits[0] == 0)) return;
for (i=n->lastdigit; i>=0; i--)
n->digits[i+d] = n->digits[i];
for (i=0; i<d; i++) n->digits[i] = 0;
n->lastdigit = n->lastdigit + d;
}
multiply_bignum(bignum *a, bignum *b, bignum *c)
{
bignum row; /* represent shifted row */
bignum tmp; /* placeholder bignum */
int i,j; /* counters */
initialize_bignum(c);
row = *a;
for (i=0; i<=b->lastdigit; i++) {
for (j=1; j<=b->digits[i]; j++) {
add_bignum(c,&row,&tmp);
*c = tmp;
}
digit_shift(&row,1);
}
c->signbit = a->signbit * b->signbit;
zero_justify(c);
}
divide_bignum(bignum *a, bignum *b, bignum *c)
{
bignum row; /* represent shifted row */
bignum tmp; /* placeholder bignum */
int asign, bsign; /* temporary signs */
int i,j; /* counters */
initialize_bignum(c);
c->signbit = a->signbit * b->signbit;
asign = a->signbit;
bsign = b->signbit;
a->signbit = PLUS;
b->signbit = PLUS;
initialize_bignum(&row);
initialize_bignum(&tmp);
c->lastdigit = a->lastdigit;
for (i=a->lastdigit; i>=0; i--) {
digit_shift(&row,1);
row.digits[0] = a->digits[i];
c->digits[i] = 0;
while (compare_bignum(&row,b) != PLUS) {
c->digits[i] ++;
subtract_bignum(&row,b,&tmp);
row = tmp;
}
}
zero_justify(c);
a->signbit = asign;
b->signbit = bsign;
}
main()
{
int a,b;
bignum n1,n2,n3,zero;
while (scanf("%d %d\n",&a,&b) != EOF) {
printf("a = %d b = %d\n",a,b);
int_to_bignum(a,&n1);
int_to_bignum(b,&n2);
add_bignum(&n1,&n2,&n3);
printf("addition -- ");
print_bignum(&n3);
printf("compare_bignum a ? b = %d\n",compare_bignum(&n1, &n2));
subtract_bignum(&n1,&n2,&n3);
printf("subtraction -- ");
print_bignum(&n3);
multiply_bignum(&n1,&n2,&n3);
printf("multiplication -- ");
print_bignum(&n3);
int_to_bignum(0,&zero);
if (compare_bignum(&zero, &n2) == 0)
printf("division -- NaN \n");
else {
divide_bignum(&n1,&n2,&n3);
printf("division -- ");
print_bignum(&n3);
}
printf("--------------------------\n");
}
}
我需要从标准输入中读取大量数据,这是我目前的代码:
int main() {
int x;
int* n1;
scanf("%d", &x); // I get the number of digits the integer will have
n1 = malloc(x * sizeof(int)); // I resize the integer pointer
}
所以我的问题是如何从标准输入中读取这个可能很大的整数?
int x;
int* n1;
int i;
scanf("%d", &x);
n1 = malloc(x * sizeof(int));
for(i = 0; i < x; ++i){
scanf("%1d", &n1[i]);//Read (unsigned) one digit
}
for(i = 0; i < x; ++i){
printf("%d", n1[i]);
}
puts("");
按照您现在的设计方式,您将有一个指向 int
的指针,换句话说:一个整数数组。可以存储数字的最大整数类型是 long long
(其大小取决于机器,在 64 位机器上通常为 8 个字节)。
您还可以考虑将数字存储在字符串中(在分配 char*
之后),或者如您所写,存储在 int
的数组中,其中每个数组元素将持有任意数量的数字(然后我建议使用 getchar()
和 atoi()
函数而不是 scanf()
)。
C 中没有 "dynamic sized int" 这样的东西。正如其他人所建议的,根据您的用例,您可能需要将数字读取为字符串。 (如果为此使用 scanf
,请注意缓冲区溢出。)
如果您需要对数字进行算术运算,您可能希望使用现有的库,例如 libgmp,以便从现有的问题解决方案中获益。您也可以自己重新实现 libgmp 的功能,但除非您将此作为学习练习,否则没有理由这样做。
处理非常大的数字的最可靠方法是使用 'bignum.c',可在以下位置找到:http://www3.cs.stonybrook.edu/~skiena/392/programs/bignum.c
引用的代码是一个完整的程序,。但是函数和结构可以免费使用。
你会在那里找到什么:
/* bignum.c
Implementation of large integer arithmetic: addition, subtraction,
multiplication, and division.
begun: February 7, 2002
by: Steven Skiena
*/
/*
Copyright 2003 by Steven S. Skiena; all rights reserved.
Permission is granted for use in non-commerical applications
provided this copyright notice remains intact and unchanged.
This program appears in my book:
"Programming Challenges: The Programming Contest Training Manual"
by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003.
See our website www.programming-challenges.com for additional information.
This book can be ordered from Amazon.com at
http://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/
*/
#include <stdio.h>
#define MAXDIGITS 100 /* maximum length bignum */
#define PLUS 1 /* positive sign bit */
#define MINUS -1 /* negative sign bit */
typedef struct {
char digits[MAXDIGITS]; /* represent the number */
int signbit; /* 1 if positive, -1 if negative */
int lastdigit; /* index of high-order digit */
} bignum;
print_bignum(bignum *n)
{
int i;
if (n->signbit == MINUS) printf("- ");
for (i=n->lastdigit; i>=0; i--)
printf("%c",'0'+ n->digits[i]);
printf("\n");
}
int_to_bignum(int s, bignum *n)
{
int i; /* counter */
int t; /* int to work with */
if (s >= 0) n->signbit = PLUS;
else n->signbit = MINUS;
for (i=0; i<MAXDIGITS; i++) n->digits[i] = (char) 0;
n->lastdigit = -1;
t = abs(s);
while (t > 0) {
n->lastdigit ++;
n->digits[ n->lastdigit ] = (t % 10);
t = t / 10;
}
if (s == 0) n->lastdigit = 0;
}
initialize_bignum(bignum *n)
{
int_to_bignum(0,n);
}
int max(int a, int b)
{
if (a > b) return(a); else return(b);
}
/* c = a +-/* b; */
add_bignum(bignum *a, bignum *b, bignum *c)
{
int carry; /* carry digit */
int i; /* counter */
initialize_bignum(c);
if (a->signbit == b->signbit) c->signbit = a->signbit;
else {
if (a->signbit == MINUS) {
a->signbit = PLUS;
subtract_bignum(b,a,c);
a->signbit = MINUS;
} else {
b->signbit = PLUS;
subtract_bignum(a,b,c);
b->signbit = MINUS;
}
return;
}
c->lastdigit = max(a->lastdigit,b->lastdigit)+1;
carry = 0;
for (i=0; i<=(c->lastdigit); i++) {
c->digits[i] = (char) (carry+a->digits[i]+b->digits[i]) % 10;
carry = (carry + a->digits[i] + b->digits[i]) / 10;
}
zero_justify(c);
}
subtract_bignum(bignum *a, bignum *b, bignum *c)
{
int borrow; /* has anything been borrowed? */
int v; /* placeholder digit */
int i; /* counter */
initialize_bignum(c);
if ((a->signbit == MINUS) || (b->signbit == MINUS)) {
b->signbit = -1 * b->signbit;
add_bignum(a,b,c);
b->signbit = -1 * b->signbit;
return;
}
if (compare_bignum(a,b) == PLUS) {
subtract_bignum(b,a,c);
c->signbit = MINUS;
return;
}
c->lastdigit = max(a->lastdigit,b->lastdigit);
borrow = 0;
for (i=0; i<=(c->lastdigit); i++) {
v = (a->digits[i] - borrow - b->digits[i]);
if (a->digits[i] > 0)
borrow = 0;
if (v < 0) {
v = v + 10;
borrow = 1;
}
c->digits[i] = (char) v % 10;
}
zero_justify(c);
}
compare_bignum(bignum *a, bignum *b)
{
int i; /* counter */
if ((a->signbit == MINUS) && (b->signbit == PLUS)) return(PLUS);
if ((a->signbit == PLUS) && (b->signbit == MINUS)) return(MINUS);
if (b->lastdigit > a->lastdigit) return (PLUS * a->signbit);
if (a->lastdigit > b->lastdigit) return (MINUS * a->signbit);
for (i = a->lastdigit; i>=0; i--) {
if (a->digits[i] > b->digits[i]) return(MINUS * a->signbit);
if (b->digits[i] > a->digits[i]) return(PLUS * a->signbit);
}
return(0);
}
zero_justify(bignum *n)
{
while ((n->lastdigit > 0) && (n->digits[ n->lastdigit ] == 0))
n->lastdigit --;
if ((n->lastdigit == 0) && (n->digits[0] == 0))
n->signbit = PLUS; /* hack to avoid -0 */
}
digit_shift(bignum *n, int d) /* multiply n by 10^d */
{
int i; /* counter */
if ((n->lastdigit == 0) && (n->digits[0] == 0)) return;
for (i=n->lastdigit; i>=0; i--)
n->digits[i+d] = n->digits[i];
for (i=0; i<d; i++) n->digits[i] = 0;
n->lastdigit = n->lastdigit + d;
}
multiply_bignum(bignum *a, bignum *b, bignum *c)
{
bignum row; /* represent shifted row */
bignum tmp; /* placeholder bignum */
int i,j; /* counters */
initialize_bignum(c);
row = *a;
for (i=0; i<=b->lastdigit; i++) {
for (j=1; j<=b->digits[i]; j++) {
add_bignum(c,&row,&tmp);
*c = tmp;
}
digit_shift(&row,1);
}
c->signbit = a->signbit * b->signbit;
zero_justify(c);
}
divide_bignum(bignum *a, bignum *b, bignum *c)
{
bignum row; /* represent shifted row */
bignum tmp; /* placeholder bignum */
int asign, bsign; /* temporary signs */
int i,j; /* counters */
initialize_bignum(c);
c->signbit = a->signbit * b->signbit;
asign = a->signbit;
bsign = b->signbit;
a->signbit = PLUS;
b->signbit = PLUS;
initialize_bignum(&row);
initialize_bignum(&tmp);
c->lastdigit = a->lastdigit;
for (i=a->lastdigit; i>=0; i--) {
digit_shift(&row,1);
row.digits[0] = a->digits[i];
c->digits[i] = 0;
while (compare_bignum(&row,b) != PLUS) {
c->digits[i] ++;
subtract_bignum(&row,b,&tmp);
row = tmp;
}
}
zero_justify(c);
a->signbit = asign;
b->signbit = bsign;
}
main()
{
int a,b;
bignum n1,n2,n3,zero;
while (scanf("%d %d\n",&a,&b) != EOF) {
printf("a = %d b = %d\n",a,b);
int_to_bignum(a,&n1);
int_to_bignum(b,&n2);
add_bignum(&n1,&n2,&n3);
printf("addition -- ");
print_bignum(&n3);
printf("compare_bignum a ? b = %d\n",compare_bignum(&n1, &n2));
subtract_bignum(&n1,&n2,&n3);
printf("subtraction -- ");
print_bignum(&n3);
multiply_bignum(&n1,&n2,&n3);
printf("multiplication -- ");
print_bignum(&n3);
int_to_bignum(0,&zero);
if (compare_bignum(&zero, &n2) == 0)
printf("division -- NaN \n");
else {
divide_bignum(&n1,&n2,&n3);
printf("division -- ");
print_bignum(&n3);
}
printf("--------------------------\n");
}
}