۰
subtitle
ارسال: #۱
مسئله ژوزف
سلام کسی الگوریتم این مساله رو میتونه توضیح بده ؟ قبلن هم ازش سوال اومده
ممنون عزیزان
ممنون عزیزان
۲
ارسال: #۲
مسئله ژوزف
ژوزف یا جوزف رو نشنیدم ولی اگه منظور همون ژوزفوس هست اینا :
ص ۵۹ جزوه ی دکتر قدسی:
![[تصویر: 157016_1_1379086261.jpg]](https://img.manesht.ir/157016_1_1379086261.jpg)
ص ۵۹ جزوه ی دکتر قدسی:
۱
ارسال: #۳
مسئله ژوزف
هم ایتی سوال اومده هم نرم یکبارم نه چند بار
پس حتمن بخونیدش نگید چیز خاصی نیست!
اینجوری بخواهید درس بخونید همه تست ها چیز خاص نیست !
پس حتمن بخونیدش نگید چیز خاصی نیست!
اینجوری بخواهید درس بخونید همه تست ها چیز خاص نیست !
۰
۰
۰
ارسال: #۶
مسئله ژوزف
۰
۰
ارسال: #۸
مسئله ژوزف
البته این سوال رو من به عنوان ژوزف هیچ جا ندیدم، اما سوال مشابه اون رو میشه تو بحث لیست های پیوندی پیدا کرد. و تقریبا ۲ ۳ باری هم ازش در کنکور ای تی و مهندسی نرم سوال اومده. پارسه هم یک فرمول معرفی کرده به این صورت :
2\left ( n-2^{\left \lfloor Logn \right \rfloor}) 12\left ( n-2^{\left \lfloor Logn \right \rfloor}) 1
البته بستگی به اشاره گر و موقعیت اون داره. و اون بحث شیفت دادن هم یک روش دیگه ست.
2\left ( n-2^{\left \lfloor Logn \right \rfloor}) 12\left ( n-2^{\left \lfloor Logn \right \rfloor}) 1
البته بستگی به اشاره گر و موقعیت اون داره. و اون بحث شیفت دادن هم یک روش دیگه ست.
۰
ارسال: #۹
مسئله ژوزف
مطلب بسیار مهمی هست که حتما یادش بگیرید.لااقل اون شیفت رو یاد بگیرید و یکم دقت کنید اشاره گر روی اولین گره باشه.
اگه نباشه اول بزرگترین عدد رو یک شیفت می دیم و سپس جواب رو به اندازه ی اختلاف اشاره گر فکر کنم جلو می بریم. می تونید روی یه لیست چرخشی کوچیک تست بگیرید.
اگه نباشه اول بزرگترین عدد رو یک شیفت می دیم و سپس جواب رو به اندازه ی اختلاف اشاره گر فکر کنم جلو می بریم. می تونید روی یه لیست چرخشی کوچیک تست بگیرید.
۰
ارسال: #۱۰
مسئله ژوزف
سلام دوستان از این قبلا سوال اومده اما صرفا اگ بخوایم بگیم همیشه راه حل مسئله جوزف و شیفت دادن باشه یه اشتباهه.
این جور سوال هارو خیلی ها تو بحث لیست پیوندی دیدین که یه لیست داده مثلا از اعداد ۱ تا هزار بعد گفته که با توجه به کد روبرو روی این لیست چه عددی بر میگرده.
من واسه این جور سوال ها با توجه به نحوه جلو بردن اشاره گرها با چن تا عدد کوچیک مثال میزنم. مثلا میگم به ازای ۱۰۱ یعنی عدد ۵ (منظورم اینه عدد اخر به جای اینکه ۱۰۰ باشه عدد ۵ باشه)
دوباره یه مثال با ۸ میزنم (۱۰۰۰) , و چند تا مثال دیگ با یه کم اعداد بزرگتر.بعد نگاه میکنم ببینم اون چن تا عدد کوچیک مثال زدم چطوری شیفت خورده مثلا یه بار می بینی شیفت به راست بوده یه بار میبینی شیفت به چپ بوده یه بار می بینی از سمت راست ۱ وارد میشه و ....
فقط یه نکته دیگ واسه حل کردن این سوالا , تو یه سوالی یادمه که حل کردم فک کنم از گسسته پوران یادم نیس مال چه سالی بود یا اصن کنکوری بود یا نه ولی یادمه واسه اعداد توان کامل ۲ خروجی تفاوت میکرد مثلا واسه ۲و۴و۶و۸و۱۶//// اینا خروجی یه مدل دیگ بود ولی واسه بقیه اعداد یه کم فرق داشت ذهنتونو درگیر یادگیری جوزف و این چیزا نکنید فقط اگ مثالشو دیدین با این روشی بهتون گفتم برید ایشالا که اکی هستش
این جور سوال هارو خیلی ها تو بحث لیست پیوندی دیدین که یه لیست داده مثلا از اعداد ۱ تا هزار بعد گفته که با توجه به کد روبرو روی این لیست چه عددی بر میگرده.
من واسه این جور سوال ها با توجه به نحوه جلو بردن اشاره گرها با چن تا عدد کوچیک مثال میزنم. مثلا میگم به ازای ۱۰۱ یعنی عدد ۵ (منظورم اینه عدد اخر به جای اینکه ۱۰۰ باشه عدد ۵ باشه)
دوباره یه مثال با ۸ میزنم (۱۰۰۰) , و چند تا مثال دیگ با یه کم اعداد بزرگتر.بعد نگاه میکنم ببینم اون چن تا عدد کوچیک مثال زدم چطوری شیفت خورده مثلا یه بار می بینی شیفت به راست بوده یه بار میبینی شیفت به چپ بوده یه بار می بینی از سمت راست ۱ وارد میشه و ....
فقط یه نکته دیگ واسه حل کردن این سوالا , تو یه سوالی یادمه که حل کردم فک کنم از گسسته پوران یادم نیس مال چه سالی بود یا اصن کنکوری بود یا نه ولی یادمه واسه اعداد توان کامل ۲ خروجی تفاوت میکرد مثلا واسه ۲و۴و۶و۸و۱۶//// اینا خروجی یه مدل دیگ بود ولی واسه بقیه اعداد یه کم فرق داشت ذهنتونو درگیر یادگیری جوزف و این چیزا نکنید فقط اگ مثالشو دیدین با این روشی بهتون گفتم برید ایشالا که اکی هستش
۰
۰
ارسال: #۱۲
RE: مسئله ژوزف
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
۰
ارسال: #۱۳
RE: مسئله ژوزف
مساله ژوزف میگه یه عده یهودی تو غاری محاصره شدن می خوان قبل از اینکه دشمنا اونا رو بکشن خودشون همدیگرو بکشن!
برا همین دور یه دایره می شینن نفر اول یه خنجر بر میداره میزنه تو قلب نفر کناریش(در جهت عقربه های ساعت) نفر بعدی خنجر رو از قلب یارو بر میداره میزنه تو قلب بقل دستی اش .... همین جوری می زنن تا آخرش یکی می مونه.
ژوزف می خواسته حساب کنه ببینه کجا بشینه زنده بمونه
تو کتاب ساختمان داده مقسمی یه فرمول برا پیدا کردن عدد باقی مانده هست
برا همین دور یه دایره می شینن نفر اول یه خنجر بر میداره میزنه تو قلب نفر کناریش(در جهت عقربه های ساعت) نفر بعدی خنجر رو از قلب یارو بر میداره میزنه تو قلب بقل دستی اش .... همین جوری می زنن تا آخرش یکی می مونه.
ژوزف می خواسته حساب کنه ببینه کجا بشینه زنده بمونه
تو کتاب ساختمان داده مقسمی یه فرمول برا پیدا کردن عدد باقی مانده هست
