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

Логическая задача на переливание жидкостей - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.79
Rumise
1 / 1 / 0
Регистрация: 24.04.2012
Сообщений: 13
24.04.2012, 19:41     Логическая задача на переливание жидкостей #1
Даны 3 стакана: 1 - й вмещает 7 литров, 2-й вмещает 5 литров, 3-й вмещает 12 литров. Первые 2 стакана пусты, в третьем 12 литров воды. Воду можно переливать из одного стакана в другой до опустошения либо заполнения одного из стаканов. Необходимо, чтобы в 1 стакане оказалось 6 литров воды. Вручную получается это сделать за 10 шагов. Я пытаюсь написать программу, которая сама будет переливать жидкость и в конце концов найдет правильный вариант. Но возникли сложности с циклами, уже целый день ломаю голову. Со всеми условиями, которые в коде, циклы зависают, и не могу понять почему.


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
#include "stdafx.h"
#include <windows.h>
#include <iostream>
#include <string.h>
#include "math.h"
#include "time.h"
#include <stdlib.h>
 
using namespace std;
 
 
void main()
{
    srand ((unsigned)time(NULL));
    int S[3] = {0, 0, 12};// содержит данные о заполненности каждого из стаканов
    const int S1[3] = {7, 5, 12}; // содержит максимальную емкость каждого из стаканов
    int x = 0, y = 0, count = 0;
    int x1 = 4, y1 = 4;
 
    
    while (S[0] != 6)
    {   
        do
        {
            x = rand() %3;// случайно выбирает из какого стакана переливать воду
        }
        while (S[x] == 0 || x == y1 );// проверяет не пуст ли стакан из которого переливаем воду
 
        do
        {               
            y = rand() %3;  // случайно выбирает в какой стакан переливать воду
        }   
        while ((y == x) || (S[y] == S1[y]) || y == x1); // проверяет, чтобы мы не переливали жидкость в тот-же стакан и проверяет не полон-ли стакан, в который мы наливаем жидкость
        
        cout << "x = " << x << " y = " << y << "\n";
        
 
    
        while ((S[x] != 0) && (S[y] < S1[y]))// переливает жидкость пока один из стаканов не опустошится или не заполнится
        {
            S[x]--;
            S[y]++;
        }
        x1 = x;// с помощью этих значений я пытаюсь избежать случаев, когда мы переливаем жидкость в тех-же стаканах,что и в прошлый раз, но в обратную сторону, чтобы сделать алгоритм умнее.
        y1 = y; 
        
        count++;
        cout << "Step № " << count<< "\n";
        cout <<"First glass = " << S[0]<<"\t"<<"Second glass = " << S[1]<<"\t"<<"Third glass = " << S[2]<<"\n";
    }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.04.2012, 19:41     Логическая задача на переливание жидкостей
Посмотрите здесь:

Логическая C++
логическая C++
C++ Логическая задачка
C++ логическая ошибка!!
Логическая игра C++
C++ Логическая задача
C++ Логическая интерпретация конструкции
Логическая ошибка в коде (задача на рекурсию) C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
24.04.2012, 23:04     Логическая задача на переливание жидкостей #2
Вот такое вот решение (перебором):

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
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
#include <iostream>
#include <iomanip>
#include <vector>
#include <array>
#include <set>
 
#include <limits.h>
 
#include <cstdio>
#include <cstdlib>
#include <ctime>
 
// Контейнер
 
struct container_t
{
    size_t volume, occupancy;
 
    container_t( ) :
        volume( 0 ), occupancy( 0 )
    {
    };
 
    container_t( const container_t &other ) :
        volume( other.volume ), occupancy( other.occupancy )
    {
    };
 
    container_t( size_t _volume )
    :
        volume( _volume ), occupancy( _volume )
    {
    };
 
    container_t( size_t _volume, size_t _occupancy )
    :
        volume( _volume ), occupancy( _occupancy )
    {
    };
 
    container_t & operator= ( const container_t &other )
    {
        volume = other.volume;
        occupancy = other.occupancy;
        return *this;
    }
 
    container_t & operator= ( size_t _occupancy )
    {
        occupancy = _occupancy > volume ? volume : _occupancy;
        return *this;
    }
 
    container_t & operator<< ( container_t &right )
    {
        size_t free_space = volume - occupancy;
        size_t transfer = free_space < right.occupancy ? free_space : right.occupancy;
 
        occupancy += transfer;
        right.occupancy -= transfer;
 
        return *this;
    }
 
};
 
 
// Операция: откуда и куда переливаем
 
struct operation_t
{
    size_t from, to;
 
    operation_t() : from( 0 ), to( 0 )
    {
    };
 
    operation_t( const operation_t &other ) :
        from( other.from ), to( other.to )
    {
    };
 
    operation_t( size_t _from, size_t _to ) :
        from( _from ), to( _to )
    {
    };
};
 
std::ostream & operator<< ( std::ostream & os, const operation_t &op )
{
    os << op.from << " -> " << op.to;
    return os;
}
 
// Решение: последовательность операций
 
struct solution_t
{
    typedef std::vector< operation_t > operation_history_t;
 
    operation_history_t operation_history; // история операций
 
    solution_t() :
        operation_history()
    {
    };
 
    solution_t( const solution_t &other ) :
       operation_history( other.operation_history )
    {
    };
};
 
bool operator< ( const solution_t &left, const solution_t &right )
{
    return left.operation_history.size() < right.operation_history.size();
}
 
std::ostream & operator<< ( std::ostream &os, const solution_t &solution )
{
    for( auto &op : solution.operation_history )
        os << op << "\n";
 
    return os;
}
 
// Набор решений
 
struct solutions_set_t
{
    typedef std::set< solution_t > solutions_t;
 
    solutions_t solutions; // решения
 
    solutions_set_t() :
        solutions()
    {
    };
 
    solutions_set_t( const solutions_set_t &other ) :
       solutions( other.solutions )
    {
    };
};
 
 
//
// Функция поиска решений
//
 
 
void search_for_solutions( solutions_set_t &solutions_set, size_t max_tries, size_t max_operations )
{
    const size_t containers_count = 3;
 
    typedef const std::array <size_t, containers_count> values_set_t;
    values_set_t default_values =
        {
            0, 0, 12
        };
 
    typedef std::array <container_t, containers_count> containers_set_t;
    containers_set_t containers =
        {
            7, 5, 12
        };
 
 
    while( max_tries-- )
    {
        std::copy( default_values.begin(), default_values.end(), containers.begin() ) ;
 
        solution_t solution;
 
        do
        {
            size_t dst, src;
 
            do
                src = rand() % containers_count;
            while( containers[ src ].occupancy == 0 );
 
            do
                dst = rand() % containers_count;
            while( src == dst || containers[ dst ].occupancy == containers[ dst ].volume );
 
            containers[ dst ] << containers[ src ];
 
            if( src == dst )
               std::cout << "src == dst\n";
 
            solution.operation_history.push_back( operation_t( src, dst ) );
        }
        while( solution.operation_history.size() < max_operations &&
              ( solutions_set.solutions.size() == 0 || solution < *( solutions_set.solutions.begin() ) )
               && containers[ 0 ].occupancy != 6 );
 
        if( containers[ 0 ].occupancy == 6 )
            solutions_set.solutions.insert( solution );
 
        if( !(max_tries % 10000) )
        {
            std::cout << "\rSearching... " << solutions_set.solutions.size() << " solutions found";
 
            if( solutions_set.solutions.size() )
                std::cout << "; min " << std::setw( 4 ) << solutions_set.solutions.begin()->operation_history.size() << " operations";
 
            std::cout << '\t' <<  std::setw( 10 ) << max_tries << " tries left";
 
            std::cout.flush();
        }
    }
 
    std::cout << "\r                                                                                                 \r";
}
 
int main( )
{
    srand( time( 0 ) );
 
    solutions_set_t solutions_set;
 
    //search_for_solutions( solutions_set, UINT_MAX, 100 );
    search_for_solutions( solutions_set, 6000000, 100 );
 
    std::cout << "Found " << solutions_set.solutions.size() << " solutions\nThe shortest is "
              << solutions_set.solutions.begin()->operation_history.size() << " operations:\n"
              << *solutions_set.solutions.begin();
 
 
    std::string input;
    std::cout << "Enter solution's rating to view it (0 for the shortest), or \"quit\" to quit.\n";
 
    while( std::cout << "\n> ", std::cin >> input && input != "quit" )
    {
        size_t id;
 
        if( sscanf( input.c_str(), "%u", &id ) && id < solutions_set.solutions.size() )
        {
            auto it = solutions_set.solutions.begin();
 
            while( id-- ) it++;
 
            std::cout << *it;
        }
    }
 
    return 0;
}
Решение менее чем за десять шагов не находил.

Не по теме:

Была мысль распараллелить, но, к сожалению, мой g++ (mingw gcc 4.6.1) ещё не поддерживает std::mutex (C++11). А жаль - изначально с этой задумкой делалось



Вообще это похоже на задачу на динамическое программирование. Интересно было бы увидеть умное решение :-)
Rumise
1 / 1 / 0
Регистрация: 24.04.2012
Сообщений: 13
02.05.2012, 18:23  [ТС]     Логическая задача на переливание жидкостей #3
Talis, спасибо за помощь
А еще есть варианты решений?
Yandex
Объявления
02.05.2012, 18:23     Логическая задача на переливание жидкостей
Ответ Создать тему
Опции темы

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