Условия за ползване
Форумът е забранено:
Нарушителите ще бъдат сурово наказани от модераторите и администраторите, и те ще бъдат напълно лишен от достъп до форума.
С помощта на този форум можете да:
В тази статия, нека да поговорим за известния логически пъзел, наречен "осем царици". Същността на проблема се крие във факта, че трябва да бъде в състояние да пусне на шахматната дъска (8 х 8) осем царици, така че те не са в процес на взаимно борба (не забравяйте, че кралицата (Queen) има напред и по диагонал). Аз ще кажа, че има няколко варианта за поставяне, но за да ги намерите ръчно, не винаги е лесно, особено трудно да се сложи последната царица. Едно изпълнение настройки дами изглеждат на фигура 1 по-долу
За да се реши проблемът с проблема с осем царици, ние ще напише програма на езика за програмиране C ++, която ще определи кралиците. Аз предлагам да следвате тези тактики:
1. шахматна дъска представени като двуизмерен масив с размер 8 х 8.
2. За всяка клетка масив да се посочи брой, който ще каже колко на клетките с кралицата може да победи другите клетки. Виж Фигура 2
Както можете да видите, ако си сложиш кралицата относно позицията на х = 2, у = 1, а след това битка ще бъде 23 клетки. Тази процедура трябва да се направи, за всеки квадратен на шахматната дъска (двумерен масив). Като резултат, ние получаваме точно такава картина, както е показано по-долу на фигура 3
3. След определянето на приоритетите, изберете клетката с минимално предимство (този, с който да бие по-малко от друга клетка борда) и сложи върху нея кралицата. Мисля, че всичко е ясно. защото ако сложите кралици на тези клетки, с които да победи повече други клетки, преди пускането осем царици ние не достигат. Ние продължаваме да говорим. Ако минималният брой на приоритетните клетки намерени (както в началото на споразумение ще бъде по този начин), след това изберете appropriate'll на случаен принцип. Тъй като е логично оправдано да се организира? За да направите това, ние трябва първо да разбера каква е минималната приоритет (например 21 - че тя е най-малката в първата итерация - виж фигура 3.), след това се преброят с приоритета на клетките (в този случай, с 21 от същите тези клетки вече е 28), по-нататък генерира случайно число в границите от 1 до броя на идентичните клетки (от 28) и, от получената в броя на поколение, поставени царицата на желаното място. Клетката, в която ще се постави на кралицата, по някакъв начин ще бъдат маркирани, например, то присвояването на стойност 100. Можете да вземете абсолютно никаква стойност, освен че е избрано така, че да не се определя като минимум в приоритет.
4. След определяне на кралицата, ще трябва да ги премахнете бити клетки, маркирането им в произволен брой. Да кажем, че аз отивам да маркирате тези клетки за удобство на броя 99.
Малко обяснение. Когато основният алгоритъм на подреждане на царици ще работи и ще остане на борда (двумерен масив, който емулира шахматна дъска) килия с номера 100 (това кралица) и 99 - насинена клетки, получаваме в резултат на екрана, с условието, че ако се срещнем номер 100 - това привлече кралицата (или конзола - снежинка, грил и т.н.), в противен случай просто се клетката празно (или конзола за яснота, можете да ги маркира с тире, точки и т.н.).
5. След това всичко се повтаря от стъпка 2 до 4 отново, докато раздялата на всички дами, които трябва да бъдат осем. След това има още една точка: при първия опит, дори и с помощта на така наречените "интелигентни" подход към изпълнението на задачите, по-горе алгоритъм не може да се осигури на всички осем царици. Но има изход от тази ситуация. След поставяне ние ще проверим: Ще го постави всички кралици. Ако не е, повтарям подравняването отново.
Следната четвъртата цифра се въвеждат в действие на алгоритъма, описан по-горе за илюстративни цели. Тя може да произвежда различни варианти на договорености, но за това трябва да рестартирате вашия уеб страница ( "Refresh" бутон в браузъра ви или F5), а след това резултатът ще се промени. За съжаление, уеб-технологии Аякс, аз не знам какво друго, така че да получите нова картина имате нужда да презаредите страницата.
Това е вид на програмата (досега цитирам само основната си част - основна функция ()), която реализира алгоритъма
Както можете да видите, че е осъзнал, че съм споменато по-горе
1) да обявяват двумерен масив борда. измерение на 8 х 8 клетки - това ще бъде нашата шахматна дъска. Също така, ние ще трябва променливите за съхранение на координатите на точките (х и у), както и насоки за тях (ptrX и ptrY). За да се инициализира масив от нули, ще служим функция resetBoard ().
2) Matrix обявена, инициализира. Сега погледнете вътре в продължение на цикъла. и че ние ще трябва да се извърши изравняване на осемте царици. Както казахме в параграф 2 по-горе, трябва да зададете приоритет за всяка клетка на матрицата. Това ще направи функция updateBoard ().
4) След установяване на кралицата, маркирайте ги мъртви клетки. Дали тази функция deleteCell ().
Този процес се повтаря осем пъти точно както е посочено в условията на за цикъл. Ако, както писах по-горе, няма да работи с първия опит да се поставят осемте царици, процесът на поставяне се изчиства с помощта resetBoard () и поставяне на цикълът започва наново. За да ни информирате дали всички осем царици са поставени или не, е функция checkQueens (). връща лъжа. ако не успее да се поставят, и истина. ако беше успешен.
Тук по принцип и всичко, което исках да кажа по този алгоритъм. Пълното изпълнение на програмата се цитират по-долу.
Резултатът от програмата
Послепис Също така на сайта можете да намерите различен изпълнение на алгоритъма "Осем Куинс", изпълняван от програмист Алексей и публикуван във форума. за които мнозина, благодарение на него.
Свързани статии