【159.201算法探讨】159.201 Algorithms & Data Structures
S1 2021
Assignment 4
Write a C++ program to implement the addition operation for big numbers.A big number is a positive, whole
number that can be of any arbitrary size, and therefore will not necessarily fit into an existing C++ type.
You must implement each big number as a List of single decimal digits and you must also set up the template class
List based on a linked-list (use the sample codes).You will need to define and implement the appropriate methods
for big numbers.
Your program must be laid out in the following way:
Section A : the template class List (with extra methods if you wish to do so)
Section B : the class BigNumber (which includes a List of digits)
Section C : program (main plus functions)
The program must read in two big numbers from a txt file, add them and save the result as another big number
instance. Then all three big numbers must be displayed on the screen using the format:
32456789112341234000 +65123443122134123445=97580232234475357445
Notes:
? You must get the two big numbers from a 2 lines text file, one big number in each line (get the sample code)
? The “digits” in the List can be stored in any type you want: int, short int, char etc. You probably
realise that any type is wasting a bit of memory, as you would only need 10 digits (even char can represent
256 things).
? Remember that when a sum of two nodes goes over the base size minus 1 (in base 10, any number that is
bigger than 10-1, then you need to carry part of the result to the next node (grade school arithmetic).
? You need to read the big number as a string, but do not store the big number as a string, integer or float at
any other stage of the program. You need to use your own function that converts a string representing a
decimal number into a List. Every big number is represented by several base-10 digits, one digit per node.
? Once the addition operation is implemented, make sure to carry out the following tests (shown here in one
line due to limited space, for the program follow the format described above):
000000000000 + 000000000001 = 000000000001 ( a list with zeros)
99 + 1 = 100(check that the carry works)
12345678901234567890 + 9876543210987654321 = 22222222112222222211 (check mix of digits)
99999999999999999999 + 99999999999999999999 = 199999999999999999998(check that the carry goes all the way)
99999999999999999999 + 1 = 100000000000000000000(same thing)
100000000000000000000 + 1 =100000000000000000001 (make sure a single digit is added)
Use our virtual machine to test your submissions (host name vm000296). The input/output requirements are
essential, please follow them carefully to avoid losing marks. Spaces matter and text is case sensitive.
After you are satisfied with the performance of your code as tested in the virtual machine, submit a one source file
code on Stream by Friday 9 of April 2021. Your name and ID number must appear on top of the file as
comments. If you are working in a group, then all names and IDs must appear on top of the file as comments, but
you still need to submit individually in both the virtual machine and Stream.
推荐阅读
- 算法设计（最大和连续子数组的范围查询）
- 在链表中找到最大和第二大的值
- 为什么Python是最适合机器学习的编程语言（）
- 将数组的所有元素减少为零所需的最少步骤
- 不含回文的最长子字符串的长度
- 使用Fenwick树在L到R范围内大于K的元素数（离线查询）
- 形成具有给定范围内的整数的数组的方法，以使总和可被2整除
- 十进制等效项大于或等于K的子字符串的计数
- 修改给定数组以使奇数和偶数索引元素的总和相同