پیاده سازی الگوریتم LCS با سی پلاس همراه با داکیومنت پروژه

همراه با داکیومنت فارسی پروژه

قیمت :   ۹۵۰۰ تومان ( نه هزار و پانصد تومان)

رشته :

کامپیوتر

نوع فایل:

CPP ,

توضیحات:


توضیحات :

پیاده سازی الگوریتم LCS با  پلاس همراه با داکیومنت پروژه

الگوریتم LCS از الگوریتم هایی است که برای تشخیص  شباهت دو رشته یا پیداکردن طولانی ترین زیر رشته مشابه از رشته s1 در رشته s2 بکار میرود.

شرح مساله

دو رشته زیر را در نظر بگیرید:


S_{1}=ACCGGTCGAGTGCGCGGAGCCGGCCGAA\,\!


S_{2}=GTCGTTCGGAATGCCGTTGCTCTGTAAA\,\!

هدف مقایسه این دو رشته و پیدا کردن شباهت بین آنها است. بزرگترین زیردنباله مشترک این طور تعریف می‌شود که دنباله‌ای مانند S_{3} است به طوری که حروف موجود در S_{3} با حفظ ترتیب در S_{1} و S_{2} موجود باشد. اما مطلقاً لزومی ندارد که متوالی باشد. از طرفی S_{3} باید بزرگترین دنباله ممکن با خواص بالا باشد. به طور کلی اگر دو رشته X=\langle x_{1},x_{2},... ,x_{n}\rangle و Y=\langle y_{1},y_{2},... ,y_{n}\rangle را در نظر بگیریم٫ یک بلندترین زیر دنباله مشترک را می‌توان با استفاده از برنامهنویسیپویا پیدا کرد.

پیچیدگی زمانی

زمانی که تعداد دنباله‌های ورودی ثابت باشند٫ این مساله توسط پویا در زمان چندجمله‌ای حل می‌شود. فرض کنید N دنباله ورودی به طول n_1,n_2,... ,n_N داشته باشیم. یک راه حل ابتدایی برای جستجوی LCS این است که هر یک از2^{n_1} زیردنباله دنباله اولی را برررسی کنیم که آیا زیر دنباله برای دیگر دنباله‌های ورودی است یا خیر. هر زیر ددنباله در زمانی خطی متناسب با طول دنباله‌های باقی مانده بررسی می‌شود. بنابراین زمان الگوریتم برابر خواهد بود با:O\left(2^{n_1} \sum_{i>1} n_i\right). برای حالت ورودی با دو دنباله با n و m عنصر٫ پیچیدگی زمانی الگوریتم برابر O(mn)\,\! خواهد بود. برای تعداد ورودی‌های دلخواه برنامه نویسی پویا راه حلی با این زمان ارایه می‌کند:O\left(N \prod_{i=1}^{N} n_i\right).

توابعی با پیچیدگی کمتر موجود است.

پیاده سازی الگوریتم LCS با سی پلاس همراه با سورس کامل پروژه و داکیومنت توضیحات فارسی پروژه

همراه با فایلهای EXE , CPP

== تصویری از محیط  فایل اجرایی این پروژه : 

 LCS

 مشاهده بخشهایی از سورس کد این پروژه :

int max(int a, int b);

//***********
int lcs( char *X, char *Y,int m,int n )
{

int **L;
L = new int*[m+1];
for(int k = 0; k < (m+1); k++)
L[k] = new int[n+1];
int i, j;
int maxlen=0;
//***********
cout<<“\n”;
cout<<“substring is: “;
for (i=0; i<=m; i++)
{
for (j=0; j<=n; j++)
{
if (i == 0 || j == 0)
else if(X[i-1] == Y[j-1])
{

L[i][j] = L[i-1][j-1] + 1;
if(L[i][j]>maxlen)
{
cout<<Y[j-1];
maxlen=L[i][j];
}

}
else
L[i][j] = max(L[i-1][j], L[i][j-1]);

}
}
//************
cout<<“\n\n”;
return L[m][n];
}

int max(int a, int b)
{
return (a > b)? a : b;
}

//**************
int main()
{
char X[100];
char Y[100];
cout<<“please enter str1 : “;
gets(X);
cout<<“please enter str2 : “;
gets(Y);

 

دانلود کامل پروژه همراه با فایل سورس کد و فایل اجرایی آن
در تمامی ساعات شبانه روز >> پرداخت آنلاین و دانلود آنلاین پروژه


پذیرش و انجام سفارشات پروژه های شما
شماره تماس پشتیبانی سایت : ۰۹۳۹۲۷۶۱۶۳۰



Related posts

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

Translate »