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

سوال ساختمان داده ۸۹ کامپیوتر

ارسال:
  

arshad90 پرسیده:

سوال ساختمان داده ۸۹ کامپیوتر

یادتون باشه آخرین سوال ساختمان داده پارسال در مورد یه لیست حلقوی بود. سوال رو کامل می نویسم تا روشن شه:

با توجه به تابع روبرو و لیست حلقوی مذکور به ازای مقادیر n برابر ۷۲۹ و ۲۲۰۰ خروجی به ترتیب برابر چند خواهد بود؟

۱) ۱ و ۴۰[tex]}[/tex]

۲)۱ و ۱
۳) ۷۲۹ و ۲۲۰۰
۴) هیچ کدام

کدش هم اینه:

[tex]int SO(LIST *L){[/tex]
[tex]while (L->next!=L){[/tex]
[tex]L->next= L->next->next[/tex]
[tex]L=L->next;[/tex]
[tex]}[/tex]
[tex]return L->data[/tex]
[tex]}[/tex]

تو کتاب ساختمان داده پارسه بلافاصله یه فرمول داده و ادعا کرده عددی که این قطعه کد تولید می کنه از این فرمول به دست میاد:
[tex]2\times (n-2^{\left \lfloor logn \right \rfloor}) 1[/tex]
در وهله اول اگر من با چنین سوالی برخورد کنم با مثال یه عدد فرد و یه عدد زوج حلش می کنم. اگر با عدد فردی مثل عدد ۳ تست کنم جواب می شه ۳/ اما اگر با عدد زوج امتحان کنم می شه ۱/ اما تو این فرمول این اعداد جواب نمی دن.
سوال اینجاست این فرمول قشنگ از کجا اومده؟ چطور محاسبه شده که رسیده به این؟
شکل لیست رو هم یه لیست حلقوی فرض کنید که L به گره اول اشاره می کنه. در ضمن دستور return خارج از حلقه while قرار داره.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

HighVoltage پاسخ داده:

RE: سوال ساختمان داده ۸۹ کامپیوتر

سلام این فرمول من در آوردی غلطه این مسئله یه راه حل بازگشتی داره که توی کتاب دکتر قدسی به نام مسئله ژزفیوس معرفی شده کتاب رو ندارید از
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
حل رو ببینید.
نقل قول این ارسال در یک پاسخ

ارسال:
  

۵۴m4n3h پاسخ داده:

RE: سوال ساختمان داده ۸۹ کامپیوتر

(۱۷ بهمن ۱۳۸۹ ۰۴:۰۷ ب.ظ)High_Voltage نوشته شده توسط:  سلام این فرمول من در آوردی غلطه این مسئله یه راه حل بازگشتی داره که توی کتاب دکتر قدسی به نام مسئله ژزفیوس معرفی شده کتاب رو ندارید از
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
حل رو ببینید.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
رو ببینید!
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

hamidkhl پاسخ داده:

سوال ساختمان داده ۸۹ کامپیوتر

High_Voltage عزیز درست میگن، به علاوه‌ی این فرمول بازگشتی یک فرمول هم تو کتاب دکتر قدسی هستش که از طریق تبدیل اعداد به باینری و شیفت جواب بدست میاد، مشابه این تست یک بار تو امتحان آی تی ۸۸ (اگه اشتباه نکرده باشم!) و کامپیوتر ۷۶ (خیلی ساده تر) اومده بود، یک بار هم تو سوالات گسسته عین فرمول بازگشتی رو خواسته بودن
در مورد این سوال گزینه های ۱ و ۳ در نگاه اول حذف میشن چون تو دور اول همهی اعداد زوج حذف میشن
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

javadjj پاسخ داده:

سوال ساختمان داده ۸۹ کامپیوتر

البته باید بگم کلید اولیه این سوال ۱ بود
حالا چرا تو اصلاحیه شد گزینه ۴ دو حالت داره
یا طراح محترم اشتباه کرده بود یا سازمان سنجش کلید رو اشتباه زده
که حالت اول امکان پذیر تره سال قبل یادمه خودم هم به گزینه ۴ رسیدم و موقعی که کلید‌ها اومد تعجب کردم که بعدش اصلاح شد-در کنکور it 88 هم ازین مورد سوال اومده بود
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

ahmadnouri پاسخ داده:

RE: سوال ساختمان داده ۸۹ کامپیوتر

بله این مسئله جوزفه برای حلش هم عدد باینری خانه n‌ام رو مینویسیم بعد یه rotate به چپ می کنیم عددی که میاد همون جواب
سوال سال قبل به این شکل حل می شه
۷۲۹= ۱۰۱۱۰۱۱۰۰۱ که بعد از چرخش به چپ می شه ۰۱۱۰۱۱۰۰۱۱ = ۴۳۵ و
۲۲۰۰=۱۰۰۰۱۰۰۱۱۰۰۰ که بعد از چرخش به چپ ۰۰۰۱۰۰۱۱۰۰۰۱ = ۳۰۵
Smile[/align]
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

۵۴m4n3h پاسخ داده:

RE: سوال ساختمان داده ۸۹ کامپیوتر

(۱۷ بهمن ۱۳۸۹ ۱۲:۲۵ ب.ظ)arshad90 نوشته شده توسط:  تو کتاب ساختمان داده پارسه بلافاصله یه فرمول داده و ادعا کرده عددی که این قطعه کد تولید می کنه از این فرمول به دست میاد:
[tex]2\times (n-2^{\left \lfloor logn \right \rfloor}) 1[/tex]
در وهله اول اگر من با چنین سوالی برخورد کنم با مثال یه عدد فرد و یه عدد زوج حلش می کنم. اگر با عدد فردی مثل عدد ۳ تست کنم جواب می شه ۳/ اما اگر با عدد زوج امتحان کنم می شه ۱/ اما تو این فرمول این اعداد جواب نمی دن.
سوال اینجاست این فرمول قشنگ از کجا اومده؟ چطور محاسبه شده که رسیده به این؟

این فرمول دقیقاً با روشی که آقای یوسفی توی کتابشون استفاده کردن یکی هست! یعنی این فرمولی که نوشتید، یه عدد باینری رو یه بیت چرخش به چپ میده!
اگه از یه عدد [tex]2^{\left \lfloor \log n \right \rfloor}[/tex] رو کم کنیم، با ارزشترین یکش توی نمایش باینریش حذف میشه، وقتی عدد رو در ۲ ضرب کنیم یه بیت به چپ شیفت پیدا میکنه و وقتی با یک جمعش کنیم، اون یک باارزشش رو که از سمت چپ حذف کردیم به سمت راست اضافه میشه و این عملیات دقیقاً معادل یک چرخش به چپ هست!
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

arshad90 پاسخ داده:

سوال ساختمان داده ۸۹ کامپیوتر

دوستان عزیزم واقعا ممنونم که اینقدر خالصانه کمک می کنید و هر نکته ای که به ذهنتون میاد در بیانش دریغی ندارین.
انشالله امسال بهترین دانشگاه های ایران میزبان اعضای مانشت خواهند بود. Smile

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

۰
ارسال:
  

Maryam-X پاسخ داده:

RE: سوال ساختمان داده ۸۹ کامپیوتر

آهااااااااااااااااااااااااااااااااااا !
تازه یادم اومد این سوال چیه و کجا خوندمش....
این سوال همون ماجرای چند تا یهودیه که در اثنای جنگ جهانی دوم از ترس آلمانها به یک غار پناه می برند.
و چون منابع غذایی شون تموم می شه و بهشون فشار می یاد تصمیم می گیرند خودکشی کنند.
همگی دور هم حلقه می زنند با یک اسلحه!
رئیس گروه(که احتمالا اسمش همون ژوزفیوس باشه)که دلش نمی خواست بمیره یه حقه ای می زنه!!
می گه:عزیزان بیاین از نفر اول شروع کنیم و یکی در میون اسلحه رو به نفر بعدی بدیم تا خودش رو بکشه این اسلحه چند بار در طول حلقه می چرخه تا به همه برسه....
و دیگران انجام می دند.
می دونید آخرش چی میشه؟؟؟Huh
همه خودکشی می کنند.آخرین نفری که نوبت بهش می رسه خود رئیس گروهه که چون هیچ کس دیگه ای نمونده تا مجبورش کنه خودکشی کنه از غار می یاد بیرون و فرار می کنهWink
این سوال شماره(اندیس)نفر آخر رو می خواد.که به تعداد نفرات (یا تعداد نودهای یک لیست)بستگی داره


حالا راه حل:
همونطور که دوستان هم توی پست‌ها ذکر کردند:
این مسئله یک راه حل بازگشتی داره
ولی جالبه بدونید شخصی ایرانی به نام آروین شمس این روش را ابداع کرده که برای پیدا کردن نود بازمانده کافیست:
تعداد نودها یا نفرات را به صورت کد دودویی بنویسیم.
و بعد یک شیفت چپ سیکولار بدیم.
حالا عددی که به صورت دودویی بدست اومده رو بخونیم.
دینگ دینگ
عدد بدست اومده همون جواب مورد نظر ماست.Smile
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۰
  

shaghayegh پاسخ داده:

RE: سوال ساختمان داده ۸۹ کامپیوتر

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

۰
ارسال: #۱۱
  

ف.ش پاسخ داده:

سوال ساختمان داده ۸۹ کامپیوتر

خوب این که همین سواله بالاست!
نقل قول این ارسال در یک پاسخ

ارسال: #۱۲
  

shaghayegh پاسخ داده:

RE: سوال ساختمان داده ۸۹ کامپیوتر

نقل قول:
(۱۹ بهمن ۱۳۸۹ ۰۲:۳۸ ب.ظ)afagh1389 نوشته شده توسط:  خوب این که همین سواله بالاست!

آخرین عددش مگه ۱۰۰۰ نیست .زوج میشه که .ماله آی تی که این بود
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۳
  

delta پاسخ داده:

سوال ساختمان داده ۸۹ کامپیوتر

این سوال گسسته هم بوده
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۴
  

ف.ش پاسخ داده:

سوال ساختمان داده ۸۹ کامپیوتر

اگه سوال رو تغییر بدن مثلا به جای اینکه بین ۳ گره گره وسط حذف بشه‌، بین ۴ گره ۲ گره وسط حذف بشه چه جوری حل میشه؟!!
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۵
  

Maryam-X پاسخ داده:

RE: سوال ساختمان داده ۸۹ کامپیوتر

نه دیگه...اونوقت دیگه این راه حل جواب نمی ده
اون یکی فرمول رو آروین شمس زحمتش رو کشید این یکی رو شما پیدا کنیدBig Grin(البته بعد از کنکور)

یادمه اون روزی که استاد ساختمان داده داشت اون داستان رو تعریف می کرد و مسئله رو تشریح می کرد دقیقا همین سوال رو ازش پرسیدم.یاد آن دوران و استاد بخیر.......Angel
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۶
  

hadi_m پاسخ داده:

سوال ساختمان داده ۸۹ کامپیوتر

سلااام
این ویژگی فقط برای مقدار k=2 جواب میده در این حالت با افزایش n تابع fn دارای این خاصیت هستش که به ازای وردوی های توان دو تابع صعودی متناوب هستش (با دوره تنباوب ۲^n )یعنی به ازاد مقادیر ورودی ۱ و ۲و۴و۸و۱۶و..... مقدار نفر اول یا ۱ اخرین بازمانده میباشد.

متاسفانه این ویژگی را نمیتوان برای مقدار k=3 و..... بسط داد
حالا یه سئوال؟به نظر شما میشه فرمولی تدوین کرد که برای هر مقدار از k بتوان مستقیما جواب رابه دست اورد؟؟؟؟
فکر کنم چنین فرمولی تا کنون ارائه نشده باشه یعنی حدااقل من بی اطلاع هستم اگر دوستانی دراین زمینه اطلاع دارن ممنون میشوم عنوان کنن.
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۷
  

csharpisatechnology پاسخ داده:

سوال ساختمان داده ۸۹ کامپیوتر

یعنی اگه ما از ۵ تا گره داشته باشیم و از گره ی ۱ شروع کنیم باید گره ی ۳ باقی بمونه ؟
آیا نتیجه گیری من با توجه به عکس زیر درسته ؟
[تصویر:  141843_1_1379088121.gif]
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Question بهترین منبع ساختمان داده برای کنکور ارشد marvelous ۱۰ ۱۲,۴۶۸ ۱۵ آذر ۱۴۰۱ ۰۷:۵۶ ب.ظ
آخرین ارسال: msnmkh
  فیلم آموزش ساختمان داده negin_bt ۰ ۱,۲۴۵ ۲۰ مهر ۱۴۰۱ ۰۷:۵۶ ب.ظ
آخرین ارسال: negin_bt
  معرفی کتاب برای ساختمان داده siamakaf ۲ ۴,۶۳۲ ۱۲ آبان ۱۳۹۹ ۰۹:۲۱ ق.ظ
آخرین ارسال: siamakaf
  ساختمان داده و پایگاه داده پارسه امیدوار ۴ ۴,۴۹۱ ۱۲ خرداد ۱۳۹۹ ۰۸:۰۳ ب.ظ
آخرین ارسال: marvelous
  فصل HEAP از کتاب ساختمان داده طورانی (پارسه) tourani ۳۷ ۳۹,۶۵۵ ۱۲ اسفند ۱۳۹۸ ۰۵:۱۹ ب.ظ
آخرین ارسال: hossein4070
  منبع ساختمان داده RASPINA ۷ ۷,۸۴۹ ۱۶ آذر ۱۳۹۸ ۰۱:۳۰ ق.ظ
آخرین ارسال: Behnam‌
  ساختمان داده پوران، فصل اول، راهنمایی برای حل یک مثال ساده marvelous ۲ ۲,۹۲۹ ۲۲ مرداد ۱۳۹۸ ۰۳:۳۰ ب.ظ
آخرین ارسال: marvelous
Question فرادرس برای ساختمان داده marvelous ۷ ۶,۳۹۵ ۱۰ مرداد ۱۳۹۸ ۰۹:۳۷ ب.ظ
آخرین ارسال: marvelous
  معرفی منبع خوب برای ساختمان داده alireza9819 ۴ ۵,۶۵۹ ۱۰ مرداد ۱۳۹۸ ۰۲:۵۸ ب.ظ
آخرین ارسال: marvelous
  [دانلود] جزوه و ویس جلسه نکته تست ساختمان داده والگوریتم استاد یوسفی زمستان ٩٣ software94 ۲۳ ۲۷,۹۷۷ ۰۲ فروردین ۱۳۹۸ ۱۲:۳۲ ق.ظ
آخرین ارسال: honiehs

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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