Вопросы доказательства основной теоремы

Question

Я читаю книгу CLRS(Введение в Алгоритмы, 3-е издание) и нахожу, что в доказательстве основной теоремы есть ошибка. На странице 104, чтобы распространить доказательство на все целые числа, используется одно неравенство, которое кажется неверным. В книге сказано, что:

Наша первая цель состоит в том, чтобы определить глубину k так, чтобы nk была константой. Используя неравенство [x]<=x+1, получим

[х] здесь означает потолок х, очевидно, что [x] < x+1 не [x] <= x+1, Кроме того, на странице 54 есть еще одно неравенство, подтверждающее то, что я думаю

x -1 <  flooring(x) <= x <= ceiling(x) < x+1

Кто-нибудь может помочь уточнить это, почему они конфликтуют? если это неравенство неверно, то все доказательство не будет правильным

Answer 1

Разделить на два случая:

1. [x] > x ---> [x] < x+1 (тривиально, и я думаю, что вы согласны с этим)
2. [x] = x ---> [x]+1 = x + 1 ---> [x] < x+1

Аналогично для x-1 < floor(x), разделить на два случая:

1. floor(x) < x ---> floor(x) > x-1
2. floor(x) = x ---> floor(x) - 1 = x - 1 ---> floor(x) > x-1

Итак, в последнем уравнении - все осталось floor(x)<=c<=ceil(x) - что в значительной степени прямо из их определения, и из двух приведенных выше утверждений мы получаем, что:

x -1 <  flooring(x) <= x <= ceiling(x) < x+1