k-مکعب

rezashiri · 1390/11/10

ثابت کنید

$Q_{k}$

دوری همیلتونی دارد.

حال الگوریتمی ارائه دهید که با دریافت

$k$

از ورودی این دنباله را چاپ کند.(به صورت باینری)

goodarz · 1390/11/10

پاسخ : k-مکعب

قسمت اولش استقراست....
واسه قسمت دوم, من الگوریتم زیاد حالیم نمیشه, ولی فکر کنم بشه اینجوری نوشتش که بگیم ار راس با کد باینری

$(0,0,....,0)$

شروع کن, الگوریتم رو روی

$k-1$

تایی اول اجرا کن, بعد درایه آخر رو 1 کن, بعد الگوریتم روی

$k-1$

تایی اول رو برعکس اجرا کن بعد درایه آخر رو 0 کن.

rezashiri · 1390/11/10

پاسخ : k-مکعب

goodarz گفت

این قسمت رو من متوجه نمی شم چی کار کردید؟ میشه بیشتر توضیح بدید؟

goodarz · 1390/11/10

پاسخ : k-مکعب

ببینید طبق استقرا, یه الگوریتم وجود داره که اگه از دنباله

$(0,0,...,0)$

که k-1 صفر داره شروع می کنه و همه دنباله های باینری رو تولید می کنه تا دوباره به

$(0,0,...,0)$

برسه, حالا من میگم که تو حالت k تایی جمله آخر رو ثابت بگیرید و همون الگوریتم واسه k-1 تایی رو روش اجرا کنید. مشکلتون حل شد؟