حداقل تعداد Swap برای تولید همه جایگشتهای 1 تا n

آمار پرسش:

پرسیده شده: 2014-08-23 01:32:13 -0500
مشاهده شده: 289 بار
بروز شده: 2014-08-23 11:02:41 -0500

پرسش‌های مشابه:

آشپزباشی:‌ مرتب کردن پشته با برعکس کردن یک دنباله متوالی از ابتدای آن

تعداد مثلث های پوشاننده

تعداد جواب های معادله ${1\over x}+{1\over y}={1\over n}$ در دستگاه اعداد صحیح

Flip Sort

همه را با تلفن خبر کنید - دوره ی 05 - مرحله ی 1

یکی کردن علامت خانه‌های یک جدول $4\times 4$ از + و - ها

تبدیل جدول با چرخش‌های ساعتگرد مربع $2\times 2$

دو زیرمجموعه فرد و زوج از مجموعه {۱، 2، 3، ...64}

انگور، آن هم از نوع «درختی» - آزمون دوم آزمایشی شاززز

جدولی $2010\times 2010$ امکان رسیدن به جدولی که همه مهره ها در یک خانه جمع شوند

نکاتی در مورد نوشتن پاسخ:

در این قسمت می‌تونی به یک پرسش پاسخ بدی. اگه می‌خوای در مورد پرسش بحث و اظهار نظر کنی از قسمت «ثبت نظر» استفاده کن.
پاسخت رو دقیق و کامل بنویس، از عکس استفاده کن و اگه لازمه به منابع (کتاب یا سایت) ارجاع بده.
اگه پرسش یا پاسخ‌ها مفید هستند حتما بهشون رای بده تا پرسش‌ها و پاسخ‌های خوب مشخص بشن.

استفاده از ویرایشگر:

توی قسمت پیش‌نمایش می‌تونی ببینی متنی که نوشتی چجوری روی سایت دیده میشه.
خیلی مهم: برای اینکه به خط بعد بری باید دوتا Enter بزنی.
می‌تونی از تگ‌های معمولی و ساده‌ی html هم استفاده کنی.
با دکمه‌هایی که بالای ویرایش‌گر قرار دارند کلی کار می‌شه کرد. از عکس‌گذاشتن بگیر تا لیست شماره‌دار. حتما امتحان‌شون کن.

علائم ریاضی:

برای نوشتن علائم ریاضی می‌تونی از Mathjax استفاده کنی. راهنمای Mathjax رو از سایت math.stackexchange بخون.
برای نوشتن عبارت ریاضی وسط جمله، اون عبارت رو بین دوتا $ قرار بده.
برای نوشتن عبارت ریاضی تو یه خط جدید اون رو بین دوتا $$ قرار بده.

اعداد ۱ تا n به ترتیب روی تخته نوشته شده اند. در هر مرحله می توانیم دو تا از آنها را پاک کرده با هم جا به جا کنیم (اولی را در جای دومی و دومی را در جای اولی بنویسیم). با حداقل چند مرحله میتوانیم تمامی جایگشتهای ۱ تا n را روی تخته بنویسیم؟ اثبات کنید.

2014-08-23 01:32:13 -0500

کلاه قرمزی 3097 ● 21 ● 34 ● 57

پاک‌کردن ویرایش سوال

نظرات

سادست و البته کاربردی +1

2014-08-23 02:52:14 -0500 سماق دو

سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com

2015-08-06 08:46:58 -0500 امیر شکری

سلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه

2016-10-26 05:48:49 -0500 امیر شکری

2016-10-26 06:07:10 -0500 امیر شکری

2 پاسخ

خب باب اسفنجی اثبات خیلی شهودی ای ارائه داده . اینکه چرا با n! - 1 مرحله میشه به همه جایگشت های n تایی رسید رو توضیح میدم : (استقرا) فرض میکنیم برای n تا عدد n! - 1 تا مرحله لازمه . حالا برای اینکه تمام جایگشت های n + 1 عددی رو بسازیم میایم n تا عضو سمت راست رو در نظر میگیریم ( عضو باقیمونده = a ) و طبق فرض استقرا با n! - 1 مرحله تمام جایگشت های n + 1 عضوی که عضو اولشون a باشه رو میسازیم . بعد a رو با یه عضو دیگه جابجا میکنیم ( +1 مرحله ) و همون مراحلو روی n تای سمت راست انجام میدیم تا اینکه تمام جایگشت های n + 1 تایی تولید بشن که میشه :

$$(n ! - 1) \times (n+ 1) + n - 1$$

خب رابطه بالا برابر !(n +1 ) هست .

( امیدوارم کامل باشه )

2014-08-23 11:02:41 -0500

سماق دو 1349 ● 7 ● 19 ● 37

پاک‌کردن ویرایش پاسخ

حداقل با n!-1 مرحله میتوانیم تمامی جایگشت های 1 تا n را روی تخته بنویسیم. از آنجا که هر n! ، n جایگشت دارد و با جا به جا کردن هر دو رقم میتوان به جایگشت جدیدی رسید، با صرف نظر از حالت اول ، میتوان در n!-1 مرحله تمامی جایگشت ها را نوشت.

2014-08-23 07:08:27 -0500

باب اسفنجی 203 ● 3 ● 4 ● 9

پاک‌کردن ویرایش پاسخ

نظرات

چرا میتونیم با n!-1 مرحله همه جایگشتها رو تولید کنیم؟

2014-08-23 09:27:40 -0500 کلاه قرمزی

یک حالت در ابتدا به ما داده شده، پس با تولید یک جایگشت در هر مرحله میشه این کار را در n!-1 مرحله انجام داد.(فکر کنم این سوال رو با استقرا هم بشه حل کرد.)

2014-08-23 10:09:42 -0500 باب اسفنجی

اطلاعات بیشتر