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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.90
Kirgudu
0 / 0 / 0
Регистрация: 19.10.2011
Сообщений: 5
#1

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

22.10.2011, 19:34. Просмотров 1299. Ответов 7
Метки нет (Все метки)

Здравствуйте!
Вопрос связан с поиском в графе.

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

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

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

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

Поиск в глубину - C++
Здравствуйте. Как реализовать поиск кратчайшего пути в невзвешенном графе через поиск в глубину? Пробовал сделать так const...

Поиск в глубину - C++
Помогите с заданием пожалуйста. Число 1 можно записать как сумму n чисел вида 1 / i, где i - натуральное число. Например, для n = 3 имеем...

Поиск в глубину - C++
"В рождественскую ночь Санта-Клаус спускается по каминной трубе и раскладывает детям подарки. Кровати в комнате стоят очень плотно. Чтобы...

Поиск в глубину - C++
Объясните плз поиск в глубину с примером. Сам много реалихаций нашел, но до конца не могу разобраться, может у кого есть примерчик хороший....

поиск в глубину - C++
Дали задание реализовать поиск в глубину.Пробую релизовать по e-maxx http://e-maxx.ru/algo/dfsно не получается. vector<char> used; int...

Поиск в глубину. Графы. С++ - C++
Задана ,допустим, такая матрица смежности 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 0 Node.h #pragma once

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
ValeryLaptev
Эксперт С++
1041 / 820 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
22.10.2011, 19:37 #2
Kirgudu, графы здесь при чем? Как ты представляешь граф для этой задачки?
0
Kirgudu
0 / 0 / 0
Регистрация: 19.10.2011
Сообщений: 5
23.10.2011, 12:00  [ТС] #3
Да, да... не граф, а дерево...

Добавлено через 16 часов 19 минут
Вопрос ещё актуален. Поиск в интернете ничего не дал ( хотя может просто не знаю что точно нужно искать и как сформулировать проблему ).
Неужели никто не сталкивался в подобной задачей поиска? Подскажите, пожалуйста!
0
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
23.10.2011, 14:03 #4
Цитата Сообщение от Kirgudu Посмотреть сообщение
Можно ли, используя основные математические операции (сложение, вычитание, деление и умножение) получить число p из чисел a , b, c, d? При чем данные числа a , b, c, d можно использовать сколько угодно раз ( некоторые можно совсем не использовать ).
если числа натуральные, то это всегда возможно
0
Kirgudu
0 / 0 / 0
Регистрация: 19.10.2011
Сообщений: 5
23.10.2011, 15:42  [ТС] #5
Я знаю, что возможно. Но как? Как найти построение числа p из данных чисел с помощью основных матем. операций?
0
valeriikozlov
Эксперт C++
4670 / 2496 / 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
1
Diplomate
1 / 1 / 0
Регистрация: 10.11.2013
Сообщений: 84
13.08.2015, 23:35 #7
Хм...хорошая задачка. Я её немного усовершествую: нужно используя данные числа и математические операции получить искомое число p, причём операций должно быть минимальное количество. Никто не знает, как можно такое решить? Я даже не знаю, как тут эффективно организовать поиск, всему виной операция деления, без неё было бы легко. Может быть, решение основано на манипуляциях НОД/НОК этих чисел?
0
tegauss
30 / 24 / 24
Регистрация: 06.05.2014
Сообщений: 158
14.08.2015, 02:01 #8
Diplomate, насколько эффективное решение требуется? Первое, что приходит в голову - алгоритм перебора, логикой работы напоминающий bfs. Изначально мы находимся в корне(им будет одно из чисел). Применим к корню все возможные операции(+a, -a, *a, /a, +b, -b, *b, /b ...), получим 16 вершин. Полученные вершины положим в очередь. Далее, будем извлекать вершины из очереди, к каждой применять все операции и результат опять-таки класть в очередь. Получив на каком-либо шаге правильный результат, определим радиус поиска, который и будет результатом.

Еще, вероятно, придется рассмотреть 4 случая(в качестве корня могут выступать 4 числа).
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.08.2015, 02:01
Привет! Вот еще темы с ответами:

графы. поиск в глубину - C++
Здраствуйте. Вот такая задача N шестеpенок пpонумеpованы от 1 до N (N ≤ 10). Заданы M (0 ≤ M ≤ 45) соединений паp шестеpенoк в виде (i,...

Рекурсивный поиск в глубину - C++
Нужно найти путь по простому лабиринту от точки к точке, используя в программе рекурсивный поиск в глубину. Фотографию примера лабиринта...

графы,поиск в глубину - C++
очень нужна помощь!нужно в неориентированном графе найти компоненты связности поиском в глубину. Есть готовый алгоритм поиска,из...

Рекурсивный и нерекурсивный поиск в глубину - C++
Не уверен в правильности работы даной функции. Если начинать с вершины 2, то рекурсивный и нерекурсивный поиски дадут одинаковые...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
14.08.2015, 02:01
Ответ Создать тему
Опции темы

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