Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Julila
1 / 1 / 1
Регистрация: 21.12.2010
Сообщений: 159
#1

Задача Дам или задача Восьми

14.05.2016, 19:54. Просмотров 437. Ответов 4
Метки нет (Все метки)

помогите найти ошибку в алгоритме.
не находит ответ
подозреваю ошибку в k, i, j

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package com.company;
 
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        System.out.print("Size : ");
        damenProblem(sc.nextInt());
        sc.close();
    }
 
    public static void damenProblem(int brettgroesse){
        int [] arr = new int [brettgroesse];
        for(int i = 0 ; i<brettgroesse; i++){
            arr[i] = 0;
        }
        placeQueens(arr, brettgroesse, 1);
    }
 
    private static boolean QueenFits(int [] col, int i, int j){ // In die Methode stellt fest , ob die Dame i in der Spalte j aufgestellt
        // werden kann
        for( int k= 0; k<i; k++){
            if ((col[k] == j)  // Queeen k in the same column
                    || (k + col[k] == i + j)             // Queen k in the same main diagonale)
                    || (k - col[k] == i - j)) { // Queen in the same secondary diagonale
                return false;
            }
        }
 
       return true ;
    }
    private static void placeQueens(int[] arr, int brettgroesse, int i){
        for ( int j = 0; j < brettgroesse; j++ ){
 
          //  System.out.println(Arrays.toString(arr));
            if(QueenFits(arr, brettgroesse, j)){
                arr[i] = j; // place Queen in column
                if( i == brettgroesse){
                    System.out.println(Arrays.toString(arr));
                }
                if( i<brettgroesse-1){
                placeQueens(arr, brettgroesse,i+1 );
                arr[i]= 0;}
 
            }
        }
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.05.2016, 19:54
Ответы с готовыми решениями:

Задача о размене -задача динамического программирования?
Является ли задача о размене суммы задачей динамического программирования? Мне...

Управления ресурсами или транспортная задача
Всем привет! Недавно поставили задачу и я даже не знаю за что первым хвататься....

алгоритм какой-то или задача в лоб?
Есть циферблат (как у часов, но если у часов 12 чисел, то тут может быть...

Есть определенная задача. На чем лучше писать, C++ или C#
Прошу не пинать ногами, отличия C# от C++ я уже изучил. Интересует ваше мнение....

Задача Джонсона для 4 станков: нужны ссылки или литература
Подскажите необходимые ссылки или теорию, вообщем любую информацию для...

4
ProgJ
87 / 85 / 10
Регистрация: 20.11.2008
Сообщений: 724
14.05.2016, 22:26 #2
QueenFits или не то делает или вы её неправильно вызываете
0
Shamil1
Модератор
2109 / 1419 / 322
Регистрация: 26.03.2015
Сообщений: 5,148
15.05.2016, 00:47 #3
Цитата Сообщение от Julila Посмотреть сообщение
помогите найти ошибку в алгоритме.
А какую задачу Вы решаете? (Название мне ни о чём не говорит)
0
Julila
1 / 1 / 1
Регистрация: 21.12.2010
Сообщений: 159
15.05.2016, 00:57  [ТС] #4
https://ru.wikipedia.org/wiki/%D0%97...B7%D1%8F%D1%85
0
Shamil1
Модератор
2109 / 1419 / 322
Регистрация: 26.03.2015
Сообщений: 5,148
15.05.2016, 01:48 #5
Dame с немецкого в данном контексте переводится "ферзь". Поэтому это "задача о ферзях", а не "задача дам".
Выкладывать код с комментариями на немецком - это признак дурного тона.
Использовать для переменных не английские имена - это очень плохой стиль программирования.

Судите сами:
Знаете, что такое обфуска́ция? Используется она для того, чтобы читающему было сложнее разобраться в коде. Один из приёмов обфускации - дать переменным бессмысленные названия. Как, например, brettgroesse. Ведь, не зная немецкого, я не могу понять смысл. И даже в словаре не могу найти, так как не знаю, что искать надо Brettgröße.


Вот Вы пишите про метод QueenFits
In die Methode stellt fest , ob die Dame i in der Spalte j aufgestellt werden kann
а сами для параметра i передаёте значение brettgroesse (строка 40).
Поэтому в строке 40 меняем brettgroesse на i.

Теперь разберёмся с i.
Судя по инициализации (строка 21) и условию "i == brettgroesse" (строка 42), i меняется в диапазоне от 1 до brettgroesse.
А судя по коду метода QueenFits и условию "i<brettgroesse-1" (строка 45), i меняется в диапазоне от 0 до brettgroesse - 1.
Поэтому в строке 21 пишем:
placeQueens(arr, brettgroesse, 0);
а в строке 42 пишем:
if( i == brettgroesse - 1)




з.ы. А вообще задача решается в три строки:
Haskell
1
2
3
queens n = foldM f [] [1..n] where
      f qs _ = [q:qs | q <- [1..n] \\ qs, q `notDiag` qs] 
      q `notDiag` qs = and [abs (q - qi) /= i | (qi,i) <- qs `zip` [1..]]
0
15.05.2016, 01:48
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.05.2016, 01:48

Задача с дифференциальным уравнением и арифметической прогрессией или есть проще решение?
Дано: гражданин Эн хочет положить 10000 евро в банк и брать из этой суммы по...

Задача
При форматировании таблицы ученик перепутал ячейки. Найдите ошибки. Термины...

Задача
Определите разрешающую способность изображения, если глубина цвета 4 бита, а...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru