Математика

[Владимир]

t800 писал(а):

...и равны ли числа или нет проверяются эпсилоном (мне это на Game Dev объясняли)...

Ну почему обязательно по эпсилону? Некоторые алгоритмы допускают и проверку на точное равенство.
Занятный пример из моей преподавательской практики:

Код: Выделить всё

c=(a+b)/2;
do
{
if(f(c)==0)break;
if(f(c)*f(a)>0)a=c;
else b=c;
с=(a+b)/2;
}
while(a<c && c<b);
printf("%lg",c);

Поскольку тип double на отрезке [a;b] содержит конечное количество чисел, которое уменьшается с каждым шагом алгоритма, однажды c=(a+b)/2 станет равным или a или b.
Обычно условие выхода из цикла пишут как (b-a>epsilon), что не совсем правильно.

Цитата:

Занятный пример из моей преподавательской практики:

Код: Выделить всё

c=(a+b)/2;
do
{
if(f(c)==0)break;
if(f(c)*f(a)>0)a=c;
else b=c;
с=(a+b)/2;
}
while(a<c && c<b);
printf("%lg",c);

Помню когда я на Game Dev как-то написал код с оператором сравнения == для типа double и меня чуть было из-за этого не убили см. http://www.gamedev.ru/flame/forum/?id=229038&page=7#m97 то с тех пор я на всю жизнь запомнил, что если не хочешь чтобы тебя дразнили нубом, переменные типа double надо сравнивать как минимум вот так:

Код: Выделить всё

#include <cmath>
#include <limits>

bool is_equal(double x, double y) {
return std::fabs(x - y) < std::numeric_limits<double>::epsilon();
}


 P.S.

А вообще числа с плавающией точкой лучше сравнивать преобразованием к целочисленной переменной

Код: Выделить всё

bool AlmostEqual2sComplement(float A, float B, int maxUlps) {
    // maxUlps не должен быть отрицательным и не слишком большим, чтобы
    // NaN не был равен ни одному числу
    assert(maxUlps > 0 && maxUlps < 4 * 1024 * 1024);
    int aInt = *(int*)&A;
    // Уберем знак в aInt, если есть, чтобы получить правильно упорядоченную последовательность
    if (aInt < 0) aInt = 0x80000000 - aInt;
    // Аналогично для bInt
    int bInt = *(int*)&B;
    if (bInt < 0) bInt = 0x80000000 - bInt;
    unsigned int intDiff = abs(aInt - bInt);
    if (intDiff <= maxUlps)
    return true;
    return false;
}


см. https://habrahabr.ru/post/112953/

Есть задачка, ее надо решить.

Условие: Вы хозяин машины арбузов, Вам их надо продать. Арбузы в машине: маленькие, средние, большие и очень большие.
у вас есть продавец умеет только считать до ста, знает числа от 0 до 100, не говорит по русски и неисправный калькулятор.
У калькулятор неисправность такая: при сложении и умножении некоторых чисел он выдает NaN, для всех остальных чисел считает правильно.
для каких именно чисел калькулятор Выдает NaN вы не знаете, но точно знаете что для действий

1+2 = 3
1+3 = NaN
1+4 = 5

Т.е. Калькулятор выдает NaN при сложении чисел 1+3, но для каких еще чисел калькулятор Выдает NaN вы не знаете, знаете лишь, что
такие ошибки у Калькулятора распределены по какой-то зависимости Вам не известной

Задача: Нужно придумать схему как Продавец должен делать расчеты с покупателями за Арбузы, чтобы по результатам дня продать все арбузы,
не остаться в убытке и в тоже время торговать более-менее честно, - для придуманной схемы оценить ошибки и погрешности.

Примечание 1: Продавец продает арбузы штучно (1, 2 , 3 штуки, но всегда меньше 100 ) цена арбуза зависит от размера и выражена в целых числах, т.е. Продавец на Калькуляторе выполняет операции сложения и умножения с целыми числами,

Примечание 2: Cдачу продавец не дает, т.е. считать что сделав расчет Продавец показывает на Табло Калькулятора Покупателям сколько они должны заплатить за Арбузы и те с ним всегда рассчитываются без сдачи.

Примечание 3: Продавец торгует Арбузами без весов, размеры измеряет на глаз: маленький, средний, большой, очень большой, цена Арбузов выражена
в целых числах в интервале от 1 до 100.

Так увлёкся игрой Bitburner, что решил начать выполнять контракты. Условие одного из них следующее (не дословно, но суть та же): найти количество возможных разбиений заданного натурального числа как минимум на два натуральных слагаемых.

Например, число разбиений для числа 4 равно 4:

4 = 1 + 1 + 1 + 1
4 = 2 + 1 + 1
4 = 2 + 2
4 = 3 + 1

Для числа 5 равно 6:

5 = 1 + 1 + 1 + 1 + 1
5 = 2 + 1 + 1 + 1
5 = 2 + 2 + 1
5 = 3 + 1 + 1
5 = 3 + 2
5 = 4 + 1

Задачка довольно простая и известная (на рекурсию). Но решал ли я её самостоятельно, не помню уже. Так вот, так как я играю по-честному, то решил без гугла. Оказалось, не такая она уже и простая Пришлось очень хорошенько напрячься, чтобы получить работающий алгоритм, да такой, чтобы не было за него стыдно, т.е. без всяких там массивов и прочих костылей. Получился весьма интересный алгоритм:

Код: Выделить всё

/** @param {NS} ns **/
function ways_to_sum(n, lim)
{
   let waysToSum = 0;
   
   if (n > 1) {
      for (let i = 2; i <= n; ++i) {
         if (i < lim) {
            for (let j = 0; j < Math.floor(n / i); ++j) {
               waysToSum += 1 + ways_to_sum(n - i * (j + 1), i);
            }
         }
      }
   }

   return waysToSum;
}

export async function main(ns)
{
   const n = ns.args[0];
   const lim = ns.args[1];
   let total_ways_to_sum = 1 + ways_to_sum(n, lim);

   ns.tprint("There are " + total_ways_to_sum + " ways to sum " + n);
}

А главное - он работает Так вот, решил я посмотреть на решение этой проблемы в Интернете. Нашлись разные, но именно такого решения пока не нашёл. Довольно быстрый получился для рекурсивного

* * *
А вот уже задачка для учёных и немножко для философов Доказать или опровергнуть гипотезу о том, что можно создать вычислительную систему, на которой рекурсивные алгоритмы будут выполняться быстрее итеративных линейных, т.е. не просто быстрее, а быстрее уже существующих. На вычислительных системах с бесконечной памятью, а, следовательно, и стеком, и O(1) скоростью выделения памяти, рекурсия, думаю, будет быстрее итерации. Только сложно представить себе систему с бесконечной памятью (а ещё сложнее - с "рекурсивной" памятью). Для итеративных алгоритмов самый ценный ресурс - время, которое мы считаем бесконечным, но всё равно жалуемся и плюёмся в экран на медленные алгоритмы. Для рекурсивных алгоритмов самый ценный ресурс - память, которая, в отличие от времени, не бесконечна. Но тут уже философия. Мы, например, не готовы ждать 100 млн лет результатов работы алгоритма (так что для конкретного человека время как раз таки вполне конечно)

[Владимир]

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

Задачку попроще, а именно - "найти сами различные разбиения на слагаемые", я каждый год даю группе в качестве упражнения. Каждый раз её решают 1-2 человека. А решение - очень похожее, да.

>каждый год даю группе в качестве упражнения

Воу, не знал что тут есть препода...
Как же я люблю сопромат

Цитата:

Задачку попроще, а именно - "найти сами различные разбиения на слагаемые", я каждый год даю группе в качестве упражнения. Каждый раз её решают 1-2 человека. А решение - очень похожее, да.

И то, наверное, потому что раньше решали/читали Кнута Студентам любую "легкотню" дай решить, отключив Интернет, - и шансы на успех устремятся к нулю Решат, может быть, только "натасканные" на задачках и проработавшие кучу похожих алгоритмов до этого. Ведь проблема не "запрограммировать", а понять, как вообще подступиться к задаче, а тут уже нужен ум и сообразительность Вот Вы сходу угадаете идею, стоящую за алгоритмом выше?

 Моё решение

На примере 7-ки:

1) 7 = 1 + 1 + 1 + 1 + 1 + 1 + 1 (у любого натурального числа, которое можно представить как минимум 2-мя другими натуральными числами, будет вариант из единичек).
2) Далее считаем, сколько 2-ек, 3-ек, ..., (n - 1)-ек может входить в сумму - floor(n / i):

7 = 2 + 1 + 1 + 1 + 1 + 1
7 = 2 + 2 + 1 + 1 + 1
7 = 2 + 2 + 2 + 1, т.е. floor(7 / 2) = 3.

7 = 3 + 1 + 1 + 1 + 1
7 = 3 + 3 + 1, т.е. floor(7 / 3) = 2 и т.д.

3) Запускаем рекурсию по единичкам (можно начинать прямо с 3-ки): 7 = 3 + 1 + 1 + 1 + 1 = 3 + f(4, {limit: 3}) и 7 = 3 + 3 + 1 = 6 + f(1, {limit: 3}).

Похоже, сломался тэг [color].

[Владимир]

Дело в том, что я сам не читал ни Кнута, ни Дийкстру, ни Ахо. В разложении идём от больших слагаемых к меньшим, и всё получается.

Да, я Диме писал уже, что color сломался. Тэг работает, если набрать его вручную, просто кнопка его не вставляет в сообщение.

Я пробовал вручную, не работает. Ой, заработал, а в Preview не работает

Вот как выглядит контракт в игре. 15 - это ещё маленькое число (мало репутации за решение дают):