[编程题]A+B and C (64bit) (20)
- 热度指数：6991 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
Given three integers A, B and C in [-263
, 263
), you are supposed to tell whether A+B > C.
输入描述:
The first line of the input gives the positive number of test cases, T (<=1000). Then T test cases follow, each consists of a single line containing three integers A, B and C, separated by single spaces.
输出描述:
For each test case, output in one line "Case #X: true" if A+B>C, or "Case #X: false" otherwise, where X is the case number (starting from 1).
示例1
输入
3 1 2 3 2 3 4 9223372036854775807 -9223372036854775808 0
输出
Case #1: false Case #2: true Case #3: false
md!!!只有我是自己实现string型的加减法和大小比较的吗
#include<bits/stdc++.h>
using namespace std;
int AcompairB(string a, string b){//a大1,b大-1,等0
int al = a.size();
int bl = b.size();
if (a[0] == '-'&&b[0] != '-'){
return -1;
}
if (a[0] != '-'&&b[0] == '-'){
return 1;
}
if (a[0] != '-'&&b[0] != '-'){
if (al>bl)return 1;
if (al<bl)return -1;
if (al == bl){
for (int i = 0; i<al; i++){
if (a[i] - b[i]>0)return 1;
if (a[i] - b[i]<0)return -1;
}
return 0;
}
}
if (a[0] == '-'&&b[0] == '-'){
if (al>bl)return -1;
if (al<bl)return 1;
if (al == bl){
for (int i = 0; i<al; i++){
if (a[i] - b[i]>0)return -1;
if (a[i] - b[i]<0)return 1;
}
return 0;
}
}
return -10;
}
string MyAdd(string a, string b){
int cp = AcompairB(a, b);
string s1, s2;//s1大
if (cp == 1){
s1 = a;
s2 = b;
}
else if (cp == -1){
s1 = b;
s2 = a;
}
else{
s1 = a;
s2 = b;
}
//都正
int s1Size = s1.size();
int s2Size = s2.size();
int p = 1;
int bef = 0;
while (p <= s2Size){
int c = s1[s1Size - p] + s2[s2Size - p] + bef - '0' - '0';
bef = 0;
if (c>=10){
bef = 1;
c -= 10;
}
s1[s1Size - p] = c + '0';
p++;
}
while (bef != 0 && p <= s1Size){
int c = s1[s1Size - p] + bef - '0';
bef = 0;
if (c>=10){
bef = 1;
c -= 10;
}
s1[s1Size - p] = c + '0';
p++;
}
if (bef != 0){
s1 = '1' + s1;
}
return s1;
}
string myMinus(string a, string b, bool &isNeg){
int cp = AcompairB(a, b);
string s1, s2;//s1大
if (cp == 1){
s1 = a;
s2 = b;
isNeg = false;
}
else if (cp == -1){
s1 = b;
s2 = a;
isNeg = true;
}
else{
return "0";
}
int s1Size = s1.size();
int s2Size = s2.size();
int p = 1;
int bef = 0;
while (p <= s2Size){
int c = s1[s1Size - p] - s2[s2Size - p] + bef /*- '0' - '0'*/;//哇这里不用-'0'前面消去了
bef = 0;
if (c<0){
bef = -1;
c += 10;
}
s1[s1Size - p] = c + '0';
p++;
}
while (bef != 0 && p <= s1Size){
int c = s1[s1Size - p] + bef - '0';
bef = 0;
if (c<0){
bef = -1;
c += 10;
}
s1[s1Size - p] = c + '0';
p++;
}
if (bef != 0){
s1[0] = s1[0] - 1;
}
int q = 0;
while (s1[q] == '0'){
q++;
}
string res = s1.substr(q);
return res;
}
int main(){
int N;
cin >> N;
vector<int> res;
while (N--){
string A, B, C;
cin >> A >> B >> C;
string AB;
if (A[0] == '-'&&B[0] == '-'){
AB = '-' + MyAdd(A.substr(1), B.substr(1));
}
else if (A[0] != '-'&&B[0] != '-'){
AB = MyAdd(A, B);
}
else if (A[0] != '-'&&B[0] == '-'){
bool isNeg;
AB = myMinus(A, B.substr(1), isNeg);
if (isNeg)AB = '-' + AB;
}
else if (A[0] == '-'&&B[0] != '-'){
bool isNeg;
AB = myMinus(B, A.substr(1), isNeg);
if (isNeg)AB = '-' + AB;
}
res.push_back(AcompairB(AB, C));
}
for (int i = 1; i <= res.size(); i++){
if (res[i-1] == 1){
printf("Case #%d: true\n",i);
}
else{
printf("Case #%d: false\n", i);
}
}
return 0;
}
发表于 2017-07-12 13:31:54
回复(7)
import java.math.BigInteger;
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner in =new Scanner(System.in);
int n=in.nextInt();
for(int i=0;i<n;i++){
BigInteger a=in.nextBigInteger();
BigInteger b=in.nextBigInteger();
BigInteger c=in.nextBigInteger();
if(a.add(b).compareTo(c)>0){
System.out.println("Case #"+(i+1)+": true");
}else
System.out.println("Case #"+(i+1)+": false");
}
}
}
发表于 2018-10-03 20:06:34
回复(0)
//long double水过，注意scanf如何输入的。
//当然cin就不用管了，另外python和java自带大数就更不用说了。(编程语言带来的差异呀。。。
#include <bits/stdc++.h>
using namespace std;
long double A,B,C;
int T,kase;
int main(){
scanf("%d",&T);
while(T--){
scanf("%Lf %Lf %Lf",&A,&B,&C);
if(A+B>C) printf("Case #%d: true\n",++kase);
else printf("Case #%d: false\n",++kase);
}
return 0;
}
发表于 2018-03-05 16:20:31
回复(0)
做了个大数类
#include<iostream>
#include<ctype.h>
using namespace std;
struct bigint{
int digit[1001],tag;
void read(){
int i,j;
char c;
while(!isdigit(c=getchar())&&c!='-');
if(c=='-'){
this->tag=1;
c=getchar();
}
else this->tag=0;//看符号
while(c=='0')c=getchar();//去零
for(i=1000;isdigit(c);c=getchar()){
this->digit[--i]=c-'0';
}
for(j=0;j<1000-i;j++){
this->digit[j]=this->digit[j+i];
}
if(!j)this->tag=0;
while(j<1001)this->digit[j++]=0;//把数字写完，填好0
}
bigint operator+(bigint&m){
int a[1001],b[1001],c[1001],i,j;
bigint n;
if(this->tag){
for(i=0;i<1001&&!this->digit[i];i++)a[i]=0;
if(i<1001){
a[i]=10-this->digit[i];
while(++i<1001)a[i]=9-this->digit[i];
}
}
else{
for(i=0;i<1001;i++)a[i]=this->digit[i];
}
if(m.tag){
for(i=0;i<1001&&!m.digit[i];i++)b[i]=0;
if(i<1001){
b[i]=10-m.digit[i];
while(++i<1001)b[i]=9-m.digit[i];
}
}
else{
for(i=0;i<1001;i++)b[i]=m.digit[i];
}
for(i=j=0;i<1001;i++){
c[i]=a[i]+b[i]+j;
if(c[i]>9){
c[i]-=10;
j=1;
}
else j=0;
}
if(!c[1000]){
n.tag=0;
for(i=0;i<1001;i++)n.digit[i]=c[i];
}
else{
n.tag=1;
for(i=0;!c[i];i++)n.digit[i]=0;
n.digit[i]=10-c[i];
while(++i<1001)n.digit[i]=9-c[i];
}
return n;
}
bool operator>(bigint&m){
int i;
if(this->tag!=m.tag)return this->tag<m.tag;
for(i=1000;i>=0&&this->digit[i]==m.digit[i];i--);
if(i<0)return false;
return this->tag?this->digit[i]<m.digit[i]:this->digit[i]>m.digit[i];
}
};
int N;
bigint A,B,C,sum;
int main()
{
cin>>N;
for(int i=1;i<=N;i++){
A.read();
B.read();
C.read();
sum=A+B;
cout<<"Case #"<<i<<": ";
if(sum>C)cout<<"true\n";
else cout<<"false\n";
}
}
发表于 2020-02-09 19:58:16
回复(0)
#include <iostream>
using namespace std;
int main()
{ int T; cin>>T; for(int i=1;i<=T;i++) { long long a,b,c,ans; bool flag = false; cin>>a>>b>>c; ans = a + b; if(a<0 && b<0 && ans>=0) flag = false; else if(a>0 && b>0 && ans<=0) flag = true; else flag = (ans > c); cout<<"Case #"<<i<<": "<<(flag?"true":"false")<<endl; } return 0;
}
发表于 2018-03-08 00:38:35
回复(0)
import java.math.BigInteger;
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
for(int i=1;i<=n;i++){
BigInteger bi1=new BigInteger(in.next());
BigInteger bi2=new BigInteger(in.next());
BigInteger bi3=new BigInteger(in.next());
System.out.print("Case #"+i+": ");
if(bi1.add(bi2).compareTo(bi3)>0){
System.out.println("true");
}else{
System.out.println("false");
}
}
}
}
发表于 2017-01-22 14:13:15
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for(int i = 1;i<=n;i++){
String a = in.next();
String b = in.next();
String c = in.next();
String result = add(a, b);
if(result.charAt(0)=='-'&&c.charAt(0)=='-')
System.out.printf("Case #%d: %b\n",i, compareNegative(result, c));
else if(result.charAt(0)=='-')
System.out.printf("Case #%d: false\n",i);
else if(c.charAt(0)=='-')
System.out.printf("Case #%d: true\n",i);
else
System.out.printf("Case #%d: %b\n",i,
result.length()==c.length()?
result.compareTo(c)>0:
result.length()>c.length());
}
}
private static String add(String a,String b){
int aStart = 0;
int bStart = 0;
if(a.charAt(0)=='-'&&b.charAt(0)=='-'){
aStart = 1;
bStart = 1;
}else if(a.charAt(0)=='-')
return sub(b, a.substring(1));
else if(b.charAt(0)=='-')
return sub(a, b.substring(1));
char[] result = new char[Math.max(a.length()-aStart, b.length()-bStart)+1];
int i = a.length()-1;
int j = b.length()-1;
int k = result.length-1;
int f = 0;//进位
while(i>=aStart||j>=bStart){
int aval = i >= aStart ? a.charAt(i--) - '0' : 0;
int bval = j >= bStart ? b.charAt(j--) - '0' : 0;
int sum = f + aval + bval;
f = sum/10;
sum %= 10;
result[k--] = (char)(sum+'0');
}
if(f!=0)
result[k--] = (char)(f+'0');
if(aStart==1&&bStart==1)
return "-"+new String(result,k+1,result.length-k-1);
return new String(result,k+1,result.length-k-1);
}
private static String sub(String a,String b){
// a - b
boolean flag = false;
if(a.length()<b.length()
|| (a.length()==b.length()&&a.compareTo(b)<0)){
String temp = b;
b = a;
a = temp;
flag = true;
}
char[] result = new char[a.length()];
char[] ach = a.toCharArray();
char[] bch = b.toCharArray();
int f = 0;
int i = a.length()-1;
int j = b.length()-1;
int k = result.length-1;
while(i>=0){
int aval = getInt(ach[i--]);
int bval = j >= 0 ? getInt(bch[j--]) : 0;
int sub = aval;
int l = i;//前一位
while(sub<bval){
int before = getInt(ach[l]);//向前借数
if(before>0){
sub += 10;
ach[l] = getChar(before-1);
}
l--;
}
result[k--] = getChar(sub-bval);
}
if(flag)
return "-"+getResult(result,k+1);
return getResult(result,k+1);
}
private static String getResult(char[] s,int start){
StringBuilder sb = new StringBuilder();
boolean flag = true;
for(int i = start;i<s.length;i++){
if(flag&&s[i]=='0')
continue;
flag = false;
sb.append(s[i]);
}
return sb.length()==0?"0":sb.toString();
}
private static boolean compareNegative(String a,String b) {
if(a.length()>b.length())
return false;
if(a.length()<b.length())
return true;
int i = 1;
for(;i<a.length();i++){
if(a.charAt(i)!=b.charAt(i))
return a.charAt(i) - b.charAt(i)<0;
}
return false;
}
private static int getInt(char c){
return c-'0';
}
private static char getChar(int a){
return (char)(a+'0');
}
}
发表于 2016-07-22 21:33:16
回复(0)
浙大测试平台上这个题一个case只有100ms（毫秒）
python好虚怎么办？
答：C#提供了一种128位定点整数类型Decimal，其中96位表示精确值（尾数），32位表示10^-x（阶码）
随手掏出C#，编辑框里写一发即可。
using System;
class Prob{
public static void Main(String[] args){
int T=int.Parse(Console.ReadLine());
int Case=0;
while(T-->0){
string[] tk=Console.ReadLine().Split(new char[]{' '});
Decimal a=Decimal.Parse(tk[0]);
Decimal b=Decimal.Parse(tk[1]);
Decimal c=Decimal.Parse(tk[2]);
Console.Write("Case #"+(++Case)+": ");
Console.WriteLine(a+b>c?"true":"false");
}
}
}
发表于 2016-01-29 21:39:10
回复(0)
解法一：
用long double ，这样可以不用做溢出判断。所以代码很简洁：
#include<iostream>
using namespace std ;
int main()
{
int T ;
cin >> T ;
for( int i = 1; i <= T; ++i )
{
long double a, b, c, ans ;
cin >> a >> b >> c ;
cout << "Case #"<< i <<": " << (a+b>c ? "true" : "false") << endl ;
}
return 0 ;
}
但是，不能用double。 至于为什么long double可以
而double不行，我暂时还不能得出肯定的结论。不过在我差了一些资料后，我想可能的原因是这样的：
- C++ Primer(5th Edition) 中提到，C++规定了 double 和 long double 的最小尺寸均为10位有效数字,而float是6位。
- 一般来说，float的有效数字是7位，double是16位，而long double的有效位不少于double(一般是多少暂时没有查到).
- 而题目要求数字范围在 [-2 63 , 2 63 ]. 2 63 = 9,223,372,036,854,775,808 有19位。 超过了double的有效位范围。
解法二：
long long。 但还要考虑溢出，long
long占64b，是有符号的。可以表示的范围 [-2 63 , 2 63 -1 ]。
#include<iostream>
#include<fstream>
#define LOCAL using namespace std ;
const long long mid = 2 << 62 ;
int main()
{
#ifdef LOCAL
#define cin fin
ifstream fin("F:\\input.txt") ;
#endif
int T ;
cin >> T ;
for( int i = 1; i <= T; ++i )
{
long long a, b, c, ans ;
bool flag = true ; //ture:a+b > c; false: a+b <= c
cin >> a >> b >> c ;
ans = a + b ;
if( a < 0 && b < 0 && ans >= 0) { flag = false ; }//Overflow, a+b<c
else if( a > 0 && b > 0 && ans <= 0 ) { flag = true ; } //Overflow, a+b>c
else flag = ( ans > c ) ;
cout << "Case #"<< i <<": " << (flag ? "true" : "false") << endl ;
}
return 0 ;
}
溢出判断的逻辑并没有什么难点。不过要注意的是一个语言的细节。
a + b >= 0 ;
与下面这句看起来一样，但实际上还是有差别的。
ans = a + b ; ans >= 0 ;似乎是因为只有赋值以后才能正确判断a+b是否溢出。 第一种写法如果放在解法二的溢出判断里面，无法通过pat官网的后面两组测试数据。而第二种写法能正确通过所有测试数据。 至于其中原因，我不得而知。 各位如果有谁知道麻烦告诉我！
发表于 2016-01-07 21:03:17
回复(5)
提供一种新思路。作为C语言忠实玩家，表示一定要会用位运算。
PS:>>1不能换成/2，请自行思考。
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int main(int argc, char *argv[])
{
int64_t a, b, c, half_a, half_b, half_c;
int i, cnts;
scanf("%d", &cnts);
for(i = 1; i <= cnts; ++i) {
scanf("%lld%lld%lld", &a, &b, &c);
half_a = a >> 1;
half_b = b >> 1;
half_c = c >> 1;
printf("Case #%d: ", i);
if(half_a + half_b > half_c)
printf("true\n");
else if(half_a + half_b == half_c)
printf("%s\n", (a & 1) + (b & 1) > (c & 1) ? "true" : "false");
else
printf("false\n");
}
return EXIT_SUCCESS;
}
发表于 2018-03-08 23:32:15
回复(2)
#include <cstdio>
using namespace std;
long long a, b, c;
bool solve(long long n1, long long n2, long long n3){
if(n1 > 0 && n2 >0){
if(n3 < 0)
return true;
else
return n1 > n3 - n2;
}
if(n1 < 0 && n2 < 0){
if(n3 >= 0)
return false;
else
return n1 > n3 - n2;
}
else
return n1 + n2 > n3;
}
int main(){
int n;
scanf("%d", &n);
for(int i=1; i<=n; i++){
bool flag;
scanf("%lld %lld %lld", &a, &b, &c);
flag = solve(a, b, c);
if(flag)
printf("Case #%d: true\n", i);
else
printf("Case #%d: false\n", i);
}
return 0;
}
发表于 2017-08-28 18:01:49
回复(1)
你不该检测a+b的结果是否溢出，因为溢出本身不该被检测
整数溢出在C/C++是一个未定义行为（UB），UB会产生不可预测的行为，这也就是为什么很多人提到很多玄学，什么“表达式”，“需要换一种写法”，因为你写的是UB，UB不可预测，编译器可以对其做任何事情。
规范的代码应该是这样的
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
long long a, b, c;
for (int i = 0; i < t; i++) {
scanf("%lld %lld %lld", &a, &b, &c);
long long sum = a + b;
// 避免UB和IB，可以在任何平台和编译器上正确运行
bool overflowed = ((b > 0 && a > INT64_MAX - b) || (b < 0 && a < INT64_MIN - b));
if (overflowed && a > 0)
printf("Case #%d: true\n", i + 1);
else if (overflowed && a < 0)
printf("Case #%d: false\n", i + 1);
else if (sum > c)
printf("Case #%d: true\n", i + 1);
else
printf("Case #%d: false\n", i + 1);
}
return 0;
}
发表于 2023-10-20 11:54:21
回复(1)
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
while(cin>>n) {
for(int i=1; i<=n; i++) {
long long a,b,c;
cin>>a>>b>>c;
if(a>0&&b>0) {
if(a+b<0) {
cout<<"Case #"<<i<<": true"<<endl;
} else if(a+b>c) {
cout<<"Case #"<<i<<": true"<<endl;
} else {
cout<<"Case #"<<i<<": false"<<endl;
}
} else if(a<0&&b<0) {
if(a+b>=0) {
cout<<"Case #"<<i<<": false"<<endl;
} else if(a+b>c) {
cout<<"Case #"<<i<<": true"<<endl;
} else {
cout<<"Case #"<<i<<": false"<<endl;
}
} else if(a+b>c) {
cout<<"Case #"<<i<<": true"<<endl;
} else {
cout<<"Case #"<<i<<": false"<<endl;
}
}
}
return 0;
}
发表于 2022-11-02 22:56:50
回复(6)
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#include<string>
using namespace std;
int main()
{
int N;
cin >> N;
for (int i = 0; i < N; i++)
{
//if (N != 63) {
// continue;
//}
long long a, b, c;
long long a1, b1, c1;
long long a2, b2, c2;
cin >> a >> b >> c;
a1 = a / 100000000, a2 = a % 100000000;
b1 = b / 100000000, b2 = b % 100000000;
c1 = c / 100000000, c2 = c % 100000000;
if (a1+b1>c1) {
cout << "Case #" << i + 1 << ": true" << endl;
}
else if(a1 + b1 < c1)
{
/*if (i == 48&&N!=63) {
cout << "警告:" << a << "#" << b << "#" << c << endl;
}*/
cout << "Case #" << i + 1 << ": false" << endl;
}
else {
if (a2 + b2 > c2) {
cout << "Case #" << i + 1 << ": true" << endl;
}
else if (a2 + b2 < c2)
{
/*if (i == 48&&N!=63) {
cout << "警告:" << a << "#" << b << "#" << c << endl;
}*/
cout << "Case #" << i + 1 << ": false" << endl;
}
else
{
cout << "Case #" << i + 1 << ": false" << endl;
}
}
}
return 0;
} long long 解法
发表于 2021-10-10 18:01:48
回复(1)
因为这道题，我写了一个类(BigInteger--cpp实现
为什么需要大数加减类？
对于计算机而言，基本的数据类型一般最多为64位数据表示范围，这个范围是有限的，没法无限的表示所有的数据，那么有没有一种方式能够表示所有的大数，并完成加减乘除呢？
答案肯定是有的，由于数据都是由一位一位的数字所组成，我们只需要用数组中的每一位表示一位数字，便可完成对大数的模拟了。
那么我们说明时候需要用到大数模拟呢？对竞赛人而言，有很多题目实际上就是高精度大数模拟类型，而对于普通的程序员而言，大数模拟也仅是在做某个逻辑运算而保证不会溢出的最佳策略，那么大家难道不好奇如何实现一个大数模拟类吗？
现在就从封装一个简单的加减类开始了解这样一个大数模拟是怎么实现的👀
大数加减类实现详解
一、流程图总览
- 如图总体来说分为五部分：
- 静态成员函数：属于类的公共接口(核心)
- 构造和析构函数：构造对象以及析构对象
- 成员数据：用于运算的数据以及表示对象的数据
- 运算符重载：用于自定义运算方式(核心)
- 内部成员函数：属于对象的公共接口
二、成员数据和构造函数详解
- 成员数据
bool f; //是否是负数的标记 char *nums; //存储非符号的大数各个位 int length; //nums的数据长度 int capacity; //nums的可用容量
- 构造和析构
//缺省构造函数 BigInteger() : length(0), capacity(1), f(false) { nums = new char[capacity]; } //用于转化普通字符串的构造函数 BigInteger(const char *n) : length(strlen(n)), f(false) { int start = 0; if (n[0] == '-') { f = true; start++; } while (start<length&&n[start] == '0')start++; capacity = length * 10; nums = new char[capacity]; std::copy(n + start, n + length, nums); length = length - start; } //拷贝构造函数 BigInteger(BigInteger &a) { capacity = a.capacity; length = a.length; f = a.f; nums = new char[capacity]; std::copy(a.nums, a.nums + length, nums); } //移动构造函数：这里调用了等于号，根据a的类型来决定用哪个等于号 BigInteger(BigInteger &&a) :length(0){ *this = a; } //析构函数 ~BigInteger() { delete[] nums; }三、(算法核心)静态成员函数和运算符重载详解
static Swap()
//调用std的swap实现对基本数据的交换 static void Swap(BigInteger &a, BigInteger &b) { std::swap(a.length, b.length); std::swap(a.capacity, b.capacity); std::swap(a.f, b.f); std::swap(a.nums, b.nums); }static compare()
//不看符号比较nums的大小：表示a是否比b大 static bool compare(const BigInteger &a,const BigInteger &b) { //比较纯nums大小(不看符号 int n1 = a.length; int n2 = b.length; if (n1 != n2)return n1 > n2; //返回a和b哪个大，true则位a大 int i = 0; while (i < n1 && a.nums[i] == b.nums[i])i++; //a b一样长的情况下，比较两个的值 if (i == n1) return false; return a.nums[i] > b.nums[i]; }static isEqual()
//表示a和b是否相等 bool isEqual(BigInteger &a, BigInteger &b) { if (a.f != b.f || (a.length != b.length))return false; int i = 0; while (i < a.length && a.nums[i] == b.nums[i])i++; return i == a.length && a.f == b.f; }(*核心算法)static add()
不看符号的加法，符号这方面由重载加法运算符控制。
static BigInteger add(BigInteger &a, BigInteger &b) { //不看符号的加法 a.reverse();//尾端对齐 b.reverse(); BigInteger t; int up = 0; int len = a.length > b.length ? a.length : b.length; for (int i = 0; i < len; i++) { int ta = i < a.length ? a[i] - '0' : 0; int tb = i < b.length ? b[i] - '0' : 0; int base = ta + tb + up; t.push_back(base % 10 + '0'); up = base / 10; } if (up) t.push_back(up + '0'); t.reverse();//返回原位 a.reverse(); b.reverse(); return t; }(*核心算法)static minus()
不看符号的减法,默认了a的nums大小(不看符号)是比b大的。
static BigInteger minus(BigInteger &a, BigInteger &b) { a.reverse(); b.reverse(); BigInteger t; int len = a.length > b.length ? a.length : b.length; for (int i = 0; i < len; i++) { int ta = i < a.length ? a[i] - '0' : 0; int tb = i < b.length ? b[i] - '0' : 0; int base = ta - tb; if (base < 0) { base += 10; a[i + 1]--; } t.push_back(base + '0'); } t.reverse(); a.reverse(); b.reverse(); return t; }char &operator[]
char &operator[](int i) { return nums[i]; }BigInteger &operator=
用了两个版本--右值引用和左值引用版本
- 右值引用延长寿命，用交换的方式实现(毕竟是将亡值
BigInteger &operator=(BigInteger&& a) { //Swap&Copy方式实现右值赋值重载 Swap(*this, a); return *this; } - 左值引用深拷贝
BigInteger &operator=(const BigInteger &a) {//深拷贝 if (length != 0)//如果不是初始化调用的 = ，则肯定需要先把原来的内存delete掉 delete[]nums; capacity = a.capacity; length = a.length; f = a.f; nums = new char[capacity]; std::copy(a.nums, a.nums + length, nums); return *this; }bool operator<
重载了小于号，好处在于可以直接利用stl进行各种排序操作了。
注意：一定要写成const版本的成员函数，不然STL库无法调用，因为STL库中的所有比较都是基于const对象。
bool operator<(const BigInteger &a) const {
if (f && !a.f) { //其中一个为负数，则那个是更小的
return true;
} else if (!f && a.f)
return false;
if (f) { //两者都为负数的情况，左边的值要更大则为true
return compare(*this, a);
}//两者均为正数，则值更小的在左边为true
return compare(a, *this);
} (*核心算法)BigInteger operator+
利用静态成员函数完成无符号的加减，然后在这里进行判断各种符号情况，根据不同的符号情况进行不同的加法处理。
- 注意在调用minus之前需要比较两个数的nums谁更大，更大的放在第一个参数上！
BigInteger operator+(BigInteger &a) {
BigInteger res;
bool flag;
if (a.f && f) { //同为负数情况，直接相加，再改符号
res = add(*this, a);
flag = true;
} else if (a.f && !f) {//左正右负
if (compare(a, *this)) { //看负数对应的nums是否比正数大
flag = true;
res = minus(a, *this);
} else {
flag = false;
res = minus(*this, a);
}
} else if (!a.f && f) {
if (compare(*this, a)) { //与上一个相同
flag = true;
res = minus(*this, a);
} else {
flag = false;
res = minus(a, *this);
}
} else { //同时为正数就是最简单的加法
flag = false;
res = add(*this, a);
}
res.f = flag;
return res;
} (*核心算法)BigInteger operator-
同样是分类讨论，同样是根据不同的类型调用minus和add函数。
- 与正数不同的处理在于对符号的处理，如果同为负数，则需要判断两者是否相等，防止两数相等相减后减为
0，而被处理为-0。BigInteger operator-(BigInteger &a) { BigInteger res; bool flag; if (a.f && f) { //同为负数情况--左边-右边==(不看符号)右边-(不看符号)左边 if (compare(a, *this)) { flag = false; res = minus(a, *this); } else { if (isEqual(*this, a)) flag = false; else flag = true; res = minus(*this, a); } } else if (a.f && !f) { //左边为正，右边为负--左边-右边==左边+右边 flag = false; res = add(a, *this); } else if (!a.f && f) { //右边为正，左边为负--左边-右边==两边为负的加法 flag = true; res = add(a, *this); } else { //同时为正数--左边-右边==左边-右边(分类讨论正负 if (compare(a, *this)) { //右边>左边,符号为负 res = minus(a, *this); flag = true; } else { //右边<左边，符号为正 res = minus(*this, a); flag = false; } } res.f = flag; return res; }四、其他内部成员函数详解
向外提供的get接口
int getCap() { return capacity; } int getLength() { return length; } bool isNegative() { return f; } bool isEmpty() { return length == 0; }进行赋值操作所必备的push_back和reverse函数
void push_back(char x) { if (length >= capacity) {//扩容操作 capacity *= 2; char *t = nums; nums = new char[capacity]; std::copy(t, t + length, nums); delete[]t; } nums[length++] = x; } void reverse() {//反转操作 int l = 0, r = length - 1; while (l < r) { std::swap(nums[l], nums[r]); l++; r--; } }无关紧要的
read()输入接口 和print()输出测试接口void print() { if (f) printf("-"); nums[length] = '\0'; int i = 0; while (nums[i] == '0')i++; printf("%s", nums + i); } void read() {//利用getchar()给对象赋上数据 char c = getchar(); if (c == '-') { f = true; c = getchar(); } while (c == '0') c = getchar();//将前导0消耗掉 while (c != '\n') { push_back(c);//不断的调用push_back即可 c = getchar(); } }
整理代码
.h声明文件
如果在声明类的同时进行定义，则内部的成员函数默认就是内联的。所以我们一般把短小的代码进行内联，以下的实现均是以该规律进行。
//
// Created by Alone on 2021/10/7.
//
#ifndef MY_TINY_STL_BIGINTEGER_H
#define MY_TINY_STL_BIGINTEGER_H
#include <algorithm>
#include <iostream>
#include <cstring>
class BigInteger {
bool f;
char *nums;
int length;
int capacity;
public:
//构造函数
BigInteger() : length(0), capacity(1), f(false) { //缺省构造函数
nums = new char[capacity];
}
BigInteger(const char *n);
BigInteger(const BigInteger &a);
BigInteger(BigInteger &&a);
~BigInteger() { //析构函数
delete[] nums;
}
public:
//静态函数
static void Swap(BigInteger &a, BigInteger &b);
static bool compare(const BigInteger &a, const BigInteger &b);
bool isEqual(BigInteger &a, BigInteger &b);
static BigInteger add(BigInteger &a, BigInteger &b);
static BigInteger minus(BigInteger &a, BigInteger &b);
public:
//运算符重载
char &operator[](int i) {
return nums[i];
}
BigInteger &operator=(BigInteger &&a) { //Swap&Copy方式实现右值赋值重载
Swap(*this, a);
return *this;
}
BigInteger &operator=(const BigInteger &a);
bool operator<(const BigInteger &a) const;
BigInteger operator+(BigInteger &a);
BigInteger operator-(BigInteger &a);
public:
//对象的基本成员函数
int getCap() {
return capacity;
}
int getLength() {
return length;
}
bool isNegative() {
return f;
}
bool isEmpty() {
return length == 0;
}
void reverse();
void push_back(char x);
void print();
void read();
};
#endif //MY_TINY_STL_BIGINTEGER_H
.cpp定义并实现
//
// Created by Alone on 2021/10/7.
//
#include "BigInteger.h"
//@构造函数实现
BigInteger::BigInteger(const char *n) : length(strlen(n)), f(false) { //用于初始值的构造函数
int start = 0;
if (n[0] == '-') {
f = true;
start++;
}
while (start < length && n[start] == '0')start++;
capacity = length * 10;
nums = new char[capacity];
std::copy(n + start, n + length, nums);
length = length - start;
}
BigInteger::BigInteger(const BigInteger &a) { //拷贝构造函数
capacity = a.capacity;
length = a.length;
f = a.f;
nums = new char[capacity];
std::copy(a.nums, a.nums + length, nums);
}
BigInteger::BigInteger(BigInteger &&a) : length(0) { //移动构造函数
*this = a;
}
//@静态函数实现
void BigInteger::Swap(BigInteger &a, BigInteger &b) {
std::swap(a.length, b.length);
std::swap(a.capacity, b.capacity);
std::swap(a.f, b.f);
std::swap(a.nums, b.nums);
}
bool BigInteger::compare(const BigInteger &a, const BigInteger &b) {
int n1 = a.length;
int n2 = b.length;
if (n1 != n2)return n1 > n2; //返回a和b哪个大，true则位a大
int i = 0;
while (i < n1 && a.nums[i] == b.nums[i])i++; //a b一样长的情况下，比较两个的值
if (i == n1)
return false;
return a.nums[i] > b.nums[i];
}
bool BigInteger::isEqual(BigInteger &a, BigInteger &b) {
if (a.f != b.f || (a.length != b.length))return false;
int i = 0;
while (i < a.length && a.nums[i] == b.nums[i])i++;
return i == a.length && a.f == b.f;
}
BigInteger BigInteger::add(BigInteger &a, BigInteger &b) {
a.reverse();//尾端对齐
b.reverse();
BigInteger t;
int up = 0;
int len = a.length > b.length ? a.length : b.length;
for (int i = 0; i < len; i++) {
int ta = i < a.length ? a[i] - '0' : 0;
int tb = i < b.length ? b[i] - '0' : 0;
int base = ta + tb + up;
t.push_back(base % 10 + '0');
up = base / 10;
}
if (up)
t.push_back(up + '0');
t.reverse();//返回原位
a.reverse();
b.reverse();
return t;
}
BigInteger BigInteger::minus(BigInteger &a, BigInteger &b) {
a.reverse();
b.reverse();
BigInteger t;
int len = a.length > b.length ? a.length : b.length;
for (int i = 0; i < len; i++) {
int ta = i < a.length ? a[i] - '0' : 0;
int tb = i < b.length ? b[i] - '0' : 0;
int base = ta - tb;
if (base < 0) {
base += 10;
a[i + 1]--;
}
t.push_back(base + '0');
}
t.reverse();
a.reverse();
b.reverse();
return t;
}
//@运算符重载实现
BigInteger &BigInteger::operator=(const BigInteger &a) {
if (length != 0)//如果不是初始化调用的 = ，则肯定需要先把原来的内存delete掉
delete[]nums;
capacity = a.capacity;
length = a.length;
f = a.f;
nums = new char[capacity];
std::copy(a.nums, a.nums + length, nums);
return *this;
}
BigInteger BigInteger::operator+(BigInteger &a) {
BigInteger res;
bool flag;
if (a.f && f) { //同为负数情况，直接相加，再改符号
res = add(*this, a);
flag = true;
} else if (a.f && !f) {//左正右负
if (compare(a, *this)) { //看负数对应的nums是否比正数大
flag = true;
res = minus(a, *this);
} else {
flag = false;
res = minus(*this, a);
}
} else if (!a.f && f) {
if (compare(*this, a)) { //与上一个相同
flag = true;
res = minus(*this, a);
} else {
flag = false;
res = minus(a, *this);
}
} else { //同时为正数就是最简单的加法
flag = false;
res = add(*this, a);
}
res.f = flag;
return res;
}
BigInteger BigInteger::operator-(BigInteger &a) {
BigInteger res;
bool flag;
if (a.f && f) { //同为负数情况--左边-右边==(不看符号)右边-(不看符号)左边
if (compare(a, *this)) {
flag = false;
res = minus(a, *this);
} else {
if (isEqual(*this, a))
flag = false;
else flag = true;
res = minus(*this, a);
}
} else if (a.f && !f) { //左边为正，右边为负--左边-右边==左边+右边
flag = false;
res = add(a, *this);
} else if (!a.f && f) { //右边为正，左边为负--左边-右边==两边为负的加法
flag = true;
res = add(a, *this);
} else { //同时为正数--左边-右边==左边-右边(分类讨论正负
if (compare(a, *this)) { //右边>左边,符号为负
res = minus(a, *this);
flag = true;
} else { //右边<左边，符号为正
res = minus(*this, a);
flag = false;
}
}
res.f = flag;
return res;
}
bool BigInteger::operator<(const BigInteger &a) const {
if (f && !a.f) { //其中一个为负数，则那个是更小的
return true;
} else if (!f && a.f)
return false;
if (f) { //两者都为负数的情况，左边的值要更大则为true
return compare(*this, a);
}//两者均为正数，则值更小的在左边为true
return compare(a, *this);
}
//@基本成员函数
void BigInteger::reverse() {
int l = 0, r = length - 1;
while (l < r) {
std::swap(nums[l], nums[r]);
l++;
r--;
}
}
void BigInteger::push_back(char x) {
if (length >= capacity) {
capacity *= 2;
char *t = nums;
nums = new char[capacity];
std::copy(t, t + length, nums);
delete[]t;
}
nums[length++] = x;
}
void BigInteger::print() {
if (f)
printf("-");
nums[length] = '\0';
int i = 0;
while (nums[i] == '0')i++;
printf("%s", nums + i);
}
void BigInteger::read() {
char c = getchar();
if (c == '-') {
f = true;
c = getchar();
}
while (c == '0') c = getchar();//将前导0消耗掉
while (c != '\n') {
push_back(c);//不断的调用push_back即可
c = getchar();
}
} 功能测试
一、基本的加减测试
运行的测试代码：
打印输出
python输出
- 总结
与python输出无异，故通过测试。但碍于测试数据太过少，不是很有说服力，还有后面的解题测试。
二、存储个人输入的数据+排序测试
测试代码(方便测试只输入了10个数据)：
排序输出：
三、解题测试
正好最近刷的PAT甲级就涉及到大数的加减hhh！
题目描述
OJ平台
解题代码
#include "bits/stdc++.h"
class BigInteger {
bool f;
char *nums;
int length;
int capacity;
public://构造函数
BigInteger() : length(0), capacity(1), f(false) { //缺省构造函数
nums = new char[capacity];
}
BigInteger(const char *n) : length(strlen(n)), f(false) { //用于初始值的构造函数
int start = 0;
if (n[0] == '-') {
f = true;
start++;
}
while (start < length && n[start] == '0')start++;
capacity = length * 10;
nums = new char[capacity];
std::copy(n + start, n + length, nums);
length = length - start;
}
BigInteger(const BigInteger &a) { //拷贝构造函数
capacity = a.capacity;
length = a.length;
f = a.f;
nums = new char[capacity];
std::copy(a.nums, a.nums + length, nums);
}
BigInteger(BigInteger &&a) : length(0) { //移动构造函数
*this = a;
}
~BigInteger() { //析构函数
delete[] nums;
}
public://静态成员函数
static void Swap(BigInteger &a, BigInteger &b) {
std::swap(a.length, b.length);
std::swap(a.capacity, b.capacity);
std::swap(a.f, b.f);
std::swap(a.nums, b.nums);
}
static bool compare(const BigInteger &a, const BigInteger &b) { //比较纯nums大小(不看符号
int n1 = a.length;
int n2 = b.length;
if (n1 != n2)return n1 > n2; //返回a和b哪个大，true则位a大
int i = 0;
while (i < n1 && a.nums[i] == b.nums[i])i++; //a b一样长的情况下，比较两个的值
if (i == n1)
return false;
return a.nums[i] > b.nums[i];
}
bool isEqual(BigInteger &a, BigInteger &b) {
if (a.f != b.f || (a.length != b.length))return false;
int i = 0;
while (i < a.length && a.nums[i] == b.nums[i])i++;
return i == a.length && a.f == b.f;
}
static BigInteger add(BigInteger &a, BigInteger &b) { //不看符号的加法
a.reverse();//尾端对齐
b.reverse();
BigInteger t;
int up = 0;
int len = a.length > b.length ? a.length : b.length;
for (int i = 0; i < len; i++) {
int ta = i < a.length ? a[i] - '0' : 0;
int tb = i < b.length ? b[i] - '0' : 0;
int base = ta + tb + up;
t.push_back(base % 10 + '0');
up = base / 10;
}
if (up)
t.push_back(up + '0');
t.reverse();//返回原位
a.reverse();
b.reverse();
return t;
}
static BigInteger minus(BigInteger &a, BigInteger &b) { //不看符号的减法,默认了a的长度或者大小是比***的(所以外界不要乱调用
a.reverse();
b.reverse();
BigInteger t;
int len = a.length > b.length ? a.length : b.length;
for (int i = 0; i < len; i++) {
int ta = i < a.length ? a[i] - '0' : 0;
int tb = i < b.length ? b[i] - '0' : 0;
int base = ta - tb;
if (base < 0) {
base += 10;
a[i + 1]--;
}
t.push_back(base + '0');
}
t.reverse();
a.reverse();
b.reverse();
return t;
}
public://成员函数和重载运算符
char &operator[](int i) {
return nums[i];
}
BigInteger &operator=(BigInteger &&a) { //Swap&Copy方式实现右值赋值重载
Swap(*this, a);
return *this;
}
BigInteger &operator=(const BigInteger &a) {//深拷贝
if (length != 0)//如果不是初始化调用的 = ，则肯定需要先把原来的内存delete掉
delete[]nums;
capacity = a.capacity;
length = a.length;
f = a.f;
nums = new char[capacity];
std::copy(a.nums, a.nums + length, nums);
return *this;
}
int getCap() {
return capacity;
}
int getLength() {
return length;
}
bool isNegative() {
return f;
}
bool isEmpty() {
return length == 0;
}
void reverse() {
int l = 0, r = length - 1;
while (l < r) {
std::swap(nums[l], nums[r]);
l++;
r--;
}
}
void push_back(char x) {
if (length >= capacity) {
capacity *= 2;
char *t = nums;
nums = new char[capacity];
std::copy(t, t + length, nums);
delete[]t;
}
nums[length++] = x;
}
bool operator<(const BigInteger &a) const {
if (f && !a.f) { //其中一个为负数，则那个是更小的
return true;
} else if (!f && a.f)
return false;
if (f) { //两者都为负数的情况，左边的值要更大则为true
return compare(*this, a);
}//两者均为正数，则值更小的在左边为true
return compare(a, *this);
}
BigInteger operator+(BigInteger &a) {
BigInteger res;
bool flag;
if (a.f && f) { //同为负数情况，直接相加，再改符号
res = add(*this, a);
flag = true;
} else if (a.f && !f) {//左正右负
if (compare(a, *this)) { //看负数对应的nums是否比正数大
flag = true;
res = minus(a, *this);
} else {
flag = false;
res = minus(*this, a);
}
} else if (!a.f && f) {
if (compare(*this, a)) { //与上一个相同
flag = true;
res = minus(*this, a);
} else {
flag = false;
res = minus(a, *this);
}
} else { //同时为正数就是最简单的加法
flag = false;
res = add(*this, a);
}
res.f = flag;
return res;
}
BigInteger operator-(BigInteger &a) {
BigInteger res;
bool flag;
if (a.f && f) { //同为负数情况--左边-右边==(不看符号)右边-(不看符号)左边
if (compare(a, *this)) {
flag = false;
res = minus(a, *this);
} else {
if (isEqual(*this, a))
flag = false;
else flag = true;
res = minus(*this, a);
}
} else if (a.f && !f) { //左边为正，右边为负--左边-右边==左边+右边
flag = false;
res = add(a, *this);
} else if (!a.f && f) { //右边为正，左边为负--左边-右边==两边为负的加法
flag = true;
res = add(a, *this);
} else { //同时为正数--左边-右边==左边-右边(分类讨论正负
if (compare(a, *this)) { //右边>左边,符号为负
res = minus(a, *this);
flag = true;
} else { //右边<左边，符号为正
res = minus(*this, a);
flag = false;
}
}
res.f = flag;
return res;
}
void print() {
if (f)
printf("-");
nums[length] = '\0';
int i = 0;
while (nums[i] == '0')i++;
printf("%s", nums + i);
}
void read() {//利用getchar()给对象赋上数据
char c = getchar();
if (c == '-') {
f = true;
c = getchar();
}
while (c=='\n'||c == '0'||c == ' ') c = getchar();//将前导0消耗掉和空格
while (c != '\n'&&c != ' '&& c != '\t') {
push_back(c);//不断的调用push_back即可
c = getchar();
}
}
};
int main() {
using namespace std;
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
char a[100], b[100], c[100];
printf("Case #%d: ", i);
cin >> a >> b >> c;
BigInteger a1(a), b2(b), c2(c);
BigInteger t = c2 - b2;
if (t < a1)
cout << "true\n";
else cout << "false\n";
}
return 0;
} 正确输出
总结
很多人，可能觉得做项目一定得是那种高大上，又或者是那种贪吃蛇小游戏、扫雷小游戏类型，实际上只要你有兴趣，任何一个东西都能成为你的练手项目，并且收获收获也许比你跟风去弄几个小游戏更大。
做这个小项目，我的收获是，对C++的语法更加的了解了，关于移动构造器、拷贝构造器、赋值重载这块弄得更清楚了，最大的收获在于强化了一个类的设计思路，这个是最重要的。
多写一些类的实现，不仅有利于对算法和语言语法的理解，更大的收获在于对各个功能的设计思路，作为程序员，我们最需要的就是这样的逻辑思维，从接到需求开始，我们应该能迅速的抽象出各种实现方案，然后进行不断的优化，得出属于自己的代码！
编辑于 2021-10-08 01:22:16
回复(1)
//没想到是这样简单的方式，以为考察高精度加减法呢,不过就一个20分的题，估计也不是
// 溢出的判断方法激：上溢必定是两个正数相加，结果超过INT_MAX，导致结果变成负数或零。下溢同理（或0）。
#include<iostream>
using namespace std;
long long a,b,c,d,n,k=1;
int main(){
cin>>n;
while(n--){
cin>>a>>b>>c;
d=a+b;
if(a>0&&b>0&&d<=0) printf("Case #%lld: true\n",k++);
else if(a<0&&b<0&&d>=0) printf("Case #%lld: false\n",k++);
else if(a+b>c){
printf("Case #%lld: true\n",k++);
}
else{
printf("Case #%lld: false\n",k++);
}
}
}
/***
//高精度相加和比较
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+10;
vector<int> add(vector<int>&a,vector<int>&b,int n,int m){
vector<int>res;
int t=0;
for(int i=0;i<n||i<m||t;i++){
if(i<n) t+=a[i];
if(i<m) t+=b[i];
res.push_back(t%10);
t/=10;
}
// 别忘了反转
reverse(res.begin(),res.end());
return res;
}
vector<int> sub(vector<int>&a,vector<int>&b,int n,int m){
vector<int>res;
if(n<m){
res=sub(b,a,m,n);
return res;
}
else if(n==m){
for(int i=n-1;i>=0;i--){
if(a[i]<b[i]) return sub(b,a,m,n);
else if(a[i]>b[i]) return sub(a,b,n,m);
}
return res;
}
//n>=m；
int t=0;
for(int i=0;i<n;i++){
t+=a[i];
if(i<m) t-=b[i];
res.push_back((t+10)%10);
if(t<0) t=-1;
else t=0;
}
//去前导零
for(int i:res){
if(i==0) res.pop_back();
else break;
}
reverse(res.begin(),res.end());
return res;
}
int main(){
int k,n,m;
cin>>k;
bool flag=false;
vector<int>a;
vector<int>b;
vector<int>res;
string sa,sb,sc;
int zer=0;
while(k--){
cin>>sa>>sb>>sc;
n=sa.size(),m=sb.size();
for(int i=n-1;i>=0;i--) {
if(i==0&&!isdigit(sa[i])) {
n--;
continue;
}
a.push_back(sa[i]-'0');
}
for(int i=m-1;i>=0;i--) {
if(i==0&&!isdigit(sb[i])) {
m--;
continue;
}
b.push_back(sb[i]-'0');
}
if(sa[0]=='-'&&sb[0]=='-'){
if(sc[0]!='-') {
cout<<"true"<<endl;
continue;
}
res=add(a,b,n,m);
if(res.size()>sc.size()){
cout<<"false"<<endl;
}
else if(res.size()<sc.size())cout<<"true"<<endl;
else{
for(int i=0;i<sc.size();i++){
if(sc[i]>res[i]){
cout<<"false"<<endl;
break;
}
else if(sc[i]<res[i]){
cout<<"true"<<endl;
break;
}
}
cout<<"true"<<endl;
}
}
..........
}
}
***/
// 溢出的判断方法激：上溢必定是两个正数相加，结果超过INT_MAX，导致结果变成负数或零。下溢同理（或0）。
#include<iostream>
using namespace std;
long long a,b,c,d,n,k=1;
int main(){
cin>>n;
while(n--){
cin>>a>>b>>c;
d=a+b;
if(a>0&&b>0&&d<=0) printf("Case #%lld: true\n",k++);
else if(a<0&&b<0&&d>=0) printf("Case #%lld: false\n",k++);
else if(a+b>c){
printf("Case #%lld: true\n",k++);
}
else{
printf("Case #%lld: false\n",k++);
}
}
}
/***
//高精度相加和比较
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+10;
vector<int> add(vector<int>&a,vector<int>&b,int n,int m){
vector<int>res;
int t=0;
for(int i=0;i<n||i<m||t;i++){
if(i<n) t+=a[i];
if(i<m) t+=b[i];
res.push_back(t%10);
t/=10;
}
// 别忘了反转
reverse(res.begin(),res.end());
return res;
}
vector<int> sub(vector<int>&a,vector<int>&b,int n,int m){
vector<int>res;
if(n<m){
res=sub(b,a,m,n);
return res;
}
else if(n==m){
for(int i=n-1;i>=0;i--){
if(a[i]<b[i]) return sub(b,a,m,n);
else if(a[i]>b[i]) return sub(a,b,n,m);
}
return res;
}
//n>=m；
int t=0;
for(int i=0;i<n;i++){
t+=a[i];
if(i<m) t-=b[i];
res.push_back((t+10)%10);
if(t<0) t=-1;
else t=0;
}
//去前导零
for(int i:res){
if(i==0) res.pop_back();
else break;
}
reverse(res.begin(),res.end());
return res;
}
int main(){
int k,n,m;
cin>>k;
bool flag=false;
vector<int>a;
vector<int>b;
vector<int>res;
string sa,sb,sc;
int zer=0;
while(k--){
cin>>sa>>sb>>sc;
n=sa.size(),m=sb.size();
for(int i=n-1;i>=0;i--) {
if(i==0&&!isdigit(sa[i])) {
n--;
continue;
}
a.push_back(sa[i]-'0');
}
for(int i=m-1;i>=0;i--) {
if(i==0&&!isdigit(sb[i])) {
m--;
continue;
}
b.push_back(sb[i]-'0');
}
if(sa[0]=='-'&&sb[0]=='-'){
if(sc[0]!='-') {
cout<<"true"<<endl;
continue;
}
res=add(a,b,n,m);
if(res.size()>sc.size()){
cout<<"false"<<endl;
}
else if(res.size()<sc.size())cout<<"true"<<endl;
else{
for(int i=0;i<sc.size();i++){
if(sc[i]>res[i]){
cout<<"false"<<endl;
break;
}
else if(sc[i]<res[i]){
cout<<"true"<<endl;
break;
}
}
cout<<"true"<<endl;
}
}
..........
}
}
***/
发表于 2021-01-05 20:11:30
回复(0)
%lld会把9223372036854775808读成9223372036854775807，所以还是自己实现吧。
#include<cstdio>
#include<cstring>
int main() {
int n, l[2][3], a[3], b[30], i, j, c, len;
char s[3][30];
scanf("%d", &n);
for (i = 1; i <= n; i++) {
scanf("%s%s%s", s[0], s[1], s[2]);
printf("Case #%d: ", i);
for (j = 0; j < 3; j++) {
l[0][j] = l[1][j] = strlen(s[j]);
}
if (s[0][0] == '-') a[0] = -1, l[1][0]--;
else a[0] = 1;
if (s[1][0] == '-') a[1] = -1, l[1][1]--;
else a[1] = 1;
if (s[2][0] == '-') a[2] = 1, l[1][2]--;
else a[2] = -1;
c = 0;
len = l[1][0] > l[1][1] ? l[1][0] : l[1][1];
len = len > l[1][2] ? len : l[1][2];
for (j = 0; j < len; j++) {
b[j] = c;
if (j < l[1][0])
b[j] += a[0] * (s[0][l[0][0] - 1 - j] - '0');
if (j < l[1][1])
b[j] += a[1] * (s[1][l[0][1] - 1 - j] - '0');
if (j < l[1][2])
b[j] += a[2] * (s[2][l[0][2] - 1 - j] - '0');
c = (b[j] + 30) / 10 - 3;
b[j] -= c * 10;
}
if (c > 0) printf("true\n");
else if (c < 0) printf("false\n");
else {
for (j = 0; j < len; j++) {
if (b[j] != 0) break;
}
if (j == len) printf("false\n");
else printf("true\n");
}
}
return 0;
}
编辑于 2020-04-02 23:10:48
回复(0)
pat能过，牛客有一个过不了
#include<iostream>
#include<vector>
#include<string>
using namespace std;
string add(string a,string b) {
string ans;
ans.resize(a.size() > b.size() ? a.size() : b.size());
int i = a.size()-1;
int j = b.size()-1;
int k = ans.size() - 1;
int cf = 0;
while (i>=0&&j>=0) {
char tmp = '0' + (a[i] - '0' + b[j] - '0' + cf) % 10;
cf = (a[i] - '0' + b[j] - '0' + cf) / 10;
ans[k] = tmp;
i--;
j--;
k--;
}
while (i >= 0) {
ans[k] = '0'+(a[i]-'0'+cf)%10;
cf = (a[i] - '0'+ cf) / 10;
k--;
i--;
}
while (j >= 0) {
ans[k] = '0' + (b[j] - '0' + cf) % 10;
cf = (b[j] - '0' + cf) / 10;
k--;
j--;
}
if (cf == 1) {
ans = "1" + ans;
}
return ans;
}
string sub(string a,string b) {//保证是大减小
string ans;
ans.resize(a.size());
int i = a.size() - 1;
int j = b.size() - 1;
int k = ans.size() - 1;
int cf = 0;
while (j >= 0) {
if (a[i] - b[j] - cf < 0) {
ans[k] = '0'+(a[i] - b[j] - cf+10)%10;
cf = 1;
}
else {
ans[k] = '0' + a[i] - b[j] - cf;
cf = 0;
}
i--;
j--;
k--;
}
while (i >= 0) {
if (a[i]-'0' - cf < 0) {
ans[k] = '0' + (a[i]-'0' - cf + 10) % 10;
cf = 1;
}
else {
ans[k] =a[i] - cf;
cf = 0;
}
k--;
i--;
}
return ans;
}
int judge(string a, string b) {//a大b返回1,b大a返回-1,相等返回0
int al = a.size();
int bl = b.size();
if (a[0] == '-'&&b[0] != '-'){
return -1;
}
else if (a[0] != '-'&&b[0] == '-'){
return 1;
}
else if (a[0] != '-'&&b[0] != '-'){
if (al>bl)return 1;
else if (al<bl)return -1;
else{
for (int i = 0; i < al; i++) {
if (a[i] - b[i] > 0)return 1;
if (a[i] - b[i] < 0)return -1;
}
}
return 0;
}
else{
if (al>bl)return -1;
else if (al<bl)return 1;
else{
for (int i = 0; i<al; i++){
if (a[i] - b[i]>0)return -1;
if (a[i] - b[i]<0)return 1;
}
}
return 0;
}
return -10;
}
int main() {//1 -20202220 202002 1
int numofCase;
string A, B, C, ans;
cin >> numofCase;
for (int i = 1; i <= numofCase; i++) {
cin >> A >> B >> C;
printf("Case #%d: ", i);
if (A[0] != '-' && B[0] != '-') {
ans = add(A, B);
}
else if (A[0] == '-' && B[0] == '-') {
B.erase(0, 1);
A.erase(0, 1);
ans = "-" + add(A, B);
}
else if (A[0] != '-' && B[0] == '-') {
B.erase(0, 1);
int tmp = judge(A, B);//比较a,b的绝对值大小
if (tmp == 1 || tmp == 0) {
ans = sub(A, B);
}
else {
ans = "-" + sub(B, A);
}
}
else if (A[0] == '-' && B[0] != '-') {
A.erase(0, 1);
int tmp = judge(A, B);
if (tmp == 1) {
ans = "-" + sub(A, B);
}
else {
ans = sub(B, A);
}
}
if (judge(ans, C) == 1) {
printf("true\n");
}
else {
printf("false\n");
}
}
}
编辑于 2020-04-04 15:21:12
回复(0)
//PAT通过测试代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
int t,flag;
LL a,b,c,res;
scanf("%d",&t);
for(int i = 1; i <= t; i++){
scanf("%lld%lld%lld",&a,&b,&c);
res = a+b;
if(a>0&&b>0&&res<=0) flag = 1;
else if(a<0&&b<0&&res>=0) flag = 0;
else flag = (a+b > c?1:0);
printf("Case #%d: ",i),flag?printf("true\n"):printf("false\n");
}
return 0;
}
发表于 2019-04-01 13:22:47
回复(0)
问题信息
难度：
33条回答
13收藏
10556浏览
通过挑战的用户
-
2023-03-14 17:21:30
-
2023-03-06 19:46:11 -
2023-02-28 17:10:36
-
2023-02-24 14:06:13
-
2023-02-23 21:31:51
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
