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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Вызов из разных потоков функции чтения из файла, dll http://www.cyberforum.ru/cpp-beginners/thread557504.html
Доброго времени суток. Помогите пожалуйста написать программу, вот задание: Вызов из разных потоков функции чтения из файла. Функция находится в dll динамическое подключение . Функция чтения:...
C++ Задача на двумерный массив Найти максимальный элемент матрицы http://www.cyberforum.ru/cpp-beginners/thread557503.html
C++ работа с файлами
1. Написать программу, которая создает файл и записывает в него 5 введенных пользователем целых чисел, при чем каждое число должно находиться в отдельной строке.(без использования файловых потоков)...
Считывание строки из файла. C++
Появилась проблема. Строка из файла считывается, но не реагирует на пробелы. И не находит конец строки. #include <fstream> #include<iostream> using namespace std; int main(){ char s; ifstream...
C++ Даны целые числа a1, a2, a3. Получить целочисленную матрицу [ by]i, j= 1,2,3 для которой bij= ai - 3aj http://www.cyberforum.ru/cpp-beginners/thread557490.html
Даны целые числа a1, a2, a3. Получить целочисленную матрицу i, j= 1,2,3 для которой bij= ai - 3aj
C++ Выяснить можно ли с поля (k,l) одним ходом ферьзя попасть на поле(m,n). Если нет, то выяснить, как это можно сделать за два хода Поле шахмотной доски определяеся парой натуральных чисел, каждая из которых не превосходит восьми: первое число номер вертикали (при счете слева на права), второе-номер (при счете снизу вверх). даны... подробнее

Показать сообщение отдельно
talis
791 / 543 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
24.04.2012, 23:04
Вот такое вот решение (перебором):

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). А жаль - изначально с этой задумкой делалось



Вообще это похоже на задачу на динамическое программирование. Интересно было бы увидеть умное решение :-)
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru