Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.70/46: Рейтинг темы: голосов - 46, средняя оценка - 4.70
_nobody_
8 / 8 / 0
Регистрация: 18.04.2009
Сообщений: 115
1

Расставлены три белые и три черные шашки; нужно поменять местами белые и черные

23.10.2010, 13:26. Просмотров 8623. Ответов 8
Метки нет (Все метки)

Имеется линейная доска из семи клеток, на которых расставлены три
белые и три черные шашки. Можно двигать шашки на пустое место и перепрыгивать через одну на пустое место. В обратную сторону
двигать шашки не разрешается. Цель: поменять местами белые и
черные.
тоесть
--------------------------
БББ ЧЧЧ -> ЧЧЧ БББ
--------------------------
подскажите алгоритм решения
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.10.2010, 13:26
Ответы с готовыми решениями:

Увеличить минимальный элемент в три раза и поменять местами с последним
В заданном массиве M(5) действительных чисел увеличить минимальный элемент в три раза и поменять...

Поменять местами черные и белые шарики (шашки)
*Имеется N лунок, в которых расставлены L черных и S белых шаров. Поменять местами черные и белые...

белые кат. черные... фиалетавые ? о.О
Вот хочу раз и навсегда понять истину названий "белые каталоги" и "черные каталоги". Я конечно...

Вселенная, черные и белые дыры
Вселенная - порождение Черной дыры, кстати эта теория мне больше всего нравится, она очень схожа с...

Белые и черные шары в ящиках
в первом ящике 6 белых 9 черных шаров. во втором 9 белых 5 черных. из каждого ящика взяли по шару....

8
valeriikozlov
Эксперт С++
4695 / 2520 / 752
Регистрация: 18.08.2009
Сообщений: 4,550
23.10.2010, 18:48 2
Вариант:
БББ ЧЧЧ
БББЧ ЧЧ
ББ ЧБЧЧ
Б БЧБЧЧ
БЧБ БЧЧ
БЧБЧБ Ч
БЧБЧБЧ
БЧБЧ ЧБ
БЧ ЧБЧБ
ЧБЧБЧБ
Ч БЧБЧБ
ЧЧБ БЧБ
ЧЧБЧБ Б
ЧЧБЧ ББ
ЧЧ ЧБББ
ЧЧЧ БББ
0
_nobody_
8 / 8 / 0
Регистрация: 18.04.2009
Сообщений: 115
23.10.2010, 20:29  [ТС] 3
конечно спасибо.... но я хотел алгоритм....
чтобы его закодировать и чтобы прога сама нашла такое решения....
0
valeriikozlov
Эксперт С++
4695 / 2520 / 752
Регистрация: 18.08.2009
Сообщений: 4,550
24.10.2010, 00:14 4
ну если алгоритм, то я бы сделал так:
объявил бы глобально массив типа int размером [16][7].
Допустим белые шашки 1, черные 2, пустая клетка 0.
В первую строку массива написал 1110222
И дальше рекурсивная функция, должна выглядеть так: (индексацию начинаю с нуля в примере)
void rec(int a, int b)// здесь в параметрах функции передаю следующее: a - индекс пустой клетки, b - номер текущей строки
{
for(int i=0; i<7; i++)// все данные из предыдущей строчки копируем в следущую
mas[b+1][i]=mas[b][i];
b++;
if(a>0 && а-1==1 )
{mas[b][a]=1; mas[b][a-1]=0; rec(a-1, b);
// теперь возвращаем все перемещения обратно
mas[b][a]=0; mas[b][a-1]=1;
}
if(a>1 && а-2==1 )
{mas[b][a]=1; mas[b][a-2]=0; rec(a-2, b);
// теперь возвращаем все перемещения обратно
mas[b][a]=0; mas[b][a-2]=1;
}
if(a<6 && а+1==2 )
{mas[b][a]=2; mas[b][a+1]=0; rec(a+1, b);
// теперь возвращаем все перемещения обратно
mas[b][a]=0; mas[b][a+1]=2;
}
if(a<5 && а+2==2 )
{mas[b][a]=2; mas[b][a+2]=0; rec(a+2, b);
// теперь возвращаем все перемещения обратно
mas[b][a]=0; mas[b][a+2]=2;
}
b--;
}
Вам оставляю додумать как остановить в нужный момент рекурсию (по идее если рекурсия достигнет заполнения последней 15-ой строки (индексацию веду с нуля) и одного в ней любого передвижения, то в ней как раз и будет нужная нам конечная комбинация). После этого в строках массива и будут хранится все нужные передвижения шашек.
1
24.10.2010, 00:14
_nobody_
8 / 8 / 0
Регистрация: 18.04.2009
Сообщений: 115
24.10.2010, 01:49  [ТС] 5
valeriikozlov,
а почему имено 16?
в вашем варианте действительно 16 строк.. а как вы узнали... или как програма до этого додумалась?
0
valeriikozlov
Эксперт С++
4695 / 2520 / 752
Регистрация: 18.08.2009
Сообщений: 4,550
24.10.2010, 03:08 6
программа до этого не додумалась, вариант полной замены черных на белые всегда будет в 16 строк, не больше и не меньше. Можете сделать массив большим чем 16 строк, тогда проверяйте условие полоной замены на каждой строке. Посмотрите, что получится все равно 16 строк.
1
Хохол
Эксперт С++
475 / 443 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
24.10.2010, 10:24 7
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
#include <fstream>
#include <queue>
 
using namespace std;
 
ofstream cout("output.txt");
 
const int n = 3;
const int m = 2*n+1;
const char s[3] = {'_', 'b', 'w'};
 
int empty = 0, black = 1, white = 2;
const int size = 1 << (m*2);
int d[size];
int from[size];
queue<int> q;
int cur = 0, start = 0, finish = 0;
 
void set(int &cur, int pos, int val)
{
    pos <<= 1;
    cur &= ~((1 << pos)|(1 << (pos+1)));
    cur |= val << pos;
}
 
int get(int cur, int pos)
{
    pos <<= 1;
    return (cur >> pos) & 3;
}
 
void print(int cur)
{
    for(int i = 0; i < m; i++)
    {
        cout << s[cur&3];
        cur >>= 2;
    }
}
 
void tryy(int next)
{
    if(d[next] == -1)
    {
        q.push(next);
        d[next] = d[cur]+1;
        from[next] = cur;
    }
}
 
int main()
{
    for(int i = 0; i < n; i++)
    {
        set(start,i,black);
        set(finish,i,white);
    }
    //set(start,n,empty);
    //set(finish,n,empty);
    for(int i = n+1; i < m; i++)
    {
        set(start,i,white);
        set(finish,i,black);
    }
 
    memset(d,-1,sizeof(d));
 
    d[start] = 0;
    from[start] = -1;
    q.push(start);
 
    while(true)
    {
        cur = q.front();
        q.pop();
        if(cur == finish)
        {
            while(cur != -1)
            {
                print(cur);
                cout << endl;
                cur = from[cur];
            }
            break;
        }
        for(int i = 0; i < m-1; i++)
        {
            int t = get(cur,i);
            if(t != empty && get(cur,i+1) == empty)
            {
                int next = cur;
                set(next,i,empty);
                set(next,i+1,t);
                tryy(next);
            }
        }
 
        for(int i = 1; i < m; i++)
        {
            int t = get(cur,i);
            if(t != empty && get(cur,i-1) == empty)
            {
                int next = cur;
                set(next,i,empty);
                set(next,i-1,t);
                tryy(next);
            }
        }
 
        for(int i = 0; i < m-2; i++)
        {
            int t = get(cur,i);
            if(t != empty && get(cur,i+1) != empty && get(cur,i+2) == empty)
            {
                int next = cur;
                set(next,i,empty);
                set(next,i+2,t);
                tryy(next);
            }
        }
 
        for(int i = 2; i < m; i++)
        {
            int t = get(cur,i);
            if(t != empty && get(cur,i-1) != empty && get(cur,i-2) == empty)
            {
                int next = cur;
                set(next,i,empty);
                set(next,i-2,t);
                tryy(next);
            }
        }
    }
}
output.txt
Код
www_bbb
wwwb_bb
ww_bwbb
w_wbwbb
wbw_wbb
wbwbw_b
wbwbwb_
wbwb_bw
wb_bwbw
_bwbwbw
b_wbwbw
bbw_wbw
bbwbw_w
bbwb_ww
bb_bwww
bbb_www
1
_nobody_
8 / 8 / 0
Регистрация: 18.04.2009
Сообщений: 115
24.10.2010, 16:20  [ТС] 8
Хохол,
хочу похвалить тебя, класно пишеш...
почти ничего разобрать не могу....
с побитовыми ф-ями не сильно дружуюю(

Добавлено через 53 минуты
если не сложно обясните что делают следущие строки
C++
1
2
3
4
5
6
7
8
9
10
void set(int &cur, int pos, int val)
{
        pos <<= 1;// это как я понимаю умножение на 2
        cur &= ~((1 << pos)|(1 << (pos+1)));//  вообще не понимаю что оно делает
        cur |= val << pos;\\ это типа КАР + (ВАЛ умножается на ПОЗ ) так?
}
и я не понимаю что эта ф-я делает????
и обясните пожалуйста еще следующие ф-ии 
void tryy(int next)
int get(int cur, int pos)
Добавлено через 1 час 28 минут
и еще..... что такое масивы Д и ФРОМ ???
0
Mr.X
Эксперт С++
3192 / 1719 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
25.10.2010, 14:54 9
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
//////////////////////////////////////////////////////////////////////////////////////
//Имеется линейная доска из семи клеток, на которых расставлены три белые 
//и три черные шашки. Можно двигать шашки на пустое место и перепрыгивать 
//через одну на пустое место. В обратную сторону двигать шашки не разрешается. 
//Цель: поменять местами белые и черные.
//то есть
//--------------------------
//  БББ ЧЧЧ -> ЧЧЧ БББ
//--------------------------
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string           T_board;
typedef std::vector<T_board>  T_moves;
//////////////////////////////////////////////////////////////////////////////////////
void  go
    (
        T_board         board_start,
        T_moves         moves,
        const T_board&  board_finish,
        int&            variants_counter
    )
{
    if(board_start == board_finish)
    {
        std::copy(moves.begin(), moves.end(), 
                  std::ostream_iterator<T_board>(std::cout, "\n"));
 
        std::cout << std::endl
                  << std::endl;
        ++variants_counter;
    }
    else
    {        
        int empty_ind   = board_start.find(' ');
        int ind_start   = std::max(0,                                        empty_ind - 2);
        int ind_finish  = std::min(static_cast<int>(board_start.size() - 1), empty_ind + 2);
 
        for(int chip_ind = ind_start; chip_ind <= ind_finish; ++chip_ind)
        {
            if(chip_ind != empty_ind
               && board_start[chip_ind] == (chip_ind < empty_ind ? 'Б' : 'Ч'))
            {
                T_board  board_start_new(board_start);                
                std::swap(board_start_new[chip_ind], board_start_new[empty_ind]);
                T_moves  moves_new(moves);
                moves_new.push_back(board_start_new);
                go(board_start_new, moves_new, board_finish, variants_counter);                
            }            
        }
    }
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    T_board  board_start("БББ ЧЧЧ");
    T_moves  moves(1, board_start);
    T_board  board_finish("ЧЧЧ БББ");
    int  variants_counter = 0;
    go(board_start, moves, board_finish, variants_counter);
    std::cout << "Всего "
              << variants_counter
              << " вариантов решения."
              << std::endl;
}
1
25.10.2010, 14:54
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.10.2010, 14:54

В двух урнах белые и черные шары
Need your HELP brothers and sisters!!! Дали контрольную не могу решить. Помогите пожалуйста.Вот...

В урне находятся белые и черные шары
В урне находятся белые и черные шары.Известно , что белые шары составляют либо 50% , либо 40%...

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


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

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

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