(۳۰ مرداد ۱۳۹۳ ۱۱:۴۷ ق.ظ)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])
دیگه جایگشت حساب شده و عناصر ارایه رو چاپ میکنیم

________________________________________________________________________________​_________

ببخشید فکر کنم گیج کننده توضیح دادم ولی خب شما دیگه یه جوری باهاش کنار بیاین

اگه خیلی بد توضیح ندادم و سوال خودتون رو هم متوجه نشید هنوز بگید تا اونم توضیح بدم

(۲۶ مرداد ۱۳۹۳ ۰۱:۲۵ ب.ظ)Bahar_sh نوشته شده توسط:  سلام.
مرتبه زمانی تابع f چی میشه؟
ی سوال دیگه هم اینکه: این همون الگوریتم جایگشت هستش؟ اگه کسی میتونه لطف کنه الگوریتم جایگشت توضیح بده.
ممنون

(۲۹ مرداد ۱۳۹۳ ۰۹:۵۹ ق.ظ)shayesteb نوشته شده توسط:  

(26 مرداد ۱۳۹۳ ۰۱:۲۵ ب.ظ)Bahar_sh نوشته شده توسط:  سلام.
مرتبه زمانی تابع f چی میشه؟
ی سوال دیگه هم اینکه: این همون الگوریتم جایگشت هستش؟ اگه کسی میتونه لطف کنه الگوریتم جایگشت توضیح بده.
ممنون

سلام میشه بگید جایگشت را از توی چه منبعی خوندین؟

(۲۹ مرداد ۱۳۹۳ ۰۶:۲۶ ب.ظ)miladcr7 نوشته شده توسط:  بله همون الگوریتم جایگشت هستش

(۳۰ مرداد ۱۳۹۳ ۰۷:۳۴ ب.ظ)Ava.arshad94 نوشته شده توسط:  بسیار هم عالی، خیلی خوب توضیح دادی استاد


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

(۳۰ مرداد ۱۳۹۳ ۰۹:۳۲ ب.ظ)miladcr7 نوشته شده توسط:  زمان اجراش وقتی !n میشه که زمان چاپ عناصر ارایه رو [tex]O(1)[/tex] در نظر بگیری که این فرض چندان درست نیست

(۳۰ مرداد ۱۳۹۳ ۱۱:۱۵ ب.ظ)miladcr7 نوشته شده توسط:  فرض ما بر اینه که نمیتونیم عناصر ارایه رو به صورت مستقیم مثلا با یه دستور پرینت چاپ کنیم و احتیاج به یه حلقه داریم که روی عناصر ارایه حرکت کنه که زمان این چاپ کردن n میشه.درسته؟

---

میشه بگید کجای زمان اجراش مشکل دارید؟

(۳۰ مرداد ۱۳۹۳ ۱۱:۳۱ ب.ظ)miladcr7 نوشته شده توسط:  ببینید اون طور که توی جزوه استاد یوسفی نوشته که باید قبول کنیم چاپ عناصر در زمان n صورت میگیره پس پیش فرض همینه.به من نظرم اگه صورت سوال خودش مشخص نکنه کاملا منطقی هستش که شما کل عناصر ارایه رو نمیتونی توی [tex]O(1)[/tex] محاسبه کنی و حتما به حلقه احتیاج داریم

---

جواب کلی همینه حالا اگه تو نحوه ی محاسبه [tex]n(n!)[/tex] مشکلی داشتی بگو برات توضیح میدم

(۱۰ مهر ۱۳۹۳ ۰۶:۱۹ ب.ظ)s.h5102 نوشته شده توسط:  سلام
توضیح تون خیلی خوب بود، اما من متوجه نمیشم چرا گفتید k همیشه صفره؟ وقتی الگوریتم داره مقدار k رو از ورودی می گیره به نظرم یه جورایی الگوریتم تبدیل هست تا جایگشت (یعنی انتخاب k عنصر از n عنصر که توش ترتیب انتخاب عناصر هم مهم هست). گیج شدم. میشه لطفا یکم دیگه درمورد این k توضیح بدید؟؟؟

(۱۰ مهر ۱۳۹۳ ۰۶:۵۹ ب.ظ)miladcr7 نوشته شده توسط:  

(10 مهر ۱۳۹۳ ۰۶:۱۹ ب.ظ)s.h5102 نوشته شده توسط:  سلام
توضیح تون خیلی خوب بود، اما من متوجه نمیشم چرا گفتید k همیشه صفره؟ وقتی الگوریتم داره مقدار k رو از ورودی می گیره به نظرم یه جورایی الگوریتم تبدیل هست تا جایگشت (یعنی انتخاب k عنصر از n عنصر که توش ترتیب انتخاب عناصر هم مهم هست). گیج شدم. میشه لطفا یکم دیگه درمورد این k توضیح بدید؟؟؟

سلام
الان سوالتون از منه؟