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

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

ارسال:
  

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  استخدام در فنآوری اطلاعات خدمات حوزه علمیه قم oloom-ensani ۱۵ ۳,۲۴۲ ۲۴ اردیبهشت ۱۴۰۰ ۰۴:۳۹ ب.ظ
آخرین ارسال: oloom-ensani
  فناوری اطلاعات پزشکی چیست ؟ mahan najafi ۹ ۱۴,۱۹۹ ۱۹ آذر ۱۳۹۹ ۱۲:۲۱ ب.ظ
آخرین ارسال: bahador567
  مصاحبه دانشگاه اطلاعات و امنیت ملی Happiness.72 ۹۸ ۸۰,۴۰۲ ۰۵ آذر ۱۳۹۹ ۰۵:۰۵ ب.ظ
آخرین ارسال: Ali001100
  دانلود آموزش تصویری کلاس درس نظریه اطلاعات و کدینگ دانشگاه فردوسی jazana ۵ ۳,۴۵۱ ۰۷ خرداد ۱۳۹۹ ۰۹:۱۰ ق.ظ
آخرین ارسال: hosein92
  نظریه اطلاعات و سیستم کدینگ hosein92 ۰ ۷۵۰ ۰۵ خرداد ۱۳۹۹ ۱۱:۲۸ ب.ظ
آخرین ارسال: hosein92
  سوال ۸ دکتری علوم کامپیوتر سال ۹۴ ss311 ۲ ۱,۴۵۲ ۲۶ اردیبهشت ۱۳۹۹ ۱۲:۳۷ ب.ظ
آخرین ارسال: ss311
  معرفی منابع برای درس بازیابی پیشرفته اطلاعات saghi5373 ۷ ۸,۰۷۱ ۲۲ اسفند ۱۳۹۸ ۱۲:۳۵ ق.ظ
آخرین ارسال: atahmasebi
  ثبت نام نمونه دولتی هفتم ۹۹-۱۴۰۰ edumoshaver1 ۰ ۷۲۳ ۱۲ اسفند ۱۳۹۸ ۰۴:۵۸ ب.ظ
آخرین ارسال: edumoshaver1
  اعلام نتایج آزمون نمونه دولتی ۹۹-۱۴۰۰ edumoshaver1 ۰ ۱,۱۵۰ ۱۲ اسفند ۱۳۹۸ ۰۴:۵۶ ب.ظ
آخرین ارسال: edumoshaver1
  بازارکار مشاوره فناوری اطلاعات saeedtech ۰ ۷۸۶ ۱۴ بهمن ۱۳۹۸ ۰۵:۵۵ ب.ظ
آخرین ارسال: saeedtech

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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