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

Исполнитель Водолей - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.70
Hi4ko
74 / 74 / 4
Регистрация: 21.10.2010
Сообщений: 376
25.01.2011, 01:45     Исполнитель Водолей #1
У исполнителя “Водолей” есть два сосуда, первый объемом A литров, второй объемом B литров, а также кран с водой. Водолей может выполнять следующие операции:

1. Наполнить сосуд A (обозначается >A).
2. Наполнить сосуд B (обозначается >B).
3. Вылить воду из сосуда A (обозначается A>).
4. Вылить воду из сосуда B (обозначается B>).
5. Перелить воду из сосуда A в сосуд B (обозначается как A>B).
6. Перелить воду из сосуда B в сосуд A (обозначается как B>A).

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

Программа получает на вход три натуральных числа A, B, N, не превосходящих 104 Вам необходимо вывести алгоритм действий Водолея, который позволяет получить в точности N литров в одном из сосудов, если же такого алгоритма не существует, то программа должна вывести текст Impossible.

Количество операций в алгоритме не должно превышать 105. Гарантируется, что если задача имеет решение, то есть решение, которое содержит не более, чем 105 операций.
Написал свой код:
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
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int A,B,N,x=0,y=0,z;
cin>>A>>B>>N;
z=2*A-B;
if(z>0)
{
z=2*A-B;
}
else
{
z=B-2*A;
}
if((A<N)&&(B<N))
{
cout<<"Impossible"<<endl;
}
else
{
if(A<B)
{
if((N%z==0)||(z%N==0))//проверка возможности действия
{
if(N==2*A-B)//1 случай
{
y=A;
x=0;
do
{
x=x+y;
if(x<B)
{
y=0;
}
else
{
y=x-B;
x=B;
}
cout<<">A"<<endl;
cout<<"A>B"<<endl;
}while((x!=N)||(y!=N));
}
else//2 случай
{
x=B; cout<<">B"<<endl;
y=0;
{
    do{
    y=A;
    if(x>A)
    {
    x=x-A;
    cout<<"B>A"<<endl;
    cout<<"A>"<<endl;
    if((x-A)==N)
    {
    cout<<">B"<<endl;
    cout<<"B>A"<<endl;
    break;}}
    else
    {
    A=x;
    x=B;
    }}while((x!=N)||(y!=N));}}}
else
{
cout<<"Impossible"<<endl;
}}
else
{
if(A>B)
{
if((N%z==0)||(z%N==0))//проверка возможности действия
{
if(N==2*B-A)//1 случай
{
y=B;
x=0;
do
{
x=x+y;
if(y<A)
{
x=x+y;
y=0;
}
else
{
y=x-A;
x=A;
}
cout<<">B"<<endl;
cout<<"B>A"<<endl;
}while((x!=N)||(y!=N));
}
else//2 случай
{
x=A; cout<<">A"<<endl;
y=0;
{
    do{
    y=B;
    if(x>B)
    {
    x=x-B;
    cout<<"A>B"<<endl;
    cout<<"B>"<<endl;
    if((x-B)==N)
    {
    cout<<">A"<<endl;
    cout<<"A>B"<<endl;
    break;}}
    else
    {
    B=x;
    x=A;
    }}while((x!=N)||(y!=N));}}}
else
{
cout<<"Impossible"<<endl;
}}
else
{
cout<<"Impossible"<<endl;
}}}}
Почему-то когда ввожу данные, цикл не прекращается. Помогите, пожалуйста, в чём ошибка
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.01.2011, 01:45     Исполнитель Водолей
Посмотрите здесь:

Кто исполнитель
Исполнитель водолей Turbo Pascal
C++ Задача "Исполнитель"
C++ Задача "Водолей"
Исполнитель Робот
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
rrrFer
Заблокирован
25.01.2011, 10:59     Исполнитель Водолей #2
Hi4ko, открою секрет почему на другие темы отвечают, а на твою - нет. Когда я вижу
C++
1
}}}}
появляется непреодолимое желание покинуть тему.
ЗЫ. если хочешь чтобы помогли - не издевайся над форумчанами, форматируй код нормально.
Начал смотреть код, вижу:
C++
1
2
3
y=0;
{
        do{
зачем первая фигурная скобка?(после y=0

Добавлено через 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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <cmath>
using namespace std;
int main(){
    int A,B,N,x=0,y=0,z;
    cin>>A>>B>>N;
    z=2*A-B;
    if(z>0)
        z=2*A-B;
    else
        z=B-2*A;
    if((A<N)&&(B<N))
        cout<<"Impossible"<<endl;
    else{
        if(A<B){
            if((N%z==0)||(z%N==0)){//проверка возможности действия
                if(N==2*A-B){//1 случай
                    y=A;
                    x=0;
                    do{
                        x=x+y;
                        if(x<B)
                            y=0;
                        else{
                            y=x-B;
                            x=B;
                        }
                        cout<<">A"<<endl;
                        cout<<"A>B"<<endl;
                    }while((x!=N)||(y!=N));
                }
                else{//2 случай
                    x=B; cout<<">B"<<endl;
                    y=0;
                    do{
                        y=A;
                        if(x>A){
                            x=x-A;
                            cout<<"B>A"<<endl;
                            cout<<"A>"<<endl;
                            if((x-A)==N){
                                cout<<">B"<<endl;
                                cout<<"B>A"<<endl;
                                break;
                            }
                        }
                        else{
                            A=x;
                            x=B;
                        }
                    }while((x!=N)||(y!=N));
                }
            }
            else
                cout<<"Impossible"<<endl;
        }
        else{
            if(A>B){
                if((N%z==0)||(z%N==0)){//проверка возможности действия
                    if(N==2*B-A){//1 случай
                        y=B;
                        x=0;
                        do{
                            x=x+y;
                            if(y<A){
                                x=x+y;
                                y=0;
                            }
                            else{
                                y=x-A;
                                x=A;
                            }
                            cout<<">B"<<endl;
                            cout<<"B>A"<<endl;
                        }while((x!=N)||(y!=N));
                    }
                    else{//2 случай
                        x=A; 
                        cout<<">A"<<endl;
                        y=0;
                        do{
                            y=B;
                            if(x>B){
                                x=x-B;
                                cout<<"A>B"<<endl;
                                cout<<"B>"<<endl;
                                if((x-B)==N){
                                    cout<<">A"<<endl;
                                    cout<<"A>B"<<endl;
                                    break;
                                }
                            }
                            else{
                                B=x;
                                x=A;
                            }
                        }while((x!=N)||(y!=N));
                    }
                }
                else
                    cout<<"Impossible"<<endl;
            }
            else
                cout<<"Impossible"<<endl;
        }
    }
}
Добавлено через 1 минуту
C
1
int main(){
return в конце не хватает, по теме: попробуй переписать программу с нуля

Добавлено через 51 минуту
вот вариант(не оптимальный, но на небольших N работает N<8 проверял). На больших N будет очень долго считать. Использовал перебор с возвратами.
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
#include <iostream>
using namespace std;
class glass{
    int capacity,
        value;
public:
    glass(int);
    void full();
    void pour();
    bool hit(int N);
    friend void pour(glass&,glass&);
    friend bool Aquarius (glass&,glass&,int N,int T);
};
int main(){
    glass   A(2),
            B(11);
    int N=9;
    
    if(Aquarius(A,B,N,8))
        cout<<"yes";
    else
        cout<<"no";
 
    cin.get();
    return 0;
}
 
glass::glass(int C){
    capacity=C;
    value=0;
}
void glass::full(){
    value=capacity;
}
void glass::pour(){
    value=0;
}
bool glass::hit(int N){
    return N==value;
}
 
void pour(glass& g1,glass& g2){
    int t=g1.capacity-g1.value;
    if(t<=g2.value){
        g1.full();
        g2.value-=t;
    }
    else{
        g1.value+=g2.value;
        g2.pour();
    }
}
bool Aquarius(glass& g1,glass& g2,int N, int T){
    glass g(0),gg(0);
    if(T<0) return 0;
    if(g1.hit(N)||g2.hit(N))
        return 1;
    //наполняю А
    g.capacity=g1.capacity;
    g.value=g1.capacity;
    if(Aquarius(g,g2,N,T-1)){
        cout<<"<-\"A>\"";
        return 1;
    }
    //наполняю В
    g.capacity=g2.capacity;
    g.value=g2.capacity;
    if(Aquarius(g1,g,N,T-1)){
        cout<<"<-\"B>\"";
        return 1;
    }
    //выливаю из А
    g.capacity=g1.capacity;
    g.value=0;
    if(Aquarius(g,g2,N,T-1)){
        cout<<"<-\"A<\"";
        return 1;
    }
    //выливаю из В
    g.capacity=g2.capacity;
    g.value=0;
    if(Aquarius(g1,g,N,T-1)){
        cout<<"<-\"B<\"";
        return 1;
    }
    //переливаю из В в А
    g.capacity=g1.capacity;
    g.value=g1.value;
    gg.capacity=g2.capacity;
    gg.value=g2.value;
    pour(g,gg);
    if(Aquarius(g,gg,N,T-1)){
        cout<<"<-\"B>A\"";
        return 1;
    }
    //переливаю из А в В
    g.capacity=g1.capacity;
    g.value=g1.value;
    gg.capacity=g2.capacity;
    gg.value=g2.value;
    pour(gg,g);
    if(Aquarius(g,gg,N,T-1)){
        cout<<"<-\"A>B\"";
        return 1;
    }   
    return 0;
 
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.01.2011, 14:31     Исполнитель Водолей #3
Hi4ko, Проверяйте:
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
#include <iostream>
#include <string>
using namespace std;
bool fl=true;
int mas[105], i_mas=0, A, B, N, temp_A=0, temp_B=0;
void rec(int col, int op)
{
    int temp, temp1;
    if(!fl)
        return;
    if(N==temp_A || N==temp_B)
        fl=false;
    if(col==105)
        return;
    if(col!=0 && temp_A==0 && temp_B==0)
        return;
    if(fl && temp_A!=A && temp_B!=B && op!=2 && op!=3 && !(temp_A!=0 && temp_B==0))
    {
        mas[i_mas++]=0;
        temp=temp_A;
        temp_A=A;
        rec(col+1, 0);
        temp_A=temp;
        if(fl)
        i_mas--;
    }
    if(fl && temp_B!=B && temp_A!=A && op!=3 && op!=2 && !(temp_B!=0 && temp_A==0))
    {
        mas[i_mas++]=1;
        temp=temp_B;
        temp_B=B;
        rec(col+1, 1);
        temp_B=temp;
        if(fl)
        i_mas--;
    }
    if(fl && temp_A!=0 && temp_B!=0 && op!=0 && op!=1)
    {
        mas[i_mas++]=2;
        temp=temp_A;
        temp_A=0;
        rec(col+1, 2);
        temp_A=temp;
        if(fl)
        i_mas--;
    }
    if(fl && temp_B!=0 && temp_A!=0 && op!=1 && op!=0)
    {
        mas[i_mas++]=3;
        temp=temp_B;
        temp_B=0;
        rec(col+1, 3);
        temp_B=temp;
        if(fl)
        i_mas--;
    }
    if(fl && temp_B!=B && temp_A!=0 && op!=5)
    {
        mas[i_mas++]=4;
        temp=temp_A;
        temp1=temp_B;
        if(temp_B+temp_A<=B)
        {
            temp_B+=temp_A;
            temp_A=0;           
        }
        else
        {
            temp_A-=B-temp_B;
            temp_B=B;
        }
        rec(col+1, 4);
        temp_A=temp;
        temp_B=temp1;
        if(fl)
        i_mas--;
    }
    if(fl && temp_A!=A && temp_B!=0 && op!=4)
    {
        mas[i_mas++]=5;
        temp=temp_B;
        temp1=temp_A;
        if(temp_A+temp_B<=A)
        {
            temp_A+=temp_B;
            temp_B=0;           
        }
        else
        {
            temp_B-=A-temp_A;
            temp_A=A;
        }
        rec(col+1, 5);
        temp_B=temp;
        temp_A=temp1;
        if(fl)
        i_mas--;
    }
}
int main()
{
    string t[6]={">A",">B","A>","B>","A>B","B>A"};
    cin>>A>>B>>N;
    rec(0, -1);
    if(fl)
        cout<<"Impossible";
    else
        for(int i=0; i<i_mas; i++)
            cout<<t[mas[i]]<<endl;        
        return 0;
}
rrrFer
Заблокирован
25.01.2011, 14:57     Исполнитель Водолей #4
valeriikozlov, Работает много быстее чем мой вариант, у меня полный перебор, т.е. сначала выбирается 105 операций типа 1, если результат не достигнут - то последняя операция заменятся на 2,3...6, потом тоже самое с предпоследней(поэтому на большом N долго работает)
очень понравилась вот эта часть у вас:
C++
1
if(fl && temp_A!=A && temp_B!=B && op!=2 && op!=3 && !(temp_A!=0 && temp_B==0))
мне было лень над этим думать, но видимо, надо было подумать
Hi4ko
74 / 74 / 4
Регистрация: 21.10.2010
Сообщений: 376
26.01.2011, 01:02  [ТС]     Исполнитель Водолей #5
Hi4ko, открою секрет почему на другие темы отвечают, а на твою - нет. Когда я вижу
C++
1
}}}}
появляется непреодолимое желание покинуть тему.
ЗЫ. если хочешь чтобы помогли - не издевайся над форумчанами, форматируй код нормально.
Начал смотреть код, вижу:
C++
1
2
3
y=0;
{
        do{
зачем первая фигурная скобка?(после y=0
По поводу 1: просто строк много, а на каждую скобку строку - я думал, будет ужасно. Теперь буду знать)
По поводу y=0 - просто много над ней работал, устал, скобку случайно написал, не заметил)
А так - спасибо за помощь, я сам уже облегчу прогу)
огромное спасибо
Yandex
Объявления
26.01.2011, 01:02     Исполнитель Водолей
Ответ Создать тему
Опции темы

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