فرض کنید آریه ای با n عنصر که با اعداد یک تا n پر شده، هر عنصر یکبار استفاده شده است. یکی از عناصر را آرایه نیست بر اساس چه الگوریتمی و با چه مرتبه اجرای میشه اون گمشده رو پیدا کرد؟
لطفا کمکم کنید دوستان
اگر فرض کنیم آرایه نامرتبه و اون عدد گمشده هم مشخص نیست(یعنی نمیدونیم چه عددیه و در چه محلی از آرایه بوده) مرتبه اجرایی الگوریتم از (O(n خواهد بود.چون برای پیدا کردن عنصر گمشده است باید کل آرایه جستجو شود
(۲۴ بهمن ۱۳۹۰ ۰۲:۳۳ ق.ظ)fatima1537 نوشته شده توسط: اگر فرض کنیم آرایه نامرتبه و اون عدد گمشده هم مشخص نیست(یعنی نمیدونیم چه عددیه و در چه محلی از آرایه بوده) مرتبه اجرایی الگوریتم از (O(n خواهد بود.چون برای پیدا کردن عنصر گمشده است باید کل آرایه جستجو شود
نکته کار اینجاست که ما نمی دونیم اون عنصر کدومه که دنبالش سرچ کنیم.
یعنی یکی گم شده . باید پیدا کنیم کی گم شده
در کتاب مقسمی دیدم که این طوری حل کرده: هر عنصر را از لیست می خوانیم و در لیست دیگه ای به جای هر عنصر true یا false قرار می دهیم. مثلا لیست ۱و۲و۳و۴و۵ داریم که ۳ گم شده.
پس داریم ۱۲۴۵
یکی یکی از سر لیست می خوانیم . پس فقط یک عنصر هست که false شده پس همون عنصر گم شده است. با جستجوی خطی برای یافتن عنصر FALSE می توان به جواب رسید.
[attachment=2697]
یک راه دیگه هم هست:
جمع اعداد یک تا N را حساب کنید . بعد جمع اعداد موجود در لیست هم حساب کنید. این دو را ازهم کم کنید میشه عنصر حذف شده.
که میشه از مرتبه n
راه دیگر:
یکجا هم دیدم که سوال را این طوری حل کرده . xor اعداد ۱ تا n را حساب می کنیم. xor اعداد موجود را هم حساب می کنیم. دوتا عدد حاصل از دو xor را باهم xor می کنیم. جواب xor همان عنصر گم شده است. این هم از مرتبه n است.
برای لیست مرتب این مرتبه به logn هم می رسد ولی لیست این سوال مرتب نیست.
اگر ندونیم چه عنصری گم شده باید اول آرایه رو به صورت غیر نزولی مرتب کرد که از مرتبه nlogn میشه(به روش تقسیم و غلبه) و بعد هر عنصر در اندیس مربوط به خودش قرار میگیره مگر اینکه عنصری گم شده باشه(که باعث میشه بقیه در یک خانه با اندیس کمتر قرار گرفته باشند)
برای پیدا کردن عنصر گمشده باید آرایه از ابتدا جستجو بشه و شماره اندیس با محتوای خانه آرایه مقایسه بشه.اگر محتوا کمتر از اندیس بود همون عنصر گمشده است .که جستجو هم حداکثر از مرتبه( O(n است
ودر کل مرتبه زمانی الگوریتم میشه از مرتبه n log n
من روشی که به ذهنم رسیده بود رو گفتم.
ولی روشهایی هم که نوشتید جالبن
(۲۴ بهمن ۱۳۹۰ ۰۲:۳۰ ب.ظ)saeedeh123 نوشته شده توسط: یک راه دیگه هم هست:یه تکنیک دیگه هم هست که فقط با بیت اعداد سر و کار داره اونم از مرتبه خطیه( برای این مسئله کلی راه راه کار خطی داریم )
جمع اعداد یک تا N را حساب کنید . بعد جمع اعداد موجود در لیست هم حساب کنید. این دو را ازهم کم کنید میشه عنصر حذف شده.
که میشه از مرتبه n
راه دیگر:
یکجا هم دیدم که سوال را این طوری حل کرده . xor اعداد ۱ تا n را حساب می کنیم. xor اعداد موجود را هم حساب می کنیم. دوتا عدد حاصل از دو xor را باهم xor می کنیم. جواب xor همان عنصر گم شده است. این هم از مرتبه n است.
برای لیست مرتب این مرتبه به logn هم می رسد ولی لیست این سوال مرتب نیست.
در کل این تکنیکا بیشتر بچه های ACM دنبالش هستن . بعضی از این تکنیکا خیلی خفن هست و واقعا هوشمندانه طرح میشه
کلا بچه های که تو این زمینه کار میکنن خیلی سریع قدرت پردازش مغزشون بالا میره و خیلی خلاق میشن
جمع اعداد یک تا N را حساب کنید . بعد جمع اعداد موجود در لیست هم حساب کنید. این دو را ازهم کم کنید میشه عنصر حذف شده.
این راه حل به دلیل اینکه ثابت کمتری داره از بقیه سریعتره .... ممنون از پاسختون...!
