Задачки

[m_ax]

нет, можно еще меньше.

Lagovas , не подсказывайте)) Мы ещё подумаем)

[m_ax]

И так, кажется назрело решение))

Во-первых всего хранилищь как и раньше 3. На расстояниях 500/3, 2*500/3 и 500 миль.
Будучи в самом начале пустыни с заполненым баком, хранилища должны быть заполнены каждое 1/3 бака.
Теперь последовательно посчитаем сколько нужно топлива, чтоб наполнить каждое хранилище и при этом оказаться в начале пустыни.
1) Для заполнения первого хранилища 1/3 бака нужно 1 бак.
2) Для заполнения только второго хранилища 1/3 бака нужно 3 бака
3) Для заполнения третьего хранилища 1/3 бака нужно 5 баков.

Итак, всего вкупе нужно (5+3+1) + 1 = 10 баков = 5000 галлонов   

[Lagovas]

И даже это не самое оптимальное решение)

[m_ax]

Если сделать 6 хранилищь, на расстоянии
S_i = i/6 * 500 (i = 1,2,3,4,5,6)
То получается что можно обойтись 9 баками, т.е. 9 * 500 = 4500 галлонов.
Опять не факт, что это оптимальный вариант.
Надо попробывать решить эту задачу в общем случае.

[Lagovas]

Вы близки, но это еще не самый оптимальный способ.

[m_ax]

Решил в общем случае.

Ход решения такой:
Разбиваем первые 500 миль пути на n точек:
0, 500/n, 2*500/n, ...,  (n-1)*500/n, 500.

Пусть всего необходимо N баков горючего.
Тогда, доставляя эти N баков до первого хранилища (500/n)
получим:
N - (2*s1+1)/n = N_1;
где s1 - целое число (1,2,3,...)
Второе уравнение:
N_1 - (2*s2+1)/n = N_2;
и так далее.

Получается рекурентное соотношение.
Терерь учтём, что N_n = 1 и запишем систему с другог конца:

N_(n-1) - (2*s1+1)/n = 1;
N_(n-2) - (2*s2+1)/n = N_(n-1);
...
N_(0) - (2*sn+1)/n = N_(1);

Вначале определяем N_(n-1) = 1 + (2*s1+1)/n.
s1 - берём минимально возможным.
Например, для n=6, s1 = 1.

И так по цепочке добираемся до N_(0).

Вот программка, которая считает N_(0), как функцию n.

Код

C++ (Qt)
#include <iostream>
#include <fstream>
#include <cmath>
 
double func(int n) {
    double v = 1.0;
    for (int i = 0; i < n; ++i) {
        int l = 0;
        while (true) {
            l++;
            int s = (int)ceil(double(2*l+1)/double(n)+v)-1;
            if (l==s) break;
        }
        v += (2.0*l+1.0)/double(n);
    }
    return v;
}
 
int main()
{
    std::ofstream out("test.txt");
    for (int i = 3; i < 50; ++i) {
        out << i << " " << func(i) << std::endl;
    }
    return 0;
}
 

   
А вот график зависимости N (в баках, левая ось и в галлонах - правая) от числа разбиений n.

Минимальное целое значение баков = 8 т.е. 4000 галлонов. Однако, это значение соответствует нескольким значениям n. 

[Igors]

Ход решения такой:
Разбиваем первые 500 миль пути на n точек:
0, 500/n, 2*500/n, ...,  (n-1)*500/n, 500.

Так что, расстояние между точками (0, 1) такое же как и между (1, 2)? Это очевидно неоптимально - ведь доставлять топливо дальше дороже

Принципиально как ставить точки, Для первой все ясно 1/3 бака. Но я не могу придумать рекуррентное соотношение для второй. Если "на шару" то просто золотым сечением - даже если это будет неоптимально, то близко

[m_ax]

Ход решения такой:
Разбиваем первые 500 миль пути на n точек:
0, 500/n, 2*500/n, ...,  (n-1)*500/n, 500.

Так что, расстояние между точками (0, 1) такое же как и между (1, 2)? Это очевидно неоптимально - ведь доставлять топливо дальше дороже

Принципиально как ставить точки, Для первой все ясно 1/3 бака. Но я не могу придумать рекуррентное соотношение для второй. Если "на шару" то просто золотым сечением - даже если это будет неоптимально, то близко

Я считаю, что правильное значение суммарного топлива, мы получим в пределе больших n.
И это значение (в баках) V = 7.6730...  т.е. 7.673*500 = 3836.5 галлон

[m_ax]

Всё. до меня дошло как она решается))

Нужно начинать с конца т.е. с отметки 500 миль.
Первое уравнение для колличества топлива в предыдущем хранилище:
V - (2*s+1)*L = 1
Здесь L - расстояние от последнего хранилища до предыдущего.
s - целое число = 1,2,3,..
Начинаем с самых малых s.
s=1, тогда
V = 1+3*L <= s+1
Получаем, что L = 1/3, V = 2

Далее проделываем всё для следующего хранилища:
V - (2*s+1)*L = 2
V = 2+(2*s+1)*L <= s+1
Здесь минимальное s = 2
V = 2+5*L <= 3
L = 1/5, V = 3.

И так далее.
Получаем следующий ряд:
0  1/3  1/5  1/7  1/9  1/11  1/13
1  2     3     4     5     6      7

Получается, что при 7 баках мы проедем S = (1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/13) * 500 миль.
Тогда первое хранилище нужно расположить на расстоянии S1
S1 = (1 - 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/13) * 500 миль = 2021/45045 * 500 миль
И находится там с 7 баками
Теперь легко найти скмарное колличество топлива:
V - (2*s + 1)*2021/45045 = 7
V = (2*s+1)*2021/45045 + 7 <= s+1
s = 7,
V = 15*2021/45045 + 7 = 7.67299367299...

V = 7.67299367299 баков или 7.67299367299 * 500 = 3836.49683650 галлон

[Igors]

Нужно начинать с конца т.е. с отметки 500 миль.
Первое уравнение для колличества топлива в предыдущем хранилище:
V - (2*s+1)*L = 1
Здесь L - расстояние от последнего хранилища до предыдущего.
s - целое число = 1,2,3,..
Начинаем с самых малых s.
s=1, тогда
V = 1+3*L <= s+1
Получаем, что L = 1/3, V = 2

Интересно, но пожалуйста дайте возможность мне (а может и другим) Вас понять. Во-первых предъявляем формулы с полным списком используемых переменных и поясняем откуда взялись "условные единицы". Во-вторых где начало а где конец - у Вас не разберешь Получается что расстояние от последнего хранилища (на отметке 500, посередине пустыни) до предыдущего = 1/3 (т.е. 500 / 3) самое большое или как? 

Ну и в-третьих: есть ли желание решать др задачки - но в реальном проекте и, возможно, за деньги? (это вопрос не ко всем а к m_ax лично)

[m_ax]

Интересно, но пожалуйста дайте возможность мне (а может и другим) Вас понять. Во-первых предъявляем формулы с полным списком используемых переменных и поясняем откуда взялись "условные единицы". Во-вторых где начало а где конец - у Вас не разберешь. Получается что расстояние от последнего хранилища (на отметке 500, посередине пустыни) до предыдущего = 1/3 (т.е. 500 / 3) самое большое или как?

Хорошо, постараюсь не так сумбурно объеснить ход мыслей:

Пусть имеется n хранилищь. Сколько точно мы пока не знаем. Но мы знаем, что хранилище № n должно находится на расстоянии 500 миль и там должен быть 1 бак.
Далее топливо я буду мерить в баках, а расстояния отнесённые к 500 милям, т.е. L = 1 соответствует 500 миль.

Пусть теперь, хранилище № (n-1) находится на расстоянии L от хранилища № n.
Пусть там всего V баков. Это V можно представить себе в виде суммы:
V = (2*s+1)*L + 1,
где (2*s+1) - число переездов туда-сюда (нечётное), а (2*s+1)*L - топливо, потраченное на перевозку топлива из хранилища № (n-1) в хранилище № n.
Естественно, что потраченное на перевозку топливо должно быть как можно меньше.
Пробуем s = 1:
V = 3*L+1,
но с другой стороны должно выполняться условие V <= s+1.
s+1 - соответствует максимально-возможному колличесву топлива, которое мы можем забрать при (2*s+1) переездах.
Соответственно получаем первое уравнение:
3*L+1 <= s+1 = 2
откуда находим
L = 1/3 т.е. 1/3 * 500 миль
V = 2 бака

Аналогичное уравнение строим для хранилища № (n-2)
V = (2*s+1)*L + 2
пробуем s = 1:
3*L + 2 <= s+1 = 2
и видим, что s = 1 не удовлетворяет неравенству. Пробуем s = 2:
5*L + 2 <= s+1 = 3
Получаем
L = 1/5
V = 3

Продолжаем эту процедуру. И приходим к следующему выводу:
Хранилище (n) - содержит 1 бак
Хранилище (n-1) находится на расстоянии 1/3 от хранилища (n) и содержит 2 бака
Хранилище (n-2) находится на расстоянии 1/5 от хранилища (n-1) и содержит 3 бака
Хранилище (n-3) находится на расстоянии 1/7 от хранилища (n-2) и содержит 4 бака
Хранилище (n-4) находится на расстоянии 1/9 от хранилища (n-3) и содержит 5 бака
Хранилище (n-5) находится на расстоянии 1/11 от хранилища (n-4) и содержит 6 бака
Хранилище (n-6) находится на расстоянии 1/13 от хранилища (n-5) и содержит 7 бака

Суммарное расстояние от хранилища (n) в направлении к началу пустыни S:
S = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/13
следовательно (n-6) хранилище находится на расстоянии S1 = 1-S от начала пустыни:
S1 = 2021/45045 т.е. 2021/45045 * 500 миль
В этом хранилище нам нужно быть с 7 баками. Тогда последнее уравнение есть:
V = (2*s+1)*S1 + 7 <= s+1
Оно удовлетворяет при минимальном s = 7. Тогда получаем
V = 15 * S1 + 7 = 15 * 2021/45045 + 7 баков, т.е. (15 * 2021/45045 + 7)*500 галлон.

Ну и в-третьих: есть ли желание решать др задачки - но в реальном проекте и, возможно, за деньги? (это вопрос не ко всем а к m_ax лично)

Это я Вам напишу в личку 
 

   

[Igors]

Пусть имеется n хранилищь. Сколько точно мы пока не знаем. Но мы знаем, что хранилище № n должно находится на расстоянии 500 миль и там должен быть 1 бак.
Далее топливо я буду мерить в баках, а расстояния отнесённые к 500 милям, т.е. L = 1 соответствует 500 миль.

Пожалуйста не поймите меня превратно (мол, невнимательно читал Ваш пост, сразу бросился спорить) - но с какого перепугу а последнем хранилище должен быть 1 бак? Ведь натаскать его сюда явно дороже, почему бы не выехать с полным баком и потом все время дозаправляться "чем дальше - тем меньше" - но продолжать путь с полным баком?

[m_ax]

Пусть имеется n хранилищь. Сколько точно мы пока не знаем. Но мы знаем, что хранилище № n должно находится на расстоянии 500 миль и там должен быть 1 бак.
Далее топливо я буду мерить в баках, а расстояния отнесённые к 500 милям, т.е. L = 1 соответствует 500 миль.

Пожалуйста не поймите меня превратно (мол, невнимательно читал Ваш пост, сразу бросился спорить) - но с какого перепугу а последнем хранилище должен быть 1 бак? Ведь натаскать его сюда явно дороже, почему бы не выехать с полным баком и потом все время дозаправляться "чем дальше - тем меньше" - но продолжать путь с полным баком?

Последнее хранилище находится ровно посередине пустыни (500 миль). Одного бака будет достаточно, чтоб пересечь оставшеюся половину пустыни.
В смысле, когда мы приезжаем к последнему хранилищу у нас в сего один бак топлива. Заливаем его и едем до конца уже не парясь)   

[kuzulis]

А мне кажется, что невозможно вообще пересечь пустыню, т.к. расход 500 гал/милю (т.е. проедем 500 миль без дозоправки).
Но длина пустыни 1000 миль, плюс еще (по условию задачи), необходимо из бака по ходу движения заполнять хранилища на пути =>
получается, что мы еще будем перерасходовать горючку из бака машины, поэтому проедем вообще менее 500 миль!

----
Ай, тьфу, ступил  

Это типа нужно ехать в пустыню, ставить там новое хранилище и заправлять его, возвращаться назад, заправляться, ехать опять в пустыню, ставить еще хранилище (может быть, подзаправившись из предыдущего хранилища), ехать назад и т.п..

Жёсткая задачка. 

[Lagovas]

Все, решили) В методичке ответ 3837,5. В общем смысл правильный, но насколько я помню, у него в некоторых случаях есть язьяны, если юзать в реальной жизни. Мы делали решение на паскале, и там при каких то расстояниях выходило очень большое количество действий, и расстояния были очень маленькими. И что бы проехать те расстояния, человеку не хватило бы жизни) А вообще молодец, решил. Вот файлик с этой задачи выложу, заслужил)
http://floomby.ru/content/55PT6XIANk/