Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.80
Mechanical Poet
2 / 2 / 0
Регистрация: 26.10.2009
Сообщений: 9
#1

О 8 ферзях(Без рекурсии) - C++

20.11.2010, 14:49. Просмотров 2599. Ответов 12
Метки нет (Все метки)

Пытаюсь сделать задачу о 8 ферзях без рекурсии. Сделал набросок, но работает как то криво. В чем проблема?

C++
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <stdlib.h>
#include <stdio.h>
 
int board [ 8 ][ 8 ];
 
void resetQ ( int i , int j )
{
    for ( int x = 0; x < 8; x++ )
    {
        --board [x][j];
        --board [i][x];
        int k;
        k = j - i + x;
        if ( k >= 0 && k<8 )
            --board [ x ][ k ];
        k = j+i-x;
        if ( k >= 0 && k < 8 )
            --board [ x ][ k ];
    }
    board [ i ][ j ] = 0;
}
 
void setQ ( int i, int j )
{
    for ( int x = 0; x < 8; x++ )
    {
        ++board [ x ][ j ];
        ++board [ i ][ x ];
        int k;
        k = j - i + x;
        if ( k >= 0 && k < 8 )
            ++board [ x ][ k ];
        k = j + i - x;
        if ( k >= 0 && k < 8 )
            ++board [ x ][ k ];
    }
    board [ i ][ j ] = -1;
}
 
bool tryQ ( int i )
{
    bool result = false;
    bool pro=false;
    while(i < 8 )
    {
        for ( int j = 0; j < 8 ; j++)
        {
            for ( int g = 0; g < 8 ; g++ )
                {
                    if ( board [i+1][g] == 0)
                        pro=true;
                }
            if ( board [ i ][ j ] == 0 )
            {
                setQ ( i, j );
                if ( pro==false )
                {
                    resetQ ( i, j );
                }
                else
                    i++;
                if ( i == 7 )
                result = true;
            }
            pro=false;
            if ( result )
            break;
        }
        
    }
    return result;
}
 
int main ()
{
    for ( int i = 0; i < 8; i++ )
        for ( int j = 0; j < 8; j++ )
    board [ i ][ j ] = 0;
    tryQ ( 0 );
    for ( int i = 0; i < 8; i++ )
    {
        for ( int j = 0; j < 8; j++ )
        {
            if ( board [ i ][ j ] == -1 )
            printf ( "1 " );
            else 
            printf ( "0 " );
            
        }
        printf ( "\n" );
    }
printf ( "\n" );
 
    for ( int i = 0; i < 8; i++ )
    {
        for ( int j = 0; j < 8; j++ )
        {
            printf ( "%d ", board [ i ][ j ]);
            
        }
        printf ( "\n" );
    }
 
    system ( " Pause " );
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.11.2010, 14:49
Здравствуйте! Я подобрал для вас темы с ответами на вопрос О 8 ферзях(Без рекурсии) (C++):

Рекурсия без рекурсии - C++
Как известно с рекурсией связана маленькая скорость и проблема переполнения стека. Ее можно сымитировать с помощью обычного стека. ...

Функция Аккермана без рекурсии - C++
Возможно сделать функцию Аккермана НЕ рекурсивно, а циклически? Сложность с которой я столкнулся в том что невозможно написать цикл A(0,...

Функция Аккермана без рекурсии - C++
Задача: A(0, n) = n + 1; A(m, 0) = A(m–1, 1); при m &gt; 0; A(m, n) = A(m–1, A(m, n–1)); при m &gt; 0 и n &gt; 0. С рекурсией она...

Написать функцию без рекурсии - C++
bool st(int a) { if(a==1) return true; else return ((a%5==0) ? st(a/5) : false); }

Сортировка слияниеим без рекурсии - C++
Нужна сортировка слиянием без использования рекурсии. Помогите ...

Обход бинарного дерева без рекурсии - C++
нужно написать алгоритм обхода бинарного дерева без использования рекурсии, а с помощью стека. Проверить на дереве int, но в самом коде...

12
SimaLiveEvil
5 / 5 / 0
Регистрация: 02.05.2010
Сообщений: 40
20.11.2010, 15:29 #2
ну вроде как
C
1
2
3
4
5
        for ( int i = 0; i < 8; i++ ) 
        {
                for ( int j = 0; j < 8; j++ )
                      board [ i ][ j ] = 0;
        }
вот так нужно инициализировать массив...

хотя нет... разницы нет...

Добавлено через 11 минут
у Вас цикл
C
1
while(i < 8)
зацикливается на i = 6
0
Mechanical Poet
2 / 2 / 0
Регистрация: 26.10.2009
Сообщений: 9
20.11.2010, 17:16  [ТС] #3
Я вижу что зацикливается на i=6, но нимагу понять почему. Я никак нимагу до конца правильно реализовать эту задачу
0
Shevva
17 / 17 / 0
Регистрация: 13.09.2009
Сообщений: 140
20.11.2010, 17:20 #4
Mechanical Poet, ты случайно не из КНУ?
0
Mechanical Poet
2 / 2 / 0
Регистрация: 26.10.2009
Сообщений: 9
20.11.2010, 17:26  [ТС] #5
Цитата Сообщение от Shevva Посмотреть сообщение
Mechanical Poet, ты случайно не из КНУ?
Нет, я из ТГУ
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
21.11.2010, 20:52 #6
C++
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string  T_queens_disp;
//////////////////////////////////////////////////////////////////////////////////////
bool  last_elem_is_correct(const T_queens_disp&  queens_disp)
{
    int  pos = queens_disp.size() - 1;
    for(int i = 0; i < pos; ++i)
    {
        int diff_abs = abs(queens_disp[i] - queens_disp[pos]);
        if(!diff_abs
           || diff_abs == pos - i) return  false;
    }
    return  true;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  successfully_inc_last_elem(T_queens_disp&  queens_disp)
{   
    for(;;)
    {
        ++*queens_disp.rbegin();
        if(*queens_disp.rbegin() > '8')
        {
            return  false;
        }
        if(last_elem_is_correct(queens_disp))
        {
            return  true;
        }
    }   
}
//////////////////////////////////////////////////////////////////////////////////////
bool  get_next_queens_disposition(T_queens_disp&  queens_disp)
{
    for(;;)
    {
        if(!successfully_inc_last_elem(queens_disp))
        {
            if(queens_disp.size() == 1)
            {
                return  false;
            }
            else
            {
                queens_disp.erase(queens_disp.size() - 1);
            }
        }
        else
        {
            if(queens_disp.size() == 8)
            {
                return true;
            }
            else
            {
                queens_disp += '0';
            }
        }
    }   
}
//////////////////////////////////////////////////////////////////////////////////////
void  print_all_queens_disposition()
{
    T_queens_disp  queens_disp_cur("0");
    std::cout << "Расстановки на шахматной доске 8 ферзей, не бьющих друг друга:"
              << std::endl;
 
    int  count = 0;
    while(get_next_queens_disposition(queens_disp_cur))
    {
        std::cout << "#"
                  << ++count
                  << ":\t"
                  << queens_disp_cur
                  << std::endl;
    }    
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    print_all_queens_disposition(); 
}
1
Mechanical Poet
2 / 2 / 0
Регистрация: 26.10.2009
Сообщений: 9
26.11.2010, 00:08  [ТС] #7
Mr.X, спасибо. Но мне надо чтобы он находил одно единственное решение. Я начал писать код, но застрял. Может кто нибудь сможет помочь?
C++
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <stdlib.h>
#include <stdio.h>
 
int board [ 8 ][ 8 ];
struct NODE
{
        int cell;
        NODE *next, *prev;
};
 
NODE *first = NULL;
NODE *h = NULL;
 
void resetQ ( int i , int j )
{
    j=h->cell;
    if(h == first)
        first = NULL;
    NODE *t = h;
    h = h->prev;
    if(h)
        h->next = NULL;
    delete t;
    for ( int x = 0; x < 8; x++ )
    {
        --board [x][j];
        --board [i][x];
        int k;
        k = j - i + x;
        if ( k >= 0 && k<8 )
            --board [ x ][ k ];
        k = j+i-x;
        if ( k >= 0 && k < 8 )
            --board [ x ][ k ];
    }
    board [ i ][ j ] = 0;
}
 
void setQ ( int i, int j )
{
    if(first == NULL)
    {
        h = new NODE;
        h->prev = NULL;
        h->cell=j;
        h->next = NULL;
        first = h;
    }
    else
    {
        h->next = new NODE;
        h->next->prev = h;
        h=h->next;
        h->cell=j;
        h->next = NULL;
    }
 
    for ( int x = 0; x < 8; x++ )
    {
        ++board [ x ][ j ];
        ++board [ i ][ x ];
        int k;
        k = j - i + x;
        if ( k >= 0 && k < 8 )
            ++board [ x ][ k ];
        k = j + i - x;
        if ( k >= 0 && k < 8 )
            ++board [ x ][ k ];
    }
    board [ i ][ j ] = -1;
}
 
bool tryQ ( int i )
{
    bool result = false;
    bool w = false;
    for ( int i=0; i<8; )
    {
        for ( int j = 0; j < 8 ; j++ )
        {
            if ( board [ i ][ j ] == 0 )
            {
                setQ ( i, j );
                if ( i == 7 )
                result = true;
                else
                {
                    w = false;
                    for ( int g = 0; g < 8 ; g++ )
                        if ( board [ i+1][ g ] == 0 )
                            w=true;
                    if ( w != true )
                    {
                        resetQ ( i, j );
                    }
                    else 
                    {
                        i++;
                        break;
                    }
                }
            }
            if ( result )
                return true;
        }
    }
    return result;
}
 
int main ()
{
    for ( int i = 0; i < 8; i++ )
        for ( int j = 0; j < 8; j++ )
    board [ i ][ j ] = 0;
    tryQ ( 0 );
    for ( int i = 0; i < 8; i++ )
    {
        for ( int j = 0; j < 8; j++ )
        {
            if ( board [ i ][ j ] == -1 )
            printf ( "1 " );
            else 
            printf ( "0 " );
            
        }
        printf ( "\n" );
    }
 
    printf ( "\n" );
 
    for ( int i = 0; i < 8; i++ )
    {
        for ( int j = 0; j < 8; j++ )
        {
            printf ( "%d ", board [ i ][ j ] );          
        }
        printf ( "\n" );
    }
 
 
    system ( " Pause " );
}
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
26.11.2010, 23:41 #8
Цитата Сообщение от Mechanical Poet Посмотреть сообщение
Mr.X, спасибо. Но мне надо чтобы он находил одно единственное решение.
В моем коде это делает функция get_next_queens_disposition.

Добавлено через 4 часа 37 минут
Для доски произвольного размера:
C++
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
//////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string  T_str;
//////////////////////////////////////////////////////////////////////////////////////
const int  BOARD_DIM_MIN               = 1;
const int  BOARD_DIM_MAX               = 20;
char       queens_disp[BOARD_DIM_MAX]  = {'0'};
int        queens_disp_size            = BOARD_DIM_MIN;
//////////////////////////////////////////////////////////////////////////////////////
int  symb_to_int(char  symb)
{
    return (symb <= '9') 
           ? symb - '0'
           : symb - 'a' + 0xa;
}
//////////////////////////////////////////////////////////////////////////////////////
char  int_to_symb(int int_val)
{
    return (int_val <= 9)
           ? '0' + int_val
           : 'a' + int_val - 0xa;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  last_elem_is_correct()
{
    int  pos_last  = queens_disp_size - 1;
    int  diff_abs  = 0;
    for(int i = 0; i < pos_last; ++i)
    {
        int diff_abs = abs(symb_to_int(queens_disp[i]) - symb_to_int(queens_disp[pos_last]));
        if(!diff_abs
           || diff_abs == pos_last - i) return  false;
    }
    return  true;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  successfully_inc_last_elem(int  board_dim)
{    
    char&  last_elem = queens_disp[queens_disp_size - 1];
    for(;;)
    {
        last_elem = int_to_symb(symb_to_int(last_elem) + 1);      
 
        if(symb_to_int(last_elem) > board_dim)        
        {
            return  false;
        }
        if(last_elem_is_correct())
        {
            return  true;
        }
    }   
}
//////////////////////////////////////////////////////////////////////////////////////
bool  get_next_queens_disposition(int  board_dim)
{    
    for(;;)
    {
        if(!successfully_inc_last_elem(board_dim))
        {
            if(queens_disp_size == 1)
            {
                return  false;
            }
            else
            {                
                --queens_disp_size;                
            }
        }
        else
        {
            if(queens_disp_size == board_dim)
            {
                return true;
            }
            else
            {
                ++queens_disp_size; 
                queens_disp[queens_disp_size - 1] = '0';
            }
        }
    }   
}
//////////////////////////////////////////////////////////////////////////////////////
void  print_all_queens_disposition(int  board_dim)
{    
    int  count = 0; 
    while(get_next_queens_disposition(board_dim))
    {
        ++count;
        if(count == 1)
        {
            std::cout << "Расстановки на шахматной доске размерностью "
                      << board_dim 
                      << " стольких же ферзей, "
                      << std::endl
                      << "не бьющих друг друга:"
                      << std::endl;        
        }
        std::cout << "#"
                  << count
                  << ":\t"
                  << T_str(queens_disp, queens_disp + board_dim)
                  << std::endl;
    }
 
    if(!count)
    {
        std::cout << "Не существует расстановок на шахматной доске размерностью "
                  << board_dim 
                  << " стольких же ферзей, не бьющих друг друга:"
                  << std::endl;       
    }
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));    
 
    int  board_dim = 0;
    do
    {
        std::cout << "Введите размерность шахматной доски "
                  << BOARD_DIM_MIN
                  << " <= n <= "
                  << BOARD_DIM_MAX
                  << ": ";
 
        std::cin >> board_dim;        
    }while(board_dim < BOARD_DIM_MIN 
          || BOARD_DIM_MAX < board_dim);
 
    print_all_queens_disposition(board_dim);            
}
0
-=ЮрА=-
Заблокирован
Автор FAQ
04.05.2012, 19:26 #9
Учебный пример: задача о восьми ферзях
0
Kuzia domovenok
1951 / 1804 / 140
Регистрация: 25.03.2012
Сообщений: 6,245
Записей в блоге: 1
04.05.2012, 21:28 #10
Просили ж без рекурсии!!!
0
-=ЮрА=-
Заблокирован
Автор FAQ
04.05.2012, 22:24 #11
Kuzia domovenok, у тебя претензии???
Вначале темы автору нужен был рабочий код
Цитата Сообщение от Mechanical Poet Посмотреть сообщение
Сделал набросок, но работает как то криво.
, надо без рекурсии правим то что дано по ссылке. Чё за наезды млин?
0
Evg
05.05.2012, 19:58
  #12

Не по теме:

Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
надо без рекурсии правим то что дано по ссылке. Чё за наезды млин?
Удивительно, почему ты не выкатил исходники ядра линукса и не сказал, что после доработки напильником получится задача о 8 ферзях

0
-=ЮрА=-
05.05.2012, 20:49     О 8 ферзях(Без рекурсии)
  #13

Не по теме:

Цитата Сообщение от Evg Посмотреть сообщение
Удивительно, почему ты не выкатил исходники ядра линукса и не сказал, что после доработки напильником получится задача о 8 ферзях
- а что они есть в инете, дай ссылку сейчас моментом сделаю

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.05.2012, 20:49
Привет! Вот еще темы с ответами:

Разложение на простые множители без рекурсии - C++
Задача такая : Надо написать две функции get_all_divisorts и get_lowest_divisor. Функция main должна вызывать get_all_divisorts ,...

Нестандартная быстрая сортировка (без рекурсии) - C++
Помогите пожалуйста, нужно написать программу для одномерного массива, с помощью быстрой сотрировки без рекурсии. Если можно с...

Нахождение определителя матрицы n-го порядка без рекурсии - C++
Здравствуйте, мне на дом дали задачу на С++ написать программу которая находит определитель матрицы n го порядка, я довольно быстро её...

Написано рекрусивно. нужен код без рекурсии.! - C++
int per (int k) { int i; for(i=1;i&lt;=n;i++) { if (color==0) ...


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

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

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