[Disney]

Всем доброго времени суток.
Задача:
Пройти расстояние (S), за определенное количество шагов (n), при этом заданы величины начального (a) и конечного (b) шагов, причём начальный это шаг ещё перед прохождением расстояния, а конечный это уже следующий шаг после прохождения расстояния.
Найти:
Равномерное изменение шага (x)
Пример
S=24, n=7, a=5, b=4 надо найти x=0.5
5->4.5-4.0-3.5-3.0-2.5-3.0-3.5->4

[zamtmn]

В такой постановке задача имеет много решений (помоему n/2), например
5->4.75-4.5-4.25-4.0-3.75-3.5-3.75->4
и сводится и линейной интерпетации, путем отброса части 4.0-3.75-3.5-3.75->4 в моем решении и 4.0-3.5-3.0-2.5-3.0-3.5->4 в вашем

вру. путь тоже задан - тогда перебираем решения и выбираем нужное

[Do$]

Це ж арифметическая прогрессия!
В вики все формулы есть.

[Disney]

Сообщение от Do$ Це ж арифметическая прогрессия!

Не, не она

Сообщение от ВикипедиЯ числовая последовательность , в которой каждый член, начиная со второго, есть сумма предыдущего члена и некоторого постоянного числа d , называемого разностью или шагом арифметической прогрессии.

Дело в том, что в моём случаи число d почти всегда один раз меняет знак.

Сообщение от Disney 5->4.5-4.0-3.5-3.0-2.5-3.0-3.5->4

5-0.5 -> 4.5-0.5 -> 4-0.5->3.5-0.5->3.0-0.5->2.5+0.5->3.0+0.5->3.5+0.5->4

[bargool]

так по какому критерию найденное изменение шага считается верным?
можно ж вообще сделать x = (a-b)/(n+1)

[zamtmn]

>>Не, не она
она. точнее они - у вас 2 прогресси

[Disney]

Сообщение от bargool так по какому критерию найденное изменение шага считается верным?

Жёстко задана сумма шагов (Расстояние S)

Сообщение от zamtmn она. точнее они - у вас 2 прогресси

Хорошо, 2 очень взаимосвязанные арифметические прогрессии. Дальше как?

[bargool]

а вот про расстояние я не увидел

[zamtmn]

вариант с перебором n/2 раза не устраивает?

[Disney]

Сообщение от zamtmn вариант с перебором n/2 раза не устраивает?

Что-то я так и не уловил суть этого варианта "научного тыка"

[zamtmn]

Для упрощения буду считать что начальное значение всегда больше конечного. Для наглядности прилагаю график величины шага от номера шага.
Предлагаю разбить график на 2 части: до тоги как величина шага пересекает b и и после. это пересечение возможно только за четное число шагов (включая 0) до последнего шага, отсюда количество n/2 вариантов для перебора.
первая часть графика - линейная интерпретация (или арифметическая прогрессия) от a к b, вторая - состоит из 2х интерпретаций от b к b
по первой части находим x, считаем сумму - если не совпало - сдвигаем точку пересечения и повторяем

upd:
можно попробовать выразить путь от величины шага (x) и номера шага пересечения(n1) и решить систему уравнений
путь(x,n1) = S
и
a-n1*x=b (нпервый член прогрессии от a к b = b)

тогда перебирать не понадобится

[KronSerg]

Вывел уравнение для x, но больно оно заморочное получилось, нет времени решать, дам наводку.
Я ввёл два новых неизвестных Х1 - количество шагов до смены знака, Х2 - количество шагов после смены знака
Вышла система из 3-х уравнений с 3-мя неизвестными
Х1+Х2=n 'Это понятно.
(n-X2)x-X2*x-x=a-b 'Вывел сумму всех шагов через изменение результата
X1*(2a-X1*x-x)/2+X2*(a-X1*x+b)/2=S 'вывел расстояние через сумму n первых членов арифметической прогрессии
Система решается, но заморочно, может дома возьмусь.

[bargool]

Думаю, код на питоне вполне сойдёт за псевдокод, по этому алгоритм должен быть понятен.
Скорость подбора шага можно увеличить, если использовать не тупой перебор, а двоичный поиск
Решал рекурсивно

Код:

[Выделить все]

def path_length(n, a, b, x):
    """
    Функция возвращает расстояние, пройденное за n шагов,
    при этом шаги переменные, изменяются на x
    n: Количество шагов между a и b (в b попадаем на n+1 шаге)
    a: Начальная точка
    b: Конечная точка
    x: Шаг изменения значения точек
    Returns: Пройденный путь
    """
    # Значение текущей точки:
    p = z(a, x, 1)
    # Если n == 1 - мы добрались до последней точки
    if n == 1:
        return p
    # Если при изменении знака шага мы
    # попадём в конечную точку - меняем его
    if z(p, -x, n) == b:
        x = -1*x
    # Идём к следующей точке
    return p + path_length(n-1, p, b, x)

def z(a, x, n):
    """
    Функция возвращает значение точки,
    в которую попадём из текущей за n шагов
    с шагом изменения значения точки x
    a: Начальная точка
    x: Шаг изменения точек
    n: Количество шагов
    """
    return a + x*n

def sign(a):
    """
    Функция возвращает знак числа a
    """
    if a > 0:
        return 1
    elif a < 0:
        return -1
    return 0


# Задаём начальные условия
a = 5.0
b = 4.0
s = 24
n = 7
# Минимальный шаг изменения - идём по прямой от a к b
# Все шаги должны быть кратны этому значению (мне так кажется :))
step = abs((a - b)/(n + 1.0))
x = 0.0
eps = 0.01 # Точность
path = 0.0 # Расчётный путь
# Подбираем шаг, пока расчётный путь не сойдётся с заданным
# Также, шаг ну уж никак не должен превышать сам требуемый путь
while abs(path - s) > eps and x <= s:
    x += step
    path = path_length(n, a, b, x*sign(b-a))

if abs(path - s) > eps:
    print "Нет решения"
else:
    print "Величина шага = %f" % x

Проверял только на паре примеров - работает. Надо конечно больше проверок.

[Disney]

Сообщение от KronSerg Вышла система из 3-х уравнений с 3-мя неизвестными ... Система решается, но заморочено, может дома возьмусь.

Я тоже пытался решить подобную систему уравнений, исписав 10 листов, пришёл к трёхэтажному квадратному уравнению, но подставив в него исходные данные получил не верное решение, видать где-то ошибся
bargool, zamtmn, к сожалению, метод подбора это как-то не по научному , это я привел упрощённый пример, а в действительности количество шагов (n) может быть очень большим.
И как оказалось, пока вполне достаточно равного шага, тупо пут (S) разделить на количество шагов (n)

[DEM]

Disney
Тут наверное больше похоже на логистическую задачу....
Может по искать алгоритмы в этом направлении, потому как перебор не такой уж и большой получается..

[bargool]

Сообщение от Disney метод подбора это как-то не по научному , это я привел упрощённый пример, а в действительности количество шагов (n) может быть очень большим.

нормально, вполне по научному Кол-во шагов тут не сильно влияет.
Численные методы решения уравнений слышал - тоже подбор ))
Только вот я всё туплю - где применяется этот алгоритм в твоей видюшке?
Хочешь, я перепишу свой вариант на c# (заодно оптимизирую), и выдам тебе в виде lisp-функции? Посмотришь, как оно будет работать.
И ещё, дай, пожалуйста, вариант с большим кол-вом n - потестировать.

[KronSerg]

Решил систему, получил это:
-((n+1)^2)*x^2+2*(a*n+b*n-2*s)*x+(a-b)^2=0
На приведённом примере сходится.
Проверил ещё пару на обум, тоже работает.

Соответственно ответ задачи:
x=((a*n+b*n-2*s)+SQRT((a*n+b*n-2*s)^2+((n+1)^2)*((a-b)^2)))/((n+1)^2))

[bargool]

KronSerg, зверь!

[Disney]

Всем спасибо, к сожалению задача не решается в общем случаи, это я пример составлял от обратного, придумал a, придумал b, придумал шаг x, посчитал получившуюся сумму S она соответственно и решилась.

Код:

[Выделить все]

 (defun smoother_step (a b n s / x x1 x2 list_of_step)		     
  (setq	x
	 (/
	   (+ (+ (* a n) (* b n) (* -2 s))
	      (sqrt
		(+
		  (* (+ (* a n) (* b n) (* -2 s))
		     (+ (* a n) (* b n) (* -2 s))
		  )
		  (* (* (1+ n) (1+ n)) (* (- a b) (- a b)))
		)
	      )
	   )
	   (* (1+ n) (1+ n))
	 )
  )
  (setq	x1 (fix (* 2 (/ (- a b) x)))
	x2 (- n x1)
  )
  (repeat x2
    (setq list_of_step (cons (setq b (- b x)) list_of_step))
  )
  (repeat x1
    (setq list_of_step (cons (setq b (+ b x)) list_of_step))
  )
)

Код:

[Выделить все]

(smoother_step 5 4 7 24) -> '(4.5 4.0 3.5 3.0 2.5 3.0 3.5)

в других случаях сумма не сходиться:

Код:

[Выделить все]

(smoother_step 7 4 7 24) -> '(7.12389 6.0826 5.0413 4.0 2.9587 1.9174 2.9587)
(apply '+ '(7.12389 6.0826 5.0413 4.0 2.9587 1.9174 2.9587)) ->30.0826

Сообщение от bargool где применяется этот алгоритм в твоей видюшке?

В том то и дело, что так как не решили, он и не применяться. Я хотел сделать более плавным переход от одного размера шага к другому

[Do$]

А попробуй нарисовать то, что ты хочешь получить. У меня есть подозрение, что это в принципе невозможно.