C语言矩阵转置中的问题，求解！
C语言矩阵转置中的问题，求解！ 10
我写了个矩阵（3*3）转置的程序，以下是核心部分：for(i=0;i&n;i++)&for(i=0;i&n;i++)&for(j=1;j&m;j++)&{& k=p[i][j];& p[i][j]=p[j][i];& p[j][i]=k;& }这样的操作结果是对的，但是如果把for（）中的“j=1”改为"j=0",输出的结果还是原来的矩阵，没有转置。为什么？？
这样不知道行不“for(i=0;i&n;i++) {
for(j=i+1;j&n;j++)
k=a[i][j];
a[i][j]=[j][i];
a[j][i]=k;
j=0时矩阵转置了两次，所以又变回原来的矩阵了
的感言：多谢多谢！
相关知识等待您来回答
编程领域专家当前位置： >
> 获取该类问题最优解的算法问题描述：给定一个N*N的矩阵，其中每个元素有一个权值。现从每一行取一个数
获取该类问题最优解的算法问题描述：给定一个N*N的矩阵，其中每个元素有一个权值。现从每一行取一个数
w3464123 & at
获取该类问题最优解的算法问题描述：给定一个N*N的矩阵，其中每个元素有一个权值。现从每一行取一个数，且每个数位于不同的列，问如何才能得到该N个权值和的最大值。请问有哪些算法可以有效地得到最优解？
lz看看匈牙利方法吧，该问题属于典型的指派问题，可以用匈牙利方法解决，同时也能转化为带权的二分图最大匹配，用km算法解决。w & &
& & （0）（0）
本问题标题：
本问题地址：
温馨提示：本问题已经关闭，不能解答。
暂无合适的专家
&&&&&&&&&&&&&&&
希赛网 版权所有 & &&&&湘教QS2-164&&增值电信业务经营许可证湘B2-张嘉佳|经络|家常菜|中华史|
购买过本书的顾客还买过
定价：￥69.00
广购价：￥55.20
折扣： 80%
节省：￥13.80
浏览过本书的顾客还看过
定价：￥59.90
广购价：￥51.50
折扣： 86%
节省：￥8.40
矩阵计算(英文版第3版)
准备读(0 人)，正在读(0 人)， 已读过(0人)
I S B N ：4
作&&&&者：&&&&&
出 版 社：
出版时间：
版&&&&次：初版
开&&&&本：小16开
包&&&&张：平装
定价：￥89.00
&&&&&&折扣：81%
我的价格：￥72.10
为您节省：￥16.90
广购价：￥72.10
立刻购买']);">
您可以用以下几种方式找到此商品
矩阵计算(英文版第3版)
与此 1 件拍档商品一同购买
总定价：￥89.00
总广购价：￥72.10
请至少保留一件商品。
《矩阵计算(英文版第3版)》内容简介
　　《矩阵计算》一书系统介绍了矩阵计算的基本理论和方法。内容包括矩阵乘法、矩阵分析、线性方程组、正交化和最小二乘法、特征值问题、Lanczos方法、矩阵函数及专题讨论等。本书可作为高等学校数学系高年级本科生和研究生的教材。　　本书系统介绍了矩阵计算的基本理论和方法。内容包括矩阵乘法、矩阵分析、线性方程组、正交化和最小二乘法、特征值问题、Lanczos方法、矩阵函数及专题讨论等。书中的许多算法都有现成的软件包实现，每节后还附有习题，并有注释和大量参考文献。　　本书可作为高等学校数学系高年级本科生和研究生的教材，亦可作为计算数学和工程技术人员的参考用书。
《矩阵计算(英文版第3版)》目录
1MatrixMultiplicationProblems1.1BasicAlgorithmsandNotation1.2ExploitingStructure1.3BlockMatricesandAlgorithms1.4VectorizationandRe-UseIssues2MatrixAnalysis2.1BasicIdeasfromLinearAlgebra2.2VectorNorms2.3MatrixNorms2.4FinitePrecisionMatrixComputations2.5OrthogonalityandtheSVD2.6ProjectionsandtheCSDecomposition2.7TheSensitivityofSquareLinearSystems3GeneralLinearSystems3.1TriangularSystems3.2TheLUFactorization3.3RoundoffAnalysisofGaussianElimination3.4Pivoting3.5ImprovingandEstimatingAccuracy4SpecialLinearSystems4.1TheLDMTandLDLTFactorizations4.2PositiveDefiniteSystems4.3BandedSystems4.4SymmetricIndefiniteSystems4.5BlockSystems4.6VandermondeSystemsandtheFFT4.7ToeplitzandRelatedSystems5OrthogonalizationandLeastSquares5.1HouseholderandGivensMatrices5.2TheQRFactorization5.3TheFullRankLSProblem5.4OtherOrthogonalFactorizations5.5TheRankDeficientLSProblem5.6WeightingandIterativeImprovement5.7SquareandUnderdeterminedSystems6ParallelMatrixComputations6.1BasicConcepts6.2MatrixMultiplication6.3Factorizations4SpecialLinearSystems4.1TheLDMwandLDLwFactorizations4.2PositiveDefiniteSystems4.3BandedSystems4.4SymmetricIndefiniteSystems4.5BlockSystems4.6VandermondeSystemsandtheFFT4.7ToeplitzandRelatedSystems5OrthogonalizationandLeastSquares5.1HouseholderandGivensMatrices5.2TheQRFactorization5.3TheFullRankLSProblem5.4OtherOrthogonalFactorizations5.5TheRankDeficientLSProblem5.6WeightingandIterativeImprovement5.7SquareandUnderdeterminedSystems6ParallelMatrixComputation6.1BasicConcepts6.2MatrixMultiplication6.3Factorizations7TheUnsymmetricEigenvalueProblem7.1PropertiesandDecompositions7.2PerturbationTheory7.3PowerIterations7.4TheHessenbergandRealSchurForms7.5ThePracticalQRAlgorithm7.6InvariantSubspaceComputations7.7TheQZMethodforAx=ABx8TheSymmetricEigenvalueProblem8.1PropertiesandDecompositions8.2PowerIterations8.3TheSymmetricQRAlgorithm8.4JacobiMethods8.5TridiagonalMethods8.6ComputingtheSVD8.7SomeGeneralizedEigenvalueProblems9LanczosMethods9.1DerivationandConvergenceProperties9.2PracticalLanczosProcedures9.3ApplicationstoAx=bandLeastSquares9.4ArnoldiandUnsymmetricLanczos10IterativeMethodsforLinearSystems10.1TheStandardIterations910.2TheConjugateGradientMethod10.3PreconditionedConjugateGradients10.4OtherKrylovSubspaceMethods11FunctionsofMatrices11.1EigenvalueMethods11.2ApproximationMethods11.3TheMatrixExponential12SpecialTopics12.1ConstrainedLeastSquares12.2SubsetSelectionUsingtheSVD12.3TotalLeastSquares12.4ComputingSubspaceswiththeSVD12.5UpdatingMatrixFactorizations12.6Modified/StructuredEignproblemsIndex
购买过本书的顾客还买过
广州购书中心有限公司 版权所有& 2010 经营许可证：粤B2-数学之美 系列十八 － 矩阵运算和文本处理中的分类有关问题_服务器性能评价_计算字符串的形似度-两种解法__脚本百事通
稍等，加载中……
^_^请注意，有可能下面的2篇文章才是您想要的内容：
数学之美 系列十八 － 矩阵运算和文本处理中的分类有关问题
服务器性能评价
计算字符串的形似度-两种解法
数学之美 系列十八 － 矩阵运算和文本处理中的分类有关问题
数学之美 系列十八 － 矩阵运算和文本处理中的分类问题我在大学学习线性代数时，实在想不出它除了告诉我们如何解线性方程外，还能有什么别的用途。关于矩阵的许多概念，比如特征值等等，更是脱离日常生活。后来在数值分析中又学了很多矩阵的近似算法，还是看不到可以应用的地方。当时选这些课，完全是为了混学分的学位。我想，很多同学都多多少少有过类似的经历。直到后来长期做自然语言处理的研究，我才发现数学家们提出那些矩阵的概念和算法，是有实际应用的意义的。在自然语言处理中，最常见的两类的分类问题分别是，将文本按主题归类（比如将所有介绍亚运会的新闻归到体育类）和将词汇表中的字词按意思归类（比如将各种体育运动的名称个归成一类）。这两种分类问题都可用通过矩阵运算来圆满地、同时解决。为了说明如何用矩阵这个工具类解决这两个问题的，让我们先来来回顾一下我们在余弦定理和新闻分类中介绍的方法。分类的关键是计算相关性。我们首先对两个文本计算出它们的内容词，或者说实词的向量，然后求这两个向量的夹角。当这两个向量夹角为零时，新闻就相关；当它们垂直或者说正交时，新闻则无关。当然，夹角的余弦等同于向量的内积。从理论上讲，这种算法非常好。但是计算时间特别长。通常，我们要处理的文章的数量都很大，至少在百万篇以上，二次回标有非常长，比如说有五十万个词（包括人名地名产品名称等等）。如果想通过对一百万篇文章两篇两篇地成对比较，来找出所有共同主题的文章，就要比较五千亿对文章。现在的计算机一秒钟最多可以比较一千对文章，完成这一百万篇文章相关性比较就需要十五年时间。注意，要真正完成文章的分类还要反复重复上述计算。在文本分类中，另一种办法是利用矩阵运算中的奇异值分解（Singular Value Decomposition，简称 SVD)。现在让我们来看看奇异值分解是怎么回事。首先，我们可以用一个大矩阵A来描述这一百万篇文章和五十万词的关联性。这个矩阵中，每一行对应一篇文章，每一列对应一个词。在上面的图中，M=1,000,000，N=500,000。第 i 行，第 j 列的元素，是字典中第 j 个词在第 i 篇文章中出现的加权词频（比如，TF/IDF)。读者可能已经注意到了，这个矩阵非常大，有一百万乘以五十万，即五千亿个元素。奇异值分解就是把上面这样一个大矩阵，分解成三个小矩阵相乘，如下图所示。比如把上面的例子中的矩阵分解成一个一百万乘以一百的矩阵X，一个一百乘以一百的矩阵B，和一个一百乘以五十万的矩阵Y。这三个矩阵的元素总数加起来也不过1.5亿，仅仅是原来的三千分之一。相应的存储量和计算量都会小三个数量级以上。三个矩阵有非常清楚的物理含义。第一个矩阵X中的每一行表示意思相关的一类词，其中的每个非零元素表示这类词中每个词的重要性（或者说相关性），数值越大越相关。最后一个矩阵Y中的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩阵则表示类词和文章雷之间的相关性。因此，我们只要对关联矩阵A进行一次奇异值分解，w 我们就可以同时完成了近义词分类和文章的分类。（同时得到每类文章和每类词的相关性）。现在剩下的唯一问题，就是如何用计算机进行奇异值分解。这时，线性代数中的许多概念，比如矩阵的特征值等等，以及数值分析的各种算法就统统用上了。在很长时间内，奇异值分解都无法并行处理。（虽然 Google 早就有了MapReduce 等并行计算的工具，但是由于奇异值分解很难拆成不相关子运算，即使在 Google 内部以前也无法利用并行计算的优势来分解矩阵。）最近，Google 中国的张智威博士和几个中国的工程师及实习生已经实现了奇异值分解的并行算法，我认为这是 Google 中国对世界的一个贡献。
服务器性能评价
服务器性能评估来自：/blog/1024360
工作这么久了，主要就是服务器端的开发，由于业务性质，对于性能的考虑是每天不得不面对的问题，每次出方案，都是以预估总pv、单机支持最大并发、预计机器资源。。。。。。等等一系列问题开始，所以程序运行中单个函数的耗时，上线后整体性能的观察都非常重要。经过一段时间的积累和同事的指点，把相关的内容记录下，也与有同样需求的同学分享，共同进步。
一：首先，可已从如下四个方面观察你的服务器机器目前的性能情况：
3，磁盘I/O带宽
4，网络I/O带宽
二：其次，要对如何评估系统性能有个基本的标准，经过一段时间的观察，归纳如下：
1，对于CPU，正常情况（非高峰期）下， user% + sys% & 60% 是很好的情况
也许你会问，为什么要小于60%，剩余的40%做什么？这个是业务性质决定的，tx的业务都是有时间段高峰期的，比如早九点-十点，晚八点-十点，是用户访问高峰期，我们要保证服务器能够处理尖峰并发，所以大多时候有30%~40%的空闲是可以接受而且是必须的。当你的服务器在平时cpu使用率一直&80%，那就要不得不考虑扩容或者程序本身性能优化了调皮。
2，对于内存，同样正常情况下，Swap In（si）＝0，Swap Out（so）＝0是很好的情况，当然允许偶尔的尖峰，但是曲线要相对平滑，消峰是很有必要的。如果出现 Per CPU with 10 page/s，那么就要重点观察了。
3，对于磁盘，正常情况下，iowait % & 25%是很好的情况，如果长期&40%,那么就会影响反映能力了
%user：表示CPU处在用户模式下的时间百分比。
%sys：表示CPU处在系统模式下的时间百分比。
%iowait：表示CPU等待输入输出完成时间的百分比。
swap in：即si，表示虚拟内存的页导入，即从SWAP DISK交换到RAM
swap out：即so，表示虚拟内存的页导出，即从RAM交换到SWAP DISK。
三：接下来介绍，在工作中常用到的性能分析工具， 有些常用的系统命令：
vmstat、sar、iostat、netstat、free、ps、top等
工作中，我比较常用的组合方式为：
用vmstat、sar、iostat检测是否是CPU瓶颈
2，用free、vmstat检测是否是内存瓶颈
3，用iostat检测是否是磁盘I/O瓶颈
4， 用netstat检测是否是网络带宽瓶颈
通常，会用命令uptime，看下总体cpu使用情况，例如我其中一台线上机器情况
up 580 days
load average: 1.24, 1.44, 1.67
重点关注，load average
，这三个值的大小一般不能大于系统CPU的个数，例如，本输出中系统有4个CPU,如果load average的三个值长期大于4时，说明CPU很繁忙，负载很高，可能会影响系统性能，但是偶尔大于4时，倒不用担心，一般不会影响系统性能。相反，如果load average的输出值小于CPU的个数，则表示CPU还有空闲的时间片，比如本例中的输出，CPU是非常空闲的，为下次业务放量最准备，哈哈。
用vmstat 详细分析cpu的性能：用该命令分析我线上机器 vmstat 1 procs -----------memory---------- ---swap-- -----io---- -system-- -----cpu------ r
cs us sy id wa st 2
0 解释下： Procs
r：列表示运行和等待cpu时间片的进程数，这个值如果长期大于系统CPU的个数，说明CPU不足，需要增加CPU。
b：列表示在等待资源的进程数，比如正在等待I/O、或者内存交换等。 Cpu
us：列显示了用户进程消耗的CPU 时间百分比。us的值比较高时，说明用户进程消耗的cpu时间多，但是如果长期大于50%，就需要考虑优化程序或算法。
sy：列显示了内核进程消耗的CPU时间百分比。Sy的值较高时，说明内核消耗的CPU资源很多。
根据经验，us+sy的参考值为70%，如果us+sy大于 70%说明可能存在CPU资源不足。 Memory
swpd: 虚拟内存使用情况，单位：KB
free: 空闲的内存，单位KB
buff: 被用来做为缓存的内存数，一般对块设备的读写才需要缓冲,单位：KB
cache:表示page cached的内存数量，一般作为文件系统cached，频繁访问的文件都会被cached，如果cache值较大，说明cached的文件数较多，如果此时IO中bi比较小，说明文件系统效率比较好。 Swap
si: 从磁盘交换到内存的交换页数量，单位：KB/秒
so: 从内存交换到磁盘的交换页数量，单位：KB/秒 I/O
bi: 发送到块设备的块数，单位：块/秒
bo: 从块设备接收到的块数，单位：块/秒 System
in: 每秒的中断数，包括时钟中断
cs: 每秒的环境（上下文）切换次数 注意：如果 r经常大于 4 ，且id经常少于40，表示cpu的负荷很重。
如果si，so 长期不等于0，表示内存不足。
如果disk 经常不等于0， 且在 b中的队列 大于3， 表示 io性能不好。
2） 用sar分析cpu性能，sar是个非常强大的工具，可以对系统的每个方面进行单独的统计，但是使用sar命令会增加系统开销，不过这些开销是可以评估的，对系统的统计结果不会有很大影响。 sar -u 1 4 Linux 2.6.16.60-0.21-TENCENT-090803 (RS_Server_vip)
04/28/11 21:06:13
%idle 21:06:14
77.72 21:06:15
80.40 21:06:16
78.80 21:06:17
80.00 Average:
79.23 对上面每项的输出解释如下：
%user列显示了用户进程消耗的CPU 时间百分比。
%nice列显示了运行正常进程所消耗的CPU 时间百分比。
%system列显示了系统进程消耗的CPU时间百分比。
%iowait列显示了IO等待所占用的CPU时间百分比
%steal列显示了在内存相对紧张的环境下pagein强制对不同的页面进行的steal操作 。
%idle列显示了CPU处在空闲状态的时间百分比。 有的时候会遇到cpu很空闲，但是性能低下的情况，可能是由于开的进程数小于你cpu的数目，通常web svr进程都会开的很大，因为会调用很多后台服务，属于io类型偏多，逻辑处理偏少的，例如我线上web svr 是240个proc，但逻辑svr通常进程数相对小，因为逻辑处理是耗cpu型的，如果是异步的通常是4个proc，同步的16-32个不等。进程数与服务器性能也是息息相关的。 3）内存性能评估free free -m
cached Mem:
1263 -/+ buffers/cache:
7076 Swap:
1870 注意：一般有这样一个经验公式：应用程序可用内存/系统物理内存&70%时，表示系统内存资源非常充足，不影响系统性能，应用程序可用内存/系统物理内存&20%时，表示系统内存资源紧缺，需要增加系统内存，20%&应用程序可用内存/系统物理内存&70%时，表示系统内存资源基本能满足应用需求，暂时不影响系统性能。 同样也可以用vmstat观察内存情况，重点关注si，so的值 4）i/o性能评估iostat命令 iostat -d 2 Linux 2.6.16.60-0.21-TENCENT-090803 (RS_Server_vip)
04/28/11 Device:
Blk_read/s
Blk_wrtn/s
Blk_wrtn sda
Blk_read/s
Blk_wrtn/s
Blk_wrtn sda
Blk_read/s
Blk_wrtn/s
Blk_wrtn sda
224 对上面每项的输出解释如下：
Blk_read/s表示每秒读取的数据块数。
Blk_wrtn/s表示每秒写入的数据块数。
Blk_read表示读取的所有块数。
Blk_wrtn表示写入的所有块数。
注意：1：可以通过Blk_read/s和Blk_wrtn/s的值对磁盘的读写性能有一个基本的了解，如果Blk_wrtn/s值很大，表示磁盘的写操作很频繁，可以考虑优化磁盘或者优化程序，如果Blk_read/s值很大，表示磁盘直接读取操作很多，可以将读取的数据放入内存中进行操作。
2：对于这两个选项的值没有一个固定的大小，根据系统应用的不同，会有不同的值，但是有一个规则还是可以遵循的：长期的、超大的数据读写，肯定是不正常的，这种情况一定会影响系统性能。 5）I/O性能评估sar sar -d 2 3 Linux 2.6.16.60-0.21-TENCENT-090803 (RS_Server_vip)
04/28/11 21:24:24
%util 21:24:26
5.74 21:24:26
%util 21:24:28
0.00 21:24:28
%util 21:24:30
2.99 Average:
%util Average:
2.92 需要重点关注的几个参数含义：
await表示平均每次设备I/O操作的等待时间（以毫秒为单位）。
svctm表示平均每次设备I/O操作的服务时间（以毫秒为单位）。
%util表示一秒中有百分之几的时间用于I/O操作。 对以磁盘IO性能，一般有如下评判标准： 注意： 正常情况下svctm应该是小于await值的，而svctm的大小和磁盘性能有关，CPU、内存的负荷也会对svctm值造成影响，过多的请求也会间接的导致svctm值的增加。
await值的大小一般取决与svctm的值和I/O队列长度以及I/O请求模式，如果svctm的值与await很接近，表示几乎没有I/O等待，磁盘性能很好，如果await的值远高于svctm的值，则表示I/O队列等待太长，系统上运行的应用程序将变慢，此时可以通过更换更快的硬盘来解决问题。
%util项的值也是衡量磁盘I/O的一个重要指标，如果%util接近100%，表示磁盘产生的I/O请求太多，I/O系统已经满负荷的在工作，该磁盘可能存在瓶颈。长期下去，势必影响系统的性能，可以通过优化程序或者通过更换更高、更快的磁盘来解决此问题。 6）网络性能netstat，重用的几种方式为： netstat -s 统计不同协议否有丢包 netstat -nlp Rev-Q是否有未读取的数据 netstat -antl
所有tcp连接状况 注意：可以通过netstat查看是否timewait过多的情况，导致端口不够用，在短连接服务中且大并发情况下，要不系统的如下两个选项打开，允许端口重用 cat tcp_tw_recycle 1 cat tcp_tw_reuse 7) 网络接收详细情况tcpdump 如果想要获取主机210.27.48.1除了和主机210.27.48.2之外所有主机通信的ip包，使用命令： #tcpdump ip host 210.27.48.1 and ! 210.27.48.2 如果想要获取主机210.27.48.1接收或发出的telnet包，使用如下命令： #sudo tcpdump
-i eht1 -Xnns0 tcp port 23 host 210.27.48.1
计算字符串的形似度-两种解法
计算字符串的相似度-两种解法一直不理解，为什么要计算两个字符串的相似度呢。什么叫做两个字符串的相似度。经常看别人的博客，碰到比较牛的人，然后就翻了翻，终于找到了比较全面的答案和为什么要计算字符串相似度的解释。因为搜索引擎要把通过爬虫抓取的页面给记录下来，那么除了通过记录url是否被访问过之外，还可以这样，比较两个页面的相似度，因为不同的url中可能记录着相同的内容，这样，就不必再次记录到搜索引擎的存储空间中去了。还有，大家毕业的时候都写过论文吧，我们论文的查重系统相信也会采用计算两个字符串相似度这个概念。
以下叙述摘自编程之美一书：
许多程序会大量使用字符串。对于不同的字符串，我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为：
1.修改一个字符（如把“a”替换为“b”）;　　
2.增加一个字符（如把“abdd”变为“aebdd”）;
3.删除一个字符（如把“travelling”变为“traveling”）;比如，对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。上面的两种方案，都仅需要一 次 。把这个操作所需要的次数定义为两个字符串的距离，而相似度等于“距离+1”的倒数。也就是说，“abcdefg”和“abcdef”的距离为1，相似度 为1/2=0.5。给定任意两个字符串，你是否能写出一个算法来计算它们的相似度呢？
原文的分析与解法　　
　　 不难看出，两个字符串的距离肯定不超过它们的长度之和（我们可以通过删除操作把两个串都转化为空串）。虽然这个结论对结果没有帮助，但至少可以知道，任意两个字符串的距离都是有限的。我们还是就住集中考虑如何才能把这个问题转化成规模较小的同样的子问题。如果有两个串A=xabcdae和B=xfdfa，它们的第一个字符是 相同的，只要计算A[2,...,7]=abcdae和B[2,...,5]=fdfa的距离就可以了。但是如果两个串的第一个字符不相同，那么可以进行
如下的操作（lenA和lenB分别是A串和B串的长度）。
1.删除A串的第一个字符，然后计算A[2,...,lenA]和B[1,...,lenB]的距离。
2.删除B串的第一个字符，然后计算A[1,...,lenA]和B[2,...,lenB]的距离。
3.修改A串的第一个字符为B串的第一个字符，然后计算A[2,...,lenA]和B[2,...,lenB]的距离。
4.修改B串的第一个字符为A串的第一个字符，然后计算A[2,...,lenA]和B[2,...,lenB]的距离。
5.增加B串的第一个字符到A串的第一个字符之前，然后计算A[1,...,lenA]和B[2,...,lenB]的距离。
6.增加A串的第一个字符到B串的第一个字符之前，然后计算A[2,...,lenA]和B[1,...,lenB]的距离。
在这个题目中，我们并不在乎两个字符串变得相等之后的字符串是怎样的。所以，可以将上面的6个操作合并为：
1.一步操作之后，再将A[2,...,lenA]和B[1,...,lenB]变成相字符串。
2.一步操作之后，再将A[2,...,lenA]和B[2,...,lenB]变成相字符串。
3.一步操作之后，再将A[1,...,lenA]和B[2,...,lenB]变成相字符串。
通过以上1和6,2和5，3和4的结合操作，最后两个字符串每个对应的字符会相同，但是这三种操作产生的最终的两个字符串是不一样的。我们不知道通过上述的三种结合那种使用的操作次数是最少的。所以我们要比较操作次数来求得最小值。
下面这幅图是摘自编程之美：从中我们可以看出一些信息。
可以看到，在计算的过程中，有索引越界的情况，抓住这个特点，就可以尽早的结束程序，同时还有重复计算的情况，比如(strA, 2, 2, strB, 2, 2).为了减少计算的次数，可以采用临时数组存储中间的结果。下面给出程序：
#include&stdio.h&
#include&stdlib.h&
#include&string.h&
int min(int a, int b, int c) {
if(a & b) {
int compute_distance(char *strA, int pABegin, int pAEnd, char *strB, int pBBegin, int pBEnd, int **temp) {
if(pABegin & pAEnd) {
if(pBBegin & pBEnd) {
return pBEnd - pBBegin + 1;
if(pBBegin & pBEnd) {
if(pABegin & pAEnd) {
return pAEnd - pABegin + 1;
if(strA[pABegin] == strB[pBBegin]) {
if(temp[pABegin + 1][pBBegin + 1] != 0) {
a = temp[pABegin + 1][pBBegin + 1];
a = compute_distance(strA, pABegin + 1, pAEnd, strB, pBBegin + 1, pBEnd, temp);
if(temp[pABegin + 1][pBBegin + 1] != 0) {
a = temp[pABegin + 1][pBBegin + 1];
a = compute_distance(strA, pABegin + 1, pAEnd, strB, pBBegin + 1, pBEnd, temp);
temp[pABegin + 1][pBBegin + 1] =
if(temp[pABegin + 1][pBBegin] != 0) {
b = temp[pABegin + 1][pBBegin];
b = compute_distance(strA, pABegin + 1, pAEnd, strB, pBBegin, pBEnd, temp);
temp[pABegin + 1][pBBegin] =
if(temp[pABegin][pBBegin + 1] != 0) {
c = temp[pABegin][pBBegin + 1];
c = compute_distance(strA, pABegin, pAEnd, strB, pBBegin + 1, pBEnd, temp);
temp[pABegin][pBBegin + 1] =
return min(a, b, c) + 1;
void main() {
char a[] = "efsdfdabcdefgaabcdefgaabcdefgaabcdefgasfabcdefgefsdfdabcdefgaabcdefgaabcdefgaabcdefgasfabcdefg";
char b[] = "efsdfdabcdefgaabcdefgaaefsdfdabcdefgaabcdefgaabcdefgaabcdefgasfabcdabcdefggaabcdefgasfabcdefg";
int len_a = strlen(a);
int len_b = strlen(b);
int **temp = (int**)malloc(sizeof(int*) * （len_a + 1）);
for(int i = 0; i & len_a + 1; i++) {
temp[i] = (int*)malloc(sizeof(int) * (len_b + 1));
memset(temp[i], 0, sizeof(int) * (len_b + 1));
memset(temp, 0, sizeof(temp));
int distance = compute_distance(a, 0, len_a - 1, b, 0, len_b - 1, temp);
printf("%d\n", distance);
之所以在return min(a, b, c) + 1,进行加1的操作，是为了表示在当前两个对应位置的字符不相等的时候，我们采取了一次操作，不管是上述6种情况中的哪一种。而当两个字符相等的时候，就不需要加1，因为没有进行操作。这种方法是从前向后的操作，还有一种就是采用动态规划的形式。如果想理解动态规划的这种方式，建议先学习求两个字符串的最常公共子序列。所谓最常公共子序列就是给定两个字符串s1，s2，找出一个最常的字符串s3，s3中的每个字符同时在s1，s2中出现，但是不必连续。下面给出应用动态规划解决字符串相似度的解释和程序源码.
设Ai为字符串A(a1a2a3 … am)的前i个字符（即为a1,a2,a3 … ai）
设Bj为字符串B(b1b2b3 … bn)的前j个字符（即为b1,b2,b3 … bj）
设 L(i,j)为使两个字符串和Ai和Bj相等的最小操作次数。
当ai==bj时 显然 L(i,j) = L(i-1,j-1)
当ai!=bj时
若将它们修改为相等，则对两个字符串至少还要操作L(i-1,j-1)次
若删除ai或在bj后添加ai，则对两个字符串至少还要操作L(i-1,j)次
若删除bj或在ai后添加bj，则对两个字符串至少还要操作L(i,j-1)次
此时L(i,j) = min( L(i-1,j-1), L(i-1,j), L(i,j-1) ) + 1
显然，L(i,0)=i，L(0,j)=j, 再利用上述的递推公式，可以直接计算出L(i,j)值。L(i,0)代表Ai和B0，如果想把一个字符串和一个空字符串变的相同，那么之后删除非空串中的字符或者把空串变成和非空串相同的字符串，那么所需要操作的次数为i次。
#include&stdio.h&
#include&stdlib.h&
#include&string.h&
int min(int a, int b, int c) {
if(a & b) {
int compute_distance(char *strA, int len_a, char *strB, int len_b, int **temp) {
for(i = 1; i &= len_a; i++) {
temp[i][0] =
for(j = 1; j &= len_b; j++) {
temp[0][j] =
temp[0][0] = 0;
for(i = 1; i &= len_a; i++) {
for(j = 1; j &= len_b; j++) {
if(strA[i -1] == strB[j - 1]) {
temp[i][j] = temp[i - 1][j - 1];
temp[i][j] = min(temp[i - 1][j], temp[i][j - 1], temp[i - 1][j - 1]) + 1;
return temp[len_a][len_b];
void main() {
char a[] = "efsdfdabcdefgaabcdefgaabcdefgaabcdefgasfabcdefgefsdfdabcdefgaabcdefgaabcdefgaabcdefgasfabcdefg";
char b[] = "efsdfdabcdefgaabcdefgaaefsdfdabcdefgaabcdefgaabcdefgaabcdefgasfabcdabcdefggaabcdefgasfabcdefg";
int len_a = strlen(a);
int len_b = strlen(b);
int **temp = (int**)malloc(sizeof(int*) * (len_a + 1));
for(int i = 0; i & len_a + 1; i++) {
temp[i] = (int*)malloc(sizeof(int) * (len_b + 1));
memset(temp[i], 0, sizeof(int) * (len_b + 1));
int distance = compute_distance(a, len_a, b, len_b, temp);
printf("%d\n", distance);
最终两个解法的运行结果是一样的。敬请读者验证。
如果您想提高自己的技术水平，欢迎加入本站官方1号QQ群：&&，&&2号QQ群：，在群里结识技术精英和交流技术^_^
本站联系邮箱：