python 최 장 공공 서브 시퀀스 구현
2228 단어 python최 장 공통 서브 시퀀스
1.최 적 화 된 성질 을 찾아내 고 그 구조 적 특징 을 새긴다.
서열 a 는 모두 m 개의 요소 가 있 고 서열 b 는 모두 n 개의 요소 가 있다.만약 에 a[m-1]=b[n-1]라면 a[m]와 b[n]의 가장 긴 공공 서브 서열 길 이 는 a[m-1]와 b[n-1]의 가장 긴 공공 서브 서열 길이+1 이다.하면,만약,만약...b[n-1],그러면 a[m]와 b[n]의 가장 긴 공공 서브 시퀀스 길 이 는 MAX(a[m-1]와 b[n]의 가장 긴 공공 서브 시퀀스 길이,a[m]와 b[n-1]의 가장 긴 공공 서브 시퀀스 길이)입 니 다.
2.귀속 정의 최 우수 값
3.아래 에서 위로 가장 좋 은 값 을 계산한다.
python 코드 는 다음 과 같 습 니 다:
def lcs(a,b):
lena=len(a)
lenb=len(b)
c=[[0 for i in range(lenb+1)] for j in range(lena+1)]
flag=[[0 for i in range(lenb+1)] for j in range(lena+1)]
for i in range(lena):
for j in range(lenb):
if a[i]==b[j]:
c[i+1][j+1]=c[i][j]+1
flag[i+1][j+1]='ok'
elif c[i+1][j]>c[i][j+1]:
c[i+1][j+1]=c[i+1][j]
flag[i+1][j+1]='left'
else:
c[i+1][j+1]=c[i][j+1]
flag[i+1][j+1]='up'
return c,flag
def printLcs(flag,a,i,j):
if i==0 or j==0:
return
if flag[i][j]=='ok':
printLcs(flag,a,i-1,j-1)
print(a[i-1],end='')
elif flag[i][j]=='left':
printLcs(flag,a,i,j-1)
else:
printLcs(flag,a,i-1,j)
a='ABCBDAB'
b='BDCABA'
c,flag=lcs(a,b)
for i in c:
print(i)
print('')
for j in flag:
print(j)
print('')
printLcs(flag,a,len(a),len(b))
print('') 
실행 결과 출력 은 다음 과 같 습 니 다:
4.계산 에 따라 가장 좋 은 정 보 를 얻 을 수 있 고 구조 가 가장 좋다.
위의 그림 은 운행 결과 이 고 첫 번 째 행렬 은 공공 서브 시퀀스 의 길 이 를 계산 하 는 것 으로 가장 긴 것 은 4 이다.두 번 째 행렬 은 구조 가 가장 좋 은 것 이다.마지막 으로 가장 좋 은 BCBA 를 출력 합 니 다.
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
로마 숫자를 정수로 또는 그 반대로 변환그 중 하나는 로마 숫자를 정수로 변환하는 함수를 만드는 것이었고 두 번째는 그 반대를 수행하는 함수를 만드는 것이었습니다. 문자만 포함합니다'I', 'V', 'X', 'L', 'C', 'D', 'M' ; 문자열이 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
