Форум программистов, компьютерный форум CyberForum.ru

Миссионеры и людоеды - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.79
Djulbars
 Аватар для Djulbars
24 / 4 / 2
Регистрация: 19.08.2011
Сообщений: 62
12.09.2011, 08:32     Миссионеры и людоеды #1
Помогите разобраться в логической задаче.
Условие.
Миссионеры и людоеды.
Три миссионера и три людоеда находятся по одну сторону реки, через которую они хотят переправиться. В их распоряжении имеется лодка, которая может выдержать вес только двух человек. Кроме того, если в какой-то момент число людоедов станет больше числа миссионеров, миссионеры будут съедены независимо от того, на каком берегу реки это случится.
Нужно решить задачу рекурсивным методом
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.09.2011, 08:32     Миссионеры и людоеды
Посмотрите здесь:

Поиск в ширину (миссионеры и людоеды) на SWI-Prolog Prolog
Prolog "Миссионеры и людоеды", prolog 5.2

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Чистый
Автор FAQ
 Аватар для Чистый
2572 / 1379 / 70
Регистрация: 08.09.2011
Сообщений: 3,705
Записей в блоге: 1
12.09.2011, 10:30     Миссионеры и людоеды #2
если решение только логическое то как то вот так:
1. 2 людоеда переправляются на левый берег.
2. Возвращается один из людоедов.
В итоге: на правом берегу 2Л и 3М, на левом 1Л.
3. Посылаем на левый берег 2Л.
4. Возвращаем 1Л.
Итог: на правом берегу 1Л и 3М, на левом 2Л.
5. Пускаем 2М на левый берег.
6. Возвращаем 1Л и 1М.
Итог: На правом берегу 2Л и 2М, на левом 1Л и 1М
7. Посылаем на левый берег 2М.
8. Возвращаем на правый берег 1Л.
Итак: на правом берегу 3Л, на левом 3М.
9. Посылаем на левый берег 2Л.
10. Возвращаем назад 1Л.
11. Переправляем последних 2Л.
Байт
12.09.2011, 12:04
  #3

Не по теме:

См "Волк, коза и капуста"

easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
12.09.2011, 13:39     Миссионеры и людоеды #4
Цитата Сообщение от Байт Посмотреть сообщение
См "Волк, коза и капуста"
Тоже про это вспомнил, один момент смутил:

Цитата Сообщение от Djulbars Посмотреть сообщение
если в какой-то момент число людоедов станет больше числа миссионеров...
А что бы их просто попарно не перевозить? Всегда поровну будет... Или я опять чего-то не понял?
... А, ну да - лодку же надо как-то на другой берег возвращать! Ну тогда по алгоритму из второго поста, там вроде никого не съели...
RaiaNKnight
 Аватар для RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 458
Записей в блоге: 1
12.09.2011, 13:41     Миссионеры и людоеды #5
Действительно, почему нельзя перевозить парами? Может быть тогда в условии следовало бы указать, что людоед с миссионером в лодке перевозиться не может?
Чистый
Автор FAQ
 Аватар для Чистый
2572 / 1379 / 70
Регистрация: 08.09.2011
Сообщений: 3,705
Записей в блоге: 1
12.09.2011, 14:19     Миссионеры и людоеды #6
если мне не изменяет память лодка не должна пустовать при перевозках...
Mr.X
Эксперт С++
 Аватар для Mr.X
2803 / 1579 / 247
Регистрация: 03.05.2010
Сообщений: 3,670
13.09.2011, 09:22     Миссионеры и людоеды #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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
/////////////////////////////////////////////////////////////////////////////////////////
// Миссионеры и людоеды.
// Три миссионера и три людоеда находятся по одну сторону реки, через которую они хотят 
// переправиться. В их распоряжении имеется лодка, которая может выдержать вес только 
// двух человек. Кроме того, если в какой-то момент число людоедов станет больше числа 
// миссионеров, миссионеры будут съедены независимо от того, на каком берегу реки это 
// случится.
// Нужно решить задачу рекурсивным методом
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
struct T_missionaries_and_cannibals_state
{
    //-----------------------------------------------------------------------------------
    struct  T_go_arg
    {
        bool  forward_;
        int   missionaries_;
        int   cannibals_; 
        //-------------------------------------------------------------------------------
        T_go_arg
            (
                bool  forward,
                int   missionaries,
                int   cannibals
            )
            : forward_       (forward),
              missionaries_  (missionaries),
              cannibals_     (cannibals)
        {}
    };
    //-----------------------------------------------------------------------------------
    typedef std::vector<T_go_arg>  T_go_args;
    //-----------------------------------------------------------------------------------
    int   missionaries_here_;
    int   cannibals_here_;
    int   missionaries_there_;
    int   cannibals_there_;
    bool  boat_is_here_;    
    //-----------------------------------------------------------------------------------
    T_missionaries_and_cannibals_state
        (
            int   missionaries_here,
            int   cannibals_here,
            int   missionaries_there,
            int   cannibals_there,
            bool  boat_is_here
        )
        : missionaries_here_   (missionaries_here),
          cannibals_here_      (cannibals_here),
          missionaries_there_  (missionaries_there),
          cannibals_there_     (cannibals_there),
          boat_is_here_        (boat_is_here)
    {}
    //-----------------------------------------------------------------------------------
    bool  operator== (const T_missionaries_and_cannibals_state&  state) const
    {
        return    cannibals_here_      == state.cannibals_here_
               && cannibals_there_     == state.cannibals_there_
               && missionaries_here_   == state.missionaries_here_
               && missionaries_there_  == state.missionaries_there_
               && boat_is_here_        == state.boat_is_here_;
    }
    //-----------------------------------------------------------------------------------
    operator bool() const
    {
        return    cannibals_here_       >= 0               
               && cannibals_there_      >= 0
               && (missionaries_here_   == 0 || missionaries_here_   >= cannibals_here_ )
               && (missionaries_there_  == 0 || missionaries_there_  >= cannibals_there_);
    }
    //-----------------------------------------------------------------------------------
    bool  go(const T_go_arg&  go_arg)
    {
        int  missionaries  = go_arg.missionaries_;
        int  cannibals     = go_arg.cannibals_;
        if(go_arg.forward_)
        { 
            if(!boat_is_here_) return  false;    
        }
        else
        {
            if(boat_is_here_) return  false;
            missionaries  *= -1;
            cannibals     *= -1;
        }
        boat_is_here_        = !boat_is_here_;
        missionaries_here_   -= missionaries;
        missionaries_there_  += missionaries;
 
        cannibals_here_      -= cannibals;
        cannibals_there_     += cannibals;
        return  *this;
    }
    //-----------------------------------------------------------------------------------    
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::vector<T_missionaries_and_cannibals_state>  T_history;
/////////////////////////////////////////////////////////////////////////////////////////
void  go_missionaries_and_cannibals
    (
        T_history                                             history,
        const T_missionaries_and_cannibals_state&             finish_state,
        const T_missionaries_and_cannibals_state::T_go_args&  go_args
    )
{
    if(history.back() == finish_state)
    {
        std::cout << "м.зд"
                  << "\t"
                  << "л.зд"
                  << "\t"
                  << "м.там"
                  << "\t"
                  << "л.там"
                  << std::endl;
                  
        for(T_history::const_iterator  state_it = history.begin();
            state_it != history.end(); ++state_it)
        {
            std::cout << state_it->missionaries_here_
                      << "\t"
                      << state_it->cannibals_here_
                      << "\t"
                      << state_it->missionaries_there_
                      << "\t"
                      << state_it->cannibals_there_
                      << std::endl
                      << std::endl;
        }
        return;
    }
            
    if(
        history.size() > 1
        &&
        std::find
            (
                history.rbegin() + 1,
                history.rend(),
                history.back()
            ) 
            != history.rend()
      )
    {
        return;
    }
 
    for(T_missionaries_and_cannibals_state::T_go_args::const_iterator  arg_it = go_args.begin();
        arg_it != go_args.end(); ++arg_it)
    {
        T_missionaries_and_cannibals_state  next_state = history.back();
        if( !next_state.go(*arg_it) ) continue;
        T_history  new_history = history;    
        new_history.push_back(next_state);
        go_missionaries_and_cannibals
            (
                new_history, 
                finish_state, 
                go_args
            );    
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    T_missionaries_and_cannibals_state::T_go_args  go_args;
    for(int  forward = 0; forward <= 1; ++forward)
    {
        for(int  missionaries = 0; missionaries <= 2; ++missionaries)
        {
            for(int  cannibals = 0; cannibals <= 2; ++cannibals)
            {
                int  sum = missionaries + cannibals;
                if(   sum < 1
                   || sum > 2 )
                {
                    continue;
                }
                go_args.push_back
                    ( 
                        T_missionaries_and_cannibals_state::T_go_arg
                            (
                                forward == 0, 
                                missionaries, 
                                cannibals
                            ) 
                    );
            }
        }
    }
 
    T_missionaries_and_cannibals_state  start_state   (3, 3, 0, 0, true  );
    T_missionaries_and_cannibals_state  finish_state  (0, 0, 3, 3, false );
    T_history                           history       (1, start_state);
    go_missionaries_and_cannibals
        (
            history, 
            finish_state, 
            go_args
        );    
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
13.09.2011, 09:42     Миссионеры и людоеды #8
Цитата Сообщение от RaiaNKnight Посмотреть сообщение
Действительно, почему нельзя перевозить парами?

Не по теме:

потому что лодка не радиоуправляемая, хотя, кто знает

ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
13.09.2011, 14:44     Миссионеры и людоеды #9
Цитата Сообщение от RaiaNKnight Посмотреть сообщение
Действительно, почему нельзя перевозить парами? Может быть тогда в условии следовало бы указать, что людоед с миссионером в лодке перевозиться не может?
Перевозчика нет. Людоеды и миссионеры должны сами себя перевозить туда и возвращать лодку обратно.
При этом на обоих берегах должно выполняться условие, что миссионеров не меньше, чем людоедов.

Программа должна выводить полный ход решения. Это первая лаба у нас на ИИ - полный перебор при решении интеллектуальных задач.
Gepar
13.09.2011, 19:06
  #10

Не по теме:

Цитата Сообщение от Чистый Посмотреть сообщение
В итоге: на правом берегу 2Л и 3М, на левом 1Л.
Вот тут по идеи миссионеры должны съесть людоедов так как миссионеров становится больше

Чистый
13.09.2011, 19:50
  #11

Не по теме:

После этого 2Л должны перейти на сторону 3М и принять их веру...

Djulbars
 Аватар для Djulbars
24 / 4 / 2
Регистрация: 19.08.2011
Сообщений: 62
13.09.2011, 19:51  [ТС]     Миссионеры и людоеды #12
Цитата Сообщение от Чистый Посмотреть сообщение

Не по теме:

После этого 2Л должны перейти на сторону 3М и принять их веру...

Не по теме:

Точно

Yandex
Объявления
13.09.2011, 19:51     Миссионеры и людоеды
Ответ Создать тему
Опции темы

Текущее время: 03:14. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru