مسابقه‌ی تصادفی

 
 
 عنصر
عنصرمسابقه كامپيوتر
مسابقه شماره ۲۰۴

سوال)


یک ردیف از عددهای 1 تا 10 به ما داده شده است. دو عمل زیر را می‌توانیم بر روی هر ردیف انجام دهیم :
-عنصر اول و دوم ردیف را جابجا کنیم.
-عنصر اول ردیف را برداشته , آن را در آخر ردیف قرار دهیم.
آیا با استفاده از دو عمل فوق , می‌توانیم ردیف داده شده را مرتب کنیم؟

 


پاسخ)


با الگوریتم زیر می‌توان جای هر دو عضو دلخواه مانند i و j با فرض اینکه i قبل از j باشد را عوض کرد :
-ابتدا با توجه به عمل دوم تمام اعضای قبل از i را به انتهای دنباله به ترتیب انتقال می‌دهیم.
-با توجه به عمل اول جای i و عضو بعد از آن را عوض کرده و سپس با توجه به عمل دوم آن را به انتهای دنباله انتقال می‌دهیم و این کار را تا جایی ادامه می‌دهیم که  i و j مجاور باشند , در این مرحله خود i را به انتها منتقل می‌کنیم.
-با توجه به عمل اول جای j و عضو بعد از آن را عوض کرده و سپس با توجه به عمل دوم آن را به انتهای دنباله انتقال می‌دهیم و کار را تا جایی ادامه می‌دهیم که جای خالی i و j پر شود.
-با توجه به عمل دوم تا جای ممکن اعضا را به انتها انتقال می‌دهیم تا ترتیب اولی ظاهر شود با این تفاوت که جای i و j عوض شده باشد.
با الگوریتم بالا ابتدا 1 را به ابتدا , سپس 2 را به جایگاه دوم و ... انتقال می‌دهیم

1391/7/1 لينک مستقيم

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تایید انصراف
 المپیاد کامپیوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
خطایی روی داده است.
خطا: بازديدها فعلا" غیر قابل دسترسی می باشد.