معمای صفحه شطرنج نامتناهی - 2 امتیاز
- شروع کننده موضوع narenjak
- تاریخ شروع
- وضعیت
احسان
کاربر فوقفعال
- ارسالها
- 137
- امتیاز
- 19
- نام مرکز سمپاد
- شهید اژهای
- شهر
- اصفهان
- مدال المپیاد
- نقرهی المپیاد کامپیوتر
- دانشگاه
- شریف
- رشته دانشگاه
- مهندسی کامپیوتر
پاسخ : معمای صفحه شطرنج نامتناهی - 2 امتیاز
میشه این:
4 5 6 7 0
3 2 1 0 7
2 3 0 1 6
1 0 3 2 5
0 1 2 3 4
(پائینترین سطر رو سطر شماره ۱ در نظر گرفتم!)
جالبه که روی قطر (یعنی خونههایی که شماره ی سطر و ستونشون مساویه) عدد ۰ قرار میگیره
کلا این چیدمان، پر از ویژگیها ی خفنه انگار
به نقل از narenjak :
میشه این:
4 5 6 7 0
3 2 1 0 7
2 3 0 1 6
1 0 3 2 5
0 1 2 3 4
(پائینترین سطر رو سطر شماره ۱ در نظر گرفتم!)
جالبه که روی قطر (یعنی خونههایی که شماره ی سطر و ستونشون مساویه) عدد ۰ قرار میگیره
کلا این چیدمان، پر از ویژگیها ی خفنه انگار
narenjak
کاربر فوقحرفهای
- ارسالها
- 863
- امتیاز
- 836
- نام مرکز سمپاد
- علامه حلی
پاسخ : معمای صفحه شطرنج نامتناهی - 2 امتیاز
6 کجای سطر دوم هست ؟
یه سوال
الان دقیقا معلومه عدد 1000000000000000000 در سطر دوم کدوم ستونه ؟
تو روش من معلومه
به نقل از احسان :میشه این:
4 5 6 7 0
3 2 1 0 7
2 3 0 1 6
1 0 3 2 5
0 1 2 3 4
(پائینترین سطر رو سطر شماره ۱ در نظر گرفتم!)
جالبه که روی قطر (یعنی خونههایی که شماره ی سطر و ستونشون مساویه) عدد ۰ قرار میگیره
کلا این چیدمان، پر از ویژگیها ی خفنه انگار
6 کجای سطر دوم هست ؟
یه سوال
الان دقیقا معلومه عدد 1000000000000000000 در سطر دوم کدوم ستونه ؟
تو روش من معلومه
احسان
کاربر فوقفعال
- ارسالها
- 137
- امتیاز
- 19
- نام مرکز سمپاد
- شهید اژهای
- شهر
- اصفهان
- مدال المپیاد
- نقرهی المپیاد کامپیوتر
- دانشگاه
- شریف
- رشته دانشگاه
- مهندسی کامپیوتر
پاسخ : معمای صفحه شطرنج نامتناهی - 2 امتیاز
یه ویژگی جالب دیگه برای اون راهی که گفتم:
در یک سطر، اگه عدد x در ستون y باشه، عدد y هم در ستون x خواهد بود!
به خاطر همین خیلی راحت میشه فهمید که در یک سطر خاص، عدد x تو کدوم ستون قرار میگیره! (کافیه ببینید بر اساس الگوریتمی که گفتم، توی همون سطر، در ستون x چه عددی قرار میگیره!)
پی اس : یاد آوری میکنم که توی راه من، هم سطرها و هم ستونها از ۰ شماره گذاری شده اند و خونهها ی جدول هم با عددها ی حسابی پر شده اند (نه طبیعی!)
به نقل از احسان :من یه راه کامپیوتری براش پیدا کردم:
میشه فرض کرد که هم سطرها و هم ستون ها، از ۰ شماره گذاری شده اند و عددها ی این صفحه ی شطرنج هم قراره عددها ی حسابی باشند (به جای عددها ی طبیعی)
برای این که بفهمیم تو خونه ی سطر i و ستون j ،چه عددی باید قرار بگیر، این کار رو انجام بدید:
هر ۲ عدد رو ببرید در مبنای ۲. حالا به ازای هر k ، اگه k امین رقم i ، برابر با ۱ بود، همه ی k رقم سمت راست عدد j را not کنید (یعنی اگه ۰ بود، ۱ کنید و اگه ۱ بود، ۰ کنید)
میشه ثابت کرد که این ترتیب از پر کردن، ویژگیها ی لازم رو داره!
(همون طور که میبینید، در یک راه کامپیوتری، شمارش از ۰ شروع میشه و عددها همه در مبنا ی ۲ هستند!!)
یه ویژگی جالب دیگه برای اون راهی که گفتم:
در یک سطر، اگه عدد x در ستون y باشه، عدد y هم در ستون x خواهد بود!
به خاطر همین خیلی راحت میشه فهمید که در یک سطر خاص، عدد x تو کدوم ستون قرار میگیره! (کافیه ببینید بر اساس الگوریتمی که گفتم، توی همون سطر، در ستون x چه عددی قرار میگیره!)
پی اس : یاد آوری میکنم که توی راه من، هم سطرها و هم ستونها از ۰ شماره گذاری شده اند و خونهها ی جدول هم با عددها ی حسابی پر شده اند (نه طبیعی!)
احسان
کاربر فوقفعال
- ارسالها
- 137
- امتیاز
- 19
- نام مرکز سمپاد
- شهید اژهای
- شهر
- اصفهان
- مدال المپیاد
- نقرهی المپیاد کامپیوتر
- دانشگاه
- شریف
- رشته دانشگاه
- مهندسی کامپیوتر
پاسخ : معمای صفحه شطرنج نامتناهی - 2 امتیاز
اگه یه نگاهی به پست من میانداختید، میفهمیدید که دقیقا جواب شما رو دادم:
توی اون راه، هم میشه فهمید که در سطر i و ستون j چه عددی قرار میگیره
هم میشه فهمید که عدد x در کدوم ستون از سطر i قرار میگیره
و هم میشه فهمید که عدد x در کدوم سطر از ستون j قرار میگیره
اگه فرض کنیم سطرها و ستونها از ۰ شماره گذاری شده اند و جدول هم با عددها ی حسابی پر شده، در سطر ۲، عدد ۱۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰ در ستون ۱۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۲ قرار میگیره (و عدد ۱۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۲ هم در ستون ۱۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰)
به نقل از narenjak :
اگه یه نگاهی به پست من میانداختید، میفهمیدید که دقیقا جواب شما رو دادم:
به نقل از احسان :
توی اون راه، هم میشه فهمید که در سطر i و ستون j چه عددی قرار میگیره
هم میشه فهمید که عدد x در کدوم ستون از سطر i قرار میگیره
و هم میشه فهمید که عدد x در کدوم سطر از ستون j قرار میگیره
به نقل از narenjak :
اگه فرض کنیم سطرها و ستونها از ۰ شماره گذاری شده اند و جدول هم با عددها ی حسابی پر شده، در سطر ۲، عدد ۱۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰ در ستون ۱۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۲ قرار میگیره (و عدد ۱۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۲ هم در ستون ۱۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰۰)
احسان
کاربر فوقفعال
- ارسالها
- 137
- امتیاز
- 19
- نام مرکز سمپاد
- شهید اژهای
- شهر
- اصفهان
- مدال المپیاد
- نقرهی المپیاد کامپیوتر
- دانشگاه
- شریف
- رشته دانشگاه
- مهندسی کامپیوتر
پاسخ : معمای صفحه شطرنج نامتناهی - 2 امتیاز
من یه سوتی دادم تو گفتن جواب که اصلاح میکنم:
برای اثبات درستی راه هم یه راهنمایی میکنم:
برای ۲ تا عدد صحیح نا منفی (یعنی عدد حسابی) xor این جوری تعریف میشه:
هر ۲ عدد رو ببرید به مبنای ۲. حالا به ازای هر k, اگه k امین رقم هر ۲ مساوی بود، k امین رقم جواب میشه ۰ و در غیر این صورت، k امین رقم جواب میشه ۱.
فرض کنید که xor رو با نماد ^ نشون بدم.
در حقیقت تو راهی که گفتم، عددی که در سطر i و ستون j قرار میگیره، عدد i ^ j هست!
حالا کافیه ثابت کنید که
- یک : xor خاصیت جا به جائی داره
- و دو : x ^ y ^ y = x
من یه سوتی دادم تو گفتن جواب که اصلاح میکنم:
به نقل از احسان :
برای اثبات درستی راه هم یه راهنمایی میکنم:
برای ۲ تا عدد صحیح نا منفی (یعنی عدد حسابی) xor این جوری تعریف میشه:
هر ۲ عدد رو ببرید به مبنای ۲. حالا به ازای هر k, اگه k امین رقم هر ۲ مساوی بود، k امین رقم جواب میشه ۰ و در غیر این صورت، k امین رقم جواب میشه ۱.
فرض کنید که xor رو با نماد ^ نشون بدم.
در حقیقت تو راهی که گفتم، عددی که در سطر i و ستون j قرار میگیره، عدد i ^ j هست!
حالا کافیه ثابت کنید که
- یک : xor خاصیت جا به جائی داره
- و دو : x ^ y ^ y = x
- وضعیت