صفحهها: ۱ ۲
سلام.
مرتبه زمانی تابع f چی میشه؟
ی سوال دیگه هم اینکه: این همون الگوریتم جایگشت هستش؟ اگه کسی میتونه لطف کنه الگوریتم جایگشت توضیح بده.
ممنون
(۲۶ مرداد ۱۳۹۳ ۰۱:۲۵ ب.ظ)Bahar_sh نوشته شده توسط: سلام.
مرتبه زمانی تابع f چی میشه؟
ی سوال دیگه هم اینکه: این همون الگوریتم جایگشت هستش؟ اگه کسی میتونه لطف کنه الگوریتم جایگشت توضیح بده.
ممنون
سلام میشه بگید جایگشت را از توی چه منبعی خوندین؟
(۲۹ مرداد ۱۳۹۳ ۰۹:۵۹ ق.ظ)shayesteb نوشته شده توسط:(26 مرداد ۱۳۹۳ ۰۱:۲۵ ب.ظ)Bahar_sh نوشته شده توسط: سلام.
مرتبه زمانی تابع f چی میشه؟
ی سوال دیگه هم اینکه: این همون الگوریتم جایگشت هستش؟ اگه کسی میتونه لطف کنه الگوریتم جایگشت توضیح بده.
ممنون
سلام میشه بگید جایگشت را از توی چه منبعی خوندین؟
ی مثالی توی جزوه ی طراحی الگوریتم سیدجوادی بود که البته نفهمیدمش!
(۲۹ مرداد ۱۳۹۳ ۰۶:۲۶ ب.ظ)miladcr7 نوشته شده توسط: بله همون الگوریتم جایگشت هستش
جواب سوال دوستمونو دیگه، مرتبه ش
Sent from my iPad using
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
(۲۹ مرداد ۱۳۹۳ ۱۰:۱۸ ب.ظ)miladcr7 نوشته شده توسط: سلام خسته نباشید.کدتون یه عمل جایگزینی کم داره.زمان اجراش هم میشه:[tex]\theta(n(n)!)[/tex]سلام. نه کدش درسته، توی جزوه ی یوسفی که بچه ها هر جلسه آپلود میکنن، بود!
لطفا هم این سوالو توضیح بدین هم الگوریتم جایگشتو. مرسی
سلام.خب اولش الگوریتم جایگشت رو توضیح میدم براتون.کد این الگوریتم به صورت زیر هستش:
![[تصویر: 291418_01287860734464166081.png]](https://img.manesht.ir/291418_01287860734464166081.png)
بچه ها خطوط قرمز رو در نظر نگیرید چون خواستم مرتب بنویسم با ویژال نوشتم دیگه ایناش رو تعریف نکردم.عکس رو هم مستقیما گذاشتم که دم دست باشه
اینم لینک عکس هر طور راحت بودید:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
خب من اول روش کار این الگوریتم رو توضیح میدم بعدش کد هم دستتون میاد.[tex]n[/tex] عنصر داریم که میخوایم جایگشت این [tex]n[/tex] عنصر رو به دست بیاریم از قبل هم میدونیم که جایگشت [tex]n[/tex] عنصر مقدارش [tex]n![/tex] میشه حالا این کد چجوری چیکار میکنه:
یه ارایه به اسم [tex]a[/tex] داریم که عناصرمون توی این ارایه قرار دارند و تعداد این عناصر هم [tex]n[/tex] تاست.خب ۲ تا از پارامترهای ورودی تابع (ورودی اول که ارایست و ورودی اخر هم تعداد عناصر ارایه) مشخص شد [tex]k[/tex] هم که پارامتر دوم هستش رو تو ادامه میگیم چیکار میکنه و اصلا برای چی تعریفش کردیم.شرط [tex]if[/tex] به ازای برابری [tex]k=n-1[/tex] هم تمام عناصر ارایه رو چاپ میکنه و حالا ایده اصلی تو این الگوریتم اینه که ما هربار یکی از عناصر رو توی خونه اول ارایه قرار میدیم و جایگشت بقیه عناصر رو به ازای این عنصر پیدا میکنیم
خب یه مثال رو در نظر میگیریم:فرض کنید یه ارایه از ۳ عنصر داریم که به ترتیب [tex]a,b,c[/tex] توی خونه های ارایه قرار دارن.خب حالا نحوه محاسبه جایگشت ها این شکلیه:
یه بار [tex]a[/tex] توی خونه اول ارایه قرار میدیم و جایگشت های مختلف [tex](b,c)[/tex] رو به دست میاریم که میشه [tex]bc,cb[/tex] و وقتی با [tex]a[/tex] ترکیب شه میشن:[tex]abc,acb[/tex]
بار بعدی مثلا [tex]b[/tex] رو توی خونه اول ارایه قرار میدیم و جایگشت های مختلف [tex](a,c)[/tex] رو به دست میاریم که میشه [tex]ac,ca[/tex] و وقتی با [tex]b[/tex] ترکیب شه میشن:[tex]bac,bca[/tex]
و بار اخر [tex]c[/tex] رو توی خونه اول ارایه قرار میدیم و جایگشت های مختلف [tex](a,b)[/tex] رو به دست میاریم که میشه [tex]ab,ba[/tex] و وقتی با [tex]c[/tex] ترکیب شه میشن:[tex]cab,cba[/tex]
خب فکر کنم حالا دلیل وجود [tex]k[/tex] رو هم فهمیده باشید مقدار اصلی [tex]k[/tex] همیشه صفر میمونه به علت این که عنصری رو که میخوایم جایگشت های بقیه عناصر رو به ازاش محاسبه کنیم توی خونه اول ارایه قرار بدیم و عناصر مختلف رو هم با کمک [tex]i[/tex] به دست میاریم که این کار رو خط ۲۶ برای ما انجام میده.
پس تکلیف جایگزینی اول (خط ۲۶ ) معلوم شد: ازای [tex]k=0[/tex]کارش اینه که عنصری که میخوایم جایگشت بقیه عناصر رو به ازاش به دست بیاریم با یه جایگزینی توی خونه اول ارایه قرار میدیم برای [tex]k>0[/tex] سایر عناصر رو با هم جابه جا میکنه
بعدش یه فراخوانی بازگشتی داریم که [tex]k[/tex] رو یه واحد اضافه میکنیم چون میخوایم تمام جایگشت بقیه عناصر رو به ازای خونه اول به دست بیاریم.و هر بار هم یه واحد اضافه میشه تا وقتی که به [tex]n[/tex] برسه
و جایگزینی اخر(خط ۲۸):این جایگزینی به این علته که میخوایم عناصر رو به ترتیب اولیه برگردونیم یا به عبارت دیگه میخوایم ترتیب عناصر ورودی رو حفظ کنیم یعنی اگه ترتیب عناصر [tex]a,b,c[/tex] هستش بعد از اتمام هم ترتیب عناصر تو ارایه همون [tex]a,b,c[/tex] هست
و برای چاپ عناصر ارایه هم از [tex]if[/tex] اول استفاده میکنیم.درباره شرطش هم این که قبول دارید توی یه ارایه [tex]n[/tex] عنصری وقتی به خونه [tex]n-1[/tex] برسیم مطمئنا تمام جایگشت ها حساب شدن چون فقط خونه اخر مونده که تنها حالتش همون اخر بودنه پس شرط اینطوره که تا وقتی که به خونه ماقبل اخر رسیدیم باید جایگشت ها رو حساب کنیم و اگه توی خونه ماقبل اخر بودیم (یعنی [tex]k=n-1[/tex])
دیگه جایگشت حساب شده و عناصر ارایه رو چاپ میکنیم
_________________________________________________________________________________________
ببخشید فکر کنم گیج کننده توضیح دادم ولی خب شما دیگه یه جوری باهاش کنار بیاین
اگه خیلی بد توضیح ندادم و سوال خودتون رو هم متوجه نشید هنوز بگید تا اونم توضیح بدم
(۳۰ مرداد ۱۳۹۳ ۱۱:۴۷ ق.ظ)miladcr7 نوشته شده توسط: خب من اول روش کار این الگوریتم رو توضیح میدم بعدش کد هم دستتون میاد.[tex]n[/tex] عنصر داریم که میخوایم جایگشت این [tex]n[/tex] عنصر رو به دست بیاریم از قبل هم میدونیم که جایگشت [tex]n[/tex] عنصر مقدارش [tex]n![/tex] میشه حالا این کد چجوری چیکار میکنه:مرسی فهمیدم.
یه ارایه به اسم [tex]a[/tex] داریم که عناصرمون توی این ارایه قرار دارند و تعداد این عناصر هم [tex]n[/tex] تاست.خب ۲ تا از پارامترهای ورودی تابع (ورودی اول که ارایست و ورودی اخر هم تعداد عناصر ارایه) مشخص شد [tex]k[/tex] هم که پارامتر دوم هستش رو تو ادامه میگیم چیکار میکنه و اصلا برای چی تعریفش کردیم.شرط [tex]if[/tex] به ازای برابری [tex]k=n-1[/tex] هم تمام عناصر ارایه رو چاپ میکنه و حالا ایده اصلی تو این الگوریتم اینه که ما هربار یکی از عناصر رو توی خونه اول ارایه قرار میدیم و جایگشت بقیه عناصر رو به ازای این عنصر پیدا میکنیم
خب یه مثال رو در نظر میگیریم:فرض کنید یه ارایه از ۳ عنصر داریم که به ترتیب [tex]a,b,c[/tex] توی خونه های ارایه قرار دارن.خب حالا نحوه محاسبه جایگشت ها این شکلیه:
یه بار [tex]a[/tex] توی خونه اول ارایه قرار میدیم و جایگشت های مختلف [tex](b,c)[/tex] رو به دست میاریم که میشه [tex]bc,cb[/tex] و وقتی با [tex]a[/tex] ترکیب شه میشن:[tex]abc,acb[/tex]
بار بعدی مثلا [tex]b[/tex] رو توی خونه اول ارایه قرار میدیم و جایگشت های مختلف [tex](a,c)[/tex] رو به دست میاریم که میشه [tex]ac,ca[/tex] و وقتی با [tex]b[/tex] ترکیب شه میشن:[tex]bac,bca[/tex]
و بار اخر [tex]c[/tex] رو توی خونه اول ارایه قرار میدیم و جایگشت های مختلف [tex](a,b)[/tex] رو به دست میاریم که میشه [tex]ab,ba[/tex] و وقتی با [tex]c[/tex] ترکیب شه میشن:[tex]cab,cba[/tex]
خب فکر کنم حالا دلیل وجود [tex]k[/tex] رو هم فهمیده باشید مقدار اصلی [tex]k[/tex] همیشه صفر میمونه به علت این که عنصری رو که میخوایم جایگشت های بقیه عناصر رو به ازاش محاسبه کنیم توی خونه اول ارایه قرار بدیم و عناصر مختلف رو هم با کمک [tex]i[/tex] به دست میاریم که این کار رو خط ۲۶ برای ما انجام میده.
پس تکلیف جایگزینی اول (خط ۲۶ ) معلوم شد: ازای [tex]k=0[/tex]کارش اینه که عنصری که میخوایم جایگشت بقیه عناصر رو به ازاش به دست بیاریم با یه جایگزینی توی خونه اول ارایه قرار میدیم برای [tex]k>0[/tex] سایر عناصر رو با هم جابه جا میکنه
بعدش یه فراخوانی بازگشتی داریم که [tex]k[/tex] رو یه واحد اضافه میکنیم چون میخوایم تمام جایگشت بقیه عناصر رو به ازای خونه اول به دست بیاریم.و هر بار هم یه واحد اضافه میشه تا وقتی که به [tex]n[/tex] برسه
و جایگزینی اخر(خط ۲۸):این جایگزینی به این علته که میخوایم عناصر رو به ترتیب اولیه برگردونیم یا به عبارت دیگه میخوایم ترتیب عناصر ورودی رو حفظ کنیم یعنی اگه ترتیب عناصر [tex]a,b,c[/tex] هستش بعد از اتمام هم ترتیب عناصر تو ارایه همون [tex]a,b,c[/tex] هست
و برای چاپ عناصر ارایه هم از [tex]if[/tex] اول استفاده میکنیم.درباره شرطش هم این که قبول دارید توی یه ارایه [tex]n[/tex] عنصری وقتی به خونه [tex]n-1[/tex] برسیم مطمئنا تمام جایگشت ها حساب شدن چون فقط خونه اخر مونده که تنها حالتش همون اخر بودنه پس شرط اینطوره که تا وقتی که به خونه ماقبل اخر رسیدیم باید جایگشت ها رو حساب کنیم و اگه توی خونه ماقبل اخر بودیم (یعنی [tex]k=n-1[/tex])
دیگه جایگشت حساب شده و عناصر ارایه رو چاپ میکنیم
_________________________________________________________________________________________
ببخشید فکر کنم گیج کننده توضیح دادم ولی خب شما دیگه یه جوری باهاش کنار بیاین
اگه خیلی بد توضیح ندادم و سوال خودتون رو هم متوجه نشید هنوز بگید تا اونم توضیح بدم
راجع به مرتبه زمانی اون کد، چرا ! n نمیشه؟
(۳۰ مرداد ۱۳۹۳ ۰۷:۲۶ ب.ظ)miladcr7 نوشته شده توسط: کد خودتون یا کد جایگشت رو میگید؟کد خودم
بسیار هم عالی، خیلی خوب توضیح دادی استاد
Sent from my iPad using
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
(۳۰ مرداد ۱۳۹۳ ۰۷:۳۴ ب.ظ)Ava.arshad94 نوشته شده توسط: بسیار هم عالی، خیلی خوب توضیح دادی استاد
Sent from my iPad using
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
اختیار داری شما
اگه توی کد خودتون هم مشکلی داشتید بگید شاید تونستم کمک کنم
زمان اجراش وقتی !n میشه که زمان چاپ عناصر ارایه رو [tex]O(1)[/tex] در نظر بگیری که این فرض چندان درست نیست
(۳۰ مرداد ۱۳۹۳ ۰۹:۳۲ ب.ظ)miladcr7 نوشته شده توسط: زمان اجراش وقتی !n میشه که زمان چاپ عناصر ارایه رو [tex]O(1)[/tex] در نظر بگیری که این فرض چندان درست نیستممنون بابت راهنماییتون!
اگه میشه ی کم در رابطه با مرتبه زمانی تابع f توضیح بدین و اینکه چرا O(1) فرض درستی نیست؟
فرض ما بر اینه که نمیتونیم عناصر ارایه رو به صورت مستقیم مثلا با یه دستور پرینت چاپ کنیم و احتیاج به یه حلقه داریم که روی عناصر ارایه حرکت کنه که زمان این چاپ کردن n میشه.درسته؟
میشه بگید کجای زمان اجراش مشکل دارید؟
(۳۰ مرداد ۱۳۹۳ ۱۱:۱۵ ب.ظ)miladcr7 نوشته شده توسط: فرض ما بر اینه که نمیتونیم عناصر ارایه رو به صورت مستقیم مثلا با یه دستور پرینت چاپ کنیم و احتیاج به یه حلقه داریم که روی عناصر ارایه حرکت کنه که زمان این چاپ کردن n میشه.درسته؟همین دستور پرینت، آخه حلقه نیست که! کجای سوال همچین فرضی کرده که یکباره نمیشه چاپ کرد؟ منظورم اینه که از کجا باید بفهمیم؟
میشه بگید کجای زمان اجراش مشکل دارید؟