Решение задачи.

← →
lb (2003-01-13 19:09) [0]

Нужно решить назадачу на Pascal(c++) (лучше первое).
Даны два целых числа a,b. Любое из чисел можно заменить
либо их суммой, либо разностью. Написать алгоритм, который
определить можно ли выполнив некоторое ко-во таких преобразований
над числами, получить вместо одного из них число d.
Например: из чисел (5,6) может быть получено число 7 следующим
образом: (5,6) -> (-1,6) -> (-1,7).
---------------
Значь у меня есть вариант смособом подбора + внедрения некоторого интелекта.
например, будет две вложенные процедуры (каторые реализуют возможность
первого выполнения разности), потом определение, являеться ли число положительным,
если да -> выполнение ещё одной вложенной структуры... и т.д.
Имхо я задачу решить могу, но возможно есть ли какой-то альтернативный способ решения?
если имееться, или вы хотите мне предложить его либо дать совет, ответьте.
буду рад.
lbster

← →
Феу (2003-01-13 22:46) [1]

А не можно ли свести эту задачу к получению пары чисел (0, x). Если Abs(x)=d задача решена, если Abs(x)=0 - нет решений (если исходные <> d), Abs(x)=1 - можно получитьь любое число, Abs(x)=2 - можно получить только четное?
Т.е. пока нет 0 среди чисел, производим ту операцию, которая дает наименьшее по абсолютному значению число и заменяем им наибольшее.
Кажется, чушь сказал. На мои исходные данные выдает правильный результат. Но они же мои. Проверьте еще кто-нибудь?

← →
Ich Hasse (2003-01-13 23:58) [2]

Из двух разных четных чисел ты сможешь получить только четные.
Из двух разных нечетных что захочешь, то и получишь.
Из двух разный тоже все, что захочешь.

← →
Sha (2003-01-14 22:32) [3]

> Ich Hasse © (13.01.03 23:58)
> Из двух разных нечетных что захочешь, то и получишь.

Интересно, как можно получить 1 из 3 и 9 ? :))))

> Феу © (13.01.03 22:46)
> А не можно ли свести эту задачу к получению пары чисел (0, x).

Идея верная, но решение не всегда оптимально (за наименьшее число ходов).

2 lb (13.01.03 19:09)
> вариант смособом подбора + внедрения некоторого интелекта

Тут нам не обойтись без знаний, полученных в начальной школе:
1. Сначала смотрим:
- если a=с или b=c то решение уже найдено,
- если a=0 или b=0 или a=b<>c то решения нет.
2. По алгоритму Эвклида находим d=НОД(a,b) и определяем существование решения:
- если c не делится на d то решение не существует.
- если c делится на d то решение существует, и мы получаем его на шагах 3-4.
3. Уменьшаем по абсолютной величине максимальное по абсолютной величине число (a или b), используя одну из разрешенных операций (сложение или вычитание) до тех пор, пока не получим d.
4. Уменьшаем/увеличиваем на d другое число пока не получим c.

Приведенный алгоритм определяет существование решения задачи и при условии существования гарантированно находит некоторое решение. Чтобы найти оптимальное решение, не обойтись еще без двух товарищей, которые всегда думают о нас (© Jonson&Jonson): Диафанта и Фиббоначчи. Но это уже за рамками начальной школы :)

← →
Sha (2003-01-15 08:36) [4]

>Sha © (14.01.03 22:32)
>...до тех пор, пока не получим d.
По абсолютной величине, разумеется.

Примеры (a=7, b=5, c=16). Гарантированное решение: (7,5)(2,5)(2,3)(2,1)(3,1)(4,1)..(15,1)(16,1). Хорошее решение: (7,5)(2,5)(2,7)(9,7)(9,16). Оптимальное решение: (7,5)(7,-2)(7,9)(7,16).

Решение задачи. Найти похожие ветки