پست الکترونیک
آرشیو
خانه
جمعه، 29 اسفند، 1382
سوالات دوره یازدهم
اول عید تان مبارک !
دوم – من می خوام یک مرجه برای سوالات سالهای قبل المپیاد کامپیوتر درست کنم. به همین خاطر کمی اپدیت وبلاگ طول کشید. از همه دوستان هم کمک می خوام. برای اینکار اگر سوالات سالهای قبل را به صورت تایپ شده با فرمت PDF یا ورد یا TeX دارید برایم بفرستید. ممنون میشم! الان دورا یازدهم را تایپ کردم. این هم لینکش :
یازدهمین دوره المپیاد کامپبوتر مرحله دوم.
به زودی بقیه را هم می فرستم.
یم وبلاگ هم برای المپیاد ریاضی افتتاح شده :
vgs.persianblog.com
پیام هاى دیگران
¤ نوشته شده در ساعت 22:27 توسط سید نعمت الله احمدیان
دوشنبه، 25 اسفند، 1382
مشکلات بیمه شیرین است !
سه نفر داریم که با هم دوستند. البته کمی دوستی انها ابنورمال است! یکی کور و دیگری کر و انیکی لال ! ( زمان – داریوش – ارمان ) . انیکی که کر است می میرد. لاله چگونه به کوره این مطلب را برساند که کره مرده ؟
فرض کنید G یک گراف جهتدار با n راس و لااقل 4n یال باشد. ثابت کنید دوری در این گراف وجود دارد که در ان به طور متناوب جهت یالها عوض می شود. ( این قشنگترین سوال نظریه گراف است که تا کنون دیده ام )
· برای اثبات حکم بالا می توانید از دو قضیه زیر بهره بگیرید.
· گراف G دو بخشی است اگر و فقط اگر دور فرد نداشته باشد
· گراف G با e یال را در نظر بگیرید. از این گراف می توان حداکثر e/2 یال را طوری حذف نمود که گراف دو بخشی شود.
یال های یک گراف Kn با دو رنگ بخ صورت دلخواه رنگ امیزی شده است. ثابت کنید یا این گراف دور هامیلتونی تکرنگ دارد یا یک دور هامیلتونی متشکل از دو مسیر تک رنگ.
· استقرا خیلی جالبه ؟ نظر شما چیه ؟
تمام گراف های همبندی را بیابید که با حذف یک یال همبند بماند ولی با حذف دو یال نا همبند شود.
· مسیر رو دوست دارم هنوز … چون تورو یادم میاره ..
فرض کنید G یک گراف 3 منتظم باشد و فرض کنید بدانیم که یالهای G را می توان با سه رنگ چنان رنگ امیزی کرد که هیچ دو یالی مجاور هم همرنگ نباشند. و هم چنین هر رنگ امیزی با یالهای G با سه رنگ که دارای شرایط فوق باشد با تغییر نام رنگ ها به هم تبدیل شود. ثابت کنید G همیلتونی است
· اه که چقدر رنک ابی بیروح است . باید تمام ابی ها را حذفانید
· لم : هر گرافی با درجه راس 2 اجتماعی از چند دور است
برای حمید : این سوال پارسال ریاضی است. یک تورنمنت جهت دار در نظر بگیر و بر روی ان استقرا بزن !
پیام هاى دیگران
¤ نوشته شده در ساعت 22:8 توسط سید نعمت الله احمدیان
جمعه، 22 اسفند، 1382
چند سوال عامه پسند!
سوالی جالب درباره نظریه گراف
یک گراف نامتناهی ( یعنی با تعداد نامتناهی راس ) داریم که همبند است ولی درجه هر راس ان متناهی است. ثابت کنید برای هر راس P یک مسیر نامتناهی که از P شروع می شود وجود دارد.
یک مسئله الگوریتمی
N عدد داریم. سه عدد را از میان انها به گونه ای انتخاب کنید که قدر مطلق اختلاف میان میانه و میانگین این سه عدد ماکزیمم شود. همین الگوریتم را برای 5 عدد پیاده سازی کنید
یک مسئله دیگه الگوریتمی
یک ماشین داریم که دارای 9 رجیستر ( خانه حافظه ) می باشد که در در میان انها اعداد صفر الی 255 می توانند قرار گیرند. این ماشین دو عمل را می تواند بر روی اعداد انجام دهد.
S(i,j) این عمل مقدار رجیستر j را به اضافه 1 کرده و در رجیستر I قرار می دهد.
P(i) این عمل میزان عدد موجود در رجیستر I را چاپ می کند
سوال این است. عدد N ( بین 0-255) به شما داده شده است. شما الگوریتمی را پیاده سازی کنید که ابتدا 9 رجیستر ماشین را به طریق دلخواه انتخاب کرده و سپس با پیاده سازی یک سری از دستورات S,P کلیه اعداد n,n-1,n-1, … , 2,1 را به ترتیب نزولی چاپ کند. الگوریتم شما باید از کمترین میزان توالی دوره های دستورات S استفاده کند
مثلا حالت n=3
برنامه ابتدا 9 رجیستر را به صورت 020000000 پیاده کرده و بعد دستورات زیر را انجام می دهد
S(3,2) ; P(3) ; P(2) ; S(6,8) ; P(8) ; P(0)
در این برنامه بزرگترین میزان تعداد توالی دستورات S که استفاده شده ۱است. چند دوستور S متوالی داریم که پشت سر هم امده اند ؟ روشن است که چنین چیزی لازم نیست. مثلا اگر ما رجیستر ها به صورت 0123000000 ست می کردیم توالی دستورات به میزان ۰ S نبود. و دیگر سری های تک دستوری s و یا دو دستور پشت سر هم و یا سه دستور پشت سر هم نداشتیم. دقت کتید تعداد دستورات مد نظر نیست. مسلا در توالی دستور ۱ شما باید بعد از هر دستور s یک دستور p استفاده کنید . حال ۳۳ تا دستور s استفاده کنید یا یکی . مسئله ای نیست
سوالات ) الگوریتمی را پیدا کنید که عمل خواسته شده را با کمترین میزان توالی دستورات S انجام دهد
ثابت کنید برای عدد 12 حد اقل به یک توالی دستور S نیاز دارید
ایا می توان تنها یا یک توالی دستور S برنامه را برای عدد 44 نوشت؟
جواب سوال قبلی بله است. اما ایا می توان این کار را برای 45 انجام داد؟
بیشترین عددی که می توان با توالی دو دستور S نوشت چند است
برنامه ای را برای عدد 97 با 2توالی دستور S بنویسید
عدد 255 به چند توالی دستور S نیاز دارد /
دقت کنید که در میزان دستورات P هیچ محدودیتی ندارید
میزان دهی اولیه رجیستر ها بر عهده برنامه است. پس روشن است برنامه اعدادی را انتخاب می کند که بعدا کمک بیشتری به او نماید
درباره پست قبلی سوال نگفته بود کی از وزغ خوشش میاد. باید جواب بدید که در هر خانه کی با چه رنگی با چه حیوانی با چه نوشیدنی و چه مارک سیگاری زندگی می کند. پس انقدر شهار های هیتلری لطفا ندهید
همچنین من فکر می کنم البرت راجع به ۲ درصدش کمی خالی بسته. من این سوال رو تا حالا به هرکی گفتم جوابشو داده! ( دور و برم نابغه زیاد می پلکند )
یک نکته نسبتا مهم : سعی کنید برنامه نویسی++C را در لینوکس یاد بگیرید. چون در جهانی سروری که برنامه ها بر روی انها اجرا می شوند لینوکس است و هر چند کمپایل برنامه ها در لینوکس بسیار شبیه به ویندوز است ولی در بخش هایی مانند دسترسی به ارایه های خارج از محدوده تفاوت دارد.
تابعد – خداحافظ
پیام هاى دیگران
¤ نوشته شده در ساعت 0:28 توسط سید نعمت الله احمدیان
دوشنبه، 18 اسفند، 1382
باز بیدار و دوباره در خواب شدیم
به نام خدا
از این که مدتی update کردن وبلاگ طول کشید معذرت می خواهم. چون درگیر یک سایت بودم و به یک مشکل عجیب بر خورد کردم. در یک صفحه asp یک داده را کاربر Unicode تایپ می کرد و بعد صفحه انرا به sql Server می فرستاد بعد همین داده را دوباره در یک صفحه دیگه می خواندیم به صورت Unicode اما دیکه فارسی نشون نمی داد !!
بگذریم. چند پست پیش از این یک مسئله راجع به چند تا سرباز داده بودم . حل اون مسئله با استقرا خیلی ساده است. برای گام استقرا کافی است به حرکات سرباز اخری و باقی سرباز ها دقت کنید. حالا می خواهیم به این مسئله یک گیر سه پیچ دهیم. در ادامه سوال گفته شده بود که یک برنامه برای مرتب سازی سرباز ها ارائه دهیم. می خواهیم دو الگوریتم برای اینکار بیان کنیم.
خوب اولین الگوریتم به همون شیوه استقرایی عمل می کنه. هر بار یک سرباز اخری را در نظر می گیریم و باقی سرباز ها را مرتب می کنیم. برای همین باقی سرباز ها سرباز اخری را در نظر می گیریم و ادامه. ..
برنامه زیر کارتان را راه می اندازد.
فرض کنید sol[i] ارائه ای است که حاوی لیست جهت صورت های سربازان است . R یعنی به سمت راست و L یعنی به سمت چپ
K:= 0;
Do {
For ( i:= 1 ; I <= n-1 ; i++) {
If ( sol[i]='R') and (sol[i+1]='L'){
Sol[i] := 'L' ; sol[i+1] := 'R' ; i := i+1; f:=1 ; } // *
K := k + f ;
// k mizan amaliat lazem baraye moratab sazi ra mohasebe mikonad }
}While (f <> 0)
حلقه * را به عنوان دورنی ترین حلقه در نظر بگیرید.این برنامه در دور اول حداکثر N-1 مقایسه / دور دوم n-2 مقایسه و … پس در انتها حداکثر به n(n-1)/2 مقایسه نیاز داریم . بنابر این پیچیدگی این الگوریتم ( فارسی را شوت نکنید. کامپلکسیتی یا اردر هیچوقت جای پیچیدگی و مرتبه الگوریتم را نمی گیرد.) برابر است با O(n2) .
دومین روشی که برای حل این مسئله می توانید به کار ببرید این است که دسته بزرگتر را به دو بخش تقسیم کنید و هر یک از این دو بخش را مرتب کنید. برای مرتب سازی این دو بخش می توانید هر یک از انها را هم به دو بخش دیگر تقسیم کنید و … . البته در این روش میزان سوت های جناب فرمانده را نمی توانید محاسبه کنید. پیاده سازی این الگوریتم با شما.
همچنین بر خلاف گفته برخی ها ! زبان برنامه نویسی در باشگاه C++ است. پاسکال چند سالی است که دیگر منسوخ شده. بنابر این اگر از همین حالا می خواهید بخوانید باید C++ بخوانید. در المپیاد جهانی هم IOI برای ازمون می توانید از یکی از دو زبان C++ یا pascal استفاده کنیدجالب اینجاست که انتخاب سیستم عاملی را که می خواهید در ان برنامه بنویسید بر عهده شماست. Redhat Linux با gcc یا Windows XP. سیستم پاسخ دهی در المپیاد جهانی هم همه کامپیوتری است. باید بعد از نوشتن هر سوال جواب را به سرور پاسخ گویی از روی شبکه ارسال کنید. سرور ابتدا برنامه را دوباره کمپایل کرده و بعد چند جواب ازمایشی را امتحان می کند و اگر برنامه صحیح بود برای نمره دهی می فرستد. برای نمره دهی مقداری ورودی را از پیش اماده کرده اند که برنامه به هر چند تا جواب داد به همین میزان نمره می گیرد. مهمترین عامل در برنامه نویسی شما میزان زمانی است که برنامه تان صرف می کند. برای مثال در یکی از سوالات جهانی امسال سوالی بود که 5 الگوریتم مختلف برای حل ان وجود داشت که میزان نمره ای که برای ان ها داده می شد بین 30% تا 90% بود. ( درست است . 100 درصد تنها برای حالتی می دادند که در الگوریتم را به صورت ویژه ای پیاده سازی می شد. در غیر این صورت 90 درصد می گرفت. ) از این جالب تر یکی از دانش اموزان شرکت کننده بود که یکی از برنامه هایی را که نوشته بود از برنامه جواب سوال هم سریع تر پاسخ ها را محاسبه می کرد. برای همین از ان سوال هیچ کس غیر از او نتوانست نمره کامل کسب کند.
حال یک سوال واقعا جالب. می گویند پیشینه طرح این سوال به اقای البرت می رسد. الله اعلم.
اگر انرا در 15 دقیقه حل کردید دمتان گرم . برای خود من 20 دقیقه طول کشید. ولی اگر بیش از 1 ساعت سرش ماندید کمی برای حال خودتان از طرف من غصه بخورید
5 خانه داریم با 5 رنگ متفاوت . با 5 نفر با 5 ملیت متفاوت که هر کدام در یکی از این خانه ها زندگی می کنند و هر کدام 5 حیوان مختلف دارند و 5 نوع سیگار مختلف می کشند و 5 نوشیدنی مختلف می نوشند. کی در کجاست؟ از طریق اطلاعات زیر ان فرد را پیدا کنید
1- انگلیسی در خانه قرمز است.
2-المانی سیگار Prime می کشد
3-خانه سبز سمت چپ خانه سفید است
4-خانه سبز قهوه می خورد
5-خانه وسطی شیر می خورد
6-نروژی در خانه اول است
7-خانه ابی کنار خانه نروژی است
8-سوئدی سگ پرورش می دهد
9-کسی که Bahman می کشد پرنده پرورش می دهد
10- کسی که Blue Master می کشد اب جو می خورد
11-کسی که Blend می کشد کناریش گربه دارد
12-کسی که Blend می کشد همسایه اش اب می نوشد
13- کسی که DMNHS می کشد کنارش اسب دارد
14- کسی که DMNHS می کشد ( الف – در خانه زرد است)(ب- کناریش در خانه زرد است)
15-دانمارکی چای می نوشد
16- یکی هست که خیلی به وزغ علاقه دارد. ( نتیجه اخلاقی : من از عباسی خیلی خوشم میاد)
مسئله را یک بار برای حالت 1۴الف و یک بار برای 1۴ب حل کنید/
موفق باشد. تا بعد
مخصوص بر و بچ شمالی : کلاس های امسال در امل بر گذار می شود. شروع کلاس ها هم از ۲۳ اسفند است. یکشنبه می بینمتان. اگه ادرس مدرسه ما را می خواهید مستقیما به ده شلم کلا سیتی – مرکز شهید بهشتی امل بیایید.
برای طرفداران مایکروسافت : ابزار های ساخت برنامه های سازکار با Windows XP SP2 .net امد
پیام هاى دیگران
¤ نوشته شده در ساعت 16:54 توسط سید نعمت الله احمدیان
جمعه، 15 اسفند، 1382
Silent Hill 3 قشنگه ولی کمی گم و گوره
چند سوال با جواب ( این تعطیلات 5 روزه هم داره تمام میشه. )
این سوالات را یکی از بچه های مشهد سوال کرده بود :
1) 24 سکه گرد هم اندازه را در نظر بگیرید . می خواهیم انها را جوری کنار هم قرار دهیم که هر کدام با بقیه دقیقا 3 نقطه تماس داشته باشد.
2) یک شبکه m*n که شامل mn نقطه است در نظر بگیرید. به مسیری که از گوشه بالا سمت چپ شروع شده و به پایین سمت راست ختم شود و از تمام نقاط بگذرد را مسیر فراگیر گوییم/ ثابت کنید شرط وجود مسیر فراگیر برای یک صفحه این است که دست کم یکی از m یا n فرد باشد.
3) یک صفحه 6در6 داریم. با استفاده از دومینو ها انرا فرشیدیم. ثابت کنید خطی وجود دارد موازی یکی از محور های افقی و عمودی که هیچ یک از دومینو ها را قطع نمی کند.
جوابیه :
1) این سوال غیر ممکن است. اثباتی برای شبیه همین سوال در همین وبلاگ در قسمت ارشیو وجود دارد. کافی است از گراف استفاده کنید
2) اگر یکی از m یا n فرد باشد که براحتی می توان مسیری به شکل زیر ساخت:
o o—o . . . o—o
| | | | |
o o o . . . o o
| | | | |
0—0 o–… –o o
ولی اگر هیچ یک فرد نباشد پس رنگ خانه شروع را اگر سفید فرض کنیم رنگ خانه پایانی هم حتما سفید است و جون هر حرکت رنگ را تغییر می دهد پس زوج تا حرکت نیاز داریم. در حالی که تعداد حرکت ها mn-1 تاست که عددی فرد است. پس غیر ممکن است
3) این یکی سوال توی استراتژی و کتاب بابلیان و مرجع ریاضی و چند جای دیگه هم گفته شده که دیگه خیلی لوسش کردن. هر دومینو فقط در مسیر یک خط قرار می گیره. حال فرض کنید (فرض خلف)که خطی مانند t یک دومینو را قطید. دو طرف این دو مینو را در نطظر بگیرید که این دو ناحیه از طریق اون خط t بوجود امدند. چون یک سر دومینو انطرف خطه پس در این بخش تعداد خانه ها فرد است. این بخش رو نمیشه به هیچ شکلی با دومینو ها بپوشونید. پس هر یک از 10 تا خط -برشی- مثل t باید حداقل دو تا دومینو را قطع کرده باشند.پس 20 دومینو را حداکثر قطع کرده
اند. پس در کل 40 خانه باید داشته باشیم. اما کل خانه ها 36 تاست. پس خطی وجود دارد که هیچ دو مینویی را قطع نکرده است
یادداشت : صورت کلی تر این قضیه در درون کتاب استراتژی نوشته شده است.
پیام هاى دیگران
¤ نوشته شده در ساعت 20:29 توسط سید نعمت الله احمدیان
پنجشنبه، 14 اسفند، 1382
نمونه سوالاتی از اصل لانه کفتری
نمونه سوال
فرض کنید n=> 3 عددی فرد باشد. نشان دهید عددی در مجموعه
{21 – 1,22-1 ,23-1,…2n-1-1} وجود دارد که بر n بخش پذیر است
فرض کنید A مجموعه ای از 13 عدد حقیقی باشد. نشان دهید دو عدد x و y وجود دارد به طوری که
0< (x-y) / 1 + xy <= 2-√3 این عبارت شما را به یاد تانژانت نمی اندازد ؟
در یک کنفرانس علمی 1987 دانشمند از 6 کشور شرکت کردند.انها را با شماره های 1 تا 1987 شماره گذاغری می کنیم. ثابت کنید فردی وجود دارد که عدد ان از مجموع عدد دو نفر از هموطنانش یا دو برابر عدد یکی از هموطنانش است
پیام هاى دیگران
¤ نوشته شده در ساعت 21:53 توسط سید نعمت الله احمدیان
سه شنبه، 12 اسفند، 1382
اصل ناوردایی – ۲- جوابیه
پاسخ نمونه سوالات قبلی :
1) مقدار ثابتی که ما دنبالش هیستیم عبارتست از مجموع 4 راسی که با هم یال مشترکی ندارند منهای مجموع چهار راس باقیمانده دیگر ( مقادیر بر روی راس ها را یک در میان جمع و تفریق کنید) این مقدار در هر مرحله الگوریتم ثابت می ماند – چون وقتی عمل الگوریتم را انجام می دهیم به مجموع یکی اضافه و از یکی کم می شود و میزان تغییرات صفر است. به راحتی می توانید ثابت کنید که نه الف و نه ب را نمی توان انجام داد
2) این یک کمی جالب است. در این مسئله نمی خواهم بیان کنم که چه چیزی ثابت می ماند بلکه می خواهم روند تغییراتی را پیدا کنم که همواره در طول مسئله یکسان باقی می ماند
ابتدا بدیهی است که چون تعداد کل مهره ها و تعداد مهره های موجود در هر خانه محدود است و چون در حرکت اول یک مهره از مجموع کم می شود و در حرکت دوم تعداد مهره ها ثابت می ماند پس تعداد جرکت ها در نوع اول باید محدود باشد پس از جایی به بعد تمام حرکت ها از نوع دوم است. خانه ها را از چپ به راست شماره گذاری کنید و تعداد مهره های موجود در خانه iام را ai بنامید. به عبارت زیر توجه کنید
S = ∑ i=1 ∞ i ai . البته این مقدار در طول کار ما ثابت نیست ولی چیزی که این وسط ثابت است مقدار کاهش این مقدار است. جالب شد. این عددی که تعریف کردیم در طول هر مرتبه الگوریتم با انجام هر بار حرکت از نوع دوم فقط یکی کم می شود.بقیه راه حل برای شما. دیگر مسئله نکته مبهمی ندارد
برای قسمت ب دنباله فیبوناچی را در نظر بگیرید. یکی از خاصیت های مهم این دنباله عبارتست از
* ∑ i=0 n f i = f 1 + f 2 + … + fn = fn+2 – 1
رابطه بالا با استقرا ثابت می شود . ( توجه کنید که حتما باید رابطه را با استقرا قابت کرده و در ورقه خود بنویسید وگرنه نمره کامل نمی گیرید) در این مرحله هم می خواهیم یک مقدار ثابت را بیابیم.
این دفعه این مقدار را در نظر بگیرید
S = ∑ i=1 ∞ ai fi
این مقدار در طول الگوریتم همواره ثابت می ماندبه راحتی با توجه به × می توانید بگویید که هیچ مهره ای از خانه n+1 نمی تواند جلوتر رود.
پیام هاى دیگران
¤ نوشته شده در ساعت 19:46 توسط سید نعمت الله احمدیان
دوشنبه، 11 اسفند، 1382
اصل ناوردایی
اصل ناوردایی ( اصل تثبیت – اصل ثابت – Invariance Principle)
احتمالا خیلی از شما با این اصل اشنایید – این اصل اولین فصل از کتاب استراتژی حل مسئله را به خود اختصاص داده است. هدف کلی در استفاده از ان برای حل مسائل الگوریتمیک یا به طور کلی مسائلی هست که در ان عملی تماما تکرار می شود. ما می خواهیم چیزی یا ؛موجودی؛ را که در طی این تکرار ها همچنان ثابت می ماند را پیدا کنیم.
برای اینکار به چند چیز حتما توجه کنید :
1- ایا می توانیم هرگز به مرحله پایانی الگوریتم دست پیدا کنیم و ایا اصلا الگوریتم ما پایان پذیر هست ؟
2- تمامی موقعیت های پایانی به چه شکلند؟
3- ایا در طی انجام عملیات (step) های الگوریتم هیچ همگرایی یا میل کردن به موقعیت پایانی وجود دارد
4- دوراهای تناوب الگوریتم چگونه است ؟
موارد بالا کلید دستیابی به ان موجودیتی در مساله هست که همواره ثابت می ماند. دقت کنید که این اصل هیچ چیزی را ثابت نمی کند. بلکه می توانیم از ان استفاده های بسیاری کنیم
برای مثال یک مسئله نسبتا معروف : یک دایره را در نظر بگیرید. انرا به 6 بخش تقسیم کرده و به ترتیب اعداد 1 0 1 0 0 0 را در خانه های ان می نویسیم( ساعت وار ). شما در هر نویت می توانید دو خانه همسایه را انتخاب کرده و به هر دو یک واحد اضافه کنید. ایا موقعیتی پیش می اید که همه اعداد برابر باشند ؟
جواب – خیر . مقداری مانند S را بدین صورت تعریف کنید که اگر خانه ها را 1 تا 6 و مقادیر درونشان را a1 … a6 در نظر بگیریم داشته باشیم : s = a1 – a2 + a3 – a4 + a5 – a6 . خوب این مقدار در ابتدا 2 است و در هر مرحله ثابت می ماند. درست همین مهم است . یک چیز را پیدا کردیم که در تمام مراحل تغییری نمی کند. خوب در انتهای الگوریتم چه داریم. در نقطه انتهایی چون همه اعداد برابرند پس مقدار S برابر 0 می شود که غیر ممکن است. پس نمی توانیم
سوال 2 – یک جدول 8در8 داریم که در هر خانه ان یک عدد صحیح نوشته شده است. شما در هر حرکت یک مربع 3در3 یا 4در4 انتخاب کرده و به تمام اعداد درون ان 1 واحد اضافه می کنید. ایا در انتها می توانید جدولی داشته باشید که تمام اعضایش بر الف ) 2 ب)3 بخش پذیر باشد ؟
جواب ) مقدار ثابت این مسئله باقیمانده مجموع تمامی اعداد جدول غیر از ستون سوم و ششم بر 2 است( برای حالت الف). اگر این مقدار در ابتدا مخالف صفر باشد در انتها همیشه یک عدد فرد باقی می ماند
برای حالت ب هم مقدار ثابت را باقیمانده مجموع تمام ستون ها غیر از چهارم و هشتم بر 3 در نظر بگیرید
دقت کنید پیدا کردن اینکه چه چیزی ثابت است هیچوقت اسان نیست و باید خیلی تلاش کنید.
تمرین
1-یک مکعب داریم که بر روی هفت راس ان 0 و یکی 1 گذاشته ایم. در هر مرحله می توانید یک یال را انتخاب کرده و به دو راس انتهایی ان هرکدام 1 واحد اضافه کنید. هدف شما این است که
الف) 8 عدد یکسان بدست اورید ب) 8 عدد بخش پذیر بر 3 داشته باشید ایا موفق می شوید
2- جدولی با یک سطر و نا متناهی خانه در نظر بگیرید که از سمت چپ نامتاهی باشد. در بعضی از خانه های این جدول تعدادی مهره قرار داده ایم ( در یک خانه می تواند بیش از یم مهره باشد. ) دو عمل زیر را می توان بر روی مهره ها انجام داد
1) اگر در دو خانه مجاور در هر یک تعدادی مهره وجود داشته باشد می توان یکی از مهره های سمت چپ را 2 خانه به سمت راست برد و یک مهره از خانه سمت راست را خذف کرد
2) در حالتی که در یکی از خانه های سوم به بعد بیش از یک مهره وجود داشته باشد می توان یکی از مهره ها را یک خانه به سمت راست و یک مهره دیگر را 2 خانه به چپ برد
الف) ثابت کنید با اغاز از هر حالتی پس اط تعدادی عمل به وضعیتی می رسیم که دیگر هیچ عملی قابل انجام نیست
ب) فرض کنید در هر یک از خانه های اول تا nام یک مهره قرار دارد. ثابت کنید با انجام اعمال ذکر شده هیچ کاه مهره ای از خانه n+1 ام جلوتر نخواهد رفت
مرحله دوم نوزدهمین المپیاد ریاضی ایران سوال 6 – این سوال را امید نقیشه ارجمند طرح کرده بود
راهنماییی : دنباله فیبوناچی خیلی قشنکه ؟ نظر شما چیه ؟ ( مطمئنا مازیار مهدوی خیلی خوشش میاد)
در ضمن شهاب دمت گرم!
برای هری پاتری ها : تریلر های فیلم سوم را می توانید از اینجا بگیرید
پیام هاى دیگران
¤ نوشته شده در ساعت 21:40 توسط سید نعمت الله احمدیان
یکشنبه، 10 اسفند، 1382
چند سوال
… وقتی ابوسفیان به اسلام مسلح گردد
محمد هم خلع سلاح می شودعمروعاص
بت لات را که می گذارد و قران را بر می دارد
علی فاتح خندق را در صفین شکست می دهد …
پرچم قرمز کربلا هنوز بر فراز خیمه در احتزاز است
عاشورا نزدیک است.
باز هم نمونه سوال
1)بر روی تخته بنفش چند عدد از مجموعه {0,1,2} نوشته شده است. در هر مرحله دو تا از اعداد نابرابررا پاک کرده و به جای ان عدد سوم را می نویسیم ( یعنی 0 به جای 1و2 – 1 به جای 0و2 – و 2 به جای 0و1) ثابت کنید اگر بعد از چند مرحله تنها یک عدد باقی بماند این عدد بستگی ندارد که مراحل را به چه ردیفی انجام داریم و تنها به اعداد اولیه وابسته است.
2) اسان- می دانیم 7 وزنه داریم که با انها می توان 127 جسم را که وزن انها را عدد های طبیعی تشکیل می دهد وزن کرد.همه این وزنه ها را پیدا کنید
3) جالب – 6 دانشمند بر روی یک پروژه محرمانه کار می کنند و می خواهند اسناد پروژه را در یک صندوق بگذارند. می خواهند قفل صندوق را به صورتی ست کنند که صندوق فقط وقتی باز شود که حداقل سه تا از انها حاضر باشند. حداقل چند قفل لازم داریم و هر یک از دانشمندان باید چند قفل داشته باشد؟
4) باحال – دو طناب داریم . می دانیم اگر سر هر کدام را انش بزنیم بعد از یک ساعت طناب می سوزد. ولی سرعت سوختن دو طناب در جاهای مختلف متفاوت است و دو طناب با هم فرق دارند.چگونه می توان با دو طناب 45 دقیقه را اندازه می گرفت.
5) خوب – یک 1383 ضلعی داریم. ایا می توان خطی رسم نمود که همه اضلاع ان را قطع کند ؟
6) بهنام بعد از کلی تلاش در المپیاد اخر به صورت شدیدی ضابع شد و قبول نشد. بعد در کنکور شرکت کرد و دوباره ترید. سال بعد هم ریدمان ( جای راندمان) کنکورش بالا رفت. خلاصه الان در سربازی است. در سربازی یکبار خواستند سربسرشان بگذارند و برای همین انها را به صف کردند. و سپس گفتند به سورت رندم ( تصادفی ) به سمت چپ یا راست به ایستند. به از ایستایش فرمانده سوت می زند و با هر بار سوت زدن دو سرباز که روبروی هم هستند به هم پشت می کنند. و اینکار را انقدر تکرار می کنند تا سر انجام هیچ دو سربازی روبروی هم نایستاده باشند. ایا چنین چیزی ممکن است ( یعنی برای هر وضعیت اولیه سرانجام به وضعیتی می رسیم که هیچ دوسربازی رویروی هم نیستند؟؟ ) حال یک دنباله از سربازها به صورت RLRLRLRRRL در نظر بگیرید. الگوریتم با برنامه ای بنویسید گه دنباله ورودی سرباز ها را خوانده و تعداد سوت های فرمانده را بشمارد.
درباره پست قبلی – جواب سوال 2 از شهاب صحیح بود( این سوال بخش گراف از استرانژی حل مسئله بود)- جواب سوال 6 هم چون 2003 فرد است نمی شود ( برای ماتریس نقره ای عدد n باید حتما زوج باشد) سوال 1 مربوط به المپیاد USACO بود البته در انجا محدودیت زمانی وجود داشت و الگوریتم می بایست در زمان O(n*log N) اجرا می شد. – قبولی ها در امسال 775 نفر بود که تنها 75% مقدار از پیش معلوم شده 1000 نفر بود ؟ علتش را خود من هم نمی دانم. به نظر شما بهتر است بیشتر سوال مطرح شود یا مطالب اموزشی ؟
پیام هاى دیگران
¤ نوشته شده در ساعت 18:10 توسط سید نعمت الله احمدیان
یکشنبه، 10 اسفند، 1382
اعلام نتایج
تازه ها :
نتایج مرحله اول هفدهمین المپیاد فیزیک کشور اعلام شد(جدید)
نتایج مرحله اول چهاردهمین المپیاد کامپیوتر کشور کشور کشور اعلام شد(جدید)
نتایج مرحله اول بیست و دومین المپیاد ریاضی کشور اعلام شد(جدید)
نتایج مرحله اول المپیاد مقدماتی ریاضی کشور اعلام شد(جدید)
نتایج مرحله اول هفتمین المپیاد زیست شناسی کشور اعلام شد(جدید)
نتایج مرحله اول هفدهمین المپیاد ادبی کشور اعلام شد(جدید)
نتایج مرحله اول چهاردهمین المپیاد شیمی کشور اعلام شد(جدید)
نتایج کامپیوتر و فیزیک هم سرانجام اعلام شد. خودم کامپیوتر قبول شدم. برای کسانی که مرحله اول قبول شدند ارزوی موفقیت دارم.
پیام هاى دیگران
¤ نوشته شده در ساعت 14:36 توسط سید نعمت الله احمدیان
جمعه، 8 اسفند، 1382
رنگینگ
سوال و جواب :
N دایره در صفحه رسم شده اند. این دوایر صفحه را به ناحیه هایی تقسیم کرده اند.ثابت کنید می توان این نواحی را با دو رنگ چنان رنگ آمیزی کرد که هر دو ناحیه هم مرز نا همرنگ باشند.
یک استقرا کار ما را می سازد. برای پایه که بدیهی است. برای خود استقرا ثابت می کنیم n+1 دایره را می شود با شرایط مسئله رنگانید! فرض کنید n+1 دایره در صفحه رسم شده اند. یکی را انتخاب می کنیم. اینو فعلا ندید بگیرید و بقیه n دایره را رنگ کنید. مطابق فرض استقرا میشه اینکارو کرد. حالا برای ان دایره که انتخاب کردیم اگر رنگ نواحی را که در درون این دایره قرار دارند معکوس کنیم ( به رنگ دیگر تبدیل کنیم) رنگ امیزی مناسب را بدست خواهیم اورد. ثابت می کنیم معکوس کردن رنگ ها تناقضی ایجاد نمی کند. برای دو رنگ مجاور اگر بیرون از دایره انتخابی باشند که حل است . قبل از معکوس سازی که با هم تفاوت داشتند. بعد از کارمان هم که ککشان نگزید و باز با هم تفاوت دارند ( شاید اینها به نظرتان بدیهی برسد ولی باید در جوابتان همه را ذکر کنید – مثلا باید تمام فرض و گام و … را برای استقرا بنویسید – هر چند خودم اینکارو نکردم) حال اگر این دو ناحیه در درون هم قرار داشته باشند باز هم مثل حالت بالا موقع رنگ امیزی که جدا از هم بودند. بعد از معکوس سازی هم هر دو قرینه می شوند. پس مشکلی ندارد. حالت سوم برای موقعی است که یکی در درون دایره ما و دیگری در بیرون باشد. در این حالت قبل از معکوس سازی که همرنگ بودند و ایجاد مشکل می کردند ولی بعد از کار ما رنگ بیرونیه ثابت مونده ولی رنگ درونی تغییر کرده . پس با هم ناهمرنگند. حکم مسئله بنا بر استق !!! ثابت شد.
تعمیم مسئله بالا :
ثابت کنید هر نقشه را که درجه رئوس انها زوج باشد را می توان با دو رنگ رنگ امیزی کرد نمود به طوری که هر دو ناحیه با مرز مشترک نا همرنگ باشند. ( حتما توجه دارید که مسئله بالا حالت خاصی از همین مسئله است)( نقشه را یک گراف مسطح همبند در نظر بگیرید)
باز از استقرا روی یالهای گراف استفاده می کنیم.برای پایه دو یال را در نظر بگیرید. گرافی با یک طوقه ( یا هرچی . گراف با یک راس با درجه دو) که بدیهیه . برای استقرا اینگونه عمل می کنیم. یک راس را برای شروع در نظر می گیریم/ از اون به ترتیب بر روی یالها حرکت می کنیم( هر یال رو فقط یک بار میگذریم) اینقدر میریم تا یا سرمون گیج بره یا از یه راس مثل بهنام دوبار بگذریم.چون یالها محدودند پس میشه اینکارو کرد-پس به یه دور در گراف برخورد کردیم.که بهنام هم جزوی از اونه. یالهای این دور را از تو گراف اصلی می کنیم تا یک گراف کوچکتر بدست بیاریم ( عین مسئله قبلی که یک دایره را نادیده می گرفتیم. توجه دارید که دایره همان دور است) بدیهیه که درجه گراف جدیدتر ما هم زوجه. پس این کوچیکه رو بنابر فرض استقرا میشه با دورنگ رنگ کرد . بعد از اینکار گرافی دو که کندانه بودیم به اون اضافه می کنیم. بقیش مثل مسئله قبلیه. حکم ثابت شد
همچنین به سادگی می توانید ببینید اگر درجه فرد داشته باشیم رنگ امیزی غیر ممکن است. چون یک راس با درجه فرد . فرد تا ناحیه ایجاد می کند که اگر یکی در میان انها را برنگانیم دوتاهمرنگ در کنار هم قرار می گیرند.
تعمیم تعمیم مسئله بالا
حالا این مسئله رو حل کنید
همان مسئله بالا را در نظر بگیرید. N تا دایره داریم در صفحه با یک سری نواحی مشترک که اینبار هر دایره 1 وتر هم درون خود دارد. ثابت کنید می توان این نقشه را با سه رنگ رنگ امیزی نمود. نمود به طوری که هر دو ناحیه با مرز مشترک نا همرنگ باشند
این سوال یکی از تمرینات درس پیاده سازی الگوریتم ها دانشکده کامپیوتر شریف از اقای دکتر قدسی بود.
تعمیم تعمیم تعمیم مسئله بالا
یک نقشه داریم که درجه تمام رئوس ان فرد است. ایا می توان انرا با سه رنگ رنگ امیزی نمود به طوری که هر دو ناحیه با مرز مشترک نا همرنگ باشند
تعمیم تعمیم تعمیم تعمیم مسئله بالا ( مسئله چهار رنگ)
ثابت کنید هر نقشه را می توان با حداکثر چهار رنگ رنگ امیزی کرد.
برای قسمت ب سوال شایان در مورد رنگ امیزی یالی گراف شهاب راه حلشو گفت فکر کنیم صحیح باشه. به این صورت که به هر راس یک کد باینری نسبت می دیم و سپس برای هر یال ان یال را به رنگ xor ( یای مانع جمع ) عدد بین ان یال در می اوریم
× مسئله اول رو شخصی که متاسفانه اسمش رو هم نگذاشته فرستاد. خوش حال میشیم با افراد اشنا شیم! همچنین برادرزاده عمو SH.P هم خودشو لو داد. اسمش شهاب پشتکوهی است.برای نوید هم سوال نقشه جواب یه ریگ کوچیک داشت ( توی تعریف خطوط) اصلاحش کردم . برای اعتراضات اگر مثلا 30 نفری که می گیرند 31 بشوید زیاد سخت نمی گیرند.ولی اگر با اخرین نفر به صورت نجومی فاصله داشتید که انشاالله نخواهید داشت شرمنده مخصوصا سوالات مرحله دوم پارسال که نسبتا اسان تر از قبلا بود و نمره ها خیلی به هم نزدیک) همچنین مثل اینکه این پست خیلی طولانی شد. ببخشید.خواهشا نظرات یا ایده های خود را در اخرین پست بگذارید
پیام هاى دیگران
¤ نوشته شده در ساعت 23:27 توسط سید نعمت الله احمدیان
جمعه، 8 اسفند، 1382
نمونه سوالات
عاشورا و تاسوعای حسینی را پیشاپیش تسلیت عرض می نماییم
سوالاتی من باب علومه الرایانه
N -1 مستطیل داریم که هیچ دو تایی همدیگر را قطع نمی کنند ( روی هم نمی افتند ) میخواهیم ماکزیمم تعداد این مستطیل ها که توی هم واقع شده باشند ( یعنی
X1 در درون X2 . X2 در درون X3 —- Xk-1 در درون Xk واقع شده باشد و k ماکزیمم باشد. الگوریتمی برای اینکار ارائه دهید. ما فقط مشخصات راسهای مستطیل ها را می دانیم
2- در جمع بر و بچ می دانیم از هر گروه 4 نفری یک نفر هست که سه نفر دیگر را می شناسد. ثابت کنید نفری وجود دارد که با همه انشناست ( رابطه اشنایی دو طرفه است )
3-( از نوید)
نقاط وسط اضلاع یک پنج ضلعی الف را به ترتیب به هم وصل میکنیم تا پنج ضلعی جدید الف پرین بوجود اید. فرض کنید الف پرین داده شده باشد.ایا می توان الف را بدست اورد؟
4-2n نفر داریم که می خواهند بروند با هم دوتادوتا بمیرند!تعداد راههایی که می توانیم این ها را دسته بندی کنیم چند تاست ( اگر با گراف اشنا هستید تعداد تطابقات کامل در گراف کامل K2n ر پیدا کنید
5-اگر a,b,q اعداد صحیح باشند و داشته باشیم q= (a2 + b2)/(ab+1) انگاه q مربع کامل است ( این سوالات از نظر سختی دومین سوال مشکل در المپیاد جهانی ریاضی بود. در کل جهان تنها 11 نفر توانستند این سوال را حل کنند )
6-یک ماتریس n*n را که درایه های ان از مجموعه S={1,2,…,2n-1} انتخاب شده اند ماتریس نقره ای می نامند اگر به ازای i=1,2,…,n سطر iام و ستون iام روی هم همه اعضای s را شامل شوند. نشان دهید
الف) هیچ ماتریس نقره ای برای n=2003 وجود ندارد
ب) ماتریس های نقره ای برای تعداد متناهی از n وجود دارند.
× این مسئله از المپیاد جهانی ریاضی سال 1997 از ایران بود طراح اون هم پروفسور محمودیان و مهندس مهدیان بودند ( نکته جالب این است که تمام اعضای تیم ریاضی ایران از این سوال نمره کامل گرفتند )
برای برخی اشخاص (پیام)بسیار بسیار متاسفم
یک چیز : رولینگ ( نویسنده کتب هری پاتر ) به لیست بیلیونر های جهان پیوست ( همین امروز این خبر در MSN منتشر شد. فعلا در رتبه ۵۵۲ قرار دارد)
پیام هاى دیگران
¤ نوشته شده در ساعت 17:57 توسط سید نعمت الله احمدیان
پنجشنبه، 7 اسفند، 1382
جوابیه
دو نقشه ایران یکی بزرگتر یکی کوچکتر داریم.ثابت کنید همواره نقشه کوچیکه رو گر روی نقشه بزرگه بیندازیم یک نقطه ای از ((ایران)) همواره روی هم میفتد؟؟؟
حل این سوال به این صورت است/ یک خط فرضی در نظر بگیرید ( به شکل | )که ار شرقی ترین نقطه نقشه بزرگه به سمت غرب با سرعت ثابت حرکت می کنه و بر محور افقی عموده . خوب . حالا یک خط دیگر هم در نظر بگیرید که از شرقی ترین نقطه نقشه کوچیکه داره به غرب با سرعتی معادل سرعت خط اولی تقسیم بر مقیاس دو نقشه حرکت می کنه. این دو خظ را همزمان حرکت دهید. همزمان هم به غرب می رسند پس حتما در جایی با هم برخورد می کنند. مکان برخورد انها دقیقا طول نقطه مفروض ماست. اگر همین کار را هم برای شمال به جنوب انجام دهیم ( با خطی به شکل ــــــ )عرض ان نقطه را بدست می اوریم! این نقطه ای است که مسئله می خواهد.
. یک رنگ امیزی از گراف کاملn راسی را معتبر گویند هر گاه از n-1 رنگ استفاده کرده باشیم و هر راس نیز دقیقا باn-1 رنگ مجاور باشد.حال اگر n=2^k باشد ا)یک رنگ امیزی معتبر ارایه دهید. ب)یک رنگ امیزی معتبر ارایه دهید که روی هر دور همیلتونی از ان حد اقل k رنگ استفاده شود.
× امن فکر می کنم منظور این سوال رنگ امیزی یالی بوده باشد. اگر این باشد ان وقت قسمت الف حالت خاصی از قضیه ای به نام وایزینگ می باشد ( می توانید انرا در اشنایی با گراف وست یا گراف و کاربردهای ان از باندی-مورتی پیدا کنید. ) قسمت ب را هم بعدا فکر می کنم و جوابش را می نویسم
مخصوص شایان : سوال بشکه ها خیلی خفن یود. من نتونستم حلش کنم. اگه می شه خودت جوابش رو بگو/
یادداشت های بعدی من : آقا دست مریزاد- حسابی همه مارو سر کار گزاشتی- من این سوال رو برای چند نفر دیگر فرستادم مثل اقای اسفهبد. اخر متوجه شدم که این سوال هنوز حل نشده !!! ( ایم رو از تو نامه اقای اسفهبد گفتم )
یک وبلاگ جدید برای المپیاد کامپیوتر توسط بر و بچ کرجی افتتاح شد که خیلی جالب است. حتما ببینید . خوشتان می یاید.
ioikaraj.persianblog.com
در اخر ازی دوباره شروع به خواندن کرد!
پیام هاى دیگران
¤ نوشته شده در ساعت 16:58 توسط سید نعمت الله احمدیان
پنجشنبه، 7 اسفند، 1382
نتایج همه المپیاد ها ( الا کامپیوتر و فیزیک(شرکت نکردم))
تازه ها :
نتایج مرحله اول بیست و دومین المپیاد ریاضی کشور اعلام شد
نتایج مرحله اول المپیاد مقدماتی ریاضی کشور اعلام شد
نتایج مرحله اول هفتمین المپیاد زیست شناسی کشور اعلام شد
نتایج مرحله اول هفدهمین المپیاد ادبی کشور اعلام شد
نتایج مرحله اول چهاردهمین المپیاد شیمی کشور اعلام شد
——————————————————————————–
ریاضی هم قبول بیدم!!!!!!!!!! بهین هم قبول شد … تبیرکات !!!
پیام هاى دیگران
¤ نوشته شده در ساعت 10:31 توسط سید نعمت الله احمدیان
سه شنبه، 5 اسفند، 1382
من + تو = ما
باز هم نمونه سوال
1) 6 دایره به ترتیب مماس بر هم . ثابت کنید دایره ای وجود دارد که همه را قطع می کند.
2) ثابت کنید در یک 2n ضلعی محدب اگر همه راسها را به نقطه p دلخواه در درون 2n ضلعی وصل کنیم ضلعی وجود دارد که بیش از یک خط انرا قطع کرده اند ( این سوال را حتما حل کنید خیلی قشنگه )
3) یک منشی داریم که می خواهد تمرین تایپ کند. در هر خطی L کارکتر جا می شود. منشی برای تمرین خود جمله ای به طولL) m ( m < انتخاب می کند و بعد از تایپ هر جمله 1 فاصله گذاشته و جمله بعدی را تایپ می کند و اگر کلمه ای در انتهای سطر جا نشود فاصله گذاشته و سطر بعدی انرا کامل می نویسد ( هیچگاه کلمه ای در انتهای سطر نوشته نمی شود) ثابت کنید بعد از k حرکت حداقل یک ستون خالی می ماند. ( جمله تمرین مدام تکرار می گردد)
4) یک مورچه داریم سرگردان است و به صورت تصادفی یک مسیر را می پیماید. ( این مسیر ممکن است خود را احتمالا قطع کند) در انتهای حرکت خود شرط لازم و کافی را برای گزاره زیر بیابید. اگر از ابتدای مسیر حرکت مورچه شروع به حرکت کنیم و در هر جا به تقاطعی ( جایی که مسیر خودش را قطع کرده ) برخوردیم از ادامه مسیر از دست راست حرکت می کنیم و ادامه می دهیم تا به انتهای مسیر برسیم ( دقت کنید که این شیوه همیشه موثر نیست )
5) یک سوال نسبتا مشهور : 3 مگس هر بار یکی از وسط دیگری می پرد. 1383 بار این عمل را تکرار می کنند. ایا می توانند به وضعیت اولیه برسند ؟ با 1366 بار چه طور ؟
6) یک ترازوی k کفه ای و n سکه با یک سکه تقلبی سبکتر . با حداقل چند بار وزن کردن می توانیم بفهمیم کدامیک تقلبی است؟
× پاشا سلام !
× فرمت سوالات PDF می باشد. یعنی اگر از لینوکس استفاده می کنید ( همانطور که ایدین گفت ) می توانید از GSView یا PDFviewer استفاده کنید – همراه با لینوکس نصب می شوند ولی اگر از ویندوز استفاده می کنید می توانید از Adobe Acrobat استفاده کنید. نسحه رایگان اکروبات به نام Adobe Acrobat Reader در سایت شرکت Adobe وجود دارد. این فایل ها در تکس تاپپ شده اند. اگر کسی مایل باشد می توانم فایل PS را هم برایشان ارسال کنم!
× من املی هستم. پارسال هم بهین را در کلاس دیدم 0 هیکل هایمان به هم می خورد. هر دو نقلی هستیم!
پیام هاى دیگران
¤ نوشته شده در ساعت 15:23 توسط سید نعمت الله احمدیان
دوشنبه، 4 اسفند، 1382
پاسخ تشریحی سوالات مرحله اول
جوابهای مرحله اول امسال :
کلیه جوابهای تشریحی برای مرحله اول امسال را می توانید در سایت آیدین ( فامیلیشو قبلا خوانده بودم یادم رفت – حافظه- هرچند این کمبود حافظه دو جانبه است – اسم من بیش از ۵۰ بار تو این بلاگ تکرار شده اما هنوز اسم من رو نمی دونه ؟ چه کنم !) پیدا کنید. جوابهای اون هم تماما صحیح هستندـ هر چند من با ۱۴ مخالفم !!!)
ادرس سایت ایدین
پیام هاى دیگران
¤ نوشته شده در ساعت 18:46 توسط سید نعمت الله احمدیان
دوشنبه، 4 اسفند، 1382
هلیچ
به نام خدا
اصول بازی هلیچ به صورت زیر است:
شروع بازی با بهنام است. بهنام برای شروع قرعه کشی می گوید 1 . . 2 .. 3 . هلیچینتارانتینو پس از این عبارت همه شرکت کنندگان با انگشتانشان عددی بین 1 تا 3 نمایش می دهند. سپس بهنام از خودش از جهت راست شروع به شمارش یک تا مجموع تعداد انگشتانی که بچه ها اورده اند می کند.و اخرین نفر این شمارش بازنده است.
بازی هلیچ را بین عمو ولدمورت و دایی دامبلدور در نظر بگیرید. عمو ولدمورت اول است.
1-ایا این بازی منصفانه است ؟
2-اگر کمی شعور به خرج دهید متوجه می شوید که عمو ولدمورت دارد مارمولک بازی در می اورد. و احتمال برد او در بازی بشتر است ( ثابت کنید) ولی ایا دایی دامبلدور با دانستن این امر می تواند استراتژی خاصی را دنبال کند که احتمال بردش 3/2 ( 66%) شود ؟
3-اگر عمو ولدمورت به دایی دامبلدور بگوید که می خواهد چه شیره ای سرش بمالد ( یعنی در هر نوبت با چه احتمالی 1-2-3 می اورد) ایا دایی دامبلدور می تواند برنده شود؟
4-اگر هر دو طرف بهترین استراتژی ممکن خود را بدون اعلام به یکدیگر اتخاذ کنند در نهایت احتمال برد کدامیک بیشتر خواهد بود. ایا ممکن است نعویض استراتژی در وسط بازی به نفع کسی باشد؟
5- بازی را در نظر بگیرید که هرگاه مجموع 3و2یا 6 باشد عمو جان و اگر مجموع 4 یا 5 باشد دایی برنده شود . اگر هر دو طرف به طرز معقولی بازی کنند کدامیک احتمال برد بیشتری دارد
× توجه : این سوال ظاهرش قلمبه است اما سوال نسبتا اسانی است
×توجه 2 : به تعدادی دوست اشنا به گرافیک سه بعدی در برنامه نویسی و دایرکت ایکس یا اپن جی ال یا لاین تو نیاز مندم!!
همچنین سوالات PDF را از سایت دکتر قدسی کش رفتم انجا کلیک کنید میاد. ). جواب خواندن درس را هم قبلم دادم ـ اخر این هفته ازمون هماهنگ داریم = غمباد گرفتم – من با یاهو به هیچ هنوان کار نمی کنم – ای دی MSN ؛ adelahmadyan@msn.com
پیام هاى دیگران
¤ نوشته شده در ساعت 18:38 توسط سید نعمت الله احمدیان
یکشنبه، 3 اسفند، 1382
دانلود
سوالات مرحله اول االمپیاد کامپیوتر 82
سوالات مرحله دوم المپیاد کامپیوتر اردیبهشت – روز اول
سوالات مرحله دوم المپیاد کامپیوتر ادریبهشت 82 – روز دوم
همچنین اگر از ویندوز استفاده می کنید ممکن است در خوانش کمی دچار اشکال شوید. چون در لینوکس تایپ شده اند. اگر پرینت بگیرید مشکلشان حل می شود.
این را هم حتما دانلود کنید. تمام فرمول های ریاضیات گسسته و ترکیبیات به صورت فشرده
همچنین برای برخی ضوایا ( جمع مکسر ضایع) مادرزاد منظور از 3/1 یعنی 0.33 -( 1 تقسیم بر 3) م.ز.ز
خدمت آقا علی برای لطف بسیار زیادشان ! ارادت داریم!
درس بده – درس اخه – درس ماله بچه تنبلاس
پیام هاى دیگران
¤ نوشته شده در ساعت 14:28 توسط سید نعمت الله احمدیان
شنبه، 2 اسفند، 1382
فیلمkill Bill را حتما ببینید ( نمی دونم اینجا چی بنویسم)
باسلام :
– این سوال را حل کنید :
n تا بشکه بنزین و یک وانت داریم. وانت توانایی حداکثر حمل دو بشکه ( یکی در باک و یکی در پشت خود دارد) هر بشکه ۱ کیلومتر سوخت وانت را تامین می کند. ماکزیمم مسیری که می توان با این تعداد بشکه رفت چقدر است ؟
برای مثال به ازای ۳ بشکه جواب ۳/۷ صحیح است. وانت با دو بشکه ۳/۱ متر جلو می رود.۱ بشکه را می گذارد. بر می گردد و بشکه دیگر را می گیرد و دوباره به ۳/۱ بر می گردد و ان بشکه را گرفته و با این دو بشکه ۲ کیلومتر جلو می رود.
– برای کارنامه کسانی که مرحله اول قبول شده اند ولی در کف مرحله دوم مانده اند می توانند با باشگاه دانش پژوهان جوان تماس بگیرند تا کارنامه انها شامل درصد مرحله اول و دوم با رتبه انها برایشان صادر شود. به بقیه کارنامه نمی دهند.
– برای نتایج ریاضی و کامپیوتر باید از غوره پیتزا ( جای حلوا) بسازیم- ۱ الی ۲ هفته بعد.
پیام هاى دیگران
¤ نوشته شده در ساعت 18:15 توسط سید نعمت الله احمدیان
شنبه، 2 اسفند، 1382
الگوریتم تاری
الگوریتم تاریTarry's Algorithm
توجه : این الگوریتم برای زمانی خوب است که بخواهید همه یالها را از هر دو جهت طی کنید . برای جستجو در راسها بهتر است از الگوریتم دیگری موسوم به دی.اف.اس استفاده کنید
یک قلعه با تعداد زیادی اتاق و راهرو های محدود در نظر بگیرید.هر راهرو دو انتها دارد که هر انتها به یک اتاق منتهی می شود. هر اتاقی دارای چندین در است که هر در به یک راهرو باز می شود. می توان از هر اتاق به یک اتاق دیگر با گذشتن از تعدادی راهرو و یا اتاق رسید. در ابتدا بر روی هیچ دری علامتی وجود ندارد.یک ربات در یک اتاقی از قلعه وجود دارد و باید تمام اتاقهای قلعه را به روش زیر جستجو کند. این ربات از قوانین زیر پیروی می کند:
1-بعد از وارد شدن به هر راهرو از ان می گذرد و بهاتاق دیگری که در انتهای راهرو قرار دارد می رود.
2-در هنگام وارد شدن به اتاقی که تمام درهایش علامت نخورده اند بر روی دری که وارد شد علامت * می کذارد.
3-اگر در اتاقی وارد شد که تعدادی از در هایش علامت نخورده باشد بر روی یکی از درهای علامت نخورده علامت # گذاشته و وارد ان می شود.
4-هرگاه وارد اتاقی شد که تمام در هایش علامت# خورده از دری که علامت نخورده ( در صورت وجود ) خارج می شود.
5-در اتاقی که تمام در هایش علامت # خورده می ایستد.
6-در ابتدای هرکت بر یکی از در ها را انتخاب کرده و بر روی ان علامت# می گذارد.
ثابت کنید این ربات بعد از دقیقا دومین گذر از تمام راهرو ها متوقف می شود. هر گذر در یک جهت.
راهنمایی : بر روی تعداد راهرو ها از استقرا استفاده کنید. همچنین می توانید ثابت کنید گشت و گذار ربات دقیقا در نقطه ابتدایی پایان می پذیرد.
نکته : تمامی تصمیمات موضعی هستند. ربات چیزی جز اتاق یا راهروی فعلی نمی بیند