算法设计实例教程 第5章 字符串和高精度运算.ppt

对于个位a_int[0]，a_int[0]*（i+1）所得数值取其个位保留在a_int[0]，剩余的位作为进位。对于十位位a_int[1]，a_int[1]*（i+1）所得数值再加上个位的进位取其个位保留在a_int[1]，剩余的位作为进位。对于第k位a_int[k-1]，a_int[k-1]*（i+1）所得数值取其个位保留在a_int[k-1]，剩余的位作为进位。5.2.3阶乘的精确计算应用举例时间限制：1000ms内存限制：32MB问题描述输入一个正整数n，输出n!的值。 其中n!=1*2*3*…*n。输入格式 输入包含一个正整数n，n=1000。输出格式 输出n!的准确值。样例输入10样例输出36288005.2.3阶乘的精确计算1#includestdio.h2#includestring.h3#includeiostream4usingnamespacestd;5intmain()6{7intn,a[5000],s,i,j,t,d;8scanf(%d,n);9memset(a,0,sizeof(a));10a[0]=1;11d=1;12for(i=2;i=n;i++)13{14s=0;15for(j=0;jd;j++)16{17t=a[j]*i+s;//当前位置的数之前在这个位置上的数乘以i，18a[j]=t%10;//然后加上前一位数的进位19s=t/10;20}21while(s)22{23a[d++]=s%10;24s/=10;25}26}27for(i=4900;a[i]==0;i--);28for(j=i;j=0;j--)29printf(%d,a[j]);30printf(\n);31return0;32}5.3本章小结随着计算机技术应用的发展，海量数据的处理需求的出现，使得字符匹配算法越来越重要，通常希望匹配算法越快越好。在网络速度迅速发展的今天，基于字符匹配技术的网络应用存在着性能瓶颈，各种各样的匹配算法不断出现提高系统的整体性能是研究和设计者的主要工作。由于现有计算编程语言的数据类型限制，对于大数据的存储能力与计算能力有限。所以进行大数据运算时，大数据计算的一般思路为：将大数据拆分成多个小数据，使用编辑语言能够计算的小数据进行计算，再将小数据合并成大数据。。5.3本章小结**字符串和高精度运算字符串和高精度运算字符串和高精度运算字符串和高精度运算字符串和高精度运算算法设计实例教程教学分析目录CONCENTS第5章字符串和高精度运算第1章数据结构基础第2章基础算法第3章排序算法第4章查找第6章图论算法第7章动态规划算法第8章计算几何基础第9章高级算法字符串匹配是计算机科学中最古老、研究最广泛的问题之一，在信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测等方面具有广泛的应用。本章第一部分重点介绍常见的字符串匹配问题的求解策略。尽管现在的计算机的能力已经非常强大，但依然是有一个上限，它能够表示和处理的数的范围和精度总是有限的，如果在解决实际问题时，所需要处理的数据超出了计算机所能表示的范围，那么这些超出范围的数据在计算机中该如何处理呢？本章的第二部分将介绍大数求和以及阶乘的精确计算等高精度问题的求解方法。第5章字符串和高精度运算在计算机中进行信息的检索实际就是字符串匹配的应用。所谓的检索就是从被检索的文档中找出匹配的信息，被检索文档会显示匹配信息具体的位置。所谓字符串匹配就是在主串中搜索模式串是否存在及其存在的位置。如果在字符串S中查找字符串T，那么字符串S就是主串，字符串T就是模式串。5.1字符串匹配朴素模式匹配算法也称之为暴力(BF，BruteForce)算法。该算法的思想就是将主串S的第一个字符与模式串T的第一个字符进行匹配，如果相等，则比较S的第二个字符和T的第二个字符；若不相等即失配，则将模式串T整体右移一位，再将主串S的第二个字符和T的第一个字符，依次比较，直到得出最后的匹配结果。5.1.1朴素模式匹配下面图示来说明该算法，例如S=“abaacd”,T=“aac”5.1.1朴素模式匹配图5-1第一次匹配主串和模式串的第一个字符相等，进行第二个字符的