- it
- OpenJudge 数据结构与算法MOOC第二章 线性表 练习题：放苹果、大整数乘法
放苹果
放苹果
我的解答
#include <iostream>
using namespace std
;
int t
;
int M
, N
;
int F(int M
, int N
) {
if (M
< N
|| !N
)
return 0;
else if (M
== N
)
return 1;
else
return F(M
-1, N
-1) + F(M
-N
, N
);
}
int main() {
cin
>> t
;
for (int i
= 0; i
< t
; ++i
) {
cin
>> M
>> N
;
cout
<< F(M
+N
, N
) << endl
;
}
return 0;
}
大整数乘法
大整数乘法
我的解答
#include <iostream>
#include <cstring>
using namespace std
;
char a
[210], b
[210];
void reverse(char * arr
){
int tmp
= strlen(arr
);
for (int i
= 0; i
< tmp
/2; ++i
) {
int tmp2
= arr
[i
];
arr
[i
] = arr
[tmp
-1-i
];
arr
[tmp
-1-i
] = tmp2
;
}
};
void multiply(char * x
, char * y
) {
int lx
= strlen(x
);
int ly
= strlen(y
);
int count
= lx
+ly
+1;
int mid
[count
];
for (int k
= 0; k
< count
; ++k
) {
mid
[k
] = 0;
}
reverse(x
); reverse(y
);
for (int i
= 0; i
< lx
; ++i
) {
for (int j
= 0; j
< ly
; ++j
) {
int tmp
= (x
[i
] - '0') * (y
[j
] - '0');
mid
[i
+j
] += tmp
;
}
}
for (int l
= 0; l
< lx
+ly
; ++l
) {
if (mid
[l
] > 9) {
mid
[l
+1] += mid
[l
]/10;
mid
[l
] %= 10;
}
}
while (mid
[count
-1] == 0)
--count
;
for (int m
= count
-1; m
>= 0; --m
) {
cout
<< mid
[m
];
}
cout
<< endl
;
}
int main() {
memset(a
, 0, sizeof(a
));
memset(b
, 0, sizeof(b
));
cin
>> a
;
cin
>> b
;
multiply(a
, b
);
}
