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

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

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

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

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

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

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

Пусть даны 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++
Помогите с заданием пожалуйста. Число 1 можно записать как сумму n чисел вида 1 / i, где i - натуральное число. Например, для n = 3 имеем...

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

Поиск в глубину. Графы. С++ - 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

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

Не работает поиск в глубину (DFS) - C++
Вот код (заполнен для ориентированного графа 0 2 | + +/ 1--+3--+4 | + 5--+6 |

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

Конечный автомат. Лабиринт (поиск в глубину) - C++
Пусть лабиринт задан двумерным массивом bool, индексы ячеек соответствуют их координатам. Ячейка содержит true, если она проходима, и...

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

Добавлено через 16 часов 19 минут
Вопрос ещё актуален. Поиск в интернете ничего не дал ( хотя может просто не знаю что точно нужно искать и как сформулировать проблему ).
Неужели никто не сталкивался в подобной задачей поиска? Подскажите, пожалуйста!
Mayonez
380 / 272 / 21
Регистрация: 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++
4669 / 2495 / 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
Сообщений: 84
13.08.2015, 23:35     Итеративный поиск в глубину #7
Хм...хорошая задачка. Я её немного усовершествую: нужно используя данные числа и математические операции получить искомое число p, причём операций должно быть минимальное количество. Никто не знает, как можно такое решить? Я даже не знаю, как тут эффективно организовать поиск, всему виной операция деления, без неё было бы легко. Может быть, решение основано на манипуляциях НОД/НОК этих чисел?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.08.2015, 02:01     Итеративный поиск в глубину
Еще ссылки по теме:

Нужны небольшие пояснения по маленькому фрагменту кода, реализующего рекурсивный поиск в глубину по графу - C++
Здравствуйте, не могу разобраться в этой функции. Ниже есть ссылка на сам алгоритм. Заранее спасибо. Тут описан алгоритм. vector <...

рекурсия, итеративный метод - C++
помогите пожалуйста написать программу для итеративного способа вычисления. нужно вычислить элементы последовательности a(n) = a(n...

Рекурсивный и итеративный метод - C++
помогите пожалуйста написать программу для итеративного способа вычисления. нужно вычислить элементы последовательности a(n) = a(n...

Рекурсивный и итеративный методы разворачивания числа - C++
Не могу найти решение. В общем вводим целое число например '1234' , функция должна вернуть обратное число '4321'. Нашел решение используя...

Итеративный и рекурсивный методом вычисления ln 1 + x, через разложение в ряд - C++
Добрый день, друзья. Помогите мне пожалуйста с прогой. Уже мучаюсь очень долго время, не могу найти выхода. Суть задания: ...


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

Или воспользуйтесь поиском по форуму:
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 числа).
Yandex
Объявления
14.08.2015, 02:01     Итеративный поиск в глубину
Ответ Создать тему
Опции темы

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