زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۰۴:۲۹ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

سوال از تقسیم و حل

ارسال:
۱۶ مهر ۱۳۹۱, ۱۲:۵۱ ق.ظ (آخرین ویرایش در این ارسال: ۱۶ مهر ۱۳۹۱ ۰۱:۰۱ ق.ظ، توسط Mänu.)
سوال از تقسیم و حل
اگر در داخل یک آرایه [tex]a\left ( 1...n \right )[/tex] تمام اعداد صحیح صفر تا n به صورت باینری فقط یکبار دیده شوند و فقط عدد صحیح [tex]x\epsilon a\left ( 1...n \right )[/tex] در داخل آرایه نباشد ،در این صورت پیچدگی زمانی که عدد از دست رفته x را میتوان یافت کدام است؟
جواب:[tex]o(n)[/tex]

من اناری را، می کنم دانه، به دل می گویم:
خوب بود این مردم ، دانه های دلشان پیدا بود.
می پرد در چشمم آب انار: اشک می ریزم.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۱۶ مهر ۱۳۹۱, ۰۹:۵۱ ق.ظ
RE: سوال از تقسیم و حل
(۱۶ مهر ۱۳۹۱ ۱۲:۵۱ ق.ظ)mahtab_rafiei نوشته شده توسط:  اگر در داخل یک آرایه [tex]a\left ( 1...n \right )[/tex] تمام اعداد صحیح صفر تا n به صورت باینری فقط یکبار دیده شوند و فقط عدد صحیح [tex]x\epsilon a\left ( 1...n \right )[/tex] در داخل آرایه نباشد ،در این صورت پیچدگی زمانی که عدد از دست رفته x را میتوان یافت کدام است؟
جواب:[tex]o(n)[/tex]

سلام
مشکلی نیست که ! یه آرایه پر از قبل آماده میکنیم به صورتی که هر عددی که داخل هر خونش هست،همان اندیس آرایه هست
یعنی : a[i]=i بعد این آرایه رو با آرایه خودمون با استفاده از یک حلقه فور چک میکنیم و تست میکنیم که کجا همخوانی نداره
هزینه حلقه هم n میشود.

باز هوای وطنم وطنم آرزوست Heart مهر بود بر دهنم، سخنم آرزوست
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: Mänu
ارسال:
۱۶ مهر ۱۳۹۱, ۱۱:۳۱ ق.ظ
سوال از تقسیم و حل
یک راه ساده تر و البته خلاقانه تر دارم!
اعداد ۱ تا n رو با هم جمع کنین
این حاصل رو از مجموع اعداد داخل آرایه کم کنین
جواب به دست اومد!
روش سریع با مرتبه اجرایی خطی
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: Mänu , Mohammad-A
ارسال:
۱۷ مهر ۱۳۹۱, ۰۹:۲۷ ب.ظ
سوال از تقسیم و حل
(۱۶ مهر ۱۳۹۱ ۰۹:۵۱ ق.ظ)naderx نوشته شده توسط:  یه آرایه پر از قبل آماده میکنیم به صورتی که هر عددی که داخل هر خونش هست،همان اندیس آرایه هست
یعنی : a[i]=i بعد این آرایه رو با آرایه خودمون با استفاده از یک حلقه فور چک میکنیم و تست میکنیم که کجا همخوانی نداره
هزینه حلقه هم n میشود.
این روش غلطه
ضمنا اگر بخواییم طوری تغییرش بدیم که درست باشه مرتبه اجرایی خطی نخواهد داشت.
کمی بهش فکر کنین، خودتون میتونین متوجه اشتباه بودنش بشین.
روی سوال نگفته هر عدد تو جای خودشه! پس این چک کردنی که شما گفتین، با مرتبه خطی جواب درستی نخواهد داشت. (چون هر عدد رو باید یه بار با کل آرایه چک کنیم ... البته طبق روش شما)
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال:
۱۸ مهر ۱۳۹۱, ۱۱:۵۴ ق.ظ
سوال از تقسیم و حل
(۱۸ مهر ۱۳۹۱ ۰۱:۱۲ ق.ظ)mohammad-a نوشته شده توسط:  یه مسئله: به نظر شما قصد سوال از اینکه گفته اعداد به صورت باینری هستند٬ چی بوده؟ (قصد داشته چه بخشی رو گمراه کنه؟ Smile )
قصدش این بوده که داوطلب فکر کنه باید با تک تک بیت های اعداد کار کنه و چون تعداد بیت های هر عدد زیاد میشه، پس ذهنش اصلا به سمت مرتبه اجرایی خطی نمیره و مرتبه اجرایی بزرگتری رو برای جواب انتخاب میکنه و در نتیجه تو تله طراح میوفته
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: Mänu
ارسال:
۱۸ مهر ۱۳۹۱, ۱۲:۳۸ ب.ظ
سوال از تقسیم و حل
(۱۸ مهر ۱۳۹۱ ۱۲:۲۰ ب.ظ)mohammad-a نوشته شده توسط:  فکر کنم در اینصورت٬ [tex]N^2[/tex] میشد. نه؟
بازم بستگی به راه انتخابی داشت. ولی چیزی بین nlogn و n^2 میشه اگه کسی تو این دام بیوفته.
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس‌گزاری شده توسط: Mohammad-A
ارسال:
۱۹ مهر ۱۳۹۱, ۰۷:۱۹ ب.ظ (آخرین ویرایش در این ارسال: ۱۹ مهر ۱۳۹۱ ۰۸:۰۸ ب.ظ، توسط valarmorgulios.)
RE: سوال از تقسیم و حل
این سوال منظورش اینه که فقط باید از باینری استفاده کنیم و تنها حرکتی که می تونیم بکنیم دستیابی به j امین بیت درایه a[i] هست خوب برای اینکار ما اول بایدتشخیص بدهیم عدد فرده یا زوج پس کافیه به بیت logn ام هر خونه از درایه با مرتبه زمانی o[1] دسترسی پیدا کنیم که اگه تا آخر بریم میشود n حال اگه تعداد عناصر زوج از n/2 یکی کمتر باشه پس معلوم میشه عدد یکی از اعداد زوج آرایه هست وبلعکس .فرض میکنیم زوج باشه خوب حال n/2-1 عدد داریم که ایندفعه باید بیت logn -1 رو چک کنیم توجه کنید در اینجا چون گفته اعداد از یک تا n هستن اینکارو میکنیم . تو این مرحله باز اون دسته ای که بیت log n-1 شان n/4-1 باشه رو دوباره همون حرکتای بالایی رو روش میزنیم با تقسیم و غلبه (کدش هم میشه راحت نوشت) و همینطوری تا n/n پیش میریم که در نهایت میشه n+n/2+ n/4+n/8+...+n/2i که سری ۱ تقسیم بر ۲ به توان i همانطور که میدونین میشه ۲ پس در کل زمانش ۲n و از مرتبه o(n) میشه.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۱,۲۰۰ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  سخنرانی دکتر حلت fas ۲ ۴۳ ۲۳ آبان ۱۳۹۸ ۰۱:۲۱ ب.ظ
آخرین ارسال: xiaomi
  تقسیم برای محاسبه کد افزونه چرخشی (CRC) Sanazzz ۴ ۶,۱۴۴ ۲۰ آذر ۱۳۹۷ ۰۱:۱۸ ب.ظ
آخرین ارسال: Sanazzz
  راه حلی برای یافتن تداخل در روشهای تقدم Sepideh96 ۱ ۱,۹۴۴ ۰۷ بهمن ۱۳۹۶ ۱۱:۵۹ ب.ظ
آخرین ارسال: alilash
  شبکه معنایی تقسیم شده در هوش rezahe73 ۰ ۱,۱۲۸ ۱۷ دى ۱۳۹۶ ۰۴:۰۹ ق.ظ
آخرین ارسال: rezahe73
  تقسیم افراد به دو تیم ss311 ۲ ۱,۶۱۴ ۱۲ دى ۱۳۹۶ ۱۱:۵۷ ب.ظ
آخرین ارسال: ss311
  تقسیم در جبر رابطه ای Ella ۱ ۲,۰۰۹ ۲۸ آذر ۱۳۹۶ ۱۲:۰۰ ق.ظ
آخرین ارسال: Ella
  تفاوت مدل های نمونه سازی افزایشی و حلزونی Szare295@gmail.com ۲ ۳,۴۹۵ ۰۷ دى ۱۳۹۵ ۱۱:۵۷ ق.ظ
آخرین ارسال: Szare295@gmail.com
  صف حلقوی alireza01 ۸ ۸,۹۱۷ ۱۸ آبان ۱۳۹۵ ۰۳:۱۹ ب.ظ
آخرین ارسال: alireza01
  تحلیل زمانی دو حلقه تو در تو H-Arshad ۱ ۱,۹۴۱ ۱۰ آبان ۱۳۹۵ ۰۲:۳۲ ق.ظ
آخرین ارسال: Behnam‌

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close