الگوریتم ترتیب فاصله ی اعداد؟

[fsima]

سلام
میخوام اعداد 1تا11 را دوبار کنار هم بچینم که هر عدد n با تکرار خودش به اندازه n فاصله داشته باشه مثلا اعداد 1تا
3 به صورت زیر
312132
عدد 1با1 -یک فاصله داره 2با2 دوتا فاصله و 3 با 3 -سه تا فاصله داشته باشه؟
ممنونم از لطفتون

[mortezamsp]

من تا اونجاییکه عقلم الآن جواب میداد یه کد برای این برنامه زدم که برای اعداد 3 و 4 و 7 و 8 و 11 و 12 جواب میده . ولی برای 5 و 6 و بقیه جواب نمیده بیشتر از 13 هم قفل میکنه:گیج:

بخشی از کد:
for( int i=0 ;i+n+1<2*maxNum ;i++ )
{
if( numsAray[i] == 0 && numsAray[i+n+1] == 0 )//&& i<2*maxNum )
{
numsAray[i] = n ;
numsAray[i+n+1] = n ;
sortNumDist ( n-1 ) ;
.ضمنا من خودم نشستم دستی برای 5 هیچ جوابی نتونستم پیدا کنم .ببینم اصلا این الگوریتم برای همه اعداد امکان پذیر هست ؟ یه توضیح درباره خود الگوریتم بده .
درضمن از بقیه دوستان میخوام این برنامه که بصورت داینامیک راحت حل میشه رو بصورت داینامیک حلش کنن ، من نتونستم .
اینم سورس و اجراش :

[fsima]

ممنونم از جوابتون
در جوابتون باید بگم از اونجایی که استاد گفته حداقل اعداد 1تا 11 میتونن قرار بگیرند اما به نظر خودم هم غیر قابی حل میاد چون واسه 1تا 5 هم اصلا حل نمیشه و ساده تر از همه اینکه 1و2 اصلا نیتونن به این طریق قرار بگیرند البته احتمالا واسه اعداد خاصی مثل 3 و11 قابل حل باشه
طبق این برنامه ایی که نوشتین یکسری اعداد اصلا نمیتونن قرار بگیرند و در پایان هم یه سری از خانه های آرایه خالی میمونه من فکر میکنم بعد از اینکه یک بار اعداد را در آرایه قرار دادیم باید اعدادی که در آرایه باقی میمونن را به
نحوی در آرایه جا داد مثلا به جابه جا کردن بعضی از عددهایی که تو آرایه اند

با تشکر

[qwerty11]

این سوال به ازای n های مساوی با 4k+1 یا 4k+2 جواب نداره.

خونه های آرایه رو یکی در میون سفید و سیاه کن. هر عدد زوجی یه خونه ی سفید و یه خونه ی سیاه رو پوشش میده ولی هر عدد فردی یا 2 تا خونه ی سیاه رو میپوشونه یا 2تا خونه ی سفید رو. پس تعداد اعداد فرد بین 1 تا n باید زوج باشه.

[fsima]

ممنونم مطالبی که گفتین درسته مثلا اعداد 1 تا 7 به صورت زیر قرار میگیره
71316435724625
یعنی اگه خونه اول سفید باشه 7 دوم تو خونه سفیده
و 1 اولی تو خونه سیاه قرار میگره و 1 دومی تو خونه سیاه و....
اما واسه چیدن اعدا علاوه بر این مطالب یه چیزه دیگه را هم باید بدونیم اونم این که اعداد طبق چه ترتیبی وارد بشند شما یه بار امتحان کنید خودتون با دونستن این مطلبی که شما گفتین باز هم نمیشه اعدا 1تا 11 را چید

[qwerty11]

راستش من خودم تو جواب n های بزرگش موندم !

ولی اگه فقط n=11 براتون مهمه میتونین از backtrack استفاده کنین. بازم ولی روش فکر میکنم...

[fsima]

13179351081147569428102611 و 2592108151,1167948103647311
این واسه 1 تا 11 دستی بدست آوردم اما اصلا هیچ منطقی نداره

[mortezamsp]

الگوريتم هشت وزير يادتون هست ؟ آيا منطقي براش پيدا كردي ؟ مساله ذاتش طوريه كه يه قانوني به تو ميده و از تو يكسري حالات از بين حالات ممكن ميخواد .
اينجام همينه . يه مجموعه كانديد داري و يه مجموعه جواب كه بايد بر اساس قانون انتخابت ساخته بشه . منطقش همينه . بايد همه حالات ممكن رو بررسي كني و حالات درست رو بعنوان جواب برگردوني .

[pesar irooni]

دوست عزیز همونطور که بچه های دیگه گفتند از طریق روش branch-and-bound که backtracking رو تو بطن خودش داره حل میشه. یه نگاهی به روش حل هشت وزیر تو کتاب neapolitan بنداز.

[qwerty11]

مطمئنم این سوال راه حل ریاضی هم داره !

کلاً این مسئله مسئله ی معروفیه و یه اسمی هم داره که هرچی فکر میکنم یادم نمیاد !

چندتا کتاب ترکیبیات رو هم دیدم ولی اونجاها نبودن ! ولی یادمه که این مسئله رو تو یه کتابی دیدم :-؟

[pesar irooni]

دوست عزیر مطمئن باش که از طریق انشعاب و تحدید(branch-and-bound) و یا بازگشت به عقب (backtracking) -که از درخت که یک مفهوم ریاضی هست استفاده میکنند- حل میشه.

[fsima]

ممنونم از راهنمایی هاتون همون طوری که فرموده بودین یه مسله معروفه که کمتر تو کتابا به طور مستقیم در مورش حرفی زده شده
تو این انجمن هم صحبتی ازش نشده بود انشالا واسه این که این گفتگو کامل بشه الگوریتم کاملش را و برنامه اش را میذارم متاسفانه الان چون امتحان دارم نمیتونم در اولین فرصت حتما میذارمش