f(sixleaves) = sixleaves

重剑无锋 大巧不工

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  95 随笔 :: 0 文章 :: 7 评论 :: 0 Trackbacks

这道题目是大数加法。总结一些一点经验。

(1)整值函数的应用。(这个不懂的话,去看我Math栏目下有这个分析)

(2)sscanf、sprintf的应用

(3)分块计算的格式问题。

先直接看代码:
    
 1 #include <iostream>

 2 #include <cstdio>
 3 #include <vector>
 4 #include <cstring>
 5 using namespace std;
 6 struct BigInteger {
 7     static const int BASE = 100000000;
 8     static const int WIDTH = 8;
 9     vector<int> s;
10     
11     BigInteger(long long num = 0) {
12         *this = num;
13     }
14     
15     BigInteger operator=(long long num) {
16         s.clear();
17         do {
18             s.push_back(num % BASE);
19             num /= BASE;
20         }while (num > 0);
21         return *this;
22     }
23     
24 
25     BigInteger operator=(const string& str) {
26         s.clear();
27         int x;
28         int len = (str.size() - 1) / WIDTH + 1;//这里有人看不懂,请看我写的整值函数 
29         for (int i = 0; i < len; i++) {
30             int end = str.size() - i * WIDTH;
31             int start = max(0, end - WIDTH);//确定分割的区间为[start, end)是左闭右开,长度就是end - start 
32             sscanf(str.substr(start, end - start).c_str(), "%d", &x);
33             s.push_back(x);
34         }
35         return *this;
36     }
37     
38     BigInteger operator+(const BigInteger& bi) const{
39         BigInteger temp;
40         temp.s.clear();
41         for (int i = 0,g = 0;;i++) {
42             
43             if (g == 0 && i >= s.size() && i >= bi.s.size()) break;
44             int x = g;
45             if (i < s.size()) x += s[i];
46             if (i < bi.s.size()) x += bi.s[i];
47             temp.s.push_back(x % BASE);
48             g = x / BASE;
49         }
50         return temp;    
51     }    
52     
53     BigInteger operator +=(const BigInteger& b) {
54         *this = *this + b;return *this;
55     }
56 };
57 
58 istream& operator >>(istream &in, BigInteger& x) {
59     string s;
60     if (!(in >>s)) return in;
61     x = s;
62     return in;
63 }
64     
65 ostream& operator <<(ostream &out, BigInteger&bi) {
66     out << bi.s.back();
67     for (int i = bi.s.size()-2; i >= 0; i--) {//再从倒数第二个输出 
68         char buf[20];
69         sprintf(buf, "%08d", bi.s[i]);
70         //cout << buf;
71         for (int j =0; j < strlen(buf); j++) out << buf[j];
72     }
73     return out;
74 }
75 
76 int main() {
77     int n;
78     BigInteger a,b,c;
79     cin >> n;
80     int kase = 1;
81     while (n) {
82         cin >> a >> b;
83         c = a + b;
84         if (n != 1)
85            cout <<"Case " << kase++ << ":" << "\n" << a << " + " << b << " = " << c << endl << endl;
86         else
87            cout <<"Case " << kase++ << ":" << "\n" << a << " + " << b << " = " << c << endl;
88         n--;
89     }
90     return 0;
91 }
(1)(2)略。
(3)分块处理的坑:

前面两个我就不总结了,这里主要说下,分块计算的坑。假设有这个字符串"123400000001",由于我们要将其
按照没8位字符分成一块所以第一块就是00000001、第二快就是1234,然后按照小端存储格式、低地址对应低位
但是但他们用sscanf格式化成整数时候,00000001不可能还是这样,这样就是八进制了,而是变成了1,所以我们
在输出的时候,除了最高位对应的那一块可能不足8位,剩下的块肯定都要8位处理,所以上面代码,才从第二快进行
输出,而且格式是%08d.
posted on 2014-09-04 14:56 swp 阅读(1471) 评论(0)  编辑 收藏 引用 所属分类: algorithm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理