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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.70
Hi4ko
74 / 74 / 4
Регистрация: 21.10.2010
Сообщений: 376
#1

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

25.01.2011, 01:45. Просмотров 2782. Ответов 4
Метки нет (Все метки)

У исполнителя “Водолей” есть два сосуда, первый объемом 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     Исполнитель Водолей
Посмотрите здесь:

Задача "Исполнитель Водолей" - C++
У исполнителя “Водолей” есть два сосуда, первый объемом A литров, второй объемом B литров, а также кран с водой. Водолей может выполнять...

Задача "Водолей" - C++
Вот условие: Некоторые соображения: если N&gt;A и N&gt;B, то невозможно если А=B и N%A!=0, то невозможно если N=A или N=B, то...

Структуры: информация о CD-дисках (исполнитель, название, длительность звучания, стоимость) - C++
реализуйте программу для решения следующей задачи: вводится информация о CD(DVD)- дисках: исполнитель,название,длительность...

Задача "Исполнитель Раздвоитель" - C++
Исполнитель “Раздвоитель” преобразует натуральные числа. У него есть две команды: “Вычесть 1” и “Разделить на 2”, первая команда уменьшает...

Задача "Исполнитель" - C++
Имеется такая задача(во вложении). Как я понял - это задача на жадный алгоритм, но с реализацией пока имеются проблемы. Какие идеи есть?

Исполнитель Водолей - Pascal ABC
Нужен легкий код. На форуме уже видел решение, но большую его часть я не понял. У исполнителя “Водолей” есть два сосуда,...

Исполнитель водолей - Turbo Pascal
Здравствуйте! Есть &quot;Сишный&quot;(С++) код: const int LIMIT = 1e5 + 10; int a, b, n; cin &gt;&gt; a &gt;&gt; b &gt;&gt; n; char min = 'A', max = 'B';...

Задача "Исполнитель Водолей" - Python
Никак не могу додуматься до решения задачи( :wall: Исполнитель Водолей У исполнителя “Водолей” есть два сосуда, первый объемом A...

Исполнитель Раздвоитель - C (СИ)
Исполнитель “Раздвоитель” преобразует натуральные числа. У него есть две команды: “Вычесть 1” и “Разделить на 2”, первая команда уменьшает...

Кто исполнитель - Музыка
Очень понравился клип один и песня, но кто её поёт никак не могу узнать. Слил с флэшки у одного командировочного, Вот как файл называется,...

Исполнитель Робот - Информатика
дали вот несколько задач (попросили решить, будучи студентом уже не ничего помню из курса информатики), можете проверить 1-3 и объяснить...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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++
4669 / 2495 / 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     Исполнитель Водолей
Ответ Создать тему
Опции темы

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