| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1214 人关注过本帖
标题:算法看不懂,请大神解释一下
只看楼主 加入收藏
景真
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2017-12-2
收藏
 问题点数:0 回复次数:2 
算法看不懂,请大神解释一下
对于长度相同的两个字符串A,B,其距离定义为相应位置字符距离之和。2个非空格距离是它们的ASCII码之差的绝对值。空格与空格的距离为0,空格与其他字符的距离为一定值k。在一般情况下,字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干空格字符所产生的字符串。在字符串A和B的所有长度相同的扩展中,有一对距离最小的扩展,该距离称为字符串A和B的扩展距离。对于给定的字符串A和B,编程计算其扩展距离。

设字符串A和B的字串A[1..i]和B[1..j]的扩展距离为val(i,j),则val(i,j)具有最优子结构性质,递归式:
val(i,j)=min{val(i,j-1)+k,val(i,j-1)+k,val(i-1,j-1)+dist(a_i,b_j)}
算法:
int comp()
{
 int i,j,tmp,len1,len2;
 val[0][0]=0;len1=strlen(str1);len2=strlen(str2);
 for(i=0;i<=len1;i++)
  for(j=0;j<=len2;j++)
   if(i+j){
    val[i][j]=MAXINT
    if((i*j) && (tmp=val[i-1][j-1]+dist(str1[i-1],str2[j-1]))<val[i][j])
      val[i][j]=tmp;
    if(i && (tmp=val[i-1][j]+dist(str1[i-1],' '))<val[i][j])
      val[i][j]=tmp;
    if(j && (tmp=val[i][j-1]+dist(str2[j-1],' '))<val[i][j])
      val[i][j]=tmp;
                    }
return val[len1][len2];
 }

int main()
{
    readin();
    cout<<comp()<<endl;
    return 0;
 }
请问这个算法的思路是什么啊?我没看懂。
搜索更多相关主题的帖子: 算法 字符串 距离 扩展 tmp 
2017-12-02 12:02
吹水佬
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:451
帖 子:10607
专家分:43186
注 册:2014-5-20
收藏
得分:0 
看不太明,举个例说明一下。
2017-12-02 16:00
liaohs
Rank: 4
等 级:业余侠客
威 望:7
帖 子:61
专家分:292
注 册:2017-11-26
收藏
得分:0 
这个程序有明显错误。
算法就是求最小值。

[此贴子已经被作者于2017-12-4 19:38编辑过]

2017-12-04 18:50
快速回复:算法看不懂,请大神解释一下
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.058060 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved