n zarfe darim ke dar aan haa mavaade shimiaE rikhte shode ast. midanim ke dar bish az nimi az zoruf yek no'e maadde vojud darad. amale moghayese kardane 2 zarf ya'ani bardashtan aan ha va in ke begu'eim maaddeye darune aan haa yeksaan ast ya na. saabet konid mitavaan ba n-1 amale moghayese kardan hadde aghal yeki az zorufi ke maaddeye darune aan, dar bish az nesfe zarf haa vojud daarad ra peida kard
- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
جواب
سلام!
این هم جوابش:
یک تعریف کوچک: f[SUB]n[/SUB] را اولین عدد صحیحی در نظر میگیریم که از n بزرگتر و نه مساوی n باشد.
به استقرای قوی روی مقدار n اثبات می کنیم. پایه های استقرا که بدیهی هستند.
حال فرض کنید حکم برای 1 تا n-1 صحیح باشد.
اگرn زوج باشد داریم:
f[SUB]n/2[/SUB]=f[SUB](n-1)/2[/SUB]+1
ابتدا با n-2 مقایسه بین ظروف 1 تا n-1 ظرفی را می یابیم که ماده درون آن حداقل f[SUB](n-1)/2[/SUB] بار تکرار شده است.
چنین ظرفی وجود دارد زیرا در غیر این صورت نمی توان در بین n ظرفf[SUB]n/2[/SUB] ظرف با ماده یکسان یافت.
همین ظرف جواب مسئله است
اما اگر n فرد باشد:
ابتدا دو ظرف آخر (یا هر دو ظرف دیگری) را مقایسه می کنیم. اگر ماده درون آنها یکسان نبود با استفاده از روشی که برای اعداد زوج به کار بردیم با n-2+1=n+1 مقایسه ، ظرف مورد نظر را پیدا می کنیم.
اما اگر ماده درون آنها یکسان بود:
یکی از آنها (2ظرف آخر) را با
ظرف از n-2 ظرف دیگر مقایسه می کنیم.U[SUB]n[/SUB] همان سقف n است.
اگر در بین آنها حداقل u[SUB](n/2)[/SUB]-2 تا با آن یکی بودند که مسئله حل است. در غیر این صورت تا کنون n-u[SUB](n/2)[/SUB]+2 مقایسه انجام داده ایم و
مقایسه و n-2 ظرف باقی مانده است که می دانیم در بین آنها
عدد مشابه وجود دارد. اینک یک ساختار عملی برای انجام این مقایسه ارائه می دهیم:[center:054c573e40]
دو عدد که با فلش به هم مربوط شده اند با هم مقایسه می شوند[/center:054c573e40][JUSTIFY]فکر میکنم باید راه دیگری هم داشته باشد[/JUSTIFY]
سلام!
این هم جوابش:
یک تعریف کوچک: f[SUB]n[/SUB] را اولین عدد صحیحی در نظر میگیریم که از n بزرگتر و نه مساوی n باشد.
به استقرای قوی روی مقدار n اثبات می کنیم. پایه های استقرا که بدیهی هستند.
حال فرض کنید حکم برای 1 تا n-1 صحیح باشد.
اگرn زوج باشد داریم:
f[SUB]n/2[/SUB]=f[SUB](n-1)/2[/SUB]+1
ابتدا با n-2 مقایسه بین ظروف 1 تا n-1 ظرفی را می یابیم که ماده درون آن حداقل f[SUB](n-1)/2[/SUB] بار تکرار شده است.
چنین ظرفی وجود دارد زیرا در غیر این صورت نمی توان در بین n ظرفf[SUB]n/2[/SUB] ظرف با ماده یکسان یافت.
همین ظرف جواب مسئله است
اما اگر n فرد باشد:
ابتدا دو ظرف آخر (یا هر دو ظرف دیگری) را مقایسه می کنیم. اگر ماده درون آنها یکسان نبود با استفاده از روشی که برای اعداد زوج به کار بردیم با n-2+1=n+1 مقایسه ، ظرف مورد نظر را پیدا می کنیم.
اما اگر ماده درون آنها یکسان بود:
یکی از آنها (2ظرف آخر) را با
اگر در بین آنها حداقل u[SUB](n/2)[/SUB]-2 تا با آن یکی بودند که مسئله حل است. در غیر این صورت تا کنون n-u[SUB](n/2)[/SUB]+2 مقایسه انجام داده ایم و
دو عدد که با فلش به هم مربوط شده اند با هم مقایسه می شوند[/center:054c573e40][JUSTIFY]فکر میکنم باید راه دیگری هم داشته باشد[/JUSTIFY]