تست دوم ساختمان داده IT88 یه لیست پیوندی حلقوی از ۱ تا ۱۰۰۰ با یه تابع بازگشتی داده که این تابع هربار عنصر بعد از خودشو حذف میکنه. در نهایت عنصر ۹۹۷ باقی میمونه. کتاب پارسه یه فرمول داده و با اون حل کرده
[tex]2\left( n-2^{\left \lfloor \lg n \right \rfloor} \right ) 1[/tex]
اما
کتاب پوران گفته:
عدد ۱۰۰۰ را باینری بنویسید و چرخش به چپ دهید
من دقیق نفهمیدم که این تست چطور حل میشه
(02 بهمن 1390 02:28 ب.ظ)netsupport نوشته شده توسط: [ -> ]تست دوم ساختمان داده IT88 یه لیست پیوندی حلقوی از ۱ تا ۱۰۰۰ با یه تابع بازگشتی داده که این تابع هربار عنصر بعد از خودشو حذف میکنه. در نهایت عنصر ۹۹۷ باقی میمونه. کتاب پارسه یه فرمول داده و با اون حل کرده
[tex]2\left( n-2^{\left \lfloor \lg n \right \rfloor} \right ) 1[/tex]
اما
کتاب پوران گفته:
عدد ۱۰۰۰ را باینری بنویسید و چرخش به چپ دهید
من دقیق نفهمیدم که این تست چطور حل میشه
اگه کسی جواب اینو می دونه به منم بگه!
ببینید این مسئله به مسئله ژوزف معروفه و در کتب ساختمان گسسته وجود داره که در ساختمان داده اونو با لیست پیوندی شرح داده که بصورت حلقویه
ماجرا از این قراره که شما باید در هر بار یک در میان عناصر رو حذف کنید. و عنصری که آخر دفعه می ماند رو بنویسید.
برای انجام این کار دو راه وجود داره:
یکی همان فرمولیه که نوشتید و دومین راه که ساده‌تر هم هست اینه که عددی رو که باید در نظر بگیرید که در اینجا ۱۰۰۰ هست رو بصورت دودویی بنویسید و یک شیفت به چپ از نوع چرخشی بدهید و حاصل رو حساب کنید. که باز هم این راه عددی که در اخر می مونه رو بهتون میده.
مثلا فرض کنید همین ۱۰۰۰ رو اگه بصورت باینری در بیاریم میشه: [tex]1111101000[/tex] خب حالا اونو شیفت چرخشی به چپ بدهید (یک واحد) میشه [tex]1111010001[/tex] خب حالا اگه اینو تبدیل به دهدهی کنید میشه ۹۷۷
از طریق فرمول هم داریم: [tex]2*(n-2^{\left \lfloor logn \right \rfloor}) 1[/tex] که با n=1000 و [tex]\left \lfloor log1000 \right \rfloor=512[/tex] داریم:
[tex]2*(1000-512) 1 =2*488 1=976 1=977[/tex]
یه مثال دیگه هم می زنم:
مثلا فرض کنید اعداد از یک تا 10 رو بصورت پشت سر هم بنویسیم بصورت لیست پیوندی.
10 9 8 7 6 5 4 3 2 1
خب حالا از عدد 1 شروع کنید و اون رو خط بزنید و بصورت یک در میان خط بزنید. در مرحله اول داریم:
10 8 6 4 2
خب در آخر وقتی شما 9 رو خط زدید باید کار مهمی بکنید و اون اینکه عنصر بعدی اون نه، بلکه عنصر بعد اون رو علامت بزنید. از اونجایی که عنصر 10 عنصر بعدیه علامت نمی خوره و 2 علامت می خوره و داریم:
8 4
حالا عنصر بعدی 4 و بعد بعدی 8 هست که 8 علامت می خوره و داریم:
4
حالا با دو فرمول بالا اگه n=10 رو حساب کنید میشه 4
(02 بهمن 1390 02:28 ب.ظ)netsupport نوشته شده توسط: [ -> ]تست دوم ساختمان داده IT88 یه لیست پیوندی حلقوی از ۱ تا ۱۰۰۰ با یه تابع بازگشتی داده که این تابع هربار عنصر بعد از خودشو حذف میکنه. در نهایت عنصر ۹۹۷ باقی میمونه. کتاب پارسه یه فرمول داده و با اون حل کرده
[tex]2\left( n-2^{\left \lfloor \lg n \right \rfloor} \right ) 1[/tex]
اما
کتاب پوران گفته:
عدد ۱۰۰۰ را باینری بنویسید و چرخش به چپ دهید
من دقیق نفهمیدم که این تست چطور حل میشه
این دو تا لینک رو ببین:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اینجا هم در موردش بحث شده:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
نقل قول: یه مثال دیگه هم می زنم:
مثلا فرض کنید اعداد از یک تا ۱۰ رو بصورت پشت سر هم بنویسیم بصورت لیست پیوندی.
۱۰ ۹ ۸ ۷ ۶ ۵ ۴ ۳ ۲ ۱
خب حالا از عدد ۱ شروع کنید و اون رو خط بزنید و بصورت یک در میان خط بزنید. در مرحله اول داریم:
۱۰ ۸ ۶ ۴ ۲
خب در آخر وقتی شما ۹ رو خط زدید باید کار مهمی بکنید و اون اینکه عنصر بعدی اون نه، بلکه عنصر بعد اون رو علامت بزنید. از اونجایی که عنصر ۱۰ عنصر بعدیه علامت نمی خوره و ۲ علامت می خوره و داریم:
۸ ۴
حالا عنصر بعدی ۴ و بعد بعدی ۸ هست که ۸ علامت می خوره و داریم:
۴
حالا با دو فرمول بالا اگه n=10 رو حساب کنید میشه ۴
ولی اگه n=10 رو توی فرمولهای بالا قرار بدید جواب ۵ میشه که درست نیست!!!
اگر از ۲ شروع کنیم درست درمیاد. یعنی باید حذف کردن رو از عدد 2 شروع کنیم. در هر مرحله اعدادی که باقی می مانند:
۱ ۳ ۵ ۷ ۹
۱ ۵ ۹
۵