انجمنصفحه اولجستجوی انجمن

[freidoony]

(۲۳ بهمن ۱۳۹۱ ۱۲:۰۷ ب.ظ)arta.66 نوشته شده توسط:  

(23 بهمن ۱۳۹۱ ۰۱:۱۱ ق.ظ)fatima1537 نوشته شده توسط:  تست ۴۹ - ۲ - بخش "الف" که شبیه عملیات روی AVL هست. بخش "ب" غلطه.البته مرتبه ساخت و درج شبیه مین هیپ هست ولی حذف کوچکترین عنصر نیست.به نظر من میشه گزینه۲

سوال ۴۹ الف مطمئنا غلطه!! حالا چرا یه مثال ساده میارم که نقض شه شما یه درخت متوازن با اعداد ۱ تا ۸ بساز!! ۵ میاد توو ریشه ۳و ۷ هم میشن فرزندان چپ و راستش!! وبه همین ترتیب!! حالا سوال من میگم تعداد اعداد ۲ تا ۸ رو واسه من پیدا کن؟؟؟چطوری با لگاریتم میشه؟؟؟ چون اعداد توو ۲تا زیردرختم هستن!! جواب گزینه ۴ هستش جفتش را نمی توان!!

درسته
برای جستجو اگه کلید گره از aوb بزرگتر باشه زیر درخت سمت چپ جستجو می شه، اگر از a و b کوچکتر باشه زیر درخت سمت راست و اگر بین a و b باشه هر دو زیر درخت باید جستجو بشه پس بد ترین حالت زمانی اتفاق می افته که همه گره ها بین a و b باشد یعنی از درجه O(n) و بهترین حالت هم O(logn)

[fatima1537]

دوستای عزیز خواهشا یکم مهربانتر با هم بحث کنیم.به این روش نمیشه طرف مقابل رو قانع کرد.وقتی که دارید با ذکر منبع استدلال میکنید . حالا طرف مقابل قبول کنه یا نه سودی به حال ما نداره.
شما هر کدوم اثباتتون را بفرمایید . سنجش هم کلید خودش رو میده.نهایتا اعتراض مستدل میکنید.والسلام

[edge]

بیخیال آقای کنوث تو هم مثه اینکه از اون nlogk ه به دل گرفتیا خوب باشه nlogk.

[Nima Masghadi]

در مورد سوال ۴۷ ( البته من این تست رو نزدم ولی اومدم خونه حساب کردم )
این تست منظورش اینه که ابتدای صف میشه عنصر بالای یکی از پشته ها و انتهای صف هم میشه عنصر بالای پشته دومی
اول ۵۰ تا درج داریم یعنی ۵۰ تا پوش
بعد ۵۰ تا بخوایم حذف کنیم
اول باید ۵۰ تایی که درج کردیم از تو یک پشته دونه دونه برداریم بریزیم تو پشته دومی یعنی ۵۰ پاپ و ۵۰ پوش 
بعد دونه دونه حذف کنیم که میشه ۵۰ پاپ
جمعا میشه ۲۰۰

[Farid_Feyzi]

سلام عزیزان
در مورد سوال ۴۹ قسمت الف داده ساختاری به اسم درخت مرتبه آماری وجود داره که تو زمان لگاریتمی میشه عملیات گفته شده رو پاسخ داد.
این درخت ارتفاع لگاریتمی داره و علاوه بر اعمال درج و حذف و جستجو میشه دوتا عمل زیر رو هم تو زمان لگاریتمی انجام داد.
۱-پیدا کردن kامین کوچکترین عنصر
۲-پیدا کردن مرتبه یه عنصر(یعنی جایگاه یه عنصر تو ترتیب مرتب عناصر)

برای پیدا کردن تعداد عناصر بین a و b هم کافیه عبارت زیر محاسبه بشه.

(مرتبه بزرگترین عنصر کوچکتر یا مساوی b منهای مرتبه کوچکترین عنصر بزرگتر یا مساوی از a)

در مورد قسمت ب هم میشه گفت که چنین داده ساختاری نمیشه ایجاد کرد چون اگه بشه در واقع میتونیم مرتب سازی رو تو زمان کمتری از nlogn انجام بدیم یعنی تو اُ کوچیک nlogn
با ایجاد داده ساختار تو زمان n و با n بار حذف کوچیک ترین عنصر

[mehdi3254]

سوال ۴۸ یکم مشکوکه و فقط نظر طراح میتونه قبول بشه!!!!(متاسفانه)
البته به نظر من nk میشه چون بقیه گزینه ها یه جورایی هم ارز هستند! البته نه هم ارز ریاضی هم ارز از لحاظ مرتبه زمانی!

[fum_com]

سلام
در سوال ۵۰ بهترین الگوریتم برای مرتب سازی Radix sort هست و میدونیم که مرتبه زمانیش ( (d*(n + r) هست
که d همان تعداد ارقام n تعداد اعداد و r مبناست،برای به دست آوردن تعداد ارقام کافیست تا از n^k لگاریتم بگیریم در مبنای n (چون گفته بهترین) ، بنابراین داریم : K*(n + n) = 2nk پس مرتبه زمانی میشه nk

[nasman]

(۲۱ بهمن ۱۳۹۱ ۱۱:۲۷ ب.ظ)sarous نوشته شده توسط:  سوال ۱۰۱ قطعا گزینه ۲ جواب صحیحه.در بدترین حالت باید ۳۱ بسته رو باز کرد.

---

در مورد سوال ۴۷ پاسخ قطعا ۱۹۹هست که من اشتباها ۲۰۰ زدم.
من اینجور حساب کردم شد ۲۰۰ ولی غلطه.
۵۰ درج هزینش :۵۰
۱ حذف هزینش : ۵۰+۱
۴۹ درج هزینش :۴۹
۱ حذف هزینش : ۴۹+۱
جما ۲۰۰
ولی پاسخ صحیح:
۹۹درج هزینش :۹۹
۱ حذف هزینش : ۹۹+۱
جمعا ۱۹۹
سوال ۴۹:هیچکدام را نمیتوان ساخت.اولیش به avl نزدیکه و دومیش به max heap ولی این دو تا نیستن.
۵۲ قطعا از مرتبه n هست.درسته در صورت سوال مقدار اولیه مینیمم رو اشتباه انتخاب کرده ولی قطعا بخاطر همیچین قضیه ای حذف نمیشه.در بهترین حالت ۱ بار اجرا میشه و در بدترین حالت n-1 بار که بر ۲ تقسیم کنیم از مرتبه n هستش.

سوال ۴۷ چون حداکثر رو خواسته پاسخ ۲۰۰ میشه درست زدی

---

(۲۳ بهمن ۱۳۹۱ ۰۴:۳۹ ب.ظ)Mahdi .Tahmouresi نوشته شده توسط:  دوستان سئوال ۴۷ مثل اینکه طلبه زیاد داره جواب صحیح گزینه هیچکدام می باشد و پاسخ صحیح ۱۴۹ هست حالا چرا؟ لطفا مطلب پایین را بخوانید.
تو صورت سئوال گفته هر push و pop رو هر استک ۱ واحد یعنی مجموع این دو عمل ۱ واحد و گفته که بشترین هزینه برای ۱۰۰ عمل که خیلی ساده می توانید حساب کنید، ابتدا ۹۹ عمل push به استک اول حالا عمل آخر از اون ۱۰۰ عمل را انجام می دیم یعنی حذف چون استک دومی خالی مجبوریم ۹۹ pop از استک اول انجام دهیم و سپس ۹۹ Push به استک دوم و در آخر ۱ pop از استک دوم حالا تعداد push و pop ها را جمع می کنیم ۹۹+۹۹+۹۹+۱=۲۹۸ حاصل را بر ۲ تقسیم می کنیم چرا که هر ۲ عمل push و pop یک واحد بود و نتیجه می شود ۱۴۹!!!
توضیح برای آن دساه از دوستان که میگن خیر هر عمل یک واحد خیلی ساده باید بگم به شما که اگر این طور هم فرض کنیم جواب می شود ۲۹۸ حد اکثر هزینه را خواسته
موفق و سربلند باشید

پاسخ شما با فرضتان تناقض دارد فرض کنیم هر push و pop دارای هزینه یک باشند در این صورت باید تعدادشان برابر باشد و در صورتی push و pop ها با هم برابرند که ۵۰ ورود و ۵۰ خروج داشته باشیم یعنی ۵۰ push و سپس ۵۰ pop و دوباره ۵۰ push و سپس ۵۰ pop که جمعا ۲۰۰ میشود.ولی شما ۱۹۷ push و ۱۰۰ pop در نظر گرفته اید چطور میخواهید دو بدو انها را با هم جفت کنید اللهو اعلم!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!؟؟

[Mahdi .Tahmouresi]

جواب سئوال ۴۷ را من با چند نفر در میان گزاشتم و نتیجه اینه که طراح محترم یادش رفته قید کنه منظورش پر هزینه ترین عمل بین ۱۰۰ عمل چقدر هزینش میشه و راه های که من تو پستهای قبلی رفتم کاملا درست بوده فقط اگه این نکته که گفتم را رعایت کنیم جواب می شه ۱۹۹ دلیلشم اینه که هر عمل در حالت عادی ۱ واحد زمان می خواد مثل درج اولیه و زمانه بیشتر می شه که از روتین عادی خارج بشه و در بترین حالت اینه که ۹۹ عمل درج ابتدا انجام بدهیم و بعد از آن ۱ حذف اگه کمی دقت کنید هزینه ۹۹ عمل اول به ازای هر عمل یک واحد زمانی می باشد ولی برای حذف (عمل آخری) باید ۱۹۹ واحد زمانی هزینه کرد ولی این نکته کاملا غیر واضح بود و فکر نمی کنم خواننده این را برداشت کنه ولی جواب همینه این خط این نشان

[mehdi3254]

(۲۶ بهمن ۱۳۹۱ ۱۰:۲۶ ب.ظ)Mahdi .Tahmouresi نوشته شده توسط:  جواب سئوال ۴۷ را من با چند نفر در میان گزاشتم و نتیجه اینه که طراح محترم یادش رفته قید کنه منظورش پر هزینه ترین عمل بین ۱۰۰ عمل چقدر هزینش میشه و راه های که من تو پستهای قبلی رفتم کاملا درست بوده فقط اگه این نکته که گفتم را رعایت کنیم جواب می شه ۱۹۹ دلیلشم اینه که هر عمل در حالت عادی ۱ واحد زمان می خواد مثل درج اولیه و زمانه بیشتر می شه که از روتین عادی خارج بشه و در بترین حالت اینه که ۹۹ عمل درج ابتدا انجام بدهیم و بعد از آن ۱ حذف اگه کمی دقت کنید هزینه ۹۹ عمل اول به ازای هر عمل یک واحد زمانی می باشد ولی برای حذف (عمل آخری) باید ۱۹۹ واحد زمانی هزینه کرد ولی این نکته کاملا غیر واضح بود و فکر نمی کنم خواننده این را برداشت کنه ولی جواب همینه این خط این نشان

طراح که گفته حداکثر هزینه.اونم ۲۰۰ میشه.شما در نظر بگیر ۱۰۰ تا داده داریم یکی یکی میذاریم توی صف و برمیداریم.یعنی یکی میذاریم همون وقتم برمیداریم که میشه برا هر داده ۴ پوش و پاپ که میشه کلش ۴۰۰ تا و چون گفته هر پوش و پاپ یک عمل پس میشه ۲۰۰/

[۶۶الی]

(۲۲ بهمن ۱۳۹۱ ۱۱:۲۰ ق.ظ)vahidfrr نوشته شده توسط:  

(21 بهمن ۱۳۹۱ ۱۱:۲۷ ب.ظ)sarous نوشته شده توسط:  سوال ۱۰۱ قطعا گزینه ۲ جواب صحیحه.در بدترین حالت باید ۳۱ بسته رو باز کرد.

---

در مورد سوال ۴۷ پاسخ قطعا ۱۹۹هست که من اشتباها ۲۰۰ زدم.
من اینجور حساب کردم شد ۲۰۰ ولی غلطه.
۵۰ درج هزینش :۵۰
۱ حذف هزینش : ۵۰+۱
۴۹ درج هزینش :۴۹
۱ حذف هزینش : ۴۹+۱
جما ۲۰۰
ولی پاسخ صحیح:
۹۹درج هزینش :۹۹
۱ حذف هزینش : ۹۹+۱
جمعا ۱۹۹
سوال ۴۹:هیچکدام را نمیتوان ساخت.اولیش به avl نزدیکه و دومیش به max heap ولی این دو تا نیستن.
۵۲ قطعا از مرتبه n هست.درسته در صورت سوال مقدار اولیه مینیمم رو اشتباه انتخاب کرده ولی قطعا بخاطر همیچین قضیه ای حذف نمیشه.در بهترین حالت ۱ بار اجرا میشه و در بدترین حالت n-1 بار که بر ۲ تقسیم کنیم از مرتبه n هستش.

در مورد سوال ۴۹ هر دو درست است اولی avl و همه اعمال را می توتن انجام داد در زمان logn و مورد بعدی هم ماکس هیپ که مشکلی ندارد

سوال ۴۹ اولی نادرست چون وقتی گفته چند باد عنصر کوچکتر یا بزرگتر پس logn نمی شه چون چند بار succ یا pere باید صدا زده شه
ولی دومی درست بود

---

(۲۲ بهمن ۱۳۹۱ ۰۲:۳۷ ب.ظ)ADELZX نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۰۲:۳۵ ب.ظ)mfXpert نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۰۲:۲۴ ب.ظ)ADELZX نوشته شده توسط:  توی صورت سوال o کوچیک گذاشته .
و این رو قبول دارین که حذف کوچیکترین عنصر در مین هیپ از ریشه است که اونم به ارتفاع مرتبطه (logn) چون کامله؟

چه نتیجه‌ای از این حرف شما باید گرفت؟

خب چطور شما میفرمایید که میشه گره ریشه رو در کمتر از logn حذفش کرد ؟

در کمتر logn میشه چون heapify زمانش کمتر از logn

[Mahdi .Tahmouresi]

(۲۷ بهمن ۱۳۹۱ ۱۲:۵۰ ق.ظ)mehdi3254 نوشته شده توسط:  

(26 بهمن ۱۳۹۱ ۱۰:۲۶ ب.ظ)Mahdi .Tahmouresi نوشته شده توسط:  جواب سئوال ۴۷ را من با چند نفر در میان گزاشتم و نتیجه اینه که طراح محترم یادش رفته قید کنه منظورش پر هزینه ترین عمل بین ۱۰۰ عمل چقدر هزینش میشه و راه های که من تو پستهای قبلی رفتم کاملا درست بوده فقط اگه این نکته که گفتم را رعایت کنیم جواب می شه ۱۹۹ دلیلشم اینه که هر عمل در حالت عادی ۱ واحد زمان می خواد مثل درج اولیه و زمانه بیشتر می شه که از روتین عادی خارج بشه و در بترین حالت اینه که ۹۹ عمل درج ابتدا انجام بدهیم و بعد از آن ۱ حذف اگه کمی دقت کنید هزینه ۹۹ عمل اول به ازای هر عمل یک واحد زمانی می باشد ولی برای حذف (عمل آخری) باید ۱۹۹ واحد زمانی هزینه کرد ولی این نکته کاملا غیر واضح بود و فکر نمی کنم خواننده این را برداشت کنه ولی جواب همینه این خط این نشان

طراح که گفته حداکثر هزینه.اونم ۲۰۰ میشه.شما در نظر بگیر ۱۰۰ تا داده داریم یکی یکی میذاریم توی صف و برمیداریم.یعنی یکی میذاریم همون وقتم برمیداریم که میشه برا هر داده ۴ پوش و پاپ که میشه کلش ۴۰۰ تا و چون گفته هر پوش و پاپ یک عمل پس میشه ۲۰۰/

داداش شما زدی سئوال رو هم عوض کردی ۱۰۰ داده نگفته که گفته ۱۰۰ عمل اون چیزی که شما گفتین می شه ۲۰۰ عمل ولی من با شما موفقم که هر ۲ عمل push و pop گفته می شه ۱ واحد ولی جوری گفته که بشه گفت منظورش هر کدوم از اعمال یک واحده و منظورشم این بوده و همون طوری که گفتم گرانترین عمل بین ۱۰۰ عمل را خواسته نه مجموع اعمال اگرچه تو صورت سئوال گفته نشده من که از خدامه حذف شه

[Farid_Feyzi]

سلام
در مورد سوال ۵۲ باید تحلیل زیر رو انجام داد.

در واقع در مرحله iام، عنصر [tex]A[i][/tex] برای اینکه جایگزین min بشه(یعنی سطر ۴ اجرا بشه) بایستی کوچیکترین عنصر موجود در زیر آرایه ی [tex]A[1..i][/tex] باشه که احتمالش [tex]\frac{1}{i}[/tex] هست. پس برای پیدا کردن میانگین تعداد اجرای این دستور باید داشته باشیم:
[tex]\sum_{i=1}^{n}\frac{1}{i}=Ln(n)[/tex]
و در نتیجه میشه گفت میانگین [tex]\theta(logn)[/tex] خواهد بود و گزینه ۱ صحیحه.

[MajidManesht2012]

(۲۷ بهمن ۱۳۹۱ ۰۵:۵۲ ب.ظ)farid_express نوشته شده توسط:  سلام
در مورد سوال ۵۲ باید تحلیل زیر رو انجام داد.

در واقع در مرحله iام، عنصر [tex]A[i][/tex] برای اینکه جایگزین min بشه(یعنی سطر ۴ اجرا بشه) بایستی کوچیکترین عنصر موجود در زیر آرایه ی [tex]A[1..i][/tex] باشه که احتمالش [tex]\frac{1}{i}[/tex] هست. پس برای پیدا کردن میانگین تعداد اجرای این دستور باید داشته باشیم:
[tex]\sum_{i=1}^{n}\frac{1}{i}=Ln(n)[/tex]
و در نتیجه میشه گفت میانگین [tex]\theta(logn)[/tex] خواهد بود و گزینه ۱ صحیحه.

سلام، تحلیل یو خ مفید بود برام - ممنون، فقط من تحلیل خودمو مینویسم یه نگا بنداز اشکالشو بگیر
منمیگم باید جایگشت های مختلف آرایه رو در نظر بگیریم به طوری که از بهترین حالت برای رفتن به سطر ۴ و آپدیت min تا بدترین حالتش اتفاق بیفته، بهترین حالت زمانیه ک Min تو خونه اول باشه و ۰ آپدیت داریم همینطور میتونیم جایگشتی رو در نظر بگیریم ک min تو خونه دوم باشه که ۱ دونه آپدیت داریم ... تا n-1 آپدیت، حالا از یه طرف دیگه ما کلا !n جایگشت برای آرایه داریم یعنی با احتمال [tex]\frac{1}{n!}[/tex] جایگشت داریم برای انتخاب آرایه، بعدشم فرض کن min تو خونه اول باشه یعنی ۰ آپدیت برای همچین حالتی !(n-1) داریم همینطور اگه تو خونه دوم باشه باز !(n-1) و ... حالا اگه از امید ریاضی استفاده کنیم با تابع چگالی احتمال [tex]\frac{1}{n!}[/tex] داریم:
[tex]\frac{1}{n!}\sum_{i=0}^{n-1}i(n-1)!=\frac{1}{n}\sum_{i=0}^{n-1}i=\frac{n(n-1)}{2n}=\frac{n-1}{2}=\Theta (n)[/tex]

[Farid_Feyzi]

نقل قول: سلام، تحلیل یو خ مفید بود برام - ممنون، فقط من تحلیل خودمو مینویسم یه نگا بنداز اشکالشو بگیر
منمیگم باید جایگشت های مختلف آرایه رو در نظر بگیریم به طوری که از بهترین حالت برای رفتن به سطر ۴ و آپدیت min تا بدترین حالتش اتفاق بیفته، بهترین حالت زمانیه ک Min تو خونه اول باشه و ۰ آپدیت داریم همینطور میتونیم جایگشتی رو در نظر بگیریم ک min تو خونه دوم باشه که ۱ دونه آپدیت داریم ... تا n-1 آپدیت، حالا از یه طرف دیگه ما کلا !n جایگشت برای آرایه داریم یعنی با احتمال [tex]\frac{1}{n!}[/tex] جایگشت داریم برای انتخاب آرایه، بعدشم فرض کن min تو خونه اول باشه یعنی ۰ آپدیت برای همچین حالتی !(n-1) داریم همینطور اگه تو خونه دوم باشه باز !(n-1) و ... حالا اگه از امید ریاضی استفاده کنیم با تابع چگالی احتمال [tex]\frac{1}{n!}[/tex] داریم:
[tex]\frac{1}{n!}\sum_{i=0}^{n-1}i(n-1)!=\frac{1}{n}\sum_{i=0}^{n-1}i=\frac{n(n-1)}{2n}=\frac{n-1}{2}=\Theta (n)[/tex]

سلام
من به تحلیل شما زیاد وارد نمیشم() ولی اشکالاتی که وجود داره رو اشاره میکنم بهشون
۱-اگه min عنصر اول باشه سطر چهارم ۱ بار اجرا میشه نه ۰ بار(چون min در ابتدا بینهایت هستش!)
۲-شما میگی اگه تو یه جایگشت خاص min تو مکان i باشه حتما i یا i-1 (مهم نیس حالا!) بار باید آپدیت شه ولی اینطوری نیس.
مثلا اگه بگیری [tex]2 , 3, 4, 5, ... n-1, 1[/tex] که min خونه آخره در واقع فقط ۲ بار آپدیت انجام میشه.
در واقع اگه بخواییم از این روش تحلیل استفاده کنیم کار خیلی سخت میشه. واسه اینکه به حرف من برسی برای n=4 که ۲۴ تا جایگشت داریم یه بار امتحان کن. تو ۶ جایگشت ۱ تعویض، تو ۱۱ جایگشت ۲ تعویض، تو ۶ جایگشت ۳ تعویض و فقط وقتی آرایه مرتب نزولی باشه ۴ بار تعویض انجام میشه-یعنی به این راحتی نمیشه شمارش انجام داد(بر اساس تحلیل شما)
واسه همین نمیگم تحلیلت نادرسته ولی اگه دقیقترش کنی شاید به زمان لگاریتمی نزدیک بشی!

بازم شاید من تحلیل شما رو خوب متوجه نشده باشم. اگه اینطوریه لطفا روشنم کنید.