Объявления

Друзья, если не получается зарегистрироваться, напишите на почту vdv_forever@bk.ru.
Я оторву свою задницу от всех дел и обязательно Вас активирую! :smile10:
Добро пожаловать на геройский форум! :smile25:

Математика

Говорим на свободные темы
offlineАватара пользователя
Владимир  
Эксперт
Эксперт
 
Сообщения: 1031
Зарегистрирован: 30 окт 2012, 18:37
Пол: Не указан
Награды: 3
Высшая медаль (1) 1 место 2 этапа по HMM2 (1) Победителю турнира по KB (1)
Поблагодарили: 614 раз.

Re: Математика

Сообщение Владимир » 23 окт 2017, 08:31

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), что не совсем правильно.
Вернуться к началу

offlineАватара пользователя
t800  
Ветеран
Ветеран
 
Сообщения: 982
Зарегистрирован: 22 июл 2015, 11:36
Пол: Не указан
Награды: 4
Наградной знак (1) Деревянный Щит (1) Золотой Меч (1) Серебряные Сапоги (1)
Поблагодарили: 191 раз.

Re: Математика

Сообщение t800 » 23 окт 2017, 10:19

Цитата:
Занятный пример из моей преподавательской практики:
Код: Выделить всё
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 :smile2: то с тех пор я на всю жизнь запомнил, что если не хочешь чтобы тебя дразнили нубом, переменные типа double надо сравнивать как минимум вот так:

Код: Выделить всё
#include <cmath>
#include <limits>

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

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

Код: Выделить всё
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/
Вернуться к началу

offlineАватара пользователя
t800  
Ветеран
Ветеран
 
Сообщения: 982
Зарегистрирован: 22 июл 2015, 11:36
Пол: Не указан
Награды: 4
Наградной знак (1) Деревянный Щит (1) Золотой Меч (1) Серебряные Сапоги (1)
Поблагодарили: 191 раз.

Re: Математика

Сообщение t800 » 28 ноя 2017, 17:34

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

Условие: Вы хозяин машины арбузов, Вам их надо продать. Арбузы в машине: маленькие, средние, большие и очень большие.
у вас есть продавец умеет только считать до ста, знает числа от 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.
Вернуться к началу

offlineАватара пользователя
AlexSpl  
имя: Александр
Эксперт
Эксперт
 
Сообщения: 5539
Зарегистрирован: 17 сен 2010, 12:58
Пол: Мужчина
Награды: 14
Высшая медаль (1) Победителю турнира по HMM1_TE (2) Победителю этапа по HMM1 (1) Победителю этапа по HMM2 (1) Лучшему из лучших (1) 2 место 1 этапа по HMM1 (1)
3 место 1 этапа по HMM1 (1) 1 место 2 этапа по HMM2 (1) Победителю турнира по KB (2) Победителю турнира по KB (1) Грандмастер оффлайн-турниров (1) Боевой шлем (1)
Поблагодарили: 2155 раз.

Re: Математика

Сообщение AlexSpl » 07 фев 2022, 11:54

Так увлёкся игрой 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

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

Код: Выделить всё
/** @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);
}

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

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

offlineАватара пользователя
Владимир  
Эксперт
Эксперт
 
Сообщения: 1031
Зарегистрирован: 30 окт 2012, 18:37
Пол: Не указан
Награды: 3
Высшая медаль (1) 1 место 2 этапа по HMM2 (1) Победителю турнира по KB (1)
Поблагодарили: 614 раз.

Re: Математика

Сообщение Владимир » 07 фев 2022, 13:41

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

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

offlineАватара пользователя
void_17  
имя: DM
Ветеран
Ветеран
 
Сообщения: 530
Зарегистрирован: 25 апр 2021, 15:05
Откуда: Оттуда
Пол: Мужчина
Поблагодарили: 116 раз.

Re: Математика

Сообщение void_17 » 07 фев 2022, 14:43

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

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

offlineАватара пользователя
AlexSpl  
имя: Александр
Эксперт
Эксперт
 
Сообщения: 5539
Зарегистрирован: 17 сен 2010, 12:58
Пол: Мужчина
Награды: 14
Высшая медаль (1) Победителю турнира по HMM1_TE (2) Победителю этапа по HMM1 (1) Победителю этапа по HMM2 (1) Лучшему из лучших (1) 2 место 1 этапа по HMM1 (1)
3 место 1 этапа по HMM1 (1) 1 место 2 этапа по HMM2 (1) Победителю турнира по KB (2) Победителю турнира по KB (1) Грандмастер оффлайн-турниров (1) Боевой шлем (1)
Поблагодарили: 2155 раз.

Re: Математика

Сообщение AlexSpl » 07 фев 2022, 15:18

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

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

 Моё решение
На примере 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].
Вернуться к началу

offlineАватара пользователя
Владимир  
Эксперт
Эксперт
 
Сообщения: 1031
Зарегистрирован: 30 окт 2012, 18:37
Пол: Не указан
Награды: 3
Высшая медаль (1) 1 место 2 этапа по HMM2 (1) Победителю турнира по KB (1)
Поблагодарили: 614 раз.

Re: Математика

Сообщение Владимир » 07 фев 2022, 15:50

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

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

offlineАватара пользователя
AlexSpl  
имя: Александр
Эксперт
Эксперт
 
Сообщения: 5539
Зарегистрирован: 17 сен 2010, 12:58
Пол: Мужчина
Награды: 14
Высшая медаль (1) Победителю турнира по HMM1_TE (2) Победителю этапа по HMM1 (1) Победителю этапа по HMM2 (1) Лучшему из лучших (1) 2 место 1 этапа по HMM1 (1)
3 место 1 этапа по HMM1 (1) 1 место 2 этапа по HMM2 (1) Победителю турнира по KB (2) Победителю турнира по KB (1) Грандмастер оффлайн-турниров (1) Боевой шлем (1)
Поблагодарили: 2155 раз.

Re: Математика

Сообщение AlexSpl » 07 фев 2022, 15:55

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

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

Изображение
Вернуться к началу

Пред.

Вернуться в Поболтаем?

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 8

cron