انجمنصفحه اولجستجوی انجمن

[malayer]

سلام
خسته نباشید



کمک کنید برای رضای خدا

[nazaninzahra2]

(۲۱ آذر ۱۳۹۱ ۰۹:۰۰ ب.ظ)malayer نوشته شده توسط:  سلام
خسته نباشید

بچه ها برنامه می خوام که n عدد از ورودی دریافت کنه (آرایه به طول n) و دومین مینیمم را در بین اعداد دقیقا در زمان n+[logn]-2 بیابد.اعداد نامرتب هستند .

کمک کنید برای رضای خدا

سلام
چه جالب ! بعضی وقت ها حس میکنم مثل روبات هستم که خدا داره کنترلم میکنه ! چند روز پیش داشتم نیپولیتان میخوندم و توش این مسئله رو مطرح کرده بود و به عنوان تمرین این مسائله رو داده بود. من تقریبآ چهار ساعت بهش فکر کردم و روش کار کردم. از هر چی فکر کنید استفاده کردم ، لیست پیوندی ، آرایه پویا دو بعدی و حلقه های تو در تو ... و خروجی شد این فایل که براتون آپلود کردم.
میدونم یکم سخت به نظر میاد ولی ایده اصلی رو از روی نیپولیتان گرفتم. (البته اگر میخواهی امتحانش کنی حتمآ n رو عدد بده که توانی از دو باشه مثلآ : ۴ یا ۸ یا ۱۶ .... )

[a.hooshmand]

ببین این درست هست؟

کد 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;
} 


[malayer]

آقا شرمنده کردی دست درد نکنه
با چه برنامه نوشته اید .؟؟؟؟؟؟

---

پاسخ به a.hooshman
دوست دست شما درد نکنه ولی فکر کنم پیچیدگی کلشlogn+n هست

[nazaninzahra2]

(۲۱ آذر ۱۳۹۱ ۰۹:۳۰ ب.ظ)malayer نوشته شده توسط:  آقا شرمنده کردی دست درد نکنه
با چه برنامه نوشته اید .؟؟؟؟؟؟

---

پاسخ به a.hooshman
دوست دست شما درد نکنه ولی فکر کنم پیچیدگی کلشlogn+n هست

خواهش میکنم
من با سی پلاس پلاس نوشتم ، توجه داشته باشید که باید پیچیدگی بشه همون n+logn وگرنه ساده تر از این حرفا میشه نوشتش
(مثلآ کد آقای هوشمند (با تشکر از ایشان) ) تمام سختی این مسئله هم تو همین نکته نهفته که بر پیچیدگی کل تاکید داره.

[a.hooshmand]

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

---

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

)

[malayer]

آقا دست همتون درد نکنه

ولی مسئله به این صورت

n-1 حال مقایسه برای پیدا کردن کوچکترین عنصر و برای پیدا کردن مینیمم دوم باید ۱-[logn] مقایسه انجام دهیم.

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

[nazaninzahra2]

(۲۱ آذر ۱۳۹۱ ۱۱:۰۱ ب.ظ)malayer نوشته شده توسط:  آقا دست همتون درد نکنه

ولی مسئله به این صورت

n-1 حال مقایسه برای پیدا کردن کوچکترین عنصر و برای پیدا کردن مینیمم دوم باید ۱-[logn] مقایسه انجام دهیم.

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

دوست عزیز منم دقیقآ همین برنامه رو نوشتم ( اصلاح میکنم که : منظور من در پست های قبل از پیچیدگی مقایسه بود و به اشتباه نوشتم پیچیدگی)

[malayer]

بله به کمکک لیست پیوندی نوشته شده نه آرایه درسته ؟

[mfXpert]

برای به دست آوردن اون تعداد مقایسه که مد نظر شما هستش باید از درخت برنده-بازنده استفاده کرد

[nazaninzahra2]

(۲۱ آذر ۱۳۹۱ ۱۱:۱۶ ب.ظ)malayer نوشته شده توسط:  بله به کمکک لیست پیوندی نوشته شده نه آرایه درسته ؟

بله
یه مقدار از آرایه کمک گرفتم و یه مقدار از لیست پیوندی
من از روش تورنومنت استفاده کردم که یکجور درخت تصمیم گیری است.