کمک در مورد تحلیل چند برنامه به زبان c++

[miss.mini]

سلام و خسته نباشید
من اولین باره اینجا تاپیک میزنم و به شدت نیازمند کمک هستم
چند برنامه دارم که میخوام تحلیل بشه برام :ناراحت: خودمم که نمیفهمم چی میگه :افسرده: یه بنده خدایی پیدا بشه به من کمک کنه وقت تحویل به استاد لنگ نمونم:ناراحت:
5 تا برنامه س که شامل جستجوی دودویی .. الگوریتم کوله پشتی ... الگوریتم کروسکال ... الگوریتم فلوید و ماتریس استراسن هست :ناراحت:
تو رو خدا کمک کنید فقط یه امروز رو وقت دارم :افسرده:
اینم لینک دانلود برنامه هاست
http://uplod.ir/9ypu2g0voyys/barnameha.rar.htm
:ناراحت:
پیشاپیش ممنون ازتون

[miss.mini]

کسی نبود به ما کمک کنه؟ :افسرده::ناراحت:

[amirtork]

سلام،
شما شروع کن به تحلیل، اگر جاییش رو مشکل داشتی من در خدمت هستم.
ماشالله برنامه هارو هم که میخواید تحویل بدید به استاد خودتون ننوشتید، هرچند اگر خودتون مینوشتید که دیگ تو تحلیل مشکلی نبود :چشمک: این استادا تکلیف میدن دانشجو ها بنویسن که یاد بگیرن بعد دانشجو ها کپی میکنن تحویل استاد میدن!

[miss.mini]

سلام،
شما شروع کن به تحلیل، اگر جاییش رو مشکل داشتی من در خدمت هستم.
ماشالله برنامه هارو هم که میخواید تحویل بدید به استاد خودتون ننوشتید، هرچند اگر خودتون مینوشتید که دیگ تو تحلیل مشکلی نبود :چشمک: این استادا تکلیف میدن دانشجو ها بنویسن که یاد بگیرن بعد دانشجو ها کپی میکنن تحویل استاد میدن!
مشکل اینجاست استاد در مورد دو الگوریتم کروسکال و کوله پشتی چیزی به ما نگفته . یه تعریف ساده که اصلا ربطی به برنامه نداره ... برای ِهمین خاطر من اصلا نمی فهمم تو الگوریتم کوله پشتی P/W از کجا به دست میاد . اصلا P/W چی هست:اشتباه:
یا کلا تو الگوریتم کروسکال دو خط بیشتر به ما نگفته . انتظار داره ما برنامه هم تحویل بدیم :|
خب استاد وقتی میتونه از ما انتظار دا شته باشه که خودش یه درس درست و حسابی به ما داده باشه نه اینکه کتاب رو خلاصه کنه تو دو خط :لبخند:

[amirtork]

سلام مجدد
خب، اینکه استاد به شما درست و حسابی درس نداده دیگه از کمکاری استاده :لبخندساده: و عیبی نمیشه به شما وارد کرد.
شما میتونید برای اینکه در مورد این الگوریتم ها اطلاعاتی کسب کنید از لینک های زیر استفاده کنید:
1- جستو جوی دو دویی : http://en.wikipedia.org/wiki/Binary_search_algorithm
2- کوله پشتی : http://en.wikipedia.org/wiki/Knapsack_problem البته این لینک مال کوله پشتی 01 هست، از اونجایی که شما نوع مسئله ی کوله پشتی رو مشخص نکرده بودید من این رو گزاشتم، اگر مسئله ی کوله پشتیتون قابل خرد کردن بود(اجناس تقسیم پذیر) بگید که خودم در مورد الگوریتمش توضیح بدم.
3- الگوریتم کروسکال http://en.wikipedia.org/wiki/Kruskal's_algorithm
4- الگوریتم فلوید http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
5- ماتریس استراسن http://en.wikipedia.org/wiki/Strassen_algorithm
اگر در مورد مطالبی که توی لینک های بالا توضیح داده شده بود مشکلی داشتید و قسمتیشون رو متوجه نشدید، اعلام کنید.

[miss.mini]

من یه مشکل تو برنامه کوله پشتی دارم .. که متغییر PP چیکار انجام میده.
در واقع دوتا مشکل
تو خط اخر تو ارزش کوله پشتی قسمت knapsack(p,w,n-1,m) جمع ارزش رو برمیگردونه؟


#include <conio.h>
#include <stdio.h>
#include <iostream.h>

float knapsack(int p[],int w[],int n,int m)
{
int w1=m;
int i=0;
float pp=0;
while (i<=n && w1>0)
{
if (w[i]<w1)
{
cout<<" p : "<<p[i];
w1-=w[i];
pp+=p[i];
i++;
}
else
{
cout<<" p : "<<p[i];
pp+=w1*((float)p[i]/w[i]);
w1=0;
}
}
return pp;
}

void main()
{
int p[100]={6,12,7,18,9,30};
int w[100]={1,5,3,9,5,20};

int n,m;
cout<<"\nEnter Weight Knapsack : ";
cin>>m;
cout<<"Enter Num : ";
cin>>n;
for (int i=0;i<n;i++)
{
cout<<"Enter Arzesh : ";
cin>>p[i];
cout<<"\nEnter Weight : ";
cin>>w[i];
gotoxy(20,wherey()-2);
cout<<" P/W Is : "<<(float)p[i]/w[i];
gotoxy(1,wherey()+2);
cout<<".......................................\n";
}
cout<<"\n\n Arzesh Knapsack : "<<knapsack(p,w,n-1,m);

getch();
}

[amirtork]

تابع knapsack در واقع باید مجموع ارزش اون اجناسی رو که برای گذاشتن در کوله پشتی انتخاب شدن رو برگردونه
و متغیر pp هم نقشش نگه داشتن مجموع ارزش های اجناسی هست که انتخاب شدن.
شما با الگوریتم حریصانه آشنا هستید؟

[miss.mini]

تابع knapsack در واقع باید مجموع ارزش اون اجناسی رو که برای گذاشتن در کوله پشتی انتخاب شدن رو برگردونه
و متغیر pp هم نقشش نگه داشتن مجموع ارزش های اجناسی هست که انتخاب شدن.
شما با الگوریتم حریصانه آشنا هستید؟
راستش فقط یه تعریف میدونیم ازش که بیشترین ارزش رو تو همون مرحله اول انتخاب میکنه و جوابش بهینه نیست :متفکر:

[amirtork]

تقریبا درسته؛ بهترین پاسخ رو توی همون مرحله ای که توش هست انتخاب میکنه.
در واقع جوابش بعضی اوقات بهینه هم هست. برای مثال توی الگوریتم زمانبندی با مهلت معین همواره جواب صحیح رو برمیگردونه. ولی توی الگوریتم کوله پشتی؛ همیشه جواب درست رو بر نمیگردونه.
توی الگوریتم کوله پشتی هم تقریبا باید از یه چیزی شبیه به همون الگوریتم حریصانه استفاده کنید ولی یک مقدار باید پویا ترش کنی.