سلام
خسته نباشید
کمک کنید برای رضای خدا
(۲۱ آذر ۱۳۹۱ ۰۹:۰۰ ب.ظ)malayer نوشته شده توسط: سلام
خسته نباشید
بچه ها برنامه می خوام که n عدد از ورودی دریافت کنه (آرایه به طول n) و دومین مینیمم را در بین اعداد دقیقا در زمان n+[logn]-2 بیابد.اعداد نامرتب هستند .
کمک کنید برای رضای خدا
سلام
چه جالب ! بعضی وقت ها حس میکنم مثل روبات هستم که خدا داره کنترلم میکنه ! چند روز پیش داشتم نیپولیتان میخوندم و توش این مسئله رو مطرح کرده بود و به عنوان تمرین این مسائله رو داده بود. من تقریبآ چهار ساعت بهش فکر کردم و روش کار کردم. از هر چی فکر کنید استفاده کردم ، لیست پیوندی ، آرایه پویا دو بعدی و حلقه های تو در تو ... و خروجی شد این فایل که براتون آپلود کردم.
میدونم یکم سخت به نظر میاد ولی ایده اصلی رو از روی نیپولیتان گرفتم. (البته اگر میخواهی امتحانش کنی حتمآ n رو عدد بده که توانی از دو باشه مثلآ : ۴ یا ۸ یا ۱۶ .... )
ببین این درست هست؟
کد php:
#include <iostream>
#define n 10
using namespace std;
int main()
{
int a[n];
int min1,min2;
for (int i=0; i<n; i++)
cin >>a[i];
min1=min2=a[0];
for (int i=1; i<n; i++)
if (a[i]<min2)
{
if (a[i]<min1)
{
min2=min1;
min1=a[i];
}
else
min2=a[i];
}
cout << "min1=" <<min1<<" min2="<<min2<< endl;
return 0;
}
آقا شرمنده کردی دست درد نکنه
با چه برنامه نوشته اید .؟؟؟؟؟؟
پاسخ به a.hooshman
دوست دست شما درد نکنه ولی فکر کنم پیچیدگی کلشlogn+n هست
(۲۱ آذر ۱۳۹۱ ۰۹:۳۰ ب.ظ)malayer نوشته شده توسط: آقا شرمنده کردی دست درد نکنه
با چه برنامه نوشته اید .؟؟؟؟؟؟
پاسخ به a.hooshman
دوست دست شما درد نکنه ولی فکر کنم پیچیدگی کلشlogn+n هست
خواهش میکنم
من با سی پلاس پلاس نوشتم ، توجه داشته باشید که باید پیچیدگی بشه همون n+logn وگرنه ساده تر از این حرفا میشه نوشتش
(مثلآ کد آقای هوشمند (با تشکر از ایشان) ) تمام سختی این مسئله هم تو همین نکته نهفته که بر پیچیدگی کل تاکید داره.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
So, how many comparisons we make using this method. Let’s calculate (ignoring constants):
Comparisons for finding minimum: n
Comparisons for finding 2nd minimum: log(n)
Total: n + log(n
)
Comparisons for finding minimum: n
Comparisons for finding 2nd minimum: log(n)
Total: n + log(n
آقا دست همتون درد نکنه
ولی مسئله به این صورت
n-1 حال مقایسه برای پیدا کردن کوچکترین عنصر و برای پیدا کردن مینیمم دوم باید ۱-[logn] مقایسه انجام دهیم.
من برنامه می خوام که این رو پیاده سازی کنه
(۲۱ آذر ۱۳۹۱ ۱۱:۰۱ ب.ظ)malayer نوشته شده توسط: آقا دست همتون درد نکنه
ولی مسئله به این صورت
n-1 حال مقایسه برای پیدا کردن کوچکترین عنصر و برای پیدا کردن مینیمم دوم باید ۱-[logn] مقایسه انجام دهیم.
من برنامه می خوام که این رو پیاده سازی کنه
دوست عزیز منم دقیقآ همین برنامه رو نوشتم ( اصلاح میکنم که : منظور من در پست های قبل از پیچیدگی مقایسه بود و به اشتباه نوشتم پیچیدگی)
بله به کمکک لیست پیوندی نوشته شده نه آرایه درسته ؟
برای به دست آوردن اون تعداد مقایسه که مد نظر شما هستش باید از درخت برنده-بازنده استفاده کرد
(۲۱ آذر ۱۳۹۱ ۱۱:۱۶ ب.ظ)malayer نوشته شده توسط: بله به کمکک لیست پیوندی نوشته شده نه آرایه درسته ؟
بله
یه مقدار از آرایه کمک گرفتم و یه مقدار از لیست پیوندی
من از روش تورنومنت استفاده کردم که یکجور درخت تصمیم گیری است.