۰
subtitle
ارسال: #۱
پیدا کردن عنصر گمشده در بین ۱-n
فرض کنید آریه ای با n عنصر که با اعداد یک تا n پر شده، هر عنصر یکبار استفاده شده است. یکی از عناصر را آرایه نیست بر اساس چه الگوریتمی و با چه مرتبه اجرای میشه اون گمشده رو پیدا کرد؟
لطفا کمکم کنید دوستان
لطفا کمکم کنید دوستان
۰
ارسال: #۲
RE: پیدا کردن عنصر گمشده در بین ۱-n
در کتاب مقسمی دیدم که این طوری حل کرده: هر عنصر را از لیست می خوانیم و در لیست دیگه ای به جای هر عنصر true یا false قرار می دهیم. مثلا لیست ۱و۲و۳و۴و۵ داریم که ۳ گم شده.
پس داریم ۱۲۴۵
یکی یکی از سر لیست می خوانیم . پس فقط یک عنصر هست که false شده پس همون عنصر گم شده است. با جستجوی خطی برای یافتن عنصر FALSE می توان به جواب رسید.
یک راه دیگه هم هست:
جمع اعداد یک تا N را حساب کنید . بعد جمع اعداد موجود در لیست هم حساب کنید. این دو را ازهم کم کنید میشه عنصر حذف شده.
که میشه از مرتبه n
راه دیگر:
یکجا هم دیدم که سوال را این طوری حل کرده . xor اعداد ۱ تا n را حساب می کنیم. xor اعداد موجود را هم حساب می کنیم. دوتا عدد حاصل از دو xor را باهم xor می کنیم. جواب xor همان عنصر گم شده است. این هم از مرتبه n است.
برای لیست مرتب این مرتبه به logn هم می رسد ولی لیست این سوال مرتب نیست.
پس داریم ۱۲۴۵
یکی یکی از سر لیست می خوانیم . پس فقط یک عنصر هست که false شده پس همون عنصر گم شده است. با جستجوی خطی برای یافتن عنصر FALSE می توان به جواب رسید.
یک راه دیگه هم هست:
جمع اعداد یک تا N را حساب کنید . بعد جمع اعداد موجود در لیست هم حساب کنید. این دو را ازهم کم کنید میشه عنصر حذف شده.
که میشه از مرتبه n
راه دیگر:
یکجا هم دیدم که سوال را این طوری حل کرده . xor اعداد ۱ تا n را حساب می کنیم. xor اعداد موجود را هم حساب می کنیم. دوتا عدد حاصل از دو xor را باهم xor می کنیم. جواب xor همان عنصر گم شده است. این هم از مرتبه n است.
برای لیست مرتب این مرتبه به logn هم می رسد ولی لیست این سوال مرتب نیست.
ارسال: #۳
RE: پیدا کردن عنصر گمشده در بین ۱-n
(۲۴ بهمن ۱۳۹۰ ۰۲:۳۰ ب.ظ)saeedeh123 نوشته شده توسط: یک راه دیگه هم هست:یه تکنیک دیگه هم هست که فقط با بیت اعداد سر و کار داره اونم از مرتبه خطیه( برای این مسئله کلی راه راه کار خطی داریم )
جمع اعداد یک تا N را حساب کنید . بعد جمع اعداد موجود در لیست هم حساب کنید. این دو را ازهم کم کنید میشه عنصر حذف شده.
که میشه از مرتبه n
راه دیگر:
یکجا هم دیدم که سوال را این طوری حل کرده . xor اعداد ۱ تا n را حساب می کنیم. xor اعداد موجود را هم حساب می کنیم. دوتا عدد حاصل از دو xor را باهم xor می کنیم. جواب xor همان عنصر گم شده است. این هم از مرتبه n است.
برای لیست مرتب این مرتبه به logn هم می رسد ولی لیست این سوال مرتب نیست.
در کل این تکنیکا بیشتر بچه های ACM دنبالش هستن . بعضی از این تکنیکا خیلی خفن هست و واقعا هوشمندانه طرح میشه
کلا بچه های که تو این زمینه کار میکنن خیلی سریع قدرت پردازش مغزشون بالا میره و خیلی خلاق میشن
۰
ارسال: #۴
پیدا کردن عنصر گمشده در بین ۱-n
جمع اعداد یک تا N را حساب کنید . بعد جمع اعداد موجود در لیست هم حساب کنید. این دو را ازهم کم کنید میشه عنصر حذف شده.
این راه حل به دلیل اینکه ثابت کمتری داره از بقیه سریعتره .... ممنون از پاسختون...!
این راه حل به دلیل اینکه ثابت کمتری داره از بقیه سریعتره .... ممنون از پاسختون...!
۰
ارسال: #۵
پیدا کردن عنصر گمشده در بین ۱-n
اگر فرض کنیم آرایه نامرتبه و اون عدد گمشده هم مشخص نیست(یعنی نمیدونیم چه عددیه و در چه محلی از آرایه بوده) مرتبه اجرایی الگوریتم از (O(n خواهد بود.چون برای پیدا کردن عنصر گمشده است باید کل آرایه جستجو شود
ارسال: #۶
RE: پیدا کردن عنصر گمشده در بین ۱-n
(۲۴ بهمن ۱۳۹۰ ۰۲:۳۳ ق.ظ)fatima1537 نوشته شده توسط: اگر فرض کنیم آرایه نامرتبه و اون عدد گمشده هم مشخص نیست(یعنی نمیدونیم چه عددیه و در چه محلی از آرایه بوده) مرتبه اجرایی الگوریتم از (O(n خواهد بود.چون برای پیدا کردن عنصر گمشده است باید کل آرایه جستجو شود
نکته کار اینجاست که ما نمی دونیم اون عنصر کدومه که دنبالش سرچ کنیم.
یعنی یکی گم شده . باید پیدا کنیم کی گم شده
۰
ارسال: #۷
پیدا کردن عنصر گمشده در بین ۱-n
اگر ندونیم چه عنصری گم شده باید اول آرایه رو به صورت غیر نزولی مرتب کرد که از مرتبه nlogn میشه(به روش تقسیم و غلبه) و بعد هر عنصر در اندیس مربوط به خودش قرار میگیره مگر اینکه عنصری گم شده باشه(که باعث میشه بقیه در یک خانه با اندیس کمتر قرار گرفته باشند)
برای پیدا کردن عنصر گمشده باید آرایه از ابتدا جستجو بشه و شماره اندیس با محتوای خانه آرایه مقایسه بشه.اگر محتوا کمتر از اندیس بود همون عنصر گمشده است .که جستجو هم حداکثر از مرتبه( O(n است
ودر کل مرتبه زمانی الگوریتم میشه از مرتبه n log n
برای پیدا کردن عنصر گمشده باید آرایه از ابتدا جستجو بشه و شماره اندیس با محتوای خانه آرایه مقایسه بشه.اگر محتوا کمتر از اندیس بود همون عنصر گمشده است .که جستجو هم حداکثر از مرتبه( O(n است
ودر کل مرتبه زمانی الگوریتم میشه از مرتبه n log n
۰
ارسال: #۸
پیدا کردن عنصر گمشده در بین ۱-n
من روشی که به ذهنم رسیده بود رو گفتم.
ولی روشهایی هم که نوشتید جالبن
ولی روشهایی هم که نوشتید جالبن
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close