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

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

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

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

23.11.2010, 22:57. Просмотров 3792. Ответов 26
Метки нет (Все метки)

Нужна программа на Си
Помогите пожалуйста


В уравнении вида 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
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.11.2010, 22:57
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Уравнение с пропущенными цифрами (C++):

Вывод фамилии, имени и отчества с помощью функции с явно заданными или частично пропущенными параметрами - C++
1 Написать функцию с параметрами по умолчанию в соответствии с вариантом , продемонстрировать различные способы вызова функции: • с...

Дано уравнение ax2+bx+c=0. Решить уравнение, результат вывести на экран. - C++
Здравствуйте. Завтра зачет, нужно сдать две программы на с++, как их писать у меня весьма смутное представление. Собственно задание: ...

Создать производные классы линейное уравнение и квадратное уравнение, в которых данная функция переопределена - C++
Создать абстрактный базовый класс уравнение с виртуальной функцией - корни уравнения. Создать производные классы линейное уравнение и...

Написать программу, которая решает уравнение с одним неизвестным и выводит в консоль значение неизвестного. Уравнение посимвольно вводится с клавиатур - C++
Заупутался :-(

18. Написать программу, которая решает уравнение с одним неизвестным и выводит в консоль значение неизвестного. Уравнение посимвольно вводится с клави - C++
#include <iostream> using namespace std; void main() { int urov1 = 0; int urov2 = 0; int urov3 = 0; float stad = 0; ...

Работа с цифрами - C++
Не могу понять, что в программе не так. Алгоритм правильный, но расчет не идет. Исходное задание: Напишите программу, принимающую с...

26
rrrFer
Заблокирован
24.11.2010, 10:03 #2
Цитата Сообщение от xxxfelxxx Посмотреть сообщение
Добавлено через 33 минуты
upupupup
http://www.cyberforum.ru/announcement.php?a=3
2.13 Если на ваш вопрос долгое время нет ответа, уточните его, приведите дополнительные сведения, которые могут помочь участникам форума решить вашу проблему.
2.14 Чтобы "поднять" тему в разделе и поиске по форуму, используйте осмысленные сообщения, например "Тема/проблема/задача актуальна". Если вы чего-то достигли в решении проблемы на этот момент, сообщите об этом.
0
silent_1991
Эксперт С++
5005 / 3063 / 149
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
25.11.2010, 12:34 #3
Если в лоб, то составляем диофантово уравнение с некоторым количеством неизвестных и решаем его перебором.

Добавлено через 4 минуты
Короче говоря, отбросив термин "диофантово уравнение", самое тупое решение в лоб - перебор цифр.
0
Kastaneda
Jesus loves me
Эксперт С++
4749 / 2953 / 242
Регистрация: 12.12.2009
Сообщений: 7,493
Записей в блоге: 2
Завершенные тесты: 1
25.11.2010, 12:47 #4
Цитата Сообщение от silent_1991 Посмотреть сообщение
самое тупое решение в лоб - перебор цифр
Цитата Сообщение от xxxfelxxx Посмотреть сообщение
Длина уравнения не превышает 200 символов
Боюсь, что перебор может занять очень много времени, наверняка есть какой-то способ, чтоб решать подобные вещи.
0
silent_1991
Эксперт С++
5005 / 3063 / 149
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
25.11.2010, 12:49 #5
Kastaneda, а мне кажется, нет (ИМХО, но надо проверять). Достаточно быстрая операция (относительно) - сложить пару длинных чисел, отнять третье и сравнить с нулём.
Но если очень сильно подумать, думаю, можно придумать некоторые проверки, которые позволять отбросить некоторые группы вариантов. Но думать что-то неохота)))
0
Kastaneda
Jesus loves me
Эксперт С++
4749 / 2953 / 242
Регистрация: 12.12.2009
Сообщений: 7,493
Записей в блоге: 2
Завершенные тесты: 1
25.11.2010, 13:26 #6
Цитата Сообщение от silent_1991 Посмотреть сообщение
сложить пару длинных чисел, отнять третье и сравнить с нулём
а если будет 10 слогаемых? И среди них много символов '?'
Я вижу картину так:
Писать парсер - считать знаки '?' в числах, считать кол-во цифр. Перебор осуществляется так: перебирать цифры 0-9, каждую умножать на 10 в соответствующей степени и т.д. Проще показать на примере:
Код
есть число "??4?" - кол-во цифр-4
dig=0*1000+0*100+4*10+0*1
если это число не подошло, то:
dig= 0*1000+0*100+4*10+1*1
и т.д. таким образом нужно перебрать 3^10 выриантов. И так с каждым числом. По-моему ооочень долго.
Может я сильно перемудрил, на вроде так)
0
silent_1991
Эксперт С++
5005 / 3063 / 149
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
25.11.2010, 13:28 #7
Kastaneda, 10 слагаемых не будет по условию.
0
Kastaneda
Jesus loves me
Эксперт С++
4749 / 2953 / 242
Регистрация: 12.12.2009
Сообщений: 7,493
Записей в блоге: 2
Завершенные тесты: 1
25.11.2010, 13:31 #8
А зачем тогда:
Длина уравнения не превышает 200 символов
Даже если 2 слогаемых, то при 200 символов, нужно перебрать миллиарды комбинаций (ну, смотря сколько пропущенных цифр)
0
silent_1991
Эксперт С++
5005 / 3063 / 149
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
25.11.2010, 13:49 #9
Kastaneda, не, понятно, что вариантов много. И перебора много. Но просто мне кажется, что вся задача строится на переборе. И иначе её не решить. Разве что, как я уже говорил, можно определить какие-нибудь свойства, которые позволят отпросить некоторые наборы. Но я не силён в теории чисел, поэтому так просто эти свойства вряд ли всплывут, тут надо что-нибудь покурить в плане теории)))
0
Kastaneda
Jesus loves me
Эксперт С++
4749 / 2953 / 242
Регистрация: 12.12.2009
Сообщений: 7,493
Записей в блоге: 2
Завершенные тесты: 1
25.11.2010, 14:17 #10
Немного подумав нашел способ сузить диапазон перебора:
вот выражение:
?2+34=4?
очевидно, что результат может быть от 40 до 49. От наименьшего и от наибольшего отнимаем 34 (число без '?'), получается, что число ?2 может принимать значения от 6 до 15. Числа 6-9 сразу откидываем, остается перебрать 10-15 с результатами 40-49, т.е. 5*9=45 комбинаций.

Добавлено через 2 минуты
да, и еще, в введенном примере по-любому должно присутствовать хотя бы одно число без '?', иначе однозначного ответа не может быть.
0
silent_1991
Эксперт С++
5005 / 3063 / 149
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
25.11.2010, 14:20 #11
Да его и так может не быть, по условию надо выбрать любой из вариантов (другими словаим первый попавшийся))) )
0
Kastaneda
Jesus loves me
Эксперт С++
4749 / 2953 / 242
Регистрация: 12.12.2009
Сообщений: 7,493
Записей в блоге: 2
Завершенные тесты: 1
25.11.2010, 14:30 #12
Цитата Сообщение от Kastaneda Посмотреть сообщение
Числа 6-9 сразу откидываем, остается перебрать 10-15 с результатами 40-49, т.е. 5*9=45 комбинаций.
Я тут еще ступил, в диапазон 10-15 с маской ?2 входит только 12, таким образом нужно перебрать всего 1*10=10 комбинаций. Вместо 100 (это если перебирать все варианты), по-моему довольно существенный выигрыш.

Добавлено через 43 секунды
Цитата Сообщение от silent_1991 Посмотреть сообщение
Да его и так может не быть, по условию надо выбрать любой из вариантов (другими словаим первый попавшийся))) )
В вышепреведенном примере как раз может.
0
ForEveR
В астрале
Эксперт С++
7992 / 4751 / 321
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
25.11.2010, 14:45 #13
deleted.
Хотя все равно как-то дико странно насчет нулей...
0
valeriikozlov
Эксперт С++
4681 / 2507 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
25.11.2010, 16:16 #14
Я предлагаю с помощью рекурсии. По смыслу представляю решение так: ставим три числа в столбик (как при складывании столбиком) число 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 продолжаем рекурсию до конца последнего разряда самого длинного числа, при этом представляя в функции отсутствующие разряды закончившихся чисел нулями.
Если один из вариантов получился, то остальные ветви рекурсии не продолжаем.
Вот вроде так.
1
valeriikozlov
Эксперт С++
4681 / 2507 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
27.11.2010, 21:42 #15
2-ое суток меня не было, не было возможности зайти на форум, но теперь обращаюсь к xxxfelxxx - если обещаете сообщить результаты сдачи этой задачи, то обещаю, что код напишу.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.11.2010, 21:42
Привет! Вот еще темы с ответами:

Работа с цифрами - C++
Привет всем, помогите пожалуйста решить задачу. Заменить в натуральном числе все цифры 7 цифрами 8 и удалить из записи числа все единицы,...

задача с цифрами - C++
a) Дано трёхзначное число. Определить, есть ли среди его цифр одинаковые? b) Дано натуральное число с различными цифрами. Определить,...

задача с натуральными цифрами - C++
int n, count = 0; cin >> n; // вводим натуральное число, меньше которого наш знаменатель for(int i = 2; i < n; i++) { ...

Заполнение массива 6*6 цифрами от 1 до 36 - C++
Заполнить массив 6*6 цифрами от 1 до 36 по следующей схеме 1 36 35 33 30 26 2 3 34 32 29 25 4 5 6 31 28 24 7 8 9 10 27 23 11 12...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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