Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Задача с пятью ферзями 
:(
    Опции темы
Greeneyed
Дата 21.4.2006, 13:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 71
Регистрация: 20.4.2006

Репутация: нет
Всего: нет
Нужно написать программу, расставляющию 5 ферзей но поле 8х8 так,чтобы каждая клетка была под ударом хотябы одного ферзя. Нельзя пользоваться вызывами функцмй,т.е. всё должно быть в одном мудуле. Написать это нужно на С. 
PM MAIL   Вверх
Akina
Дата 21.4.2006, 14:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454
Нужно - ПИШИ, когда напишешь, ту часть кода что работает неверно - в студию.

Алгоритм прост - перебор. 5 вложенных циклов перебора позиций, в них 4 вложенных цикла проверки боев, и никаких функций. 


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.
PM MAIL WWW ICQ Jabber   Вверх
SoWa
Дата 21.4.2006, 18:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Харекришна
****


Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74
Да. Иных решений нету. Перебор долгий конечно, если не сокращать. А вообще уже обсуждалось, но немного другая задача- чтобы ферзи друг друга не били. Поищи. 


--------------------
Всем добра smile
PM MAIL ICQ   Вверх
Greeneyed
Дата 22.4.2006, 09:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 71
Регистрация: 20.4.2006

Репутация: нет
Всего: нет
Задачу я, вроде бы, решил. Вот только она выдаёт 5728 вариантом. По-моему многова-то. А ещё я в инете видел, что их всего 4860. Если кому не лень, посмотрити прикреплённый файл. 

Присоединённый файл ( Кол-во скачиваний: 27 )
Присоединённый файл  SEMA.C 4,06 Kb
PM MAIL   Вверх
SoWa
Дата 22.4.2006, 19:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Харекришна
****


Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74
А ты повторы проверял? smile 


--------------------
Всем добра smile
PM MAIL ICQ   Вверх
Greeneyed
Дата 22.4.2006, 21:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 71
Регистрация: 20.4.2006

Репутация: нет
Всего: нет
Цитата(SoWa @ 22.4.2006,  19:50)
А ты повторы проверял? smile

Нет. Их там,вроде бы, быть не должно. 
PM MAIL   Вверх
mes
Дата 23.4.2006, 00:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: нет
Всего: 250
Цитата(Greeneyed @ 22.4.2006,  21:37)
Цитата(SoWa @ 22.4.2006,  19:50)
А ты повторы проверял? smile

Нет. Их там,вроде бы, быть не должно.

Как минимум есть повторения относительно поворота доски на 180 градусов.  smile 
Взять хотя бы последнюю позицию, если повернуть доску - то она станет первой.
Чтоб такого не происходило перемешение одного из ферзей надо ограничить половиной доски: 
Т.е вместо
Код

for(a=0;a<60;a++)

Поставить
Код

for(a=0;a<32;a++)


К сожалению нет возможности проверить , буду рад если кто проверит и скажет сколько вариантов получится.

P.S.  Я думаю в строчке:
Код

int j; 
 не хватает обнуленя:
Код

int j=0; 


P.S.S.

Способ определения битых полей у тебя слишком "громоздкий" - много бесполезных операций- поле деятельности для оптимизации. smile

 


--------------------
http://opendots.net
PM MAIL WWW   Вверх
Greeneyed
Дата 23.4.2006, 14:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 71
Регистрация: 20.4.2006

Репутация: нет
Всего: нет
Цитата(mes @ 23.4.2006,  00:02)
Как минимум есть повторения относительно поворота доски на 180 градусов.  smile 

Ну, тогда поворот на 90 градусов.
Цитата(mes @ 23.4.2006,  00:02)

Способ определения битых полей у тебя слишком "громоздкий" - много бесполезных операций- поле деятельности для оптимизации. smile

Да я и сам знаю. Но ничего попроще придумать не могу.  

Это сообщение отредактировал(а) Greeneyed - 23.4.2006, 14:41
PM MAIL   Вверх
mes
Дата 23.4.2006, 18:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: нет
Всего: 250
Цитата(Greeneyed @  23.4.2006,  14:40 Найти цитируемый пост)
Да я и сам знаю. Но ничего попроще придумать не могу.  


Ну например чтоб найти месторасположение ферзя не нужно просматривать каждую клетку.
У тебя есть номер клетки, а его легко превратить в номер горизонтали и вертикали.
например для ферзя е:
Код


  f_e_x = (e >> 3) & 7;// номер горизонтали (от 0 до 7)
  f_e_y = e & 7; // номер вертикали (от 0 до 7)

for(y= f_e_y; y<64;y+=8) {

    if(doska[y]!=9) doska[y]=1;} //заполняет единицами вертикаль на которой стоит ферзь е 


для горизонтали можно и подругому: искатъ не номер горизонтали, а  номер клетки, с которой начинается горизонталь.
например, чтоб для ферзя найти  номер клетки, с которой начинается горизонталь на которой он рассположен, надо стереть последние 3 бита (остаток от деления на 8):

Код


f_e_nx:= е & 56;// номер первой клетки горизонтали (0,8,16,24,...)

for(x= f_e_nx; x<f_e_nx+8;x++) {
 if(doska[x]!=9) doska[x]=1;} //заполняет единицами горизонталь на которой стоит ферзь е 


Для диагонали: мы уже нашли номер горизонтали и вертикали (f_e_x, f_e_y). Чтоб найти начало одной из диагоналей нужно из обоих переменных вычесть наименьшую из них. Как найти конец первой диагонали и  полностью вторую диагональ я думаю понятно smile 

P.S. мне кажется если для ферзей вместо группы переменных ты создашь массив будет легче организовать цикл заполнения битых полей.

P.S.S 
Код


вместо 

if(doska[k]!=9) doska[k]=1;

а бы использовал 

 doska[k]|=1;


так как у 9 в любом случае последний бит равен 1.  Но ето дело вкуса. smile

Добавлено @ 18:18 
Цитата(Greeneyed @  22.4.2006,  09:44 Найти цитируемый пост)
Вот только она выдаёт 5728 вариантом. По-моему многова-то. А ещё я в инете видел, что их всего 4860.

Только что проверил твой исходник. После обнуления счетчика ( int j=0; smile) показал именно 4860 вариантов.
Значит в принципе у тебя всё правильно.

 


--------------------
http://opendots.net
PM MAIL WWW   Вверх
Greeneyed
Дата 27.4.2006, 17:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 71
Регистрация: 20.4.2006

Репутация: нет
Всего: нет
Спасибо. Буду исправлять. 
PM MAIL   Вверх
Greeneyed
Дата 25.5.2006, 20:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 71
Регистрация: 20.4.2006

Репутация: нет
Всего: нет
Препод - нехороший человек!!!!!!!!!!!!! Сказал, чтоб я всё сделал через функции и, чтобы можно было задавать положение первого ферзя. Никак не могу придумать функцию полного перебора. Помогите пожалуйста. 
PM MAIL   Вверх
mes
Дата 29.5.2006, 02:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: нет
Всего: 250
В таком виде пойдет?

Код


//---------------------------------------------------------------------------

#pragma hdrstop

//---------------------------------------------------------------------------
#include "stdio.h"
#include"conio.h"
#include "stdlib.h"
#pragma argsused

unsigned char F[5]; //Pozicii Ferzej
typedef unsigned char doska[8]; // 8 x 8 BITOV (dlja ekonomii vycheslenij :))

doska D,  // doska dlja proverki bityx polej
      D1; // doska dlja razmeshenija ferzej

void Clear (doska d) // ochishenie
{d[1]=d[2]=d[3]=d[4]=d[5]=d[6]=d[7]=d[8]=0;
}
void Print (doska d) //otobrazhenie doski na monitore
{  unsigned char i,j;

   for (i=8; i>0; i--) //obratnyj otschet dlja pravil'nogo izobrazhenija doski
   {
   for (j=0; j<8; j++)
       { printf ("%d ", (d[i]>>j)&1); } //pobitno otobrazhaet dosku
   printf ("\n");
   }
   printf ("\n");
}
void Mark (doska d, unsigned char f) //procedura opredelenija bityx polej
{unsigned char i,
               d1, d2,         // znachenija dlja diagonali
               px=1 <<(f & 7), // Znachenie (koordinata) po Horintali
               py=1+(f >> 3);  // Koordinata po Vertikali

 if (f<64) // Esli na doske to Metit'
 {
  d[py]|=255;   // Sled po Horizontali

  for (i=1; i<=8; i++)
  {d[i]|=px;}       //Sled po Vertikali

  d1=d2=px;
  for (i=py-1; i>=1; i--)
  {d1>>=1; d2<<=1; d[i]|=d2|d1; } //Sled po Diagonaljam vniz

  d1=d2=px;
  for (i=py+1; i<=8; i++)
  {d1>>=1; d2<<=1; d[i]|=d2|d1; } //Sled po Diagonaljam vverx
 }
}

int main(int argc, char* argv[])
{int u=0;
 unsigned char i;

   for (F[1]=0;      F[1]<60; F[1]++)
{  for (F[2]=F[1]+1; F[2]<61; F[2]++)
{  for (F[3]=F[2]+1; F[3]<62; F[3]++)
{  for (F[4]=F[3]+1; F[4]<63; F[4]++)
{  for (F[5]=F[4]+1; F[5]<64; F[5]++)
{
 Clear (D); // Chistim dosku
 Mark (D,F[1]);
 Mark (D,F[2]);
 Mark (D,F[3]);  // Metim bitye polja na doske D
 Mark (D,F[4]);
 Mark (D,F[5]);

// Proverjaem summu vsex polej :
 if (D[1]+D[2]+D[3]+D[4]+D[5]+D[6]+D[7]+D[8]==255*8)
 //Esli vse Bity Doski ustanovleny, to
 {u++; // Uvelichivaem schetchik
   Clear (D1); //ochishaem dosku Ferzej
   for (i=1; i<=5; i++)
   D1[1+(F[i]>>3)]|=(1<<(F[i] & 7)); //Rasstavljaem Ferzej
//  1+(F[i]>>3  - opredeljaet poziciju po vertikali
// 1<<(F[i] & 7) - opredeljaet mestonaxozhdenioe po gorizontali

   Print (D1); // otobrazhenie
   }

  }}}}}

printf ("%d",u);
getch();

        return 0;
}
//---------------------------------------------------------------------------




Решил подробнее остановится на этом фрагменте:
Код

               px=1 <<(f & 7), // Znachenie (koordinata) po Horintali
               py=1+(f >> 3);  // Koordinata po Vertikali



Допустим у нас ферзь стоит на 20-м  (E3)  поле:

ето 3 поле по вертикали :  1+(20>>3) = 3 (D[3])
и  5 поле по горизонтали:  1 <<(20 & 7)  = 16 или  двоичном: 0001 0000, (пятый [по номеру] бит).

  значит его положение на битовой доске  D[3]=16;

Надеюсь, всё понятно. Если нет, спрашивай ... smile 


 


--------------------
http://opendots.net
PM MAIL WWW   Вверх
mes
Дата 29.5.2006, 02:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: нет
Всего: 250
Цитата(Greeneyed @  25.5.2006,  20:37 Найти цитируемый пост)
чтобы можно было задавать положение первого ферзя.


 smile 

Не доконца понял, что требуется. Требуется, чтоб можно было задать начальное поле ?

Код

void Proverka (unsigned char f1)
{...
    for (F[1]=f1;      F[1]<60; F[1]++)
....

 или жестко зафиксировать позицию одного ферзя ?

В таком случае задаешь цикл для четырех ферзей и проверку на занятость поля 5м ферзем.

   

  


--------------------
http://opendots.net
PM MAIL WWW   Вверх
mes
Дата 29.5.2006, 12:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: нет
Всего: 250
Решил доработать код, вот что получилось :

Код


//---------------------------------------------------------------------------

#pragma hdrstop

//---------------------------------------------------------------------------
#include "stdio.h"
#include"conio.h"
#include "stdlib.h"
#pragma argsused

typedef unsigned char doska[8]; // 8 x 8 BITOV (dlja ekonomii vycheslenij :))
typedef unsigned char ferzi[5];

ferzi F; //Pozicii Ferzej


//------------------------------------------------------------------------------

void Clear (doska d) // ochishenie
{d[1]=d[2]=d[3]=d[4]=d[5]=d[6]=d[7]=d[8]=0;
}

//------------------------------------------------------------------------------

void Print (ferzi F) //otobrazhenie doski na monitore
{  unsigned char i,j;
   doska D;         // doska dlja rasstanovki Ferzej
   Clear (D);       // ochishaem dosku

   for (i=1; i<=5; i++)
   D[1+(F[i]>>3)]|=(1<<(F[i] & 7)); //Rasstavljaem 5 Ferzej

   for (i=8; i>0; i--) //obratnyj otschet dlja pravil'nogo izobrazhenija doski
   {
   for (j=0; j<8; j++)
       { printf ("%d ", (D[i]>>j)&1); } //pobitno otobrazhaet dosku
   printf ("\n");
   }
   printf ("\n");
}

//------------------------------------------------------------------------------

void Mark (doska d, unsigned char f) //procedura opredelenija bityx polej
{unsigned char i,
               d1, d2,         // znachenija dlja diagonali
               px=1 <<(f & 7), // Znachenie (koordinata) po Horintali
               py=1+(f >> 3);  // Koordinata po Vertikali

 if (f<64) // Esli na doske to Metit'
 {
  d[py]|=255;          // Sled po Horizontali

  for (i=1; i<=8; i++)
  {d[i]|=px;}          //Sled po Vertikali

  d1=d2=px;
  for (i=py-1; i>=1; i--)
  {d1>>=1; d2<<=1; d[i]|=d2|d1; } //Sled po Diagonaljam vniz

  d1=d2=px;
  for (i=py+1; i<=8; i++)
  {d1>>=1; d2<<=1; d[i]|=d2|d1; } //Sled po Diagonaljam vverx
 }
}

//------------------------------------------------------------------------------

bool Test (ferzi F)
{  doska d;      // doska dlja proverki bityx polej
 Clear (d);      // Chistim dosku
 Mark (d,F[1]);
 Mark (d,F[2]);
 Mark (d,F[3]);  // Metim bitye polja na doske D
 Mark (d,F[4]);
 Mark (d,F[5]);

// Proverjaem summu vsex polej :
 if (d[1]+d[2]+d[3]+d[4]+d[5]+d[6]+d[7]+d[8]==255*8)
  return true; // vse bity zapolneny
  return false; // kontrol'naja summa ne sovpala
 }

//------------------------------------------------------------------------------

int main(int argc, char* argv[])
{int u=0;
   for (F[1]=0;      F[1]<60; F[1]++)
{  for (F[2]=F[1]+1; F[2]<61; F[2]++)
{  for (F[3]=F[2]+1; F[3]<62; F[3]++)
{  for (F[4]=F[3]+1; F[4]<63; F[4]++)
{  for (F[5]=F[4]+1; F[5]<64; F[5]++)
{
if (Test (F))  //Proverjaem
   {              // Esli vernulos' true
    u++;       // Uvelichivaem schetchik
    Print (F); // Otobrazhaem
  }
}}}}}

 printf ("%d",u);
 getch();

        return 0;
}
//---------------------------------------------------------------------------





  

Это сообщение отредактировал(а) mes - 2.6.2006, 11:36


--------------------
http://opendots.net
PM MAIL WWW   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0591 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.