Здравствуйте, nikov, Вы писали:

N>Пусть S — это наименьшее множество рациональных чисел, содержащее число 0 и удовлетворяющее условию:
N>* Если числа p и q принадлежат S, и |p-q|<1, то число (p+q+1)/2 также принадлежит S.

N>Написать программу, которая принимает рациональное число и определяет, принадлежит ли оно множеству S.

Понятно, что S — некое подмножество конечных двоичных дробей. Так что сразу отвергнем всё то, что разлагается в бесконечные дроби.

Индукционная формула выглядит так:
r = p + (q-p)/2 + 1/2
где 0 <= q-p < 1
С каждой итерацией разрядность увеличивается на 1.
С каждой итерацией получается бОльшее число.

Таким образом, мы можем выполнить NP-полную, но, всё-таки, конечную, проверку.

Берём проверяемое число r, находим его разрядность. Пусть младший разряд назовётся eps.
Получаем уравнение r-1/2 = p+d, 0<=d<1
Для всех d в [0;1) с шагом eps получаем пары p,q = r-1/2-d, r-1/2
Для каждого числа из пары рекурсивно выполняем проверку вхождения в S.