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

Уравнение с пропущенными цифрами - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.89
xxxfelxxx
0 / 0 / 0
Регистрация: 24.10.2010
Сообщений: 31
23.11.2010, 22:57     Уравнение с пропущенными цифрами #1
Нужна программа на Си
Помогите пожалуйста


В уравнении вида A + B = C, где A, B и C — неотрицательные целые числа, некоторые цифры заменены на знаки вопроса.

Необходимо подставить вместо знаков вопроса такие десятичные цифры, чтобы уравнение стало верным, либо определить, что это невозможно.

На входе подаётся единственная строка текста — уравнение с вопросительными знаками. Длина уравнения не превышает 200 символов. Входные данные не содержат никаких символов, кроме десятичных цифр, вопросительных знаков, символа «плюс» и символа «равно». Кроме того, после конца строки может следовать символ перевода строки.

На стандартный поток вывода напечатайте уравнение с подставленными вместо знаков вопроса цифрами, если решение существует, и выведите единственное слово No, если решения нет. Если задача допускает несколько решений, выводите любое. В ответе разрешены ведущие нули (см. примеры).

Примеры

Входные данные Результат работы
?2+34=4? 12+34=46

?2+34=47 No

??2?4+9?=355 00264+91=355
Добавлено через 33 минуты
upupupup
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
xxxfelxxx
0 / 0 / 0
Регистрация: 24.10.2010
Сообщений: 31
29.11.2010, 18:22  [ТС]     Уравнение с пропущенными цифрами #21
Спасибо оргомное, но прежде чем сдавать надо в ней разобраться)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
29.11.2010, 18:44     Уравнение с пропущенными цифрами #22
Спасибо оргомное, но прежде чем сдавать надо в ней разобраться)
Помочь разобраться?
xxxfelxxx
0 / 0 / 0
Регистрация: 24.10.2010
Сообщений: 31
30.11.2010, 13:58  [ТС]     Уравнение с пропущенными цифрами #23
Было бы просто замечательно
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.11.2010, 17:07     Уравнение с пропущенными цифрами #24
xxxfelxxx,
Итак есть запись например:
??2?4+9?=355
всегда имеем для решения 3 массива типа char размером 200 - массивы a, b, c.
изначально всем элементам массивов присваиваем значение символ - '0'.
После записи в массивы значений из приведенного примера, массивы должны выглядеть так:
Массив a[] (у приведенных символов массива индексация начинается слева, т.е. самый левый символ имеет индекс равный 0):
4 ? 2 ? ?
Массив b[]:
? 9
Массив c[]:
5 5 3
Теперь после записи символов в массивы начинаем вычисление нужного нам выражения (Используем принцип сложения чисел в столбик). Для этого используем рек.функцию в параметрах которой передаем два значения: первое значение - индекс очередных складываемых цифр, второе значение - (есть или нет перенос единицы со сложения предыдущих разрядов).
Для этого изначально вызываем рек функцию так:
rec(0, 0);
, что значит будем складывать числа с индексом 0, переноса единицы с предыдущих разрядов нет.
Сама функция rec() (в реализации этого кода она самая сложная):
в ней реализовано возможное сложение очередных символов массивов a[] и b[] с учетом очередного символа c[].
В общем саму реализацию функции rec() я уже описывал здесь:
Цитата Сообщение от valeriikozlov Посмотреть сообщение
По смыслу представляю решение так: ставим три числа в столбик (как при складывании столбиком) число A, число B, число C. Проходим от младших разрядов к старшим.
Может быть три ситуации:
1. Мы можем подобрать цифру (цифры) когда при их сложении, переноса 1 в следующие разряды не будет, например:
?
3
7
или так когда переноса 1 с предыдущих разрядов не было)
?
?
9
в этом случае, выбираем любую подстановку цифры (цифр) и больше к этим разрядам мы не вернемся.
2. Мы можем подобрать цифру (цифры) когда при их сложении, перенос 1 в следующие разряды будет обязательно (какие бы варианты цифры (цифр) мы не перебирали в этих разрядах), например:
6
8
?
или так: (когда перенос 1 с предыдущих разрядов есть)
?
9
?
и в этом случае, выбираем любую подстановку цифры (цифр) и больше к этим разрядам мы не вернемся.
3. Мы можем подобрать цифру (цифры) когда при их сложении, перенос 1 в следующие разряды может быть, а может и не быть.
Вот здесь нужно выбрать один (любой) вариант с переносом 1, второй (любой) вариант без переноса 1. Этих двух вариантов хватит.
Этот процесс выбора думаю легко реализовать с помощью рек. функции. В параметрах передавать, номер разряда (очередного разряда который будем рассматривать) и переменную по которой определять, есть ли перенос 1 с предыдущих разрядов или нет.
В самой функции нужно тщательно продумать варианты когда есть один из вариантов, когда два варианта, когда нет вообще вариантов:
- например:
2
3
8
или (есть перенос 1 с предыдущих разрядов)
4
?
4
При окончании любого из чисел (числа): A,B, C продолжаем рекурсию до конца последнего разряда самого длинного числа, при этом представляя в функции отсутствующие разряды закончившихся чисел нулями.
Если один из вариантов получился, то остальные ветви рекурсии не продолжаем.
Если это понятно, то можно идти дальше: рассмотреть досконально саму функцию rec().
xxxfelxxx
0 / 0 / 0
Регистрация: 24.10.2010
Сообщений: 31
30.11.2010, 23:56  [ТС]     Уравнение с пропущенными цифрами #25
Попробовал сдать, вот что получилось:
Миниатюры
Уравнение с пропущенными цифрами  
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
01.12.2010, 02:16     Уравнение с пропущенными цифрами #26
xxxfelxxx, Номера решений: 6137, 6135, 6132 все ваши?

Добавлено через 42 минуты
Если все номера решений Ваши, то напишите что исправляли, что бы добиться 6137.
Я еще раз внимательно пересмотрел функцию rec(), нашел там 4 ошибки, так что еще раз Вам придется запустить с функцией rec() вот в таком виде:
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
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
void rec(int a1, int b1)
{
        if(fl==0)
                return;
        if(a1>=a_len && a1>=b_len && a1>=c_len)
        {
                if(b1==0)
                        fl=0;
                return;
        }
        if(a[a1]=='?' && b[a1]=='?' && c[a1]=='?')
        {
                a[a1]='0'; b[a1]='0';
                if(b1==0)
                        c[a1]='0';
                else
                        c[a1]='1';
                rec(a1+1, 0);
                if(fl==1)
                {
                a[a1]='5'; b[a1]='5';
                if(b1==0)
                        c[a1]='0';
                else
                        c[a1]='1';
                rec(a1+1, 1);
                }
        }
        if(a[a1]=='?' && b[a1]=='?' && c[a1]!='?')
        {
                if(c[a1]=='9')
                {
                        if(b1==1)
                        {
                                a[a1]='5'; b[a1]='3';
                                rec(a1+1, 0);
                                if(fl==1)
                                {
                                a[a1]='9'; b[a1]='9';
                                rec(a1+1, 1);
                                }
                        }
                        else
                        {
                                a[a1]='5'; b[a1]='4';//ош
                                rec(a1+1, 0);
                        }
                }
                else
                {
                        if(c[a1]=='0' && b1==1)
                        {
                                a[a1]='8'; b[a1]='1';
                                rec(a1+1, 1);
                        }
                        else
                        {
                                a[a1]='0'; 
                                if(b1==0)
                                        b[a1]=c[a1]; 
                                else
                                        b[a1]=c[a1]-1;//ош
                                rec(a1+1, 0);
                                if(fl==1)
                                {
                                a[a1]='9';
                                if(b1==0)
                                        b[a1]=c[a1]+1;
                                else
                                        b[a1]=c[a1];
                                rec(a1+1, 1);
                                }
                        }
                }
        }
        if(a[a1]!='?' && b[a1]=='?' && c[a1]!='?')
        {
                if(a[a1]>c[a1])
                {
                        if(b1==1)
                                b[a1]='0'+9+(c[a1]-a[a1]);
                        else
                                b[a1]='0'+10+(c[a1]-a[a1]);
                        rec(a1+1, 1);
                }
                if(a[a1]<c[a1])
                {
                        if(b1==1)
                                b[a1]='0'+(c[a1]-a[a1])-1;
                        else
                                b[a1]='0'+(c[a1]-a[a1]);
                        rec(a1+1, 0);
                }
                if(a[a1]==c[a1])
                {
                        if(b1==0)
                        {
                                b[a1]='0';
                                rec(a1+1, 0);
                        }
                        else
                        {
                                b[a1]='9';
                                rec(a1+1, 1);
                        }
                }
        }
        if(a[a1]=='?' && b[a1]!='?' && c[a1]!='?')
        {
                if(b[a1]>c[a1])
                {
                        if(b1==1)
                                a[a1]='0'+9+(c[a1]-b[a1]);
                        else
                                a[a1]='0'+10+(c[a1]-b[a1]);
                        rec(a1+1, 1);
                }
                if(b[a1]<c[a1])
                {
                        if(b1==1)
                                a[a1]='0'+(c[a1]-b[a1])-1;
                        else
                                a[a1]='0'+(c[a1]-b[a1]);
                        rec(a1+1, 0);
                }
                if(b[a1]==c[a1])
                {
                        if(b1==0)
                        {
                                a[a1]='0';
                                rec(a1+1, 0);
                        }
                        else
                        {
                                a[a1]='9';
                                rec(a1+1, 1);
                        }
                }
        }
        if(a[a1]!='?' && b[a1]!='?' && c[a1]!='?')
        {
                if(b1==1)
                {
                        if(((int)(a[a1]-'0'+b[a1]-'0')+1)%10==(int)(c[a1]-'0'))
                        {
                                if((int)(a[a1]-'0'+b[a1]-'0')+1>9)
                                        rec(a1+1, 1);
                                else
                                        rec(a1+1, 0);
                        }
                }
                else
                {
                        if((int)(a[a1]-'0'+b[a1]-'0')%10==(int)(c[a1]-'0'))
                        {
                                if((int)(a[a1]-'0'+b[a1]-'0')>9)
                                        rec(a1+1, 1);
                                else
                                        rec(a1+1, 0);
                        }
                }
        }
        if(a[a1]!='?' && b[a1]=='?' && c[a1]=='?')
        {
                if(a[a1]=='0')
                {
                        if(b1==0)
                        {
                                b[a1]='0'; c[a1]='0';
                                rec(a1+1, 0);
                        }
                        else
                        {
                                b[a1]='0'; c[a1]='1';
                                rec(a1+1, 0);
                                if(fl==1)
                                {
                                b[a1]='9'; c[a1]='0';
                                rec(a1+1, 1);
                                }
                        }
                }
                else
                {
                        if(a[a1]=='9')
                        {
                                if(b1==1)
                                {
                                        b[a1]='0'; c[a1]='0';
                                        rec(a1+1, 1);
                                }
                                else
                                {
                                        b[a1]='1'; c[a1]='0';
                                        rec(a1+1, 1);
                                        if(fl==1)
                                        {
                                        b[a1]='0'; c[a1]='9';//ош
                                        rec(a1+1, 0);
                                        }
                                }
                        }
                        else
                        {
                                b[a1]='0'; 
                                if(b1==0)
                                        c[a1]=a[a1];
                                else
                                        c[a1]=a[a1]+1;
                                rec(a1+1, 0);
                                if(fl==1)
                                {
                                b[a1]='9'; 
                                if(b1==0)
                                        c[a1]=a[a1]-1;
                                else
                                        c[a1]=a[a1];
                                rec(a1+1, 1);
                                }
                        }
                }
        }
        if(a[a1]=='?' && b[a1]!='?' && c[a1]=='?')
        {
                if(b[a1]=='0')
                {
                        if(b1==0)
                        {
                                a[a1]='0'; c[a1]='0';
                                rec(a1+1, 0);
                        }
                        else
                        {
                                a[a1]='0'; c[a1]='1';
                                rec(a1+1, 0);
                                if(fl==1)
                                {
                                a[a1]='9'; c[a1]='0';
                                rec(a1+1, 1);
                                }
                        }
                }
                else
                {
                        if(b[a1]=='9')
                        {
                                if(b1==1)
                                {
                                        a[a1]='0'; c[a1]='0';
                                        rec(a1+1, 1);
                                }
                                else
                                {
                                        a[a1]='1'; c[a1]='0';
                                        rec(a1+1, 1);
                                        if(fl==1)
                                        {
                                        a[a1]='0'; c[a1]='9';//ош
                                        rec(a1+1, 0);
                                        }
                                }
                        }
                        else
                        {
                                a[a1]='0'; 
                                if(b1==0)
                                        c[a1]=b[a1];
                                else
                                        c[a1]=b[a1]+1;
                                rec(a1+1, 0);
                                if(fl==1)
                                {
                                a[a1]='9'; 
                                if(b1==0)
                                        c[a1]=b[a1]-1;
                                else
                                        c[a1]=b[a1];
                                rec(a1+1, 1);
                                }
                        }
                }
        }
        if(a[a1]!='?' && b[a1]!='?' && c[a1]=='?')
        {
                if((int)(a[a1]-'0'+b[a1]-'0')+b1>9)
                {
                        c[a1]='0'+((int)(a[a1]-'0'+b[a1]-'0')+b1)%10;
                        rec(a1+1, 1);
                }
                else
                {
                        c[a1]='0'+(int)(a[a1]-'0'+b[a1]-'0')+b1;
                        rec(a1+1, 0);
                }
        }
 
}
Жду результатов
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.12.2010, 16:19     Уравнение с пропущенными цифрами
Еще ссылки по теме:

C++ 18. Написать программу, которая решает уравнение с одним неизвестным и выводит в консоль значение неизвестного. Уравнение посимвольно вводится с клави
Создать производные классы линейное уравнение и квадратное уравнение, в которых данная функция переопределена C++
C++ Вывод фамилии, имени и отчества с помощью функции с явно заданными или частично пропущенными параметрами

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

Или воспользуйтесь поиском по форуму:
xxxfelxxx
0 / 0 / 0
Регистрация: 24.10.2010
Сообщений: 31
01.12.2010, 16:19  [ТС]     Уравнение с пропущенными цифрами #27
Первые два непройденные решения - это ваш код. Я подключил stdlib
и еще что то подправил (вроде переменную инициализировал, ejudje вредничает по таким поводам).
Сейчас попробую сдать новый код.
Ох, намучился я с форматированием, потому что к стилю придираются

Добавлено через 2 минуты
Все, "принято на проверку"
Благодарю за помощь )
Yandex
Объявления
01.12.2010, 16:19     Уравнение с пропущенными цифрами
Ответ Создать тему
Опции темы

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