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

سوال ۴۶ دولتی فناوری اطلاعات سال ۸۸

ارسال:
  

mamat پرسیده:

سوال ۴۶ دولتی فناوری اطلاعات سال ۸۸

اگه دوست عزیزمون مسعود جان سطح سوال رو مناسب بدونند انتقالش بدن به مباجث داغ وگرنه که همینجا روش بحث میکنیم.

[تصویر:  59298_1_1379097001.jpg]

دوستان نظرات و روشتون رو نیز بگین تا روش بحث بشه.

۲
ارسال:
  

Masoud05 پاسخ داده:

RE: سوال ۴۶ ساختمان داده IT 88

(۲۸ آذر ۱۳۹۰ ۰۱:۲۶ ق.ظ)mamat نوشته شده توسط:  اگه دوست عزیزمون مسعود جان سطح سوال رو مناسب بدونند انتقالش بدن به مباجث داغ وگرنه که همینجا روش بحث میکنیم.

[تصویر:  59339_1_1379096941.jpg]

دوستان نظرات و روشتون رو نیز بگین تا روش بحث بشه.

سطح سوال خوبه اما چون دیگه اینجا گزاشتین همین جا بررسیش میکنیم (اگه خواستین منتقلش کنید )‌:
اول مینیمم رو بزار توی ریشه ---> فقط ۱ حالت میتونه رخ بده
بعدش بیا از ۶ گره باقیمانده( بجز ریشه )۳ تاش رو بزار در زیر درخت راست و ۳ تاش هم زیر درخت چپ( چون هیپ یه درخت کامله )برای گزاشتن این ۳ گره دلخواه از بین ۶ مقدار باید ۳ را از ۶ انتخاب کنی( انتخاب ۳ از ۶ )بعد اینو در ۲ ضربش کن چون ۲ تا زیر هیپ که والدشون همون ریشه است داریم( زیر هیپ راست و چپ )
حاصل بالا رو در ۲ ضرب کن چون زیر هیپ راست و چپ هر کدوم می تونه ۲ حالت باشه( یعنی با ۳ عنصر فقط ۲ هیپ مختلف می تونیم داشته باشه چون مینیمم رو میزاریم تو ریشه و با ۲ عنصر دیگه میتونیم به دلخواه یکی رو سمت راست و دیگری رو سمت چپ بزاریم )
جواب گزینه ۲ است.

[tex]2*\begin{pmatrix} 6\\ 3 \end{pmatrix} * 2 = 80 [/tex]

۰
ارسال:
  

mamat پاسخ داده:

سوال ۴۶ ساختمان داده IT 88

بله به نظر من هم جواب ایشون بعد از تصحیح که تو پست شماره ۵ این تاپیک موجوده صحیح هست.
البته من هم این جواب رو بار اول حل سوال بدست آوردم اما به نظرم غلط رسید.
ولی یکی از دوستان هم با اشاره به اینکه تو کتاب پوران پژوهش هم سوالی شبیه به این با تعداد کلید ۸ تا حل شده با اینکه راه حل آن هم قابل فهم نیست اما همان جواب که راه حل ذکر شده بدست می دهد را بدست می آورد.

پس راه حل بنده که در پست ۷ و نقل قولی که از پست خانم homa در پست ۶ آورده شده غلط می باشد.

در ضمن خانم narges_r هم اشاره صحیح کردن به جواب.

اگر با جواب بنده گمراه شدید معذرت میخوام. اما من فکر نمیکردم جواب به این سادگی بدست بیاید و برای همین مسدله را برای خودم پیچیده میکردم.

تاپیک خم بسته شد چون جواب صحیح در پست ۵ موجود استSmile.
موفق باشید

۰
ارسال:
  

Mohammad-A پاسخ داده:

سوال ۴۶ ساختمان داده IT 88

با تشکر از شما

مشخصاً این روند برای MaxHeap هم تفاوتی نخواهد داشت؛ درسته؟

ارسال:
  

mamat پاسخ داده:

RE: سوال ۴۶ ساختمان داده IT 88

با تشکر از مسعود جواب کاملا درست هست.

یعنی فرمول خاصی برای ساخت درختان متنوع heap با عناصر یا کلیدهای ۱ تا n وجود نداره بجز یافتن جایگشتها.

(۲۸ آذر ۱۳۹۰ ۰۲:۰۸ ب.ظ)mam نوشته شده توسط:  مشخصاً این روند برای MaxHeap هم تفاوتی نخواهد داشت؛ درسته؟

بله تفاوتی نخواهد داشت.

اما یکم سوال رو پیچیده‌تر بکنیم فرض کنیم برای عناصر ۱ تا ۹ بخواهیم یک max-heap یا min-heap بسازیم (یعنی دیگه درخت پر نیست و فقط شرط کامل بودن رو داره). چند درخت متفاوت میتوان ساخت؟ البته با جوابی که بالا گفته شده یافتنش کار مشکلی نیست.Smile

دوستان مشارکت کنید. اصلا نگران غلط بودن جوابتون نباشید.Smile

اینجا هدف اینه که دور هم یه چیزایی یاد بگیریم.Smile
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

mamat پاسخ داده:

سوال ۴۶ ساختمان داده IT 88

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

(۲۸ آذر ۱۳۹۰ ۰۳:۳۱ ب.ظ)homa نوشته شده توسط:  و در کل: [tex]\binom{8}{3}*\binom{8}{5}*\binom{4}{3}*\binom{4}{1}*2*2[/tex]

ببینین میتونین ایرادو پیدا کنین.Smile

۰
ارسال:
  

mamat پاسخ داده:

سوال ۴۶ ساختمان داده IT 88

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

این درخت با شرایط جدید که در پست ۴ این تاپیک شرایطش رو گفتم یک درخته کامل میشه با ۳ گره در زیر درخت ریشه سمت راست و ۵ گره در زیر درخت ریشه سمت چپ.


اول از همه ک.چکترین عنصر که تکلیفش معلومه و در ریشه قرار میگیره و حالتی نداره
الف) بررسی حالات زیر درخت ریشه سمت راست که از ۸ کلید باقی مانده میتوان [tex]\binom{8}{3}[/tex] حالت کلید انتخاب کرد حالا این ۳ کلید انتخاب شده هم به دو حالت میتونه در ۳ گره موجود در سمت راست ریشه جایگشت بشه. در نتیجه [tex]\binom{8}{3}*2[/tex]

ب) بررسی حالات سمت چپ ریشه که تعداد حالات کلید های متفاوتی که میشه بهش داد [tex]\binom{8}{5}[/tex] است و حالا حالات مختلف سمت چپ ریشه که خودش یک درخته با ۳ گره در سمت چپش و ۱ گره در سمت راستش:
ب-۱) تو این درخت جدید باز از اون ۵ تا انتخابی که تو مرحله قبل داشتیم باز کوچکترینش به عنوان ریشه قرار خواهد گرفت و حالت خاصی نخواهد داشت.
ب-۲) در زیر درخت سمت راستش که ۱ گره داره از ۴ کلید باقس مانده میتوان [tex]\binom{4}{1}[/tex] حالت انتخاب کرد و چون فقط یک گره هست پس حالت دیگه ای برای چینش نداره.
ب-۳) در زیر درخت سمت چپش باز ۳ گره موجود است که حالات انتخاب کلید برای این زیر درخت [tex]\binom{4}{3}[/tex] است و چون میشه به دوحالت مختلف کلیدها رو جایگشت داد پس میشه [tex]\binom{4}{3}*2[/tex]

خوب حالا جواب نهایی [tex]\left [ \binom{8}{3}*2 \right ] \left [ \binom{8}{5}*\left( \binom{4}{3}*2 \binom{4}{1} \right )\right ][/tex]

البته میخواستم با شکل توضیح بدم که یکم وقت ندارم دوستان ببخشن.Sad

حالا باز اگه مشکلی چه در راه حل بنده یا اینکه قابل فهم نبودنش هست بگینSmile

۰
ارسال:
  

narges_r پاسخ داده:

سوال ۴۶ ساختمان داده IT 88

نمیدونم من دارم اشتباه میکنم یا شما !
اینجا یه سوال برای من پیش اومده!
تا قسمت الف توضیحاتتونو هیچ مشکلی ندارم دقیقا از بین ۸ کلید باقیمونده باید ۳تا انتخاب بشه و از بین این سه تا یکی از همه کوچیکتره که کنار گذاشته میشه و بین دو کلید باقیمونده دوباره ۲حالت وجود داره اما تو قسمت ب توضیحات بنظرم یه مشکلی هست
وقتی تو قسمت الف از بین ۸ تا کلید ۳ تا انتخاب شد دیگه نباید این ۳تا کلید در انتخابهای بعدی شرکت داده بشن چون انتخابهامون به این شکلی که شما گفتید انتخاب با جایگذاری محسوب درحالیکی ما نمیتونیم از کلیدها بطور تکراری در چند مکان استفاده کنیم من فکر میکنم برای انتخاب کلیدهای سمت چپ باید از بین ۵ کلید ۴ کلید انتخاب کنیم که برابر ۵ میشه یعنی میتونیم اصلا دیگه انتخابی انجام ندیم، درواقع وقتی در قسمت الف از بین ۸ کلید ۳تا انتخاب کردیم هرچی کلید باقی میمونه مربوط به سمت چپه که از ۵ تا دوباره یکیش از همه کوچکتره و ما باید از بین ۴ کلید یکی رو برای سمت راست و ۳تا رو برای سمت چپ انتخاب کنیم!
همینطور برای قسمت ب-۳‌، وقتی از بین ۴ کلید یکی رو برای سمت راست انتخاب کردیم حالا فقط ۳تا کلید داریم که یکی از اونها از همه کوچیکتره پس فقط میمونه ۲ کلید که باید جایگشتشونو حساب کنیم!
یکم سوال اماریه تا ساختمانیSmile

۰
ارسال:
  

mamat پاسخ داده:

سوال ۴۶ ساختمان داده IT 88

ایرادتون اینکه قسمت الف رو درست متوجه نشدین.
ما اول برای هر زیر درخت داریم حالات مختلف تخصیص کلید رو محاسبه میکنیم. بعد از تخصیص جایگشت‌ها رو محاسبه میکنیم.
اول در هر سطح تعداد کلید باقی مونده رو باید حالات مختلف تخصیصشون رو به زیر درختها در نظر گرفت.
دیگه نمیشه برای زیر درخت چپ در قسمت (ب) گفت که دیگه برات ۵ کلید باقی موند سهم تو از زندگی همین بودهBig Grin.
امیدوارم بتونم منظورمو برسونم.
شما باید اول فکرتون لینطوری باشه که از ۸ کلید باقی مونده در سطح ۱ زیر درخت راست چند حالت انتخاب داره و زیر درخت سمت چپ چند حالت انتخاب داره.
نه اینکه ۳ تا رو دادیم به سمت راستی حالا موند ۵ تا همون ۵ تا سهم سمت چپی هست.
ما میگیم مثلا چه اعدادی میتونن در زیر درخت سمت چپ و رایت قرار بگیرند.

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

امیدوارم خوب تونسته باشم برسونم منظورمو.

۰
ارسال: #۱۰
  

narges_r پاسخ داده:

سوال ۴۶ ساختمان داده IT 88

ببینید اگر سوال اولی که گذاشتید رو هم بخوایم به همین روشی که شما گفتید حل بکنیم باید یک بار از ۶ تا یه ۳تا انتخاب بکنیم برای سمت راست و دوباره یه ۳ تا از ۶ تا انتخاب بکنیم برای سمت چپ که اینطوری عدد بدست اومده خیلی بیشتر از ۸۰ میشه
درواقع داریم از ۶ تا یه ۳تا انتخاب میکنیم برای یک سمت و ۳تای باقیمونده هم برای سمت دیگه در نظر میگیریم

بالاخره هرکی از زندگی یه سهمی داره Big Grin



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  دانلود سوالات تخصصی گرایش فناوری اطلاعات آزمون دکتری ۹۱(کد ۲۳۵۸) Lonely Palm ۲ ۵,۸۵۶ ۲۶ دى ۱۴۰۲ ۰۲:۳۳ ب.ظ
آخرین ارسال: bijibuji
  امریه ارگان های دولتی it_man ۰ ۵۱۵ ۰۸ دى ۱۴۰۱ ۰۱:۵۳ ب.ظ
آخرین ارسال: it_man
Big Grin اطلاعات در مورد دانشگاه تهران (پردیس فارابی) mehRUN ۲ ۴,۳۱۴ ۳۱ شهریور ۱۴۰۱ ۰۱:۴۱ ب.ظ
آخرین ارسال: eng.behnam
  اطلاعات راجع به سیستمهای حضور و غیاب Fingerprint ۱ ۱,۵۵۵ ۰۳ بهمن ۱۴۰۰ ۱۱:۱۴ ب.ظ
آخرین ارسال: Fingerprint
  کارشناسی ارشد فناوری اطلاعات ۱۴۰۱ tablighjonoub ۰ ۱,۴۲۶ ۰۱ دى ۱۴۰۰ ۰۸:۴۳ ب.ظ
آخرین ارسال: tablighjonoub
  منابع برای دکترا -مهندسی فناوری اطلاعات sarit ۱ ۳,۳۲۶ ۱۰ مهر ۱۴۰۰ ۰۸:۵۴ ق.ظ
آخرین ارسال: pouya47
  استخدام در فنآوری اطلاعات خدمات حوزه علمیه قم oloom-ensani ۱۵ ۸,۶۷۴ ۲۴ اردیبهشت ۱۴۰۰ ۰۴:۳۹ ب.ظ
آخرین ارسال: oloom-ensani
  فناوری اطلاعات پزشکی چیست ؟ mahan najafi ۹ ۱۷,۶۸۰ ۱۹ آذر ۱۳۹۹ ۱۲:۲۱ ب.ظ
آخرین ارسال: bahador567
  مصاحبه دانشگاه اطلاعات و امنیت ملی Happiness.72 ۹۸ ۱۰۸,۳۴۹ ۰۵ آذر ۱۳۹۹ ۰۵:۰۵ ب.ظ
آخرین ارسال: Ali001100
  دانلود آموزش تصویری کلاس درس نظریه اطلاعات و کدینگ دانشگاه فردوسی jazana ۵ ۶,۵۳۲ ۰۷ خرداد ۱۳۹۹ ۰۹:۱۰ ق.ظ
آخرین ارسال: hosein92

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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