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

[Anastasia.K]

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

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

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

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

Заранее спасибо!

[was3110]

Следует ввести понятие атомарности, т.е. единицы разрешимости задачи.
Если Р будет делиться на атом без остатка, значит задача имеет решение.
Следует рассматривать числа a < b< c< d т.е. в порядке возрастания (возможно атомарность будет достигнута раньше и более крупные вектора окажутся избыточны – не нужны для решения)
1шаг: вычисляем два атома, которые получаются из векторов a и b.
nab=b-k*a - недолет pab=(k+1)*a-b – перелет
Но оба атома меньше чем a и b.
Проверяем, если Р делится на nab или pab без остатка, то атомарность достигнута и этих векторов достаточно, чтобы получить число Р.

Если интересно продолжение, ищите контакты в профиле...