سوال طراحی الگوریتم

[yas1213]

1)الگوریتم یافتن بزرگترین و کوچک ترین عدد موجود در ارایه که حداکثر حدود 1/5n (یک و نیم) مقایسه روی عناصر ارایه انجام کند!

حداکثر حدود 1/5n (یک و نیم) مقایسه یعنی چی؟؟؟

[girl_computer]

سلام
سوال شما خیلی واضح نیست
ولی من فکر میکنم منظور همون order باشه
یعنی الگوریتم شما ازorder یک و نیم n باشه و چون ضریب تاثیری روی order نداره همون از order n باشه
باز میگم من کامل متوجه سوال شما نشدم
امیدوارم تونسته باشم کمک کنم

موفق باشی:تشویق:

[pesar irooni]

یعنی به ازای هر 2 عنصر 3 مقایسه انجام میده. یعنی یه جفت عنصر انتخاب میکنیم و بعد با هم مقایسه میکنیم و بعد عنصر بزرگتر رو با ماکسیمم فعلی و عنصر کوچکتر رو با مینیمم فعلی مقایسه میکنیم.
حالت عادی که 2n مقایسه میخواد هر عنصر رو یک بار با مینیمم و یک بار با ماکزیمم مقایسه میکنه.

[yas1213]

منظورتو نو نفهمیدم!!
عنصر بزرگتر با ماکسیمم فعلی چه فرقی داره؟؟
میشه مثال بزنین!

[pesar irooni]

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

[yas1213]

اها فهمیدم! tnx
اگه اینطوری بنویسیم که عنصر اول ارایه برابر مینیمم قرار بدیم بعد یه حلقه i=1 تا n بذاریم که یه if با شرط min بزرگتر از عناصر ارایه و به ازای این شرط عنصر دارای این شرطو min قرار بدیم
الگوریتم درسته ولی از یک و نیمn استفاده نکردم !!!
الگوریتم شما این شرط یک و نیم و داره دیگه؟؟؟

[pesar irooni]

این چیزی که شما گفتی همون الگوریتم کلاسیک قدیمیه که ماکزیمم و مینیمم رو با هم با 2n-2 مقایسه پیدا میکنه ولی چیزی که مد نظر هست و من توضیح دادم ماکزیمم و مینیمم رو با هم با 1.5n-2 مقایسه پیدا میکنه. فکر کنم هنوز متوجه نشدیدااا:متفکر:

[yas1213]

الگوریتمی که گفتیو فهمیدم این تعداد مقایسرو از کجا بدست اوردین؟

[pesar irooni]

اینم کدش به زبان C#

static void FindMinMax(int[] a)
{
int min,max;
int x, y ,start;
if (a.Length % 2 == 0)
{
if (a[0] > a[1])
{
max = a[0];
min = a[1];
}
else
{
min = a[0];
max = a[1];
}
start = 2;
}
else
{
min = max = a[1];
start = 1;
}
//Search all of array
for (int i = start; i < a.Length; i=i + 2)
{
x = a[i]; y = a[i + 1];
if (x < y) // 1st comparison
{
if (x < min) // 2nd comparison
min = x;
if (y > max) // 3rd comparison
max = y;
}
else //(x>y): x is greater than y
{
if (y < min) // 2nd comparison
min = y;
if (x > max) // 3rd comparison
max = x;
}
}
Console.WriteLine(min.ToString() + " " + max.ToString());
Console.ReadLine();
}