【算法与数据结构实战】模拟竖式加法,自定义位数

简介: 一直以来跟别人提起模拟竖式加减法都是只提一个思路,把几位放到数组里,然后怎么怎么样,但说实话还从来没实战过。网上有很多不限位数的模拟方法,基本上都是用链表。但这样实际使用上反而会比较慢,而且其实大位数不限量也不是一个很关键的点,主要是为了突破int范围去显示。

一直以来跟别人提起模拟竖式加减法都是只提一个思路,把几位放到数组里,然后怎么怎么样,但说实话还从来没实战过。

网上有很多不限位数的模拟方法,基本上都是用链表。但这样实际使用上反而会比较慢,而且其实大位数不限量也不是一个很关键的点,主要是为了突破int范围去显示。所以这次只是通过定义位数的方式去模拟。

思路就是定义一个int数组,每个数组每一个元素存储一位。代码见下:

 1 #include "stdafx.h"
 2 #include <iostream>
 3 #include <vector>
 4 #include <algorithm>
 5 #include <cstdio>
 6 #include <string>
 7 #define MAXSIZE 100//最大位数
 8 #pragma warning(disable:4996)
 9 
10 using namespace std;
11 
12 int main()
13 {
14     int num1[MAXSIZE] = { 0 }, num2[MAXSIZE] = { 0 }, sum[MAXSIZE + 1] = { 0 };
15     int size1, size2, size3;
16     char t;
17     char s1[MAXSIZE+1], s2[MAXSIZE+1];
18     gets_s(s1);
19     gets_s(s2);
20     /*测试用例,填满最大长度9
21     memset(s1, '9', sizeof(s1));
22     s1[MAXSIZE] = '\0';
23     memset(s2, '9', sizeof(s2));
24     s2[MAXSIZE] = '\0';
25     */
26     size1 = strlen(s1);
27     size2 = strlen(s2);
28     for (int i = 0; i < size1; i++)
29     {
30         num1[size1-1-i] = s1[i] - 48;//转换字符到数字
31     }
32     for (int i = 0; i < size2; i++)
33     {
34         num2[size2 - 1 - i] = s2[i] - 48;//转换字符到数字
35     }
36     if (size1 > size2) size3 = size1;
37     else size3 = size2;
38     for (int i = 0; i < size3; i++)
39     {
40         sum[i] += num1[i] + num2[i];
41         if (sum[i] >= 10) {//如果发生进位,则舍去10,向高位进1
42             sum[i + 1] = 1;
43             sum[i] -= 10;
44         }
45     }
46     if (sum[size3] == 0) size3--;
47     for (int i = size3; i >= 0; i--)
48     {
49         cout << sum[i];
50     }
51     cout << endl;
52     system("pause");
53     return 0;
54 }

 处理这个问题中还有很多问题,大概整理如下:

1.一个是输入问题,涉及到字符串到字符到数字的转换。由于确定了位数,所以我没有定义字符串,定义的是字符数组,通过gets_s函数获得字符串输入,然后再塞进字符数组。字符转数字使用ascii码-48的方式。

2.一个是输入完的字符数组转换到数字的数组,为了之后循环方便和竖式相加的时候是末尾对齐,所以这里得要做一个反循环(见代码),最后输入的数字首位被放到了数字数组的末尾。

3.一个是进位问题,基本的处理思路是,在相加的时候如果发现当前位数字大于10,减去10存储到当前位,让下一位置1。但是当前位还要考虑来自上一位的进位,所以首先给数字数组每个置0,当前位等于当前位本身的数+加数1当前位+加数2当前位。并且还要考虑到最高位发生进位,所以和的数组应该位数比加数的数组最大位+1.

4.鲁棒性问题,除了要考虑最高位溢出,还要考虑用户不正常输入,以及负数输入。基本思路就是,获取输入流之后放到一个字符串中(目前程序内已经做了),判定每一位ascii码是否符合范围。同时,如果允许负数输入,则第一位为‘-’的话,不属于异常。目前程序内没有加入。

为了方便测试边界条件,需要编写测试样例。本代码中使用的方法是通过memset对数组内元素统一置‘9’,之后通过设置末尾为‘\0’截断。经测试在全9的时候,没有发生溢出。程序符合基本要求。

目录
相关文章
|
1月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
58 9
 算法系列之数据结构-二叉树
|
1月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
66 3
 算法系列之数据结构-Huffman树
|
1月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
84 22
|
2月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
112 29
|
2月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
144 25
|
2月前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
115 23
|
4月前
|
存储 运维 监控
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
113 20
|
3月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
129 2
|
5月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
145 58
|
3月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
242 77
下一篇
oss创建bucket