1. Этот сайт использует файлы cookie. Продолжая пользоваться данным сайтом, Вы соглашаетесь на использование нами Ваших файлов cookie. Узнать больше.

Помогите решить неравенство

Тема в разделе "В помощь учащимся", создана пользователем The Chief, 14.11.13.

  1. The Chief

    The Chief Активный участник

    11.674
    944
    a^3-(a-1)^3 <= b, где a, b - целые положительные. Нужно решение в общем виде, a<=f(b).
     
  2. Ашатан

    Ашатан Активный участник

    4.086
    22
    Фу, блин... Дошла до a^2-a и зависла.
     
  3. The Chief

    The Chief Активный участник

    11.674
    944
    Упрощаем, 3a^2−3a+1 <= b , а дальше?

    Всё, нашёл, ещё проще, a^2-a <= (b-1)/3, т.е. a <= int (sqrt ((b-1)/3)
     
    Последнее редактирование: 14.11.13
  4. b70

    b70 Активный участник

    4.385
    173
    решаете квадратное уравнение, очевидно
     
  5. The Chief

    The Chief Активный участник

    11.674
    944
    Ашатан, спасибо, навели на путь истинный. :flower:

    ---------- Сообщение добавлено 14.11.2013 13:22 ----------

    b70, я-я, натюрлих. Сам сообразил.
     
  6. b70

    b70 Активный участник

    4.385
    173
    The Chief, ответ сверим?)))
     
  7. The Chief

    The Chief Активный участник

    11.674
    944
    b70, мне нужен был оценочный результат для положительных целых a. На самом деле:
    1 <= a <= (1 + sqrt( 1 + 4*c ))/2, где c = (b-1)/3.
     
  8. b70

    b70 Активный участник

    4.385
    173
    Вероятно, имелось ввиду:
    ((1 - sqrt( 1 + 4*c ))/2) <= a<= ( (1 + sqrt( 1 + 4*c ))/2), при b>=1/4 )))
     
  9. The Chief

    The Chief Активный участник

    11.674
    944
    b70, да, пардон. Именно так, только нижняя граница = 1. b>=1/4 входит в условие «a, b - положительные целые».

    PS: нужно было для оценки верхней границы цикла for a = 1 to … при известном b. :) Для больших b оценка int(sqrt(b/3)) даёт хороший результат.

    PPS: ещё бы попробовать прикинуть нижнюю границу (начало цикла)… но я там зависимость формульно не могу вывести.
     
    Последнее редактирование: 14.11.13
  10. panda-34

    panda-34 Активный участник

    1.589
    2
    Дополнительно стоит проверить в целых числах равенство b == 1 - 3 a + 3 a^2, при вычислении "<=" с плавающей точкой, мимо "=" можно и пролететь.
     
  11. b70

    b70 Активный участник

    4.385
    173
    при подстановке b=1 в нижнюю границу, начало цикла по целому а=1... вроде так.
     
  12. The Chief

    The Chief Активный участник

    11.674
    944
    b70, нет, это неравенство определяет только верхнюю границу цикла. Нутром чую, что нижняя — кубический корень из b (from b^(1/3) to sqrt(b/3), работает для b>27, у меня b >> 1000), но доказать не могу. :)

    ---------- Сообщение добавлено 14.11.2013 15:12 ----------

    panda-34, настолько точно не надо. Хотя да, проверить надо, это будет особый случай и вообще в цикл можно будет не входить.
     
  13. b70

    b70 Активный участник

    4.385
    173
    The Chief, а, понял. Ну, чем мог...
     
  14. The Chief

    The Chief Активный участник

    11.674
    944
    Есть, нашёл ограничение на начало цикла. from (b/2)^(1/3) to (b/3)^(1/2), плюс проверка нескольких особых случаев. Всем спасибо. Пошёл писать код.
     
  15. b70

    b70 Активный участник

    4.385
    173
    Не за что.
    Однако, вероятно, имелось ввиду следующее:
    from (int((b/2)^(1/3))+1) to (int((b/3)^(1/2))
    Удачи!!
     
  16. The Chief

    The Chief Активный участник

    11.674
    944
    Да. Оптимизация, блин, такая оптимизация…