سلام کسی الگوریتم این مساله رو میتونه توضیح بده ؟ قبلن هم ازش سوال اومده
ممنون عزیزان
ژوزف یا جوزف رو نشنیدم ولی اگه منظور همون ژوزفوس هست اینا :
ص ۵۹ جزوه ی دکتر قدسی:
![[تصویر: 157016_1_1379086261.jpg]](https://img.manesht.ir/157016_1_1379086261.jpg)
البته همیشه این شیفت جواب نمیده!بستگی به محل اشاره گر و طول صف داره!
من این مبحث رو جایی ندیدم
چه سالی سوال اومده؟
(۱۰ بهمن ۱۳۹۱ ۰۴:۵۸ ب.ظ)Mahoor نوشته شده توسط: من این مبحث رو جایی ندیدمقبلا برای آی تی سئوال بوده .مبحث خاصی نیست فقط یک نوع تابع بازگشتی است
چه سالی سوال اومده؟
زیاد مطلب مهمی نیست نخونید نمیاد
البته این سوال رو من به عنوان ژوزف هیچ جا ندیدم، اما سوال مشابه اون رو میشه تو بحث لیست های پیوندی پیدا کرد. و تقریبا ۲ ۳ باری هم ازش در کنکور ای تی و مهندسی نرم سوال اومده. پارسه هم یک فرمول معرفی کرده به این صورت :
[tex]2\left ( n-2^{\left \lfloor Logn \right \rfloor}) 1[/tex]
البته بستگی به اشاره گر و موقعیت اون داره. و اون بحث شیفت دادن هم یک روش دیگه ست.
مطلب بسیار مهمی هست که حتما یادش بگیرید.لااقل اون شیفت رو یاد بگیرید و یکم دقت کنید اشاره گر روی اولین گره باشه.
اگه نباشه اول بزرگترین عدد رو یک شیفت می دیم و سپس جواب رو به اندازه ی اختلاف اشاره گر فکر کنم جلو می بریم. می تونید روی یه لیست چرخشی کوچیک تست بگیرید.
هم ایتی سوال اومده هم نرم یکبارم نه چند بار
پس حتمن بخونیدش نگید چیز خاصی نیست!
اینجوری بخواهید درس بخونید همه تست ها چیز خاص نیست !
سلام دوستان از این قبلا سوال اومده اما صرفا اگ بخوایم بگیم همیشه راه حل مسئله جوزف و شیفت دادن باشه یه اشتباهه.
این جور سوال هارو خیلی ها تو بحث لیست پیوندی دیدین که یه لیست داده مثلا از اعداد ۱ تا هزار بعد گفته که با توجه به کد روبرو روی این لیست چه عددی بر میگرده.
من واسه این جور سوال ها با توجه به نحوه جلو بردن اشاره گرها با چن تا عدد کوچیک مثال میزنم. مثلا میگم به ازای ۱۰۱ یعنی عدد ۵ (منظورم اینه عدد اخر به جای اینکه ۱۰۰ باشه عدد ۵ باشه)
دوباره یه مثال با ۸ میزنم (۱۰۰۰) , و چند تا مثال دیگ با یه کم اعداد بزرگتر.بعد نگاه میکنم ببینم اون چن تا عدد کوچیک مثال زدم چطوری شیفت خورده مثلا یه بار می بینی شیفت به راست بوده یه بار میبینی شیفت به چپ بوده یه بار می بینی از سمت راست ۱ وارد میشه و ....
فقط یه نکته دیگ واسه حل کردن این سوالا , تو یه سوالی یادمه که حل کردم فک کنم از گسسته پوران یادم نیس مال چه سالی بود یا اصن کنکوری بود یا نه ولی یادمه واسه اعداد توان کامل ۲ خروجی تفاوت میکرد مثلا واسه ۲و۴و۶و۸و۱۶//// اینا خروجی یه مدل دیگ بود ولی واسه بقیه اعداد یه کم فرق داشت ذهنتونو درگیر یادگیری جوزف و این چیزا نکنید فقط اگ مثالشو دیدین با این روشی بهتون گفتم برید ایشالا که اکی هستش
دوستان سوال سال ۸۹ ساختمان رو ببینید راجع ب همینه
The Equations
We can solve both cases — in other words, for an arbitrary number of participants — using a little math.
Write n as n = 2^m + k, where 2^m is the largest power of two less than or equal to n. k people need to be eliminated to reduce the problem to a power of two, which means 2k people must be passed over. The next person in the circle, person 2k + 1, will be the winner. In other words, the winner w is w = 2k + 1.
Let’s apply these equations to a few examples:
n = 8: The equations still apply, although using them is unnecessary: n = 8 + 0, so k = 0 and w = 0 + 1 = 1.
n = 13: n = 8 + 5, so k = 5 and w = 2*5 + 1 = 11.
n = 1000: This is the example in the New York Times: n = 1000 = 512 + 488, so k = 488 and w = 2*488 + 1 = 977.
The Formula
We can combine
the equations n = 2^m + k and w = 2k + 1 to get a single formula for w:We can solve both cases — in other words, for an arbitrary number of participants — using a little math.
Write n as n = 2^m + k, where 2^m is the largest power of two less than or equal to n. k people need to be eliminated to reduce the problem to a power of two, which means 2k people must be passed over. The next person in the circle, person 2k + 1, will be the winner. In other words, the winner w is w = 2k + 1.
Let’s apply these equations to a few examples:
n = 8: The equations still apply, although using them is unnecessary: n = 8 + 0, so k = 0 and w = 0 + 1 = 1.
n = 13: n = 8 + 5, so k = 5 and w = 2*5 + 1 = 11.
n = 1000: This is the example in the New York Times: n = 1000 = 512 + 488, so k = 488 and w = 2*488 + 1 = 977.
The Formula
We can combine
Rearrange n = 2^m + k to isolate k: k = n – ۲^m.
Substitute this expression for k into w = 2k + 1:
w = 2(n – ۲^m) + 1
مساله ژوزف میگه یه عده یهودی تو غاری محاصره شدن می خوان قبل از اینکه دشمنا اونا رو بکشن خودشون همدیگرو بکشن!
برا همین دور یه دایره می شینن نفر اول یه خنجر بر میداره میزنه تو قلب نفر کناریش(در جهت عقربه های ساعت) نفر بعدی خنجر رو از قلب یارو بر میداره میزنه تو قلب بقل دستی اش .... همین جوری می زنن تا آخرش یکی می مونه.
ژوزف می خواسته حساب کنه ببینه کجا بشینه زنده بمونه
تو کتاب ساختمان داده مقسمی یه فرمول برا پیدا کردن عدد باقی مانده هست