بازی با سکه ها: 2001 سکه را به پشت برگردانید
انتخاب n عدد از بین 2n-1 عدد با شرط بخش پذیری مجموع بر n
تعمیم مسئلهِ ی جمع اعداد از المپیاد دبیرستانی امریکا
تعداد اعداد روی تخته در گام nام (نردیک 2012)
ساختن جایگشتی که میانگین هیچ دو عددی بین آن دو نباشد
آشپزباشی: مرتب کردن پشته با برعکس کردن یک دنباله متوالی از ابتدای آن
مساله برجهای هانوی: سه میله داریم که در میله اول n دیسک با شماره های ۱ تا n به ترتیب (دیسک ۱ بالا) قرار دارند و دو میله دیگر خالی هستند. هر بار میتوانیم بالاترین دیسک یک میله را به میله دیگر منتقل کنیم به شرط آن که میله هدف خالی باشد یا همه دیسکهای موجود در آن شماره بیشتری از دیسک در حال انتقال داشته باشند. میخواهیم با $2^n-1$ حرکت همه دیسکها را به میله دوم منتقل کنیم.
راه حل بازگشتی برای این مساله راه حل بازگشتی ارایه دهید.
راه حل غیر بازگشتی برای این مساله راه حل غیر بازگشتی ارایه دهید.
پاسخی درست است که شامل هر دو راه باشد.
سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com
2015-08-06 08:27:15 -0500 امیر شکریسلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-27 07:59:44 -0500 امیر شکریراه حل بازگشتی:
اگر (f(n را در نظر بگیرید میتوانیم با (f(n-1 حرکت n-1 مهره بالا را ببریم وسط بعد با 1 حرکت اون تهیه رو ببریم اخر بعد باز با (f(n-1 اون n-1 تا رو ببریم اخر
$$
f(n)=2f(n-1)+1
$$
$$
f(0)=1
$$
که جمله ی عمومیش میشه
$ 2^n-1
$
که اثبات حد اقل بودنش رو توی استقرا غیر بازگشتیش میگم
غیر بازگشتی:
با استقرا روی n ثابت میکنیم حد اقل حرکات $2^n-1$
هست
فرض : میدانیم برای n-1 درست است برای n ثابت میکنیم
میدانیم برای انتقال پهنترین حلقه به میله سوم باید همه ی حلقه ها از روی ان برداشته شوند و همچنین هیچ حلقه ای روی میله سوم نباشد پس قبل از این که این حلقه را جا به جا کنیم تمام حلقه های باید بر روی حلقه دوم باشند که میشود 1-(pow(2,n-1 (بنابر فرض استقراء) و بعد حلقه برود به حلقه سوم بعد همه حلقه ها برن روی اون که میشه باز 1-(pow(2,n-1 پس جمعا میشه $2^n-1 $
