Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Java] 5 ферзей 
:(
    Опции темы
Merhaba
Дата 28.9.2011, 10:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: нет
Всего: нет
Добрый День!!! помогите Пожалуйста придумать и запрограммировать алгоритм к следующей задаче: Найдите такую расстановку пяти ферзей на шахматной доске, при которой каждое поле будет находиться под ударом одного из них. Использовать рекурсивные функции.   smile 
PM MAIL   Вверх
Silent
Дата 29.9.2011, 13:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 6
Всего: 9
А что тут думать-то? тут писать надо smile
Держи (правда на C#, но у тебя же есть опыт перевода C#->Java ;-) ):
Код

/*
 * Задача:
 * Расставить на шахматной доске NхN M ферзей, чтобы они:
 * 1) не били друг друга
 * 2) держали все клетки под боем
 * 
 * перебор организовать рекурсивно
 */

using System;
using System.Collections.Generic;
using System.Text;

namespace Merhaba_FiveQueen
{
    public class myPoint
    {
        public int x, y;
        public myPoint(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    }
    class Program
    {
        const int N = 8;    //размерность доски
        const int M = 5;    //количество ферзей
        static bool[] d1 = new bool[2*N];    //главная диагональ
        static bool[] d2 = new bool[2*N];
        static bool[] g = new bool[N];
        static bool[] v = new bool[N];
        static Stack<myPoint> s = new Stack<myPoint>();
        static int count = 0;

        //return true если все клетки под боем
        static bool allFill()
        {
            bool res = true;
            bool [,] f = new bool[N,N];
            for (int i = 0; i < N; i++)
            {
                if (!g[i]) 
                    for (int j = 0; j < N; j++) 
                        f[i, j] = true;
                if (!v[i]) 
                    for (int j = 0; j < N; j++) 
                        f[j, i] = true;
            }
            //d1
            for (int i = 0; i < N; i++)
            {
                int x = i,
                    y = 0;
                if (!d1[N-i])
                    for (int j = 0; j < N-i; j++) 
                        f[x++, y++] = true;
                x = 0;
                y = i;
                if (!d1[N+i])
                    for (int j = 0; j < N - i; j++) 
                        f[x++, y++] = true;
            }
            //d2
            for (int i = 0; i < N; i++)
            {
                int x = 0,
                    y = N-1-i;
                if (!d2[y])
                    for (int j = 0; j <= N-1 - i; j++) 
                        f[x++, y--] = true;
                x = i;
                y = N-1;
                if (!d2[i+N-1]) 
                    for (int j = 0; j <= N-1 - i; j++) 
                        f[x++, y--] = true;
            }
            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    res &= f[i, j];
            return res;
        }

        //вывод ответа в шахматной нотации
        static void output()
        { 
            myPoint[] tmp = new myPoint[s.Count];
            s.CopyTo(tmp, 0);
            Console.Write("{0}  ", count);
            for (int i = s.Count - 1; i >= 0 ; i--)
                Console.Write("{0} {1}  ", (char)(N-1 - i + 97), tmp[i].y+1);
            Console.WriteLine();
        }

        //основная процедура поиска
        static void search(int x, int y, int level)
        {
            if (level == M)
            {
                if (allFill()) 
                {
                    count++;
                    output();
                }
            }
            else
                if (x < N)
                {
                    while (x < N)
                    {
                        if (g[x] && v[y] && d1[N - x + y] && d2[x + y])
                        {
                            s.Push(new myPoint(x, y));
                            g[x] = false;
                            v[y] = false;
                            d1[N - x + y] = false;
                            d2[x + y] = false;
                            search(x + 1, 0, level + 1);
                            s.Pop();
                            g[x] = true;
                            v[y] = true;
                            d1[N - x + y] = true;
                            d2[x + y] = true;
                        }
                        x += (++y / N);
                        y %= N;
                    }
                }
        }

        static void Main(string[] args)
        {
            Console.SetOut(new System.IO.StreamWriter("output.txt"));
            int x = 0, y = 0;
            for (int i = 0; i < N; i++)
            {
                v[i] = true;
                g[i] = true;
            }
            for (int i = 0; i < 2*N; i++)
            {
                d1[i] = true;
                d2[i] = true;
            }
            search(0, 0, 0);
            Console.Out.Close();
        }
    }
}

Количество вариантов - 728, что, кстати, совпадает с другими программами.
PM MAIL   Вверх
Merhaba
Дата 30.9.2011, 05:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: нет
Всего: нет
Silent,  а каким алгоритмом нужно руководствоваться при написании кода к данному заданию: "Найдите такую расстановку пяти ферзей на шахматной доске, при которой каждое поле будет находиться под ударом одного из них." ? smile 
PM MAIL   Вверх
Silent
Дата 30.9.2011, 07:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 6
Всего: 9
Вообще-то можно решать эту задачу несколькими алгоритмами: полный перебор, перебор с эвристиками, минимальное доминирующее множество и т.п.
В данном случае от тебя требовалось сделать перебор, ну или максимум перебор с эвристиками, организовав его с помощью рекурсивной функции поиска. Обычная перечислительная комбинаторика
PM MAIL   Вверх
Merhaba
Дата 1.10.2011, 06:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: нет
Всего: нет
Silent,  А каким требованиям должна удовлетворять постановка ферзя, чтобы выполнялось условие задачи? ("каждое поле будет находиться под ударом одного из них")   smile 
как можно переписать код, с использованием методов, которые ставят и убирают ферзя :
Код

void putQueen(int h, int v){
        positionOnVertical[v] = h;
        onHorizontal[h] = false;
        RUtoLD[v+h] = false;
        LUtoRD[(v-h) + (deskSize-1)] = false; 
    } 

    void removeQueen(int h, int v){
        positionOnVertical[v] = 0;
        onHorizontal[h] = true;
        RUtoLD[v+h] = true;
        LUtoRD[(v-h) + (deskSize-1)] = true;
    } 
 ? smile 
PM MAIL   Вверх
Silent
Дата 1.10.2011, 14:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 6
Всего: 9
Формулировка "каждое поле будет находиться под ударом одного из них" подразумевает, что на конечной расстановке ферзей любая клетка поля будет биться только лишь одним ферзем.
Сходу я не могу придумать, как изменить алгоритм чтобы ферзя можно было поставить только по этому условию, однако, как подсказывает здравый смысл, нафиг особо такое не надо - в любом случае эта оптимизация будет подмножеством вышереализованного мной алгоритма (ибо нужно чтобы ферзи друг дружку не били): для конечной расстановки просто проверять этот факт. А это просто-напросто немного модифицировать процедуру AllFill() - поменять тип массива f на int, и вместо f[i,j] = true инкрементить f[i,j]++. Если в итоге будут единички (а в позициях ферзей 4) - значит гут, расстановка нам подходит.
PM MAIL   Вверх
Merhaba
Дата 25.12.2011, 16:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: нет
Всего: нет
Silent,  скажите Пожалуйста, за что отвечает переменная level?

Добавлено через 3 минуты и 36 секунд
Silent, 
Перепишите Пожалуйста вот этот кусочек кода на Ява:
 
Код

static void output()
        { 
            myPoint[] tmp = new myPoint[s.Count];
            s.CopyTo(tmp, 0);
            Console.Write("{0}  ", count);
            for (int i = s.Count - 1; i >= 0 ; i--)
                Console.Write("{0} {1}  ", (char)(N-1 - i + 97), tmp[i].y+1);
            Console.WriteLine();
        }
PM MAIL   Вверх
Mirkes
Дата 10.1.2012, 13:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 4
Всего: 17
Цитата(Silent @  1.10.2011,  14:53 Найти цитируемый пост)
Формулировка "каждое поле будет находиться под ударом одного из них" подразумевает, что на конечной расстановке ферзей любая клетка поля будет биться только лишь одним ферзем.

Ошибка. Эта фраза означает всего лишь, что каждое поле будет биться ХОТЯ БЫ ОДНИМ ферзем.
Нельзя поставить на шахматную доску даже двух ферзей так, чтобы ни одно поле не пробивалось двумя ферзями. (опыт шахматиста).
В принципе можно организоват перебор просто ставя или снимая ферзя, но это будет совсем полный перебор.

Для этого достаточно создать доску типа int[8][8]. Обнулить. 
Далее запускаем процедуру поиска с уровнем 0 (нет поставленных ферзей)
В процедуре поиска
   Проверяем уровень. Если он =5, то проверяем наличие нулевых клеток. Если их нет, то это решение, его можно выводить.
   Если уровень 5 и есть нулевые клетки - возврат.
   перебираем все клетки по x и y от 1 до 8.
      Если клетка нулевая ставим ферзя и вызываем следующую процедуру поиска с уровнем на 1 больше. Снимаем ферзя.
    По окончании цикла - возврат

Процедура поставить ферзя. По горизонтали, вертикали и обеим диагоналям от позиции ферзя в каждую клетку добавляем по 1. В позицию ферзя добавляем 100. (не обязательно 100, но точно больше 4).
Процедура снять ферзя - тоже что поставить, но вместо увеличения - вычитаем.



--------------------
Mirkes
PM MAIL   Вверх
Mirkes
Дата 13.1.2012, 17:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 4
Всего: 17
Пожалуйста, но я не понимаю, в чем был затык у вас
Код

package fer;

public class Ferz {
    private int field[][] = new int[8][8];
    static final String not = "abcdefgh";

    public static void main(String[] arg) {
        new Ferz().run();
    }

    public boolean full() {
        for (int i = 0; i < 8; i++)
            for (int j = 0; j < 8; j++)
                if (field[i][j] == 0)
                    return false;
        return true;
    }

    public void putFerz(int x, int y) {
        for (int i = 0; i < 7; i++) {
            // Процедура поставить ферзя. По горизонтали, вертикали
            field[i][y]++;
            field[x][i]++;
            // и обеим диагоналям от позиции ферзя в каждую клетку добавляем по 1. В позицию ферзя добавляем 100. (не обязательно 100, но точно больше 4).
            if (x - i >= 0) {
                if (y - i >= 0)
                    field[x - i][y - i]++;
                if (y + i < 8)
                    field[x - i][y + i]++;
            }
            if (x + i < 8) {
                if (y - i >= 0)
                    field[x + i][y - i]++;
                if (y + i < 8)
                    field[x + i][y + i]++;
            }
        }
        field[x][y]+=100;
    }

    public void removeFerz(int x, int y) {
        for (int i = 0; i < 7; i++) {
            // Процедура снять ферзя. По горизонтали, вертикали
            field[i][y]--;
            field[x][i]--;
            // и обеим диагоналям от позиции ферзя в каждую клетку добавляем по 1. В позицию ферзя добавляем 100. (не обязательно 100, но точно больше 4).
            if (x - i >= 0) {
                if (y - i >= 0)
                    field[x - i][y - i]--;
                if (y + i < 8)
                    field[x - i][y + i]--;
            }
            if (x + i < 8) {
                if (y - i >= 0)
                    field[x + i][y - i]--;
                if (y + i < 8)
                    field[x + i][y + i]--;
            }
        }
        field[x][y]-=100;
    }


    public void find(int level) {
        // В процедуре поиска
        if (level == 5) {
            // Проверяем уровень. Если он =5, то проверяем наличие нулевых клеток. Если их нет, то это решение, его можно выводить.
            if (full()) {
                //его можно выводить
                for (int i = 0; i < 8; i++)
                    for (int j = 0; j < 8; j++)
                        if (field[i][j] > 100) {
                            System.out.print(""+not.charAt(i) + (j + 1) + " ");
                        }
                System.out.println();
            }
            // Если уровень 5 и есть нулевые клетки - возврат.
            return;
        }
        //перебираем все клетки по x и y от 1 до 8.
        for (int i = 0; i < 8; i++)
            for (int j = 0; j < 8; j++)
                if (field[i][j] == 0) {
                    //   Если клетка нулевая ставим ферзя и вызываем следующую процедуру поиска с уровнем на 1 больше. Снимаем ферзя.
                    putFerz(i, j);
                    find(level + 1);
                    removeFerz(i, j);
                }
        //По окончании цикла - возврат


    }

    public void run() {
        // Clear field
        // Для этого достаточно создать доску типа int[8][8]. Обнулить.
        for (int i = 0; i < 8; i++)
            for (int j = 0; j < 8; j++)
                field[i][j] = 0;
        // Далее запускаем процедуру поиска с уровнем 0 (нет поставленных ферзей)
        find(0);
    }
}



--------------------
Mirkes
PM MAIL   Вверх
Merhaba
Дата 13.1.2012, 21:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: нет
Всего: нет
Mirkes,  Спасибо Вам большое за помощь!!! как можно переделать код, чтобы тут был метод, который будет распечатывать расстановки (ферзь обозначается "*", клетка ".")? 
Как организовать подсчёт расстановок?
PM MAIL   Вверх
Mirkes
Дата 14.1.2012, 12:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 4
Всего: 17
Код

              //его можно выводить                
              for (int i = 0; i < 8; i++)
                    for (int j = 0; j < 8; j++)
                        if (field[i][j] > 100) {
                            System.out.print(""+not.charAt(i) + (j + 1) + " ");
                        }
                System.out.println();
            }

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

              //его можно выводить                
              for (int i = 0; i < 8; i++){
                    for (int j = 0; j < 8; j++)
                        if (field[i][j] > 100) {
                            System.out.print("*");
                        else
                            System.out.print(".");
                        }
                   System.out.println(); // переход к новой строке доски
                }
                System.out.println();  // зарделитель досок
            }

Насчет подсчета найденных ситуаций все несколько хуже - при проверке программы я обнаружил, что каждая позиция находится пять раз. Так что и доски будут распечатываться по пять раз. Есть такой вариант выхода из положения: запоминать найденные позиции и прежде чем печатать проверять не печатали ли ее раньше.


--------------------
Mirkes
PM MAIL   Вверх
Merhaba
Дата 14.1.2012, 12:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: нет
Всего: нет
Mirkes, 
Код

//   Если клетка нулевая ставим ферзя и вызываем следующую процедуру поиска с уровнем на 1 больше. Снимаем ферзя.
                    putFerz(i, j);
                    find(level + 1);
                    removeFerz(i, j);

Для какой цели нам требуется снимать ферзя?
PM MAIL   Вверх
Mirkes
Дата 16.1.2012, 17:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 4
Всего: 17
Постановка ферзя порит поле, снятие ферзя приводит поле к исходному состоянию.


--------------------
Mirkes
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

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

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


 




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


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

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