Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 15.07.2002, 00:07   #1
Авик
 
CyberJoe's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 30
Posts: 1,348
Downloads: 2
Uploads: 0
Reputation: 9 | 0
Question Kto pomoget?

Narod kto znaet zadachu o 8 korolev v shaxmatax?
------------------
dlja tex kto ne znaet
Nado rasspologit 8 Koroliv na doske shaxmatnoj tak chtobi ni odna druguju ne bila
------------------
Esli kto moget podskazat algoritm pogaluista pomogite.
A esli u kogo on est napisannij na C++ to prishlite
Zaranie spasibo
Reply With Quote
Old 15.07.2002, 02:10   #2
Младенец
 
Join Date: 07 2002
Location: Hell .. (the Netherlands)
Posts: 2
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Smile

ah.. ja ete znaju

palaji tak
E1,A2,H3,f4,C5,G6,B7,D8
Reply With Quote
Old 15.07.2002, 03:43   #3
The Reloaded
 
Aram Hambardzumyan's Avatar
 
Join Date: 01 2002
Location: behind the flesh and gelatinе of soft dull eyes
Posts: 3,387
Downloads: 4
Uploads: 0
Reputation: 146 | 4
Post

посмотри в книге вирта 'алгоритмы+структуры данных=программы', там на паскале, но думаю сойдет. а еще я ее на прологе писал, жаль, не сохранилась а то бы попугал
Reply With Quote
Old 15.07.2002, 12:25   #4
Студент
 
Join Date: 06 2002
Location: Yerevan
Posts: 258
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

Quote:
Originally posted by MuZe:
ah.. ja ete znaju

palaji tak
E1,A2,H3,f4,C5,G6,B7,D8
A posle etogo mogesh' ciklicheski menyat' poloski doski both vertically and horizontally i poluchish' vse vozmognye varianty

A algorithm ochen' prostoj, prosto raspolagaesh' drug za drugom i obychno na 8-om shage mesta ne budet, pojdesh' nazad do xoda kogda u tebya byl vybor, vyberesh' chto-nibud' drugoe i tak dalee. Drugimi slovami - brute force
__________________
http://www.d-brane.com
Reply With Quote
Old 21.07.2002, 02:31   #5
Студент
 
Join Date: 05 2002
Location: Armenia
Posts: 276
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

BAYC ET XNDIRI MEJ KAROL CHI KARALEVA A
Reply With Quote
Old 22.07.2002, 05:35   #6
Дошкольник
 
BlackMoon's Avatar
 
Join Date: 05 2002
Location: The Dark Side of The Moon
Posts: 102
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

postav pervuu korolevu v verkhnem levom uglu
sleduushuu postav tochno tak kak esli bi ti
sigral konem v pravo i t.d. tak ti postavish 4
korolevi

potom 5-uu postvishish ot verkhnei levoi opiat
po zakonu khoda konia no uje vnis, i takje ostalnie
4 korolevi

naskolko ia snau eto edinstvenni algorithm
__________________
BM
Reply With Quote
Old 22.07.2002, 09:19   #7
Студент
 
Join Date: 06 2002
Location: Yerevan
Posts: 258
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

2 BlackMoon.

Eto skoree ne algoritm, a odno chastnoe reshenie (dlya sluchaya 8x8). Kotoroe vyshe uge bylo ukazano by MuZe. (i esli razlichno to kak ya uge opyat' taki skazal ciklicheskoj perestanovkoj vsex stolbcov i strok mogno poluchit' vse resheniya iz odnogo dannogo)
Reply With Quote
Old 25.07.2002, 00:40   #8
Авик
 
CyberJoe's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 30
Posts: 1,348
Downloads: 2
Uploads: 0
Reputation: 9 | 0
Post

Quote:
Originally posted by Eddi:
Ja uznal eta zadacha imeet 92 reshenija!!!
Reply With Quote
Old 25.07.2002, 02:23   #9
Студент
 
Join Date: 06 2002
Location: Yerevan
Posts: 258
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

http://users.net1plus.com/brianl/8queens.htm - this has a java program using recursive algorithm.

I was wrong before stating that you'll get all the solutions from one. There are 12 different solutions (other 80 come from rotations and reflections).

http://mathworld.wolfram.com/QueensProblem.html - also this link gives you the formula to calculate the number of placings for nxn board and k queens.

Have fun
Reply With Quote
Old 31.07.2002, 14:54   #10
Младенец
 
Artsrun Ohanyan's Avatar
 
Join Date: 01 2002
Location: Nor Hajen
Posts: 12
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

Nerkayatcnum em xndri lutsman im tsragir@, vor@ inchpes tesnum eq bavakanin kar& e yev ashxatum e shat arag...
Arajarkeq dzer@...

Code:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void main()
{
	vector< unsigned int > Pattern( 8 );
	for ( unsigned int i = 0; i <= 7; i++ ) 
		Pattern[ i ] = i + 1;

	unsigned int uiCount = 0;
	vector< unsigned int >::iterator start = Pattern.begin(), end = Pattern.end();
	while ( next_permutation( start, end ) )
	{
		bool bFound = true;
		for ( unsigned int i = 0; i <= 7 && bFound; i++ )
			for ( unsigned int j = i + 1; j <= 7 && bFound; j++ )
				bFound = ( abs( Pattern[ i ] - Pattern[ j ] ) != abs( i - j ) );
		if ( bFound )
		{
			uiCount++;
			ostream_iterator< unsigned int > outIt( cout, &quot; &quot; );
			copy( start, end, outIt );
			cout << endl;
		}
	}
	cout << endl << uiCount << &quot; solutions.&quot; << endl;
}
Reply With Quote
Old 01.08.2002, 00:53   #11
Авик
 
CyberJoe's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 30
Posts: 1,348
Downloads: 2
Uploads: 0
Reputation: 9 | 0
Cool

Quote:
Spasibo!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Reply With Quote
Old 01.08.2002, 20:10   #12
Школьник
 
Join Date: 05 2002
Location: Yerevan
Posts: 202
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

Плохой алгоритм.... Идёт тупой перебор, а это не есть хорошо... Вот так вот.

В том же Дейтеле описан неплохой алгоритм, который достаточно легко реализовать, попробуй.

А вообще это задача на рекурсию с возвратом.
Reply With Quote
Old 27.08.2002, 07:02   #13
Младенец
 
Join Date: 08 2002
Location: Yerevan
Posts: 14
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

Рекурсивно решать или нет, все равно в основе решения этой задачи перебор. А рекурсия получается естественно, так-как посик идет по дереву кандидатов, так что каждая из его вершин приходится один раз. Это позволяет если найдено и должным образом зафиксировано одно решение, просто перейту к следующему кандидату, предлагаемому процессом полного перебора как в программе выше. Общая схема приблизительно такая.

void try(int i)
{
for ( int k = 0 to SQUARE_COUNT )
{
выбор к-го кандидата;
если подходит, записываем;
if ( i < SQUARE_COUNT )
try i+1);
}
}

Приблизительно так!
Вообще посмотрите в прекрасной статье Вирта "Program Development by Stepwise Refinement", классическая статья в программировании.
Удачи.
Reply With Quote
Old 27.08.2002, 08:46   #14
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Post

посик по дереву кандидатов ходит ? )
а кандидаты не жалуются ????

а так в принципе алгоритм именно такой )))

могу предложить другую более интерестную модификацию. Написать параллельный алгоритм для ее решения, который решает ее за (наи)меньшее количество времени
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 16:03.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.