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

Итеративный поиск в глубину - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.90
Kirgudu
0 / 0 / 0
Регистрация: 19.10.2011
Сообщений: 5
22.10.2011, 19:34     Итеративный поиск в глубину #1
Здравствуйте!
Вопрос связан с поиском в графе.

Меня интересуют идеи решения или ссылка на литературу.
Пожалуйста, подскажите...

Пусть даны 4 числа (пусть это a , b, c, d) и еще одно число ( пусть будет p ). Можно ли, используя основные математические операции (сложение, вычитание, деление и умножение) получить число p из чисел a , b, c, d? При чем данные числа a , b, c, d можно использовать сколько угодно раз ( некоторые можно совсем не использовать ).

В задаче нужно использовать итеративный поиск в глубину.

Заранее спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.10.2011, 19:34     Итеративный поиск в глубину
Посмотрите здесь:

Поиск в глубину C++
C++ поиск в глубину
C++ Не работает поиск в глубину (DFS)
C++ графы,поиск в глубину
графы. поиск в глубину C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
22.10.2011, 19:37     Итеративный поиск в глубину #2
Kirgudu, графы здесь при чем? Как ты представляешь граф для этой задачки?
Kirgudu
0 / 0 / 0
Регистрация: 19.10.2011
Сообщений: 5
23.10.2011, 12:00  [ТС]     Итеративный поиск в глубину #3
Да, да... не граф, а дерево...

Добавлено через 16 часов 19 минут
Вопрос ещё актуален. Поиск в интернете ничего не дал ( хотя может просто не знаю что точно нужно искать и как сформулировать проблему ).
Неужели никто не сталкивался в подобной задачей поиска? Подскажите, пожалуйста!
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
23.10.2011, 14:03     Итеративный поиск в глубину #4
Цитата Сообщение от Kirgudu Посмотреть сообщение
Можно ли, используя основные математические операции (сложение, вычитание, деление и умножение) получить число p из чисел a , b, c, d? При чем данные числа a , b, c, d можно использовать сколько угодно раз ( некоторые можно совсем не использовать ).
если числа натуральные, то это всегда возможно
Kirgudu
0 / 0 / 0
Регистрация: 19.10.2011
Сообщений: 5
23.10.2011, 15:42  [ТС]     Итеративный поиск в глубину #5
Я знаю, что возможно. Но как? Как найти построение числа p из данных чисел с помощью основных матем. операций?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
23.10.2011, 20:00     Итеративный поиск в глубину #6
Цитата Сообщение от Kirgudu Посмотреть сообщение
Я знаю, что возможно. Но как? Как найти построение числа p из данных чисел с помощью основных матем. операций?
слишком много вариантов нахождения числа, вот Вы и растерялись. Возьмите какой-нибудь один вариант. Например (нахождение числа p только с помощью числа a):
- если p отрицательное, то a-a-a/a-a/a........ пока не достигнете нужного результата
- если p положительное, то a/a+a/a+a/a........
- если p равно 0, то a-a
Diplomate
1 / 1 / 0
Регистрация: 10.11.2013
Сообщений: 79
13.08.2015, 23:35     Итеративный поиск в глубину #7
Хм...хорошая задачка. Я её немного усовершествую: нужно используя данные числа и математические операции получить искомое число p, причём операций должно быть минимальное количество. Никто не знает, как можно такое решить? Я даже не знаю, как тут эффективно организовать поиск, всему виной операция деления, без неё было бы легко. Может быть, решение основано на манипуляциях НОД/НОК этих чисел?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.08.2015, 02:01     Итеративный поиск в глубину
Еще ссылки по теме:

Поиск в глубину C++
C++ Матрица смежности графа - поиск в глубину
C++ Поиск в глубину

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

Или воспользуйтесь поиском по форуму:
tegauss
30 / 24 / 24
Регистрация: 06.05.2014
Сообщений: 157
14.08.2015, 02:01     Итеративный поиск в глубину #8
Diplomate, насколько эффективное решение требуется? Первое, что приходит в голову - алгоритм перебора, логикой работы напоминающий bfs. Изначально мы находимся в корне(им будет одно из чисел). Применим к корню все возможные операции(+a, -a, *a, /a, +b, -b, *b, /b ...), получим 16 вершин. Полученные вершины положим в очередь. Далее, будем извлекать вершины из очереди, к каждой применять все операции и результат опять-таки класть в очередь. Получив на каком-либо шаге правильный результат, определим радиус поиска, который и будет результатом.

Еще, вероятно, придется рассмотреть 4 случая(в качестве корня могут выступать 4 числа).
Yandex
Объявления
14.08.2015, 02:01     Итеративный поиск в глубину
Ответ Создать тему
Опции темы

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