این روش به طور گسترده در هنگام بازی با ورق استفاده می شود. عناصر (نقشه ها) از نظر ذهنی به دنباله های "آماده" A 1 , A 2 ,…, A i -1 , و بخش "باقیمانده" ( مرتب نشده) تقسیم می شوند: A i , A i +1 ,…, A N .

ماهیت روش این است که در هر مرحله i (با شروع از i = 2)، عنصر i از قسمت مرتب نشده استخراج می شود و در قسمت "تمام" قرار می گیرد، در حالی که در درج می شود. جای مناسب.

روش الگوریتم متن:

1. شروع کنید.

2. حلقه بزنید در حالی که i مقادیری از 2 تا N دارد،
مرحله = 1:

الف) عنصر i ام (A(i)) در سلول A(0) قرار می گیرد.

ب) j = -1 را اختصاص دهید، یعنی j برابر با تعداد عنصری است که در سمت چپ موضوع (i-th) قرار دارد و بنابراین در دنباله "تمام" قرار می گیرد.

ج) اگر A(0) ≥ A(j)، سپس عنصر A(0) را در سلول A(j+1) قرار دهید، در غیر این صورت عنصر A(j) را در سلول A(j+1) قرار دهید، مقدار را کاهش دهید. از j به یک و مرحله ج را تکرار کنید).

روی انجیر شکل 1 بلوک دیاگرام روش مرتب سازی را نشان می دهد ارتباط مستقیم.

روش به شرح زیر عمل می کند: در مرحله i-ام (شروع از i = 2)، عنصر i-ام در یک سلول آزاد قرار می گیرد (به عنوان مثال، A(0)). این عنصر با عنصر واقع در قسمت "تمام" در سمت چپ آن مقایسه می شود. اگر عنصر A(0) کمتر باشد، آنگاه مقایسه (عنصر j-امین) با یک موقعیت به سمت راست منتقل می شود و پس از آن عنصر بعدی برای مقایسه گرفته می شود. اگر عنصر A(0) کمتر از مقایسه نباشد، بلافاصله بعد از عنصر مقایسه شده در محل قرار می گیرد.

برنج. 1. بلوک نمودار مرتب سازی شامل مستقیم

روی انجیر 2 نمونه ای از مرتب سازی بر اساس گنجاندن مستقیم را نشان می دهد.

دنباله منبع
	A (0)
i = 2
i = 3
من = 4
I=5
من = 6
من = 7
من = 8
نتیجه

برنج. 2. نمونه ای از مرتب سازی بر اساس شمول مستقیم

مرتب سازی شامل مستقیم برای مواردی مناسب تر است که داده هایی که باید مرتب شوند به صورت متوالی (یکی پس از دیگری) می رسند.

مرتب سازی انتخاب مستقیم

ماهیت روش به شرح زیر است. کوچکترین عنصر در قسمت "باقی" (مرتب نشده) انتخاب شده و با عنصر اول (در همان قسمت مرتب نشده) جایگزین می شود. پس از آن، طول بخش مرتب نشده به اندازه یک عنصر کاهش می یابد (به وسیله اول)، و کل فرآیند با (n - 1) عنصر، سپس با (n - 2) عنصر و غیره ادامه می یابد تا زمانی که یکی باقی بماند، بزرگترین. عنصر

این روش به نوعی مخالف روش گنجاندن مستقیم است. در روش گنجاندن مستقیم، در هر مرحله، فقط یک عنصر بعدی و تمام عناصر قسمت "تمام شده" توالی در نظر گرفته می شود که در میان آنها نقطه درج این عنصر بعدی یافت می شود. و در روش انتخاب مستقیم، برای یافتن یک عنصر (حداقل)، تمام عناصر قسمت مرتب نشده بررسی می شوند و این عنصر حداقل به عنوان عنصر بعدی در قسمت از قبل آماده قرار می گیرد.

روش الگوریتم متن:

1. شروع کنید.

2. حلقه بزنید در حالی که i مقادیری از 1 تا N - 1 دارد.
مرحله = 1:

الف) عنصر جریان (i-th) را در برخی از سلول های حافظه (X) قرار داده و به خاطر بسپارید شماره سریال(i) عنصر فعلی (در متغیر K)؛

ب) حلقه بزنید در حالی که j مقادیری از i + 1 (یعنی از عنصر زیر i) تا N دارد، stride = +1:

بدنه حلقه: اگر X > A(j) باشد، عنصر A(j) را در سلول X قرار دهید و عدد آن را در سلول K به خاطر بسپارید.

ج) A(K) = A(i) و A(i) = X را اختصاص دهید.

روی انجیر 3 نمونه ای از مرتب سازی با انتخاب مستقیم را نشان می دهد.

برنج. 3. نمونه ای از مرتب سازی با انتخاب مستقیم

این روش به طور گسترده در هنگام بازی با ورق استفاده می شود. عناصر (نقشه ها) از نظر ذهنی به دنباله "آماده" A1 ... An و دنباله اصلی Ai ... An تقسیم می شوند. در هر مرحله با شروع از i=2 و افزایش I هر بار یک، از دنباله اصلی استخراج می شود عنصر i-امو به دنباله تمام شده منتقل می شود، در حالی که در جای مناسب درج شده است.

در بالا به عنوان مثال فرآیند مرتب سازی با گنجاندن هشت عدد به طور تصادفی انتخاب شده نشان داده می شود: الگوریتم این مرتب سازی به شرح زیر است:

برای i:=2 تا n انجام

گنجاندن x در جای مناسب در میان یک ... a[j];

در فرآیند واقعی جستجوی یک مکان مناسب، راحت است، مقایسه ها و حرکات متناوب به ترتیب، X را غربال کنیم، یعنی X با عنصر بعدی aj مقایسه شود، و سپس یکی از X درج شود. مکان آزاد، یا aj به سمت راست منتقل می شود و فرآیند به سمت چپ "ترک" می شود. توجه داشته باشید که فرآیند الک زمانی ممکن است پایان یابد که یکی از دو شرط مختلف زیر برآورده شود:

1. عنصر aj با کلیدی کمتر از کلید X پیدا می شود.

2. انتهای سمت چپ دنباله تمام شده رسیده است.

این مورد معمولی از یک فرآیند تکراری با دو شرط پایان به ما امکان می دهد از ترفند مانع شناخته شده (سنتینل) استفاده کنیم. در اینجا با تنظیم مانع a0 با مقدار X می توان آن را به راحتی اعمال کرد.

تجزیه و تحلیل روش گنجاندن مستقیم. تعداد مقایسات کلیدی (Ci) در غربالگری i-ام حداکثر i - 1، حداقل - 1 است. اگر فرض کنیم که همه جایگشت‌های n کلید به یک اندازه محتمل هستند، میانگین تعداد مقایسه‌ها i/2 است. تعداد انتقال (تخصیص عناصر) Mi برابر است با Ci + 2 (شامل مانع). از همین رو تعداد کلمقایسه ها و تعداد نقل و انتقالات به شرح زیر است:

ذخیره = (n2 + n - 2)/4،

Сmax = (n2 + n - 4)/4،

M دقیقه \u003d Z * (n - 1)،

M ave \u003d (n2 + 9n - 10) / 4,

M max = (n2 + 3n - 4)/2.

حداقل برآوردها در مورد یک توالی اولیه از قبل مرتب شده از عناصر رخ می دهد، در حالی که بدترین تخمین ها زمانی رخ می دهد که آنها در ابتدا به ترتیب معکوس مرتب شوند. به یک معنا، مرتب‌سازی بر اساس گنجاندن رفتار واقعاً طبیعی را نشان می‌دهد. واضح است که الگوریتم فوق فرآیند مرتب سازی پایدار را توصیف می کند: ترتیب عناصر با کلیدهای مساوی بدون تغییر باقی می ماند.

اگر به این نکته توجه داشته باشید که دنباله تمام شده (a1 ... ai-1 که می خواهید در آن درج کنید، الگوریتم با گنجاندن مستقیم به راحتی قابل بهبود است. عنصر جدید، خود قبلا سفارش داده شده است. طبیعی است که در جستجوی دودویی توقف کنیم، که در آن سعی می شود با وسط دنباله تمام شده مقایسه شود، و سپس روند تقسیم به نصف تا یافتن نقطه شمول ادامه می یابد. چنین الگوریتم مرتب سازی اصلاح شده ای روش درج باینری نامیده می شود.

مرتب سازی عبارت است از چیدمان داده ها در حافظه به صورت منظم و بر اساس پارامتر انتخاب شده. منظم بودن به عنوان افزایش (کاهش) در مقدار پارامتر از ابتدا تا انتهای آرایه داده در نظر گرفته می شود.

هنگام پردازش داده ها، دانستن فیلد اطلاعاتی داده ها و محل قرارگیری آنها در ماشین بسیار مهم است.

تمایز بین مرتب سازی داخلی و خارجی:

مرتب سازی داخلی - مرتب سازی در حافظه دسترسی تصادفی;

مرتب سازی خارجی - مرتب سازی در حافظه خارجی.

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

هنگام مرتب سازی، ممکن است همان کلیدها رخ دهد. در این مورد، مطلوب است که کلیدهای مشابه پس از مرتب سازی به همان ترتیبی که در فایل منبع وجود دارد، مرتب شوند.آی تی - مرتب سازی پایدار.

ما فقط انواعی را در نظر خواهیم گرفت که از رم اضافی استفاده نمی کنند. این گونه ها نامیده می شوند "در همان نقطه".

کارایی مرتب سازی را می توان بر اساس چندین معیار در نظر گرفت:

زمان صرف شده برای مرتب سازی؛

مقدار RAM مورد نیاز برای مرتب سازی؛

زمان صرف شده توسط برنامه نویس برای نوشتن برنامه.

ما اولین معیار را مشخص می کنیم. می توان معادل زمان صرف شده برای مرتب سازی در نظر گرفت تعداد مقایسه هاو تعداد حرکاتهنگام مرتب سازی

ترتیب تعداد مقایسه‌ها و حرکت‌ها در حین مرتب‌سازی در درون است

از O (n log n) تا O (n 2)؛

O(n) یک مورد ایده آل و دست نیافتنی است.

روش های مرتب سازی زیر وجود دارد:

روش های دقیق (مستقیم)؛

روش های بهبود یافته

روش های سختگیرانه:

روش اتصال مستقیم؛

روش انتخاب مستقیم؛

روش تبادل مستقیم

کارایی روش های سختگیرانه تقریباً یکسان است.

مرتب سازی شامل مستقیم

عناصر از نظر ذهنی به یک دنباله آماده a 1،...، a i-1 و دنباله اصلی تقسیم می شوند.

در هر مرحله، با شروع از i = 2 و افزایش i در هر بار، عنصر i از دنباله اصلی استخراج شده و به دنباله تمام شده منتقل می شود، در حالی که در جای مناسب درج می شود.

ماهیت الگوریتم به شرح زیر است:

برای i = 2 تا n

X = a (i)

ما در میان a (1) ... a (i) جایی پیدا می کنیم تا x را در بر گیرد

بعدی منم

دو الگوریتم مرتب سازی دربرگیری مستقیم وجود دارد. اول - بدون مانع

الگوریتم مرتب سازی شامل مستقیم بدون مانع

برای i = 2 تا n

X = a (i)

برای j = i - 1 تا 1

اگر x< a(j)

سپس a(j + 1) = a(j)

در غیر این صورت به ال

endif

j بعدی

L: a(j + 1) = x

بعدی منم

برگشت

نقطه ضعف الگوریتم فوق نقض فناوری است برنامه نویسی ساخت یافته، که در آن استفاده از پرش های بی قید و شرط نامطلوب است. اگر حلقه داخلی به عنوان یک حلقه زمانی سازماندهی شده باشد، باید یک "موانع" راه اندازی شود، بدون آن، با مقادیر منفی کلیدها، از بین رفتن اهمیت و "انجماد" رایانه رخ می دهد.

الگوریتم مرتب سازی شامل مستقیم مانع

برای i = 2 تا n

X = a (i)

A(0) = x (a(0) - مانع)

J = i - 1

در حالی که x< a(j) do

A(j+1) = a(j)

J = j - 1

در پایان

A(j+1) = x

بعدی منم

برگشت

کارایی الگوریتم گنجاندن مستقیم

تعداد مقایسه های کلیدی Ci در غربالگری i-ام حداکثر i-1 است، حداقل - 1. اگر فرض کنیم که همه جایگشت‌های N کلید به یک اندازه محتمل هستند، میانگین تعداد مقایسه‌ها = i/2 است. تعداد انتقالات Mi=Ci+3 (شامل مانع) است. حداقل برآوردها در مورد یک توالی اولیه از قبل مرتب شده از عناصر رخ می دهد، در حالی که بدترین تخمین ها زمانی رخ می دهد که آنها در ابتدا به ترتیب معکوس مرتب شوند. به یک معنا، مرتب‌سازی بر اساس گنجاندن رفتار واقعاً طبیعی را نشان می‌دهد. واضح است که الگوریتم فوق فرآیند مرتب سازی پایدار را توصیف می کند: ترتیب عناصر با کلیدهای مساوی بدون تغییر باقی می ماند.

تعداد مقایسه ها در بدترین حالت، زمانی که آرایه برعکس مرتب شده است، C max = n (n - 1) / 2، یعنی - O (n 2). تعداد جایگشت M max = C max + 3 (n-1)، یعنی. - O (n 2). اگر آرایه از قبل مرتب شده باشد، تعداد مقایسه ها و جایگشت ها حداقل است: Cmin = n-1; Mmin = = 3 (n-1).

مرتب سازی بر اساس مبادله مستقیم (مرتب سازی حبابی)

AT این بخشروشی توصیف می‌شود که در آن تبادل مکان‌های دو عنصر مشخص‌ترین ویژگی فرآیند است. الگوریتم تبادل مستقیم که در زیر توضیح داده شده است بر اساس مقایسه و تغییر مکان برای یک جفت است عناصر همسایهو این روند را تا مرتب شدن همه عناصر ادامه دهید.

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

C min = n - 1، سفارش O(n)،

و هیچ حرکتی وجود ندارد.

تحلیل مقایسه‌ای روش‌های مرتب‌سازی مستقیم نشان می‌دهد که «مرتب‌سازی» تبادلی در شکل کلاسیک آن، تلاقی بین مرتب‌سازی با استفاده از گنجاندن و استفاده از انتخاب‌ها است. اگر بهبودهای فوق در آن انجام شود، برای آرایه های به اندازه کافی مرتب شده است مرتب سازی حبابیحتی یک مزیت دارد

این روش معمولاً به عنوان "مرتب سازی حبابی" شناخته می شود.

الگوریتم روش تبادل مستقیم

برای j = n تا i مرحله -1

اگر a (j)< a(j - 1) then

در مورد ما، یک پاس «بیکار» گرفتیم. برای اینکه یک بار دیگر عناصر را مشاهده نکنید، و در نتیجه برای انجام مقایسه، صرف وقت در این مورد، می توانید چک باکس را وارد کنید fl، که در مقدار باقی می ماند نادرست، در صورتی که طی پاس بعدی تعویض صورت نگیرد. در الگوریتم زیر اضافات به صورت پررنگ مشخص شده اند.

fl = درست است

اگر fl = نادرست است، برگردید

fl = نادرست

برای j = n تا i مرحله -1

اگر a (j)< a(j - 1) then

fl = درست است

یک بهبود در مرتب سازی حبابی، مرتب سازی تکان دهنده است، که در آن پس از هر پاس، جهت در یک حلقه داخلی معکوس می شود.

کارایی الگوریتم مرتب سازی تبادل مستقیم

تعداد مقایسه‌ها C max = n(n-1)/2، سفارش O(n2).

تعداد حرکات M max \u003d 3C max \u003d 3n (n-1) / 2، به ترتیب O (n 2).

اگر آرایه از قبل مرتب شده باشد و الگوریتم پرچم اعمال شده باشد، تنها یک پاس کافی است و سپس حداقل تعداد مقایسه را بدست می آوریم.

مرتب سازی شامل مستقیم، مانند مرتب سازی انتخاب ساده، معمولاً برای آرایه هایی استفاده می شود که حاوی عناصر تکراری نیستند.

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

a ≤ a ≤ ... ≤ a .

در مرحله بعد، باید عنصر k -ام را بگیرید و در قسمت مرتب شده آرایه جایی برای آن پیدا کنید تا پس از درج ترتیب آن نقض نشود، یعنی باید چنین j را پیدا کنید (1 ≤ j ≤ k -1) که a [j] ≤ a[ k]< a. Затем вставить элемент а [k] на найденное место.

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

بیایید با یک مثال به این روند نگاه کنیم. فرض کنید لازم است آرایه ای از 10 عنصر را به ترتیب صعودی با استفاده از روش گنجاندن مستقیم مرتب کنیم.

1 - مرحله ام

13 6 8 11 3 1 5 9 15 7

منتا (13). شما باید یک دومی قرار دهید.

عنصر آرایه (6) به طوری که

حفظ شده است. از 6< 13, вставляем

6 در رتبه اول. قسمت مرتب شده

آرایه شامل دو عنصر است (6 13).

3 - مرحله ام

6 8 13 11 3 1 5 9 15 7 عنصر بعدی- 11. در قسمت مرتب آرایه در مرتبه سوم نوشته شده است، از 11 > 8، اما 11< 13.

5- گام

3 6 8 11 13 1 5 9 15 7 به همین دلیل، 1 به اولی نوشته می شود

6 - گام

1 3 6 8 11 13 5 9 15 7 از آنجایی که 5 > 3، اما 5< 6 то место 5 в упоря-

قسمت دختر سوم است.

7 -گام

1 3 5 6 8 11 13 9 15 7 جای عدد 9 ششمین است.

8 -گام

1 3 5 6 8 9 11 13 15 7 مکان ماقبل آخر را مشخص کنید

عنصر 15. معلوم می شود که این عنصر

عنصر آرایه از قبل در جای خود قرار دارد.

9 -گام

1 3 5 6 8 9 11 13 15 7 باقی مانده است که یک مکان مناسب برای

عنصر آخر (7).

1 3 5 6 7 8 9 11 13 15 آرایه کاملا مرتب شده است.

اکنون می توانیم به طور خلاصه بخشی از الگوریتم مرتب سازی دربرگیری مستقیم را شرح دهیم:

برای k:= 2 تا n انجام شود

(چون با جستجوی یک مکان خوب برای a شروع به مرتب سازی می کنم، از 2 به n می روم)

x را در جای مناسب در a، ...، a[k] وارد کنید

باقی مانده است که به این سوال پاسخ دهیم که چگونه مکان مناسبی برای عنصر x جستجو کنیم. بیایید کارهای زیر را انجام دهیم: به عناصر واقع در سمت چپ x (یعنی آنهایی که قبلاً مرتب شده اند) نگاه خواهیم کرد و به ابتدای آرایه حرکت می کنیم. لازم است عناصر a[j] را اسکن کنید، j از k-1 به 1 تغییر می کند. چنین اسکن زمانی باید پایان یابد که یکی از شرایط زیر برآورده شود:

عنصر یافت شده a[j]< x, что говорит о необходимости вставки x между a и a[j].

· انتهای سمت چپ قسمت مرتب آرایه رسیده است، بنابراین، در وهله اول باید x را وارد کنید.

تا زمانی که یکی از این شرایط برآورده شود، عناصر مشاهده شده را به موقعیت اول به سمت راست منتقل می کنیم، در نتیجه فضای زیر x در قسمت مرتب شده آزاد می شود.

برنامه مرتب سازی شامل مستقیم:

برنامه n3; ( مرتب سازی به ترتیب نزولی )

نوع ar=آرایه عدد صحیح;

مرتب سازی رویه3(var a:ar);

var i,j,x,k:integer;

برای k:=2 تا n انجام دهید

x:=a[k]; j:=k-1;

در حالی که (j>0)و(x>=a[j]) انجام می دهند

writeln("آرایه منبع را وارد کنید:");

برای i:=1 تا n را بخوانید(a[i]);

writeln("آرایه مرتب شده:");

برای i:=1 تا n بنویسید(a[i]," ");

هدف، واقعگرایانهمرتب‌سازی آرایه‌ها را با روش گنجاندن مستقیم بررسی کرده و کارایی این الگوریتم را ارزیابی کنید.

اطلاعات کلی

مرتب سازی شامل مستقیم، مانند مرتب سازی انتخاب ساده، معمولاً برای آرایه هایی استفاده می شود که حاوی عناصر تکراری نیستند. مرتب سازی با این روش به صورت متوالی مرحله به مرحله انجام می شود. در مرحله k-امدر نظر گرفته می شود که بخشی از آرایه حاوی اولین عناصر k-1 از قبل مرتب شده است، یعنی. بعد، شما باید بگیرید عنصر kthو در قسمت مرتب شده آرایه جایی برای آن انتخاب کنید که بعد از درج نظم آن به هم نخورد یعنی باید چنین چیزی را پیدا کنید. سپس باید عنصر a[k] را در محل پیدا شده وارد کنید. با هر مرحله، قسمت مرتب شده آرایه افزایش می یابد. انجام یک مرتب سازی کامل به n-1 مرحله نیاز دارد. باقی مانده است که به این سوال پاسخ دهیم که چگونه مکان مناسبی برای عنصر x جستجو کنیم. ما به صورت زیر عمل می کنیم: به عناصر واقع در سمت چپ x (یعنی آنهایی که قبلاً مرتب شده اند) نگاه خواهیم کرد و به ابتدای آرایه حرکت می کنیم. لازم است از طریق عناصر a[j] نگاه کنید، j از k-l به 1 تغییر می کند. چنین جستجوی زمانی پایان می یابد که یکی از شرایط زیر برآورده شود: عنصر a[j] پیدا شود. مثال اجازه دهید به طور خلاصه بخشی از الگوریتم مرتب سازی با استفاده از گنجاندن مستقیم: Begx:= a[k]; j:=k-1; (x را در یک مکان مناسب در a، ...، a[k] وارد کنید) (برای این کار، یک حلقه را سازماندهی می کنیم که در حالی که اجرا می شود) (j > 0 و x

وظیفه کنترل

برنامه ای بنویسید تا آخرین عنصر یک آرایه را بعد از اولین عنصر منفی همان آرایه وارد کند.

گزینه های وظیفه

توجه!!! مگر اینکه صریحاً خلاف آن ذکر شده باشد، داده های ورودی (آرایه منبع) و داده های خروجی (آرایه مرتب شده) به صورت فایل متنی، حاوی اعداد صحیح! برای همه کارها، ابتدا رویه ای برای مرتب سازی یک آرایه با استفاده از روش گنجاندن مستقیم بنویسید. 1. یک سری حاوی n عنصر داده می شود. آنها را به ترتیب صعودی مرتب کنید، در حالی که همه عناصر تکراری را کنار بگذارید. 2. مد را تعریف کنید این ردیف- مقداری که اغلب در بین عناصر آن رخ می دهد. 3. مجموعه داده اصلی مجموعه ای از سوابق متشکل از نام خانوادگی، سن و مدت خدمت است. چاپ این لیست: 1) به ترتیب حروف الفبا. 2) به ترتیب افزایش سن؛ 3) به منظور افزایش سابقه کار. 4. رویه ای برای مرتب سازی به ترتیب نزولی بنویسید. 5. با توجه به یک سری اعداد صحیح. همه را به ترتیب صعودی دریافت کنید اعداد مختلفدر این مجموعه گنجانده شده است. 6. به شما یک سری از n عدد صحیح مجزا داده می شود. اعداد صحیح متمایز را بدست آورید به طوری که 7. اعداد صحیح داده شده را پیدا کنید بالاترین ارزشدر این دنباله، پس از حذف همه اعضا از آن با مقدار 8. طبیعی داده شده است اعداد نتایج n ورزشکار است که در صدم ثانیه در دوی 100 متر اندازه گیری شده است. تیمی از چهار دونده برتر برای شرکت در مسابقه امدادی 4×100 تشکیل دهید، یعنی یکی از چهار عدد طبیعی i, j, k را مشخص کنید. ، l طوری که مجموع کمترین ارزش را دارد 9. با توجه به n نقطه تصادفی مستقل، با مختصات (xi; yi)، که به طور یکنواخت در دایره ای به شعاع 1 در مرکز مبدا توزیع شده اند. برنامه ای بنویسید که نقاط را به ترتیب افزایش فاصله از مرکز مرتب کند. 10. به شما n عدد صحیح دو رقمی مثبت داده می شود. در نظر گرفتن هر عدد به عنوان یک جفت رقم از محدوده 0 تا 9، آنها را (اعداد) به ترتیب صعودی مرتب کنید. 11. با توجه به n نقطه در هواپیما. یک (n-1)-link چندخط بسته غیر خود متقاطع را مشخص کنید که از همه این نقاط عبور می کند. (قطعات همسایه چندخط مجاز هستند روی همان خط مستقیم قرار گیرند.) اشاره. بیایید سمت چپ ترین نقطه (یعنی نقطه ای با کوچکترین مختصات x) را بگیریم و پرتوهایی را از آن به تمام نقاط دیگر رسم کنیم. حالا بیایید این پرتوها را از پایین به بالا مرتب کنیم و نقاط یک پرتو را با فاصله از ابتدای پرتو مرتب کنیم (این کار برای همه پرتوها به جز پرتوهای پایین و بالایی انجام می شود). چند خط از نقطه انتخاب شده (سمت چپ) در امتداد پرتو پایین، سپس در امتداد تمام پرتوهای دیگر (به ترتیب توضیح داده شده) خارج می شود و در امتداد پرتو بالایی باز می گردد. 12. با توجه به n نقطه در هواپیما. بدنه محدب آنها را بسازید - حداقل شکل محدب حاوی آنها. (حلقه لاستیکی کشیده شده روی میخ هایی که به یک تخته فرو رفته اند، پوسته محدب آنهاست.) نشانه. بیایید نقاط را مرتب کنیم. سپس با در نظر گرفتن نقاط به نوبه خود، بدنه محدب نقاط در نظر گرفته شده را می سازیم.