آمار پرسش:

• پرسیده شده: 2014-05-31 16:18:01 -0600
• مشاهده شده: 269 بار
• بروز شده: 2014-06-05 14:54:48 -0600

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

مرتب سازی عجیب با تعویض بلوکی ًًًًًً

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

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

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

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

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

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

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

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

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

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

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

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

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

علائم ریاضی:

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

Flip Sort

2

تنها عمل مجاز ما برای مرتب کردن یک آرایه، انتخاب دو خانه مجاور و تعویض محتوی آنهاست. کمترین تعداد عمل مذکور برای مرتب کردن آرایه چقدر است؟

مثال:
کمترین تعداد برای آرایه 1 2 3 4
0 است

و برای آرایه 1 3 4 2
2 است

مرتب-سازی ترکیبیات

2014-05-31 16:18:01 -0600

پسرخاله 117 ● 1 ● 1 ● 5

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

نظرات

خب کمترین تعداد که صفر هست در شرایطی که آرایه اولیه خودش مرتب باشه! اما فکر کنم منظور «کمترین تعداد عمل هست به نحوی که مطمین باشیم هر آرایه اولیه رو میشه با اون تعداد مرتب کرد»

2014-05-31 16:34:18 -0600 کلاه قرمزی

نه، کمترین تعداد به ازای آرایه داده شده (الان ویرایش میکنم)

2014-05-31 16:40:33 -0600 پسرخاله

پسر خاله عنوان بهترش کن. یه اسم انگلیسی که چیزی رو معلوم نمی‌کنه! باید عنوان یه جوری باشه که خودش به تنهایی بخش زیادی از مساله رو روشن کنه. مثلا «کمترین تعداد جابجایی برای مرتب کردن یک آرایه».

2014-05-31 23:18:22 -0600 فامیل دور

یه سوال اردری می خواد یا دقیق ؟

2014-06-01 01:30:23 -0600 عطا

این سوال رو چند وقت پیش رو یووی‌ای دیده بودم و عنوان هم همون عنوان اصلیه؛ خواستم اگه کسی سرچ کرد بتونه سوال اصلی رو پیدا کنه.

لینک سوال اینه: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1268

اندازه و اعضای آرایه رو میگیرید و عدد دقیق خروجی میدید

2014-06-01 05:01:32 -0600 پسرخاله

1

کافیه تعداد وارونگی‌ها رو حساب کنید. (دو عدد مثلِ $i$ و $j$ که $i < j$ ولی $a_i > a_j$ )

pseudo code:

for i = 1 to arraysize

for j = i + 1 to arraysize

$a_i > a_j$ if

counter++

که counter به عنوان خروجی داده‌ می‌شه. الگوریتم از $O(n^2)$ هست.

پس از دیدن نوشته‌یِ @یاشار: ببخشید من ندیدم شما نوشتین، من اینو از چند دقیقه‌ای پیش‌تر شروع به نوشتن کردم و الآن فرصت شد ارسال کنم.

2014-06-01 07:42:52 -0600

یوسفی 631 ● 2 ● 15

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

1

خب هر بار که این عمل رو روی دوتا عنصر که ترتیبشون برعکسه انجام بدیم، از تعداد وارونگی های لیستمون یدونه کم کردیم.

در نتیجه کمترین تعداد جابجایی ها برابره با تعداد وارونگی های توی لیست.

پس باید تعداد وارونگی ها رو بشمریم.

برای شمردن تعداد وارونگی ها یه راه اینه که از مرتب سازی درجی استفاده کنیم. که پیچیدگیش میشه مربعی.

ولی راه بهتر اینه که از مرتب سازی ادغامی استفاده کنیم، که در این صورت پیچیدگی میشه: $\Theta(n\;\log n)$

توضیح دقیق برای چگونگی استفاده از این دو الگوریتم برای شمردن تعداد وارونگی ها به همراه کد: لینک

2014-06-01 07:40:15 -0600

یاشار 260 ● 1 ● 3 ● 10

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

نظرات

درجی nlgn ـه؟!

2014-06-01 08:39:54 -0600 پسرخاله

منظورشون مرتب‌سازیِ ادغامی یا Merge sort هست. وگرنه مرتب‌سازیِ درجی یا Insertion sort از مرتبه‌ی n به توان ۲ هست.

2014-06-01 08:43:09 -0600 یوسفی

درسته منظورم merge sort بود

2014-06-01 11:21:59 -0600 یاشار