常用算法(C语言版)

1、程序设计之常用算法【解析算法含义】所谓解析法（analysis algorithm）是指用解析的方法找出表示问题的前提条件与结果之间关系的数学表达式，并通过表达式的计算来实现问题求解。解析算法【鸡兔同笼 】一个笼子里面关了鸡和兔子（鸡有 2 只脚，兔子有 4 只脚，没有例外）。已经知道了笼子里面脚的总数 a，问笼子里面至少有多少只动物，至多有多少只动物？ 【输入数据】 第 1 行是测试数据的组数 n，后面跟着 n 行输入。每组测试数据占 1 行，包括一个正整数 a (a 32768)。 【输出要求】 n 行，每行输出对应一个输入。输出是两个正整数，第一个是最少的动物数，第二个是最多的动物数，两

2、个正整数用空格分开。如果没有满足要求的情况出现，则输出2个0。 【输入样例 】2 3 20 【输出样例】 0 0 5 10 【解题思路】 这个问题可以描述成任给一个整数 N：如果 N是奇数，输出 0 0如果 N是 4 的倍数，输出 N / 4 N / 2如果 N不是 4的倍数，输出 N/4+1 N/2解析算法【参考程序】1. #include 2. void main( ) 3. 4. int nCases, i, nFeet; /nCases 表示输入测试数据的组数，nFeet表示输入的脚数。 5. scanf(%d, &nCases); 6. for(i = 0; i y，则增加新的箱子+

3、N；5.统计N个箱子中可以放1*1产品的空位数x;6.若1*1产品的数量x，则增加新的箱子+N;7.输出结果N；解析算法1. #include 2. int main() 3. 4. int N, a, b, c, d, e, f, y, x；/N用来存储需要的箱子数目，y用来存储 2*2 的空位数目 5. / x 用来存储 1*1 的空位数目。 6. int u4=0, 5, 3, 1; 7. /数组u 表示3*3 的产品数目分别是 4的倍数，4 的倍数+1, 4 的倍数+2, 4 的倍数+3 8. /时，为3*3的产品打开的新箱子中剩余的 2*2的空位的个数 9. while(1) 10.

4、 scanf(%d%d%d%d%d%d, &a, &b, &c, &d, &e, &f); 11. if (a = 0 & b = 0 & c = 0 & d = 0 & e = 0 & f = 0) break; 12. N = f + e + d + (c + 3) / 4; 13. /这里有一个小技巧 (c+3)/4 正好等于 c 除以4向上取整的结果,下同 14. y = 5 * d + uc % 4; 15. if(b y) N += (b - y + 8 ) / 9; 16. x = 36 * N - 36 * f - 25 * e - 16 * d - 9 * c - 4 * b

5、; 17. if(a x) N += ( a - x + 35 ) / 36; 18. printf(%dn, N); 19. retrun 0;21. 枚举（穷举）算法枚举算法法，本质上就是搜索算法。【基本思想】枚举也称作穷举，指的是从问题所有可能的解的集合中一一枚举各元素。用题目中给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。【优缺点】优点：算法简单，在局部地方使用枚举法，效果十分的好缺点：运算量过大，当问题的规模变大的时候，循环的阶数越大，执行速度越慢。【百钱买百鸡问题】有一个人有一百块钱，打算买一百只鸡。到市场一看，公鸡一只3元,母鸡一只5元,小鸡3只1元,试求

6、用100元买100只鸡,各为多少才合适?根据题意我们可以得到方程组与条件：3X + 5Y + Z/3 = 100；X + Y + Z = 100； （100 X，Y，Z = 0, Z%3 = 0）int x,y,z; for( x = 0; x 100; x+ ) /1000000次循环 for( y = 0; y 100 ; y+ ) for( z = 0; z 0 = x = 0, Z%3 = 0）,因此代码可以优化为下面这样子：for( x = 0; x = 0 ) y /= 7; z = 100 - x - y; if( z % 3 = 0 & 3 * x + 5 * y + z /

7、3 = 100 ) printf(%d %d %dn,x,y,z); 采用枚举的方法进行问题求解，需要注意3个问题：简单数学模型，数学模型中变量数量尽量少，它们之间相互独立。这样问题解的搜索空间的维度就小，反应到程序代码中，循环嵌套的层次就会少。我们上面从3维优化到一维。减少搜索的空间。利用已有知识，缩小数学模型中各个变量的取值范围，避免不必要的计算。反应到程序代码中，循环体被执行的次数少采用合适的搜索顺序。对搜索空间的遍历顺序要与数学模型中的条件表达式一致。枚举（穷举）算法【生理周期问题】人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中

8、有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同天的时间是12，则输出2（注意这里不是3）。 【输入数据 】输入四个整数：p, e, i和d。 p, e, i分别表

9、示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d 是给定的时间，可能小于p, e, 或 i。 所有给定时间是非负的并且小于365, 所求的时间小于21252。当p = e = i = d = -1时，输入数据结束。 【输出要求 】从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）。【样例输入】0 0 0 100 5 20 34 3254 5 6 7 -1 -1 -1 -1【样例输出】Case 1: the next triple peak occurs in 21152 days.Case 2: the next triple peak occurs in 1957

10、5 days. Case 3: the next triple peak occurs in 16994 days. 【解题思路】 本题的关键是理清头绪，理解输入的p、e、i、d的含义： 对于给定时间d，求出某个时间x，使得时间x为给定时间d后第一次同为三个生理周期的高峰。根据题目可得出如下条件： （21252 x = d+1） （x-p）%23= 0，（x-e）%28= 0，（x-i）%33= 0 ）枚举（穷举）算法#include int main() int p, e ,i, d; int x; int num = 1; /变量num存储输入数据的组数 while(1) scanf(%d

11、%d%d%d,&p,&e,&i,&d); if(p=-1 & e=-1 & i=-1 & d=-1) break; for( x=d+1;x=21252;x+) if(x-p)%23=0&(x-e)%28=0&(x-i)%33=0) printf(Case %d: the next triple peak occurs in %d days. ,num,x-d); num+; return 0; 枚举（穷举）算法【垃圾炸弹】2014年足球世界杯期间，为了方便球迷观看比赛，街道上很多路口都放置了直播大屏幕，但是人群散去后总会在这些路口留下一堆垃圾。为此政府决定动用一种最新发明“垃圾炸弹”。这种“

12、炸弹”利用最先进的量子物理技术，爆炸后产生的冲击波可以完全清除波及范围内的所有垃圾，并且不会产生任何其他不良影响。炸弹爆炸后冲击波是以正方形方式扩散的，炸弹威力（扩散距离）以d给出，表示可以传播d条街道。 假设城市的布局为严格的0,1024*0,1024的网格状，由于财政问题，市政府只买得起一枚“垃圾炸弹”，希望你帮他们找到合适的投放地点，使得一次清除的垃圾总量最多。（假设垃圾数量为一个非负整数，且除设置大屏幕的路口以外的地点没有垃圾） 【输入数据 】第1行给出“炸弹”威力d；第2行给出一个整数n，表示设置了大屏幕（有垃圾）的路口数目；接下来n行，每行给出三个数字x，y，i，分别代表路口的坐标

13、（x,y）以及垃圾数量i。点坐标（x,y）保证是有效的（区间在0到1024之间），同一坐标只会给出一次。【输出要求 】输出能清理垃圾最多的投放点数目，以及能够清除的垃圾总量。【样例输入】124 4 106 6 20【样例输出】1 30【数据范围】d=50,n=1000下图是一个d=1的“垃圾炸弹”爆炸后的波及范围排序算法我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。排序算法大体可分为两种：排序算法（内部）比较排序插入排序直接插入排序希尔排序冒泡排序选择排序简单选择排序堆排序快速排序归并排序非比较排序计数排序基数排序当数据规模较大时应采用时间复杂度为O(nlog2n)

14、的排序方法：快速排序、堆排序或归并排序序。快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短。排序算法稳定性的简单形式化定义为：如果Ai = Aj，排序前Ai在Aj之前，排序后Ai还在Aj之前，则称这种排序算法是稳定的。通俗地讲就是保证排序前后两个相等的数的相对顺序不变。排序算法1.插入排序直接插入排序【基本思想】将一个记录插入到已排序好的有序表中，从而得到一个新的记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。【要点】设立哨兵，作为临时存储待排序记录。【具体算法描述

15、】从第一个元素开始，该元素可以认为已经被排序取出下一个元素，在已经排序的元素序列中从后向前扫描如果该元素（已排序）大于新元素，将该元素移到下一位置重复步骤3，直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤25示例：序列 6, 5, 3, 1, 8, 7, 2, 4 进行插入排序的实现过程如下：排序算法【程序实现】/ 分类 - 内部比较排序/ 数据结构 - 数组/ 最差时间复杂度 - 最坏情况为输入序列是降序排列的,此时时间复杂度o(n2)/ 最优时间复杂度 - 最好情况为输入序列是升序排列的,此时时间复杂度o(n)/ 平均时间复杂度 - o(n2)/ 所需辅助空间

16、- o(1)/ 稳定性 - 稳定void insertsort(int a, int n) for (int i = 1; i = 0 & aj get) / 从右向左进行比较 aj + 1 = aj; / 如果当前元素大于哨兵，就将其右移 j-; aj + 1 = get; / 将哨兵放入aj右侧(相等元素的相对次序未变，是稳定的) 排序算法2.插入排序希尔排序(Shell Sort)【基本思想】希尔排序又叫缩小增量排序或递减增量排序，先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2d1

17、重复上述的分组和排序，直至所取的增量dt =1( dt dt-1d2= 1) for (int i = h; i = 0 & aj get) aj + h = aj; j = j - h; aj + h = get; h = h/2; / 递减增量 【程序实现】排序算法3.冒泡排序【基本思想】在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。【具体算法描述】比较相邻的元素

18、，如果前一个比后一个大，就把它们两个调换位置。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。【示例】序列 6, 5, 3, 1, 8, 7, 2, 4 进行冒泡排序的实现过程如下：排序算法/ 分类 - 内部比较排序/ 数据结构 - 数组/ 最差时间复杂度 - o(n2)/ 最优时间复杂度 - 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到o(n)/ 平均时间复杂度 - o(n2)/ 所

19、需辅助空间 - o(1)/ 稳定性 - 稳定void swap(int a, int i, int j) int temp = ai; ai = aj; aj = temp;void bubblesort(int a, int n) for (int j = 0; j n - 1; j+) / 每次最大元素就像气泡一样浮到数组的最后 for (int i = 0; i ai + 1) / 如果条件改成ai = ai + 1,则变为不稳定的排序算法 swap(a, i, i + 1);【程序实现】排序算法4.选择排序简单选择排序【基本思想】在要排序的一组数中，选出最小（或者最大）的一个数与第1个

20、位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。【示例】对序列 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 进行选择排序的实现过程如右图排序算法/ 分类 - 内部比较排序/ 数据结构 - 数组/ 最差时间复杂度 - o(n2)/ 最优时间复杂度 - o(n2)

21、/ 平均时间复杂度 - o(n2)/ 所需辅助空间 - o(1)/ 稳定性 - 不稳定void swap(int a, int i, int j) int temp = ai; ai = aj; aj = temp;void selectionsort(int a, int n) for (int i = 0; i n - 1; i+) / i为已排序序列的末尾 int min = i; for (int j = i + 1; j n; j+) / 未排序序列 if (aj size & aleft_child size & aright_child = 0; i-) / 从每一个非叶结点开始

22、向下进行堆调整 heapify(a, i, heap_size); return heap_size;void heapsort(int a, int n) int heap_size = buildheap(a, n); / 建立一个最大堆 while (heap_size 1) / 堆（无序区）元素个数大于1，未完成排序 / 将堆顶元素与堆的最后一个元素互换，并从堆中去掉最后一个元素 / 此处交换操作很有可能把后面元素的稳定性打乱，所以堆排序是不稳定的排序算法 swap(a, 0, -heap_size); heapify(a, 0, heap_size); / 从新的堆顶元素开始向下进行

23、堆调整，时间复杂度o(logn) 【程序实现】排序算法6.快速排序（Quick Sort）【基本思想】1）选择一个基准元素,通常选择第一个元素。2）通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小，另一部分记录的 元素值比基准值大。3）此时基准元素在其排好序后的正确位置。4）然后分别对这两部分记录用同样的方法继续进行快速排序，直到整个序列有序。【快速排序的示例】（a）一趟排序的过程：int partition(int a, int low, int high) int privotkey = alow; /基准元素 while(low high) /从两端交

24、替地向中间扫描 /从后向前搜索，将较小的元素交换到低端 while(low = privotkey) high-; swap(a,low,high); /从前向后搜索，将较大的元素交换到高端 while(low high & alow = privotkey ) low+; swap(a,low,high); return low; 排序算法（b）排序的全过程void quicksort(int a, int low, int high) if(low mid 或jright，转6 /其中一个数组已归并完，比较选取结束/否则选取ai和aj较小的存入辅助数组af如果ai=aj，afindex=a

25、i； i+； index+； 转2否则，afindex=aj； j+； index+； 转2/将尚未处理完的子表中元素存入af如果i=mid，将aimid存入afindexright /前一数组非空如果j=right , 将ajright 存入afindexright /后一数组非空归并结束，将arleftright存入aleftrightvoid merge(int a, int left, int mid, int right) / 合并两个已排好序的数组aleft.mid和amid+1.right int index=left / 辅助数组ar的起始元素 int i = left; /

26、前一数组的起始元素 int j = mid + 1; / 后一数组的起始元素 while (i = mid & j = right) if(ai = aj) arindex+=ai+; / 带等号保证归并排序的稳定性 else arindex+=aj+; while (i = mid) arindex+ = ai+; while (j = right) arindex+ = aj+; for (i=left; i = right; i+) ai = ari;排序算法/ 分类 - 内部比较排序/ 数据结构 - 数组/ 最差时间复杂度 - o(nlogn)/ 最优时间复杂度 - o(nlogn)/

27、 平均时间复杂度 - o(nlogn)/ 所需辅助空间 - o(n)/ 稳定性 - 稳定void merge(int a, int left, int mid, int right) / 归并两个已排好序的数组 /代码省略void mergesortrecursion(int a, int left, int right) / 递归实现的归并排序(自顶向下) if (left = right) return; / 当待排序的序列长度为1时，递归结束 int mid = (left + right) / 2; mergesortrecursion(a, left, mid); / 前一数组排序

28、mergesortrecursion(a, mid + 1, right); /后一数组排序 merge(a, left, mid, right); /归并两个数组void mergesortiteration(int a, int len) / 非递归(迭代)实现的归并排序(自底向上) int left, mid, right; / 子数组索引,前一个为aleft.mid，后一个子数组为amid+1.right for (int i = 1; i len; i *= 2) / 子数组的大小i初始为1，每轮翻倍 left = 0; while (left + i len) / 后一个子数组存在

29、(需要归并) mid = left + i - 1; right = mid + i len ? mid + i : len - 1; / 后一个子数组大小可能不够 merge(a, left, mid, right); left = right + 1; / 前一个子数组索引向后移动 排序算法8.计数排序【基本思想】计数排序的基本思想为一组数在排序之前先统计这组数中其他数小于这个数的个数，则可以确定这个数的位置。 例如要排序的数为 7 4 2 1 5 3 1 5；则比7小的有7个数，所有7应该在排序好的数列的第八位，同理3在第四位，对于重复的数字，1在1位和2位（暂且认为第一个1比第二个1小

30、），5和1一样位于6位和7位。【计数排序的实现办法】 首先需要三个数组，第一个数组记录A要排序的数列大小为n，第二个数组B要记录比某个数小的其他数字的个数，所以第二个数组的大小应当为K（数列中最大数的大小），第三个数组C为记录排序好了的数列的数组，大小应当为n。接着记录数列中每个数的出现次数到数组B，并通过前面的所有数的出现次数来确定比这个数小的数的个数，从而确定其位置。对于重复的数，每排好一个数则对其位置数进行减1操作，以此对完成其余相同的数字进行排位。【计数排序示例】待排序数列数i出现次数小于等于数i的个数数组A数组B0，1，1，2，3，4，5，7，9数组C排序算法/ 分类 - 内部非比较

31、排序/ 数据结构 - 数组/ 平均时间复杂度 - (n+k)（其中k是整数的范围）/ 所需辅助空间 - o(k+1)/ 稳定性 - 稳定void countsort(int a,int c,int n) int max = 0; for (int i = 0; i max ? ai : max; int b max+1; memset(b, 0, sizeof(b); /初始化数组b元素值为0 for (int i = 0; i n; i+) /统计数ai出现次数 bai+; for (int i = 1; i max + 1; i+) /依次计算范围1,max内小于等于各数的数字个数 bi

32、= bi + bi - 1; for (int i = 0; i n; i+) /将数组a各元素存入排好序的对应位置 bai-; cbai = ai; 排序算法9.基数排序（Radix Sort）先说桶排序：基本思想是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。例如要对大小为1.1000范围内的n个整数A1.n排序 首先，可以把桶设为大小为10的范围，具体而言，设集合B1存储1.10的整数，集合B2存储 (10.20的整数，集合Bi存储( (i-1)*1

33、0, i*10的整数，i = 1,2,.100。总共有 100个桶。 然后，对A1.n从头到尾扫描一遍，把每个Ai放入对应的桶Bj中。 再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任 何排序法都可以。 最后，依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这样就得到所有数字排好序的一个序列了。排序算法【基本思想】将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。 基数排序的方式可以采用LSD（Least significant d

34、igital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。SD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。以LSD为例，假设原来有一串数值如下所示：73, 22, 93, 43, 55, 14, 28, 65, 39, 81第1趟（个位数）第2趟（十位数）桶编号桶数值桶编号桶数值00181114222222，28373，93，43339414443555，6555566657773828881939993接下来将这些桶子中的数值重新串接起来，成为以下的数列：81, 22, 73

35、, 93, 43, 14, 55, 65, 28, 39最后将这些桶子中的数值重新串接起来，即最终的排序结果：14, 22, 28, 39, 43, 55, 65, 73, 81, 93排序算法void radixsort(int a,length,maxradix) int m,n,k,lsp; k=1;m=1; int temp10length-1; empty(temp); /清空临时空间 while(kmaxradix) /遍历所有关键字 for(int i=0;ilength;i+) /分配过程 if(aim) temp0n=ai; else lsp=(ai/m)%10; /确定关键

36、字 templspn=ai; n+; collectelement(a,temp); /收集 n=0; m=m*10; k+; 排序算法各种排序的稳定性，时间复杂度和空间复杂度总结：高精度计算【概念】高精度运算,是指参与运算的数(加数,减数,因子）范围大大超出了标准数据类型（整型，实型）能表示的范围的运算。以整数为例，最大的是long long类型，范围是-263 ,263 )，假如要求范围更大的两个-21000 ,21000 )范围内的数的和，这时就要用到高精度算法了。【高精度运算涉及到的问题】（1）数据的输入（2）数据的存储（3）数据的运算：如加法、乘法进位和减法借位（4）结果的输出：小数

37、点的位置和处理多余的0 当输入的数较长时，采用字符串方式输入将字符串中的每一位数字取出，用数组存储#include /c+中引用字符串类型数据必须该头文件 void init(string s,int a) /将数串s转换为数组a，并倒序存储 a0=s.size(); / 利用数组元素a0存储字符串长度,与s.length()同功能 for(int i=1;i=a0;i+) ai=sa0-i-0; / ai=sa0-i-48;高精度计算【算法分析】（1）运算顺序：两个加数右对齐； 从低位向高位运算相加；（2）运算规则：同一位的数字相加，再加上从低位上来的进位； 和/10为向高位的进位，和%10

38、为该位的值；（3）最高位的进位：最高位相加后进位值不为0， 则和的结果应添加一位；void add(int a,int b,int c) int lenc=1,x=0; /x保存每次相加的进位 while(lenc=a0|lenc=b0) clenc=alenc+blenc+x; /两数相加 x=clenc/10; /进位用于下次相加 clenc+%=10; /该位的结果 if(x=0) lenc-; else clenc=x; /处理最高位相加后的进位 c0=lenc; /保存和的长度 1.高精度加法。输入两个正整数，求他们的和高精度计算/高精度加法 #include #include /c

39、+中引用字符串类型数据必须该头文件 #include using namespace std;#define MAXN 1000 / const int MAXN=1000;int aMAXN,bMAXN,cMAXN;void init(string s,int a) /将数串s转换为数组a，并倒序存储 /代码略void add(int a,int b,int c) /高精度加法计算a+b-c /代码略int main()string a1,b1;getline(cin,a1); /getline函数默认是碰到换行符才结束，可读入空格 cinb1; /碰到空格或换行符结束 memset(a,0

40、,sizeof(a); /要引用cstring头文件 memset(b,0,sizeof(b);memset(c,0,sizeof(c);init(a1,a);init(b1,b);add(a,b,c);for(int i=c0;i=1;i-) coutci; /从高位输出 return 0;高精度计算/高精度加法改良算法，节省存储空间#include #include /c+中引用字符串类型数据必须该头文件 #include using namespace std;#define MAXN 1000 / const int MAXN=1000;int aMAXN,bMAXN;void ini

41、t(string s,int a) /将数串s转换为数组a，并倒序存储 /代码略void add(int a,int b) /高精度加法计算a+b-a int len=1; while(len=a0|lena1;cinb1; /碰到空格或换行符结束 memset(a,0,sizeof(a); memset(b,0,sizeof(b); init(a1,a);init(b1,b);add(a,b);for(int i=a0;i=1;i-) coutai; /从高位输出 return 0;高精度计算【算法分析】（1）减法的输入与存储与加法相同； 字符串输入、数组存储（2）结果位数最大是两个数中较大

42、数的位数； 比较两个数大小、被减数必须比减数大（3）借位处理； 高位减1、当前位加10（4）结果的输出； 符号位、省略高位的02.高精度减法。输入两个正整数，求他们的差/高精度运算的输入与存储#include #include #include using namespace std;#define MAXN 1000 / const int MAXN=1000;int aMAXN,bMAXN;void init(string s,int a) a0=s.size(); for(int i=1;i=a0;i+) ai=sa0-i-0; int main() string a1,b1; getl

43、ine(cin,a1); getline(cin,b1); memset(a,0,sizeof(a); memset(b,0,sizeof(b); init(a1,a); init(b1,b); 判断两个字符串a1、b1大小字符串长度不等，长度较小的字符串小；字符串长度相等，可直接比较a1b1？字符串互换与两个变量的值互换一样；/减法及借位if(alen1) len-;高精度计算/高精度运算 #include /c+中万能头文件 using namespace std;#define MAXN 1000 / const int MAXN=1000;int aMAXN,bMAXN;void init(string s,int a) /将数串s转换为数组a，并倒序存储 /代码略void sub(int a,int b) /高精