Рациональные числа
От: nikov США http://www.linkedin.com/in/nikov
Дата: 01.04.17 17:09
Оценка: 6 (2)
Пусть S — это наименьшее множество рациональных чисел, содержащее число 0 и удовлетворяющее условию:
* Если числа p и q принадлежат S, и |p-q|<1, то число (p+q+1)/2 также принадлежит S.

Написать программу, которая принимает рациональное число и определяет, принадлежит ли оно множеству S.
Re: Рациональные числа
От: andyp  
Дата: 01.04.17 21:50
Оценка:
Здравствуйте, nikov, Вы писали:

N>Пусть S — это наименьшее множество рациональных чисел, содержащее число 0 и удовлетворяющее условию:

N>* Если числа p и q принадлежат S, и |p-q|<1, то число (p+q+1)/2 также принадлежит S.

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


Могу начать рассуждение. Для любых положительных l/m, l < m пусть l/m принадлежит S. Тогда, так как 0 принадлежит S, k = (l/m+1)/2 тоже принадлежит S. Видно, что k=(l+m)/2m > 1/2. Далее, число k', принадлежащее S, может быть получено аналогично из 0 и k. Число k' тоже будет больше 1/2. Но тогда (k + k' +1)/2 тоже должно принадлежать S, чего быть не может, так как |(k + k' +1)/2| > 1. Поэтому никакое положительное рациональное l/m в S не попадает. Про отрицательные думать лень.

Про отрицательные: пусть l,m >0; m>l. Тогда если -l/m принадл. S и 0 принадл. S, то и (1-l/m)/2 тоже принадлежит S. Но (m-l)/2m >0 и приходим к рассуждениям из первого абзаца.

Тест на принадлежность к S получается просто сравнением с 0.
Отредактировано 01.04.2017 23:06 andyp . Предыдущая версия .
Re: Рациональные числа
От: kov_serg Россия  
Дата: 01.04.17 23:53
Оценка: 5 (1)
Здравствуйте, nikov, Вы писали:

N>Пусть S — это наименьшее множество рациональных чисел, содержащее число 0 и удовлетворяющее условию:

N>* Если числа p и q принадлежат S, и |p-q|<1, то число (p+q+1)/2 также принадлежит S.

Фигня какая-то:
Если число представимо по степеням двойки p=sum(ai*2^i, i=-inf..inf ) то оно пренадлежит S.
q=p+2e+1 где e=[0..1) = sum(ei*2^-i,i=1..inf)

r=(p+q+1)/2 = p+e => p'=p+k*e где k любое целое

Т.е любые числа представимые в виде суммы по степеням двойки принадлежат S

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

И тут засада т.к. разложение то бесконечное и можно с любой степенью точности разложить например 1/3,
но вот будет оно принадлежать S или нет из постановки задачи не следует.
Re: Рациональные числа
От: Mystic Artifact  
Дата: 02.04.17 00:03
Оценка: +1
Здравствуйте, nikov, Вы писали:

Я понимаю, что это on-topic — но всё таки интересно — зачем/откуда такой вопрос?
Re[2]: Рациональные числа
От: nikov США http://www.linkedin.com/in/nikov
Дата: 02.04.17 01:17
Оценка:
Здравствуйте, andyp, Вы писали:

N>>Пусть S — это наименьшее множество рациональных чисел, содержащее число 0 и удовлетворяющее условию:

N>>* Если числа p и q принадлежат S, и |p-q|<1, то число (p+q+1)/2 также принадлежит S.

A> Но тогда (k + k' +1)/2 тоже должно принадлежать S, чего быть не может, так как |(k + k' +1)/2| > 1.


Вот это я не понял. Почему этого не может быть? В условии же импликация только в одну сторону, а не эквивалентность ("тогда и только тогда").
Re[3]: Рациональные числа
От: andyp  
Дата: 02.04.17 09:03
Оценка:
Здравствуйте, nikov, Вы писали:

N>>>Пусть S — это наименьшее множество рациональных чисел, содержащее число 0 и удовлетворяющее условию:

N>>>* Если числа p и q принадлежат S, и |p-q|<1, то число (p+q+1)/2 также принадлежит S.

A>> Но тогда (k + k' +1)/2 тоже должно принадлежать S, чего быть не может, так как |(k + k' +1)/2| > 1.


N>Вот это я не понял. Почему этого не может быть? В условии же импликация только в одну сторону, а не эквивалентность ("тогда и только тогда").


Числа l/m, k, k', 0 принадлежат S, условие на модуль для парных разностей выполняется (все по модулю меньше 1) => число k_1 = (k+k'+1)/2 принадлежит S. Но |k1 — 0| > 1 и k1 мы включать не должны были => пришли к противоречию. Или я не так понимаю условие?
Re[4]: Рациональные числа
От: nikov США http://www.linkedin.com/in/nikov
Дата: 02.04.17 17:33
Оценка:
Здравствуйте, andyp, Вы писали:

A>Числа l/m, k, k', 0 принадлежат S, условие на модуль для парных разностей выполняется (все по модулю меньше 1) => число k_1 = (k+k'+1)/2 принадлежит S. Но |k1 — 0| > 1 и k1 мы включать не должны были => пришли к противоречию. Или я не так понимаю условие?


"Но |k1 — 0| > 1 и k1 мы включать не должны были" -- вот это ничем не обосновано. Похоже, что ты совершаешь логическую ошибку "denying the antecedent": из "если А, то B" ты выводишь "если не А, то не B".
Re[2]: Рациональные числа
От: nikov США http://www.linkedin.com/in/nikov
Дата: 02.04.17 17:41
Оценка: 11 (2)
Здравствуйте, Mystic Artifact, Вы писали:

MA>Я понимаю, что это on-topic — но всё таки интересно — зачем/откуда такой вопрос?


Множество S -- это так называемые fusible numbers, которые возникают из известной головоломки про точное отмеривание временных интервалов с помощью неравномерно сгорающих фитилей. Эти числа имеют неожиданную связь с ординалами в теории множеств, и ними связан ряд интересных математических теорем и недоказанных гипотез.
Re[5]: Рациональные числа
От: andyp  
Дата: 02.04.17 19:52
Оценка:
Здравствуйте, nikov, Вы писали:

N>"Но |k1 — 0| > 1 и k1 мы включать не должны были" -- вот это ничем не обосновано. Похоже, что ты совершаешь логическую ошибку "denying the antecedent": из "если А, то B" ты выводишь "если не А, то не B".


Кажется понял, что ты хочешь сказать: в множестве S могут существовать такие пары p,q, что |p-q|>=1, но они не могут порождать новые элементы множества. Тогда мои рассуждения неверны . Значит, все-таки неверно понял условие
Re[2]: Рациональные числа
От: kfmn Россия  
Дата: 03.04.17 08:03
Оценка: +2
Здравствуйте, kov_serg, Вы писали:

_>Т.е любые числа представимые в виде суммы по степеням двойки принадлежат S


В условии было еще про минимальность S. А раз так, то точно не любые.

Если p=q, то по условию p+0.5 тоже принадлежит S. Поэтому если принадлежит ноль, то и все целые и полуцелые.
Но вот дальше уже сложнее. Поскольку S принадлежат p=0 и q=1/2, то принадлежит и (p+q+1)/2 = 3/4, и все k/4 для натуральных k>=2. Но вот про 1/4 такого вроде сказать нельзя...
Аналогично, поскольку p=0 и q=3/4, то принадлежат и (p+q+1)/2 = 7/8, а поскольку p=1/2 и q=3/4, то и 9/8. Значит и все k/8 при k>=7. А вот 1/8, 3/8, 5/8 — вроде нет.
Ну и т.д. Вроде получается, что S принадлежат все числа вида k/2^n, где k>=A(n), но вид A(n) остается непонятен...


Т.е. индукция только вверх. И из минимальности S следует, что отрицательных чисел в нем нет!
Re[2]: Рациональные числа
От: vdimas Россия  
Дата: 03.04.17 21:01
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>Фигня какая-то:

_>Если число представимо по степеням двойки p=sum(ai*2^i, i=-inf..inf ) то оно пренадлежит S.

Если оно при этом рациональное, то знаменатель будет степенью двойки после сокращения дроби.
Отредактировано 04.04.2017 16:10 vdimas . Предыдущая версия . Еще …
Отредактировано 03.04.2017 21:17 vdimas . Предыдущая версия .
Отредактировано 03.04.2017 21:14 vdimas . Предыдущая версия .
Re[3]: Рациональные числа
От: kov_serg Россия  
Дата: 03.04.17 22:19
Оценка:
Здравствуйте, kfmn, Вы писали:

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


_>>Т.е любые числа представимые в виде суммы по степеням двойки принадлежат S


K>В условии было еще про минимальность S. А раз так, то точно не любые.


>>Пусть S — это наименьшее множество рациональных чисел, содержащее число 0 и удовлетворяющее условию:

>>* Если числа p и q принадлежат S, и |p-q|<1, то число (p+q+1)/2 также принадлежит S.

(1) q=p: p'=p+1/2, p=p'-1/2 => pk=p0 + k/2
q=p+1/2: p'=(2p+1/2+1)/2=p+3/4 => pk=p0 + k*(1/2+1/4)
q=p+1/2+1/4: p'=p+1/2+1/4+1/8 => pk=p0 + k*(1/2+1/4+1/8)
...
q=p+z: p'+1/2+z/2 => pk=p0+k*(1/2+z/2)
1/2+1/4+1/8 + ... + 2^-m = 1-2^-m
(2) p(k,m)=p0+k*(1-2^-m)
из (1) pk=p0+r
p'(k,m)=p0+k*(1-2^-m)-k=p0-k*2^-m

p'=p+a*2^-m

p'(0)=0+a*2^-m при любом целом a и сколь угодно большом m дают двоичное представление числа.


K>Если p=q, то по условию p+0.5 тоже принадлежит S. Поэтому если принадлежит ноль, то и все целые и полуцелые.

K>Но вот дальше уже сложнее. Поскольку S принадлежат p=0 и q=1/2, то принадлежит и (p+q+1)/2 = 3/4, и все k/4 для натуральных k>=2. Но вот про 1/4 такого вроде сказать нельзя...

Почему?

q=p+2*e-1 => 0<e<1, r=(p+q+1)/2 => r=p+e => p=r-e => pk = p + k*e где любое k-целое

K>Аналогично, поскольку p=0 и q=3/4, то принадлежат и (p+q+1)/2 = 7/8, а поскольку p=1/2 и q=3/4, то и 9/8. Значит и все k/8 при k>=7. А вот 1/8, 3/8, 5/8 — вроде нет.

K>Ну и т.д. Вроде получается, что S принадлежат все числа вида k/2^n, где k>=A(n), но вид A(n) остается непонятен...

K>Т.е. индукция только вверх. И из минимальности S следует, что отрицательных чисел в нем нет!


почему o_O ?
Re[3]: Рациональные числа
От: biocoder  
Дата: 04.04.17 00:13
Оценка:
Здравствуйте, vdimas, Вы писали:

V>Из постановки задачи следует, что существуют такие ei, для которых выполняется система уравнений:

V>(для только положительных значений, поэтому без модуля)
V>ex=ey+2ez+1
V>...

Это уравнение, похоже, неверно. В условии сказано: "Если числа p и q принадлежат S, и |p-q|<1, то число (p+q+1)/2 также принадлежит S."
Т. е., должно быть ex = -ey + 2ez — 1.
Re[4]: Рациональные числа
От: Eugene Sh Россия  
Дата: 04.04.17 01:53
Оценка: +1
Здравствуйте, kov_serg, Вы писали:

K>>Т.е. индукция только вверх. И из минимальности S следует, что отрицательных чисел в нем нет!

_>почему o_O ?
Если в каком-то S есть отрицательные числа, то давайте построим S', который будет состоять только из неотрицательных чисел, входящих в S.
S' тоже будет удовлетворять условию задачи. И ещё оно будет меньше, чем S. А это значит, что S никак не может быть ответом.
Re[5]: Рациональные числа
От: vdimas Россия  
Дата: 04.04.17 10:32
Оценка:
Здравствуйте, Eugene Sh, Вы писали:

K>>>Т.е. индукция только вверх. И из минимальности S следует, что отрицательных чисел в нем нет!

_>>почему o_O ?
ES>Если в каком-то S есть отрицательные числа, то давайте построим S', который будет состоять только из неотрицательных чисел, входящих в S.
ES>S' тоже будет удовлетворять условию задачи. И ещё оно будет меньше, чем S. А это значит, что S никак не может быть ответом.

Если в каком-то S есть положительные числа, то давайте построим S', который будет состоять только из отрицательных чисел, далее по тексту. ))

На самом деле оба утверждения не верны, согласно условию.
Re[6]: Рациональные числа
От: kfmn Россия  
Дата: 04.04.17 10:38
Оценка:
Здравствуйте, vdimas, Вы писали:

V>Здравствуйте, Eugene Sh, Вы писали:


K>>>>Т.е. индукция только вверх. И из минимальности S следует, что отрицательных чисел в нем нет!

_>>>почему o_O ?
ES>>Если в каком-то S есть отрицательные числа, то давайте построим S', который будет состоять только из неотрицательных чисел, входящих в S.
ES>>S' тоже будет удовлетворять условию задачи. И ещё оно будет меньше, чем S. А это значит, что S никак не может быть ответом.

V>Если в каком-то S есть положительные числа, то давайте построим S', который будет состоять только из отрицательных чисел, далее по тексту. ))


Если какое-то p число принадлежит S, то и все числа вида p+k/2 — тоже принадлежат для любого натурального k. Поэтому только отрицательными ограничиться не получится. К тому же по условию ноль содержится в S.
А вот только неотрицательными — вполне. Потому что (p+q+1)/2 больше чем p и q, и индукция вправо по оси возможна, а вот влево — нет.
Re[7]: Рациональные числа
От: vdimas Россия  
Дата: 04.04.17 12:26
Оценка:
Здравствуйте, kfmn, Вы писали:

V>>Если в каком-то S есть положительные числа, то давайте построим S', который будет состоять только из отрицательных чисел, далее по тексту.

K>Если какое-то p число принадлежит S, то и все числа вида p+k/2 — тоже принадлежат для любого натурального k.

Там неточность условия в том, что в формуле (p+q+1)/2 должно было оговариваться, что p и q — это уникальные элементы множества.
Иначе задача не имеет решения.


K>Поэтому только отрицательными ограничиться не получится.


Я не ограничивался отрицательными специально, это получилось в результате вычислений.


K>К тому же по условию ноль содержится в S.


При условии уникальности p и q — да.
Иначе получалось противоречие сходу, т.к. 1/2 не является элементом мн-ва.


K>А вот только неотрицательными — вполне. Потому что (p+q+1)/2 больше чем p и q,


Это только для положительных p и q верно.
Для отрицательных — зависит от (p+q+1).
Например, чтобы получить элемент мн-ва 0, (p+q+1) должно быть равно 0-лю, т.е. отрицательные числа должны входить в мн-во.


K>и индукция вправо по оси возможна, а вот влево — нет.


Следовательно, дальнейшие рассуждения неверные.
Re[8]: Рациональные числа
От: kfmn Россия  
Дата: 04.04.17 12:33
Оценка: +1
Здравствуйте, vdimas, Вы писали:

V>Там неточность условия в том, что в формуле (p+q+1)/2 должно было оговариваться, что p и q — это уникальные элементы множества.

Уникальные, значит различные?
nikov про это в условии не писал, и любое определение fusible numbers открой — там этого нет.

V>Иначе задача не имеет решения.

Объясни, почему.

K>>К тому же по условию ноль содержится в S.


V>При условии уникальности p и q — да.

V>Иначе получалось противоречие сходу, т.к. 1/2 не является элементом мн-ва.

Откуда это?
Re[9]: Рациональные числа
От: vdimas Россия  
Дата: 04.04.17 13:56
Оценка:
Здравствуйте, kfmn, Вы писали:

V>>Иначе получалось противоречие сходу, т.к. 1/2 не является элементом мн-ва.

K>Откуда это?

Из условия. Иначе получается растущее вправо бесконечное мн-во, т.е. речи о его минимальности быть не может.
Т.е., мн-во fusible numbers бесконечно.

Тогда принадлежность к нему определяется элементарно (ответил сразу же):

Если оно при этом рациональное, то знаменатель будет степенью двойки после сокращения дроби.


Итого, решение:
UPD (сравнить с 0-лем):
bool isFusible(uint numerator, uint denominator) {
    assert(denominator);
    if(!numerator) return true;
    uint a = numerator, b = denominator;
    while(a!=b) if(a>b) a-=b; else b-=a;
    denominator/=a;
    return !(denominator&(denominator-1));
}
Отредактировано 04.04.2017 16:47 vdimas . Предыдущая версия . Еще …
Отредактировано 04.04.2017 16:15 vdimas . Предыдущая версия .
Отредактировано 04.04.2017 16:07 vdimas . Предыдущая версия .
Re: Рациональные числа
От: Кодт Россия  
Дата: 04.04.17 14:25
Оценка:
Здравствуйте, 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.

Перекуём баги на фичи!
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.