- ارسالها
- 244
- امتیاز
- 801
- نام مرکز سمپاد
- شهید بهشتی شهرکرد
- شهر
- شهرکرد
- مدال المپیاد
- طلای ادبی (دورهٔ ۲۷)؛ مرحلهٔ ۱ کامپیوتر (دورههای ۲۳ و ۲۴)
- دانشگاه
- دانشگاه تهران
- رشته دانشگاه
- مهندسی نرمافزار
پاسخ : سوالات ریاضی
اول کار (۰ تا خط
) صفحه ۱ بخش ه، وقتی ۱ خط میکشیم صفحه میشه ۲ بخش، وقتی ۲ خط بکشیم صفحه میشه ۴ بخش، وقتی ۳ خط بکشیم در بهترین حالت (یعنی وقتی هیچ سه خطی همرس نباشند؛ تو این حالت تعداد نواحی ماکسیمم میشه.) صفحه میشه ۷ تا بخش.
فرض کنید n تا خط تو صفحه داریم و صفحه به m تا بخش تقسیم شده. خط n+1 اُم را که بکشیم اگه با هیچ دو خط دیگهای در یک نقطه همرس نباشه، با هر کدوم از n تا خط قبلی تو یه نقطه برخورد میکنه و با هر برخورد یه ناحیهٔ جدید میسازه. (در اصل یه ناحیهٔ قبلی را تبدیل میکنه به دو ناحیهٔ جدید.) همون اول کار هم که با هیچ خطی برخورد نداشته یه ناحیهٔ جدید میسازه. پس در کل خط n+1اُم n+1 ناحیهٔ جدید میسازه.
اگه ماکسیمم تعداد نواحی صفحه وقتی nتا خط داشته باشیم را با (f(n نشون بدیم، با توجه به حرفهایی که زدیم میشه یه رابطهٔ بازگشتی نوشت:
[ltr]
f(0)=1
f(n+1)=f(n)+(n+1)
[/ltr]
میشه یکی یکی رفت جلو و دید (f(6 میشه ۲۲. میشه هم با استقراء ثابت کرد فرمول صریحش میشه:
[ltr]
f(n)= (n^2 + n + 2)/2
[/ltr]
حالا وقتی صفحه را به ۲۲ بخش تقسیم کردیم، یه دایره میکشیم که همهٔ ۱۵ تا نقطهٔ برخورد بیفته داخل دایره. حالا دایره به ۲۲ ناحیه تقسیم شده که مقدار ماکسیمم هستش.
یه سری مسأله داریم به نام مسائل پیکربندی (configuration problems) و مسألهٔ تفکیک صفحه هم یکی از اینهاست.به نقل از HELI :
اول کار (۰ تا خط
) صفحه ۱ بخش ه، وقتی ۱ خط میکشیم صفحه میشه ۲ بخش، وقتی ۲ خط بکشیم صفحه میشه ۴ بخش، وقتی ۳ خط بکشیم در بهترین حالت (یعنی وقتی هیچ سه خطی همرس نباشند؛ تو این حالت تعداد نواحی ماکسیمم میشه.) صفحه میشه ۷ تا بخش.فرض کنید n تا خط تو صفحه داریم و صفحه به m تا بخش تقسیم شده. خط n+1 اُم را که بکشیم اگه با هیچ دو خط دیگهای در یک نقطه همرس نباشه، با هر کدوم از n تا خط قبلی تو یه نقطه برخورد میکنه و با هر برخورد یه ناحیهٔ جدید میسازه. (در اصل یه ناحیهٔ قبلی را تبدیل میکنه به دو ناحیهٔ جدید.) همون اول کار هم که با هیچ خطی برخورد نداشته یه ناحیهٔ جدید میسازه. پس در کل خط n+1اُم n+1 ناحیهٔ جدید میسازه.
اگه ماکسیمم تعداد نواحی صفحه وقتی nتا خط داشته باشیم را با (f(n نشون بدیم، با توجه به حرفهایی که زدیم میشه یه رابطهٔ بازگشتی نوشت:
[ltr]
f(0)=1
f(n+1)=f(n)+(n+1)
[/ltr]
میشه یکی یکی رفت جلو و دید (f(6 میشه ۲۲. میشه هم با استقراء ثابت کرد فرمول صریحش میشه:
[ltr]
f(n)= (n^2 + n + 2)/2
[/ltr]
حالا وقتی صفحه را به ۲۲ بخش تقسیم کردیم، یه دایره میکشیم که همهٔ ۱۵ تا نقطهٔ برخورد بیفته داخل دایره. حالا دایره به ۲۲ ناحیه تقسیم شده که مقدار ماکسیمم هستش.
