Re[10]: Рациональные числа
От: samius Япония http://sams-tricks.blogspot.com
Дата: 04.04.17 15:11
Оценка:
Здравствуйте, vdimas, Вы писали:

K>>и любое определение fusible numbers открой — там этого нет.


V>Открыл — есть:

V>http://googology.wikia.com/wiki/Fusible_number

V>По условию, данному по ссылке, нет смысла проводить идентичные манипуляции с разными фитилями, т.к. по условию они идентичны и сгорают полностью за одно и то же время.


(все, что ты открываешь, читаешь не вникая)

Formally, a real number xx is fusible if and only if x=0 or x=(a+b+1)/2, with a and b fusible numbers and |a−b|<1


Итак, если взять исходно x=0, то где же взять уникальные a и b из множества? С уникальным подходом множество fusible одноэлементно.
Re[11]: Рациональные числа
От: vdimas Россия  
Дата: 04.04.17 16:52
Оценка:
Здравствуйте, samius, Вы писали:

V>>По условию, данному по ссылке, нет смысла проводить идентичные манипуляции с разными фитилями, т.к. по условию они идентичны и сгорают полностью за одно и то же время.

S>(все, что ты открываешь, читаешь не вникая)

Кто бы говорил. ))


S>

S>Formally, a real number xx is fusible if and only if x=0 or x=(a+b+1)/2, with a and b fusible numbers and |a−b|<1

S>Итак, если взять исходно x=0, то где же взять уникальные a и b из множества?

По условию по ссылке исходно ряд строился по другой формуле:
xi=xi-1+(1-xi-1)/2 = (xi-1+1)/2, где x0=0
И число 1 тоже входит в это ряд по-условию (время горения 1-го фитиля).

Итого, получается ряд:
xi=0
x1=1/2
x2=3/4
x3=7/8
xi=1-1/2i
xoo=1

Так же по условию мы можем складывать и вычитать эти числа, чтобы получать из них новые.
Учитывая, что разница xi-xi-1=1/2i, можно получить любое число вида 1/2i, через сумму которых представить произвольное fusible number.

Итого:

Formally, a rational number x is fusible if and only if x=a*2-b, with a and b natural numbers.

Отредактировано 04.04.2017 17:04 vdimas . Предыдущая версия .
Re[2]: Рациональные числа
От: vdimas Россия  
Дата: 04.04.17 17:16
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Понятно, что S — некое подмножество конечных двоичных дробей.


Fusible numbers можно вычитать:

You are allowed to light one or more unlit ends of any fuse, but only at time \(t = 0\) or when a fuse burns out completely.

Т.е., догорел один фитиль, подожгли другой или отсчитали время м/у сгоранием двух фетилей.
Итого, можно получить произвольное число 2-n.

А значит S — это множество всех двоичных дробей.

Т.е., любое целое число или число с плавающей точкой, представимое в двоичном виде, — оно заведомо fusible. ))

Поэтому, программа может быть такой (для представления рационального числа в виде дроби):
http://www.rsdn.org/forum/etude/6746954.1

Или такой:
bool isFusible(float a) { return a>=0; }
bool isFusible(double a) { return a>=0; }
bool isFusible(int a) { return a>=0; }
bool isFusible(long a) { return a>=0; }
bool isFusible(unsigned a) { return true; }
bool isFusible(unsigned long a) { return true; }
Отредактировано 04.04.2017 17:21 vdimas . Предыдущая версия .
Re[12]: Рациональные числа
От: samius Япония http://sams-tricks.blogspot.com
Дата: 04.04.17 18:23
Оценка:
Здравствуйте, vdimas, Вы писали:

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


V>>>По условию, данному по ссылке, нет смысла проводить идентичные манипуляции с разными фитилями, т.к. по условию они идентичны и сгорают полностью за одно и то же время.

S>>(все, что ты открываешь, читаешь не вникая)

V>Кто бы говорил. ))



S>>

S>>Formally, a real number xx is fusible if and only if x=0 or x=(a+b+1)/2, with a and b fusible numbers and |a−b|<1

S>>Итак, если взять исходно x=0, то где же взять уникальные a и b из множества?

V>По условию по ссылке исходно ряд строился по другой формуле:

Нет по ссылке никакого ряда

V>xi=xi-1+(1-xi-1)/2 = (xi-1+1)/2, где x0=0

V>И число 1 тоже входит в это ряд по-условию (время горения 1-го фитиля).
о, выходит, "неточность" в определении nikov-а, т.е. требование уникальности p и q ты взял именно из своего ряда.

V>Итого, получается ряд:

V>xi=0
V>x1=1/2
V>x2=3/4
V>x3=7/8
V>xi=1-1/2i
V>xoo=1

V>Так же по условию мы можем складывать и вычитать эти числа, чтобы получать из них новые.

И даже вычитать? Т.е. -1/2 по-твоему тоже fusible.

V>Учитывая, что разница xi-xi-1=1/2i, можно получить любое число вида 1/2i, через сумму которых представить произвольное fusible number.


V>Итого:

V>

V>Formally, a rational number x is fusible if and only if x=a*2-b, with a and b natural numbers.


И при каких же натуральных a и b выходит fusible -1/2, 5/8 ?
Re: Рациональные числа
От: Кодт Россия  
Дата: 04.04.17 18:36
Оценка:
Здравствуйте, nikov, Вы писали:

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


Небольшой натурный эксперимент показал, что двоичные представления чисел там очень характерного вида

0.
0.1
0.11
0.111
.....
1.
1.0 (от 0 до 1 нуля вперемешку с единицами) 1
1.10 (от 0 до 2 нулей вперемешку с единицами) 1
1.(k-1 единиц) 0 (от 0 до k нулей вперемешку с единицами) 1
2.xxxxxxx — начиная с 2.0, встречаются все числа

Поэтому проверка выглядит достаточно простой:
x >= 2 — да, входит
x < 1 — x == 1-1/2**k
x in [1;2) — раскладываем в дробь, считаем количество L ведущих единиц (включая одну штуку до запятой) и количество значащих нулей Z; если Z<=L, то — да, входит.

Теперь осталось
— доказать, что после 2 встретятся все числа
— объяснить, почему между 1 и 2 именно такие дроби
Перекуём баги на фичи!
Re[3]: Рациональные числа
От: Кодт Россия  
Дата: 04.04.17 19:07
Оценка:
Здравствуйте, vdimas, Вы писали:

V>Fusible numbers можно вычитать:

V>А значит S — это множество всех двоичных дробей.

Нет. У нас подмножество множества fusible numbers. Сказано же: "минимальное множество"

Например, мы совершенно спокойно можем выкинуть диапазон (0;0.5).

Но тут мы, на самом деле, наталкиваемся на философский вопрос, что считать минимальным множеством.
Понятно, что все множества, удовлетворяющие условию "с нулём и замкнутое по слиянию" — счётны.
Достаточно просто взять любую функцию — f(x) = 0@x или f(x) = x@x (где @ — операция слияния, x@y = (x+y+1)/2)
и проитерировать счётное количество раз.

То есть, банально сравнивать мощности — бесполезно.

Но если мы напишем функцию F(M) = M U {x@y | x,y <- M}
и найдём его неподвижные точки Sfix = F(Sfix) = F*(Sseed)
то окажется, что между ними можно установить частичный порядок — что чьим подмножеством является. И очевидно, что если Sseed1 <= Sseed2, то Sfix1 <= Sfix2
Абсолютный минимум в этом, топологическом, смысле — это пустое множество, но мы его не засчитываем.
Самая маленькая затравка Sseed0 = {0} — по условию задачи.
Перекуём баги на фичи!
Re[4]: Рациональные числа
От: vdimas Россия  
Дата: 04.04.17 20:04
Оценка:
Здравствуйте, Кодт, Вы писали:

V>>Fusible numbers можно вычитать:

V>>А значит S — это множество всех двоичных дробей.
К>Нет. У нас подмножество множества fusible numbers. Сказано же: "минимальное множество"

Э-э-э... ну тогда для любого представленного в двоичном виде числа за основу мн-ва можно взять слагаемые 2e-ni, где ni — номера ненулевых разрядов мантиссы (начиная со старших) и e=экспонента для плавающего представления или сдвиг точки для фиксированного. Затем дополнить это мн-во производными членами по формуле (a+b+1)/2 для всех пар слагаемых, у которых |a-b|<1. Проводить такое дополнение в цикле до тех пор, пока в мн-ве будут появляться новые члены. Оно?
Re[13]: Рациональные числа
От: vdimas Россия  
Дата: 04.04.17 20:10
Оценка:
Здравствуйте, samius, Вы писали:

V>>По условию по ссылке исходно ряд строился по другой формуле:

S>Нет по ссылке никакого ряда

Плохо читал, значит.
Обрати внимание на то, как получили 45 секунд.


V>>Так же по условию мы можем складывать и вычитать эти числа, чтобы получать из них новые.

S>И даже вычитать?

Да. Зажги две разных цепочки "фитильных событий", и замерь время м/у окончанием их.


S>Т.е. -1/2 по-твоему тоже fusible.


Только если "отрезок времени" может быть отрицательным. ))



V>>

V>>Formally, a rational number x is fusible if and only if x=a*2-b, with a and b natural numbers.

S>И при каких же натуральных a и b выходит fusible -1/2, 5/8?

5/8 => a=5, b=3
Re[5]: Рациональные числа
От: vdimas Россия  
Дата: 04.04.17 20:18
Оценка:
Здравствуйте, vdimas, Вы писали:

V>Э-э-э... ну тогда для любого представленного в двоичном виде числа за основу мн-ва можно взять слагаемые 2e-ni, где ni — номера ненулевых разрядов мантиссы (начиная со старших) и e=экспонента для плавающего представления или сдвиг точки для фиксированного. Затем дополнить это мн-во производными членами по формуле (a+b+1)/2 для всех пар слагаемых, у которых |a-b|<1. Проводить такое дополнение в цикле до тех пор, пока в мн-ве будут появляться новые члены. Оно?


А не, это просто нахождение такого минимального мн-ва, которому принадлежит исходное число.
Но не выяснение принадлежности к минимальному мн-ву, получаемому от 0-ля.
Re[13]: Рациональные числа
От: vdimas Россия  
Дата: 04.04.17 20:58
Оценка: +1
Здравствуйте, samius, Вы писали:

V>>Так же по условию мы можем складывать и вычитать эти числа, чтобы получать из них новые.

S>И даже вычитать?

По той ссылке недостаточно было сказано.
Нашел первоисточник, там написано:

The
 interval 
starts 
when 
first 
fuse 
is 
lit, 
ends 
when 
last 
fuse 
goes 
out.


Т.е. вычитать нельзя.
Re[10]: Рациональные числа
От: Eugene Sh Россия  
Дата: 04.04.17 22:18
Оценка:
Здравствуйте, vdimas, Вы писали:

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

Минимальное множество не обязано быть ограниченным. Пусть себе растёт вправо, сколько ему вздумается. Главное, чтобы у него не было меньшего подмножества, которое тоже бы удовлетворяло условию задачи.
Re[2]: Рациональные числа
От: Eugene Sh Россия  
Дата: 04.04.17 22:23
Оценка:
Здравствуйте, Кодт, Вы писали:

К>2.xxxxxxx — начиная с 2.0, встречаются все числа

Совсем все? Или можно взять только числа конечной длины?
Re[11]: Рациональные числа
От: vdimas Россия  
Дата: 05.04.17 05:02
Оценка:
Здравствуйте, Eugene Sh, Вы писали:

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

ES>Минимальное множество не обязано быть ограниченным. Пусть себе растёт вправо, сколько ему вздумается. Главное, чтобы у него не было меньшего подмножества, которое тоже бы удовлетворяло условию задачи.

Боюсь, в данном случае оба мн-ва совпадают, что минимальное, что полное.

Наверно имелось ввиду исключить всякие суммы таких fusible numbers из мн-ва? Но тут, похоже, любая их сумма может быть выведена как последовательность "обязательных" применений исходной формулы (p+q+1)/2.
Re[4]: Рациональные числа
От: vdimas Россия  
Дата: 05.04.17 05:15
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Но тут мы, на самом деле, наталкиваемся на философский вопрос, что считать минимальным множеством.

К>Понятно, что все множества, удовлетворяющие условию "с нулём и замкнутое по слиянию" — счётны.
К>Достаточно просто взять любую функцию — f(x) = 0@x или f(x) = x@x (где @ — операция слияния, x@y = (x+y+1)/2)
К>и проитерировать счётное количество раз.

А можно еще уточнить насчет "счетны"?
Например, порождаемый простейший ряд (для случая y=0) 1-2-n бесконечен, сходится в пределе к 1-му.
Или имелось ввиду конкретное двоичное представление числа с плавающей запятой в компьютере?


К>Но если мы напишем функцию F(M) = M U {x@y | x,y <- M}

К>и найдём его неподвижные точки Sfix = F(Sfix) = F*(Sseed)
К>то окажется, что между ними можно установить частичный порядок — что чьим подмножеством является. И очевидно, что если Sseed1 <= Sseed2, то Sfix1 <= Sfix2
К>Абсолютный минимум в этом, топологическом, смысле — это пустое множество, но мы его не засчитываем.
К>Самая маленькая затравка Sseed0 = {0} — по условию задачи.

Как написал уже рядом, похоже, что любая сумма fusible numbers так же выражается через "обязательное" применение формулы (x+y+1)/2, вычисляющей "необходимый обязательный минимум". То бишь, похоже, что объединение вообще всех (произвольных) мн-в, удовлетворяющих условию, будет совпадать с минимальным или являться его подмножеством.
Отредактировано 05.04.2017 5:15 vdimas . Предыдущая версия .
Re[5]: Рациональные числа
От: Eugene Sh Россия  
Дата: 05.04.17 06:53
Оценка:
Здравствуйте, vdimas, Вы писали:

V>А можно еще уточнить насчет "счетны"?

Счётное множество
Re[3]: Рациональные числа
От: Кодт Россия  
Дата: 05.04.17 07:11
Оценка:
Здравствуйте, Eugene Sh, Вы писали:

К>>2.xxxxxxx — начиная с 2.0, встречаются все числа

ES>Совсем все? Или можно взять только числа конечной длины?

Да, я имел в виду все конечные дроби. С самого начала же сказал, что из {0} за конечное число шагов получаются только конечноразрядные числа.
Перекуём баги на фичи!
Re[5]: Рациональные числа
От: Кодт Россия  
Дата: 05.04.17 07:42
Оценка:
Здравствуйте, vdimas, Вы писали:

V>А можно еще уточнить насчет "счетны"?

V>Например, порождаемый простейший ряд (для случая y=0) 1-2-n бесконечен, сходится в пределе к 1-му.
V>Или имелось ввиду конкретное двоичное представление числа с плавающей запятой в компьютере?

Пределы здесь не при чём, речь идёт о мощностях.
Известно, что все счётные множества равномощны, то есть, каждому элементу одного такого множества можно взаимно однозначно сопоставить элемент другого.
Отсюда — парадоксы, например, о том, что множество чётных натуральных чисел эквивалентно множеству всех натуральных чисел. Хотя "на бытовом уровне" множество чётных "меньше" множества натуральных.

Поэтому топикстартер толкнул нас на тонкий лёд.

1. Все подходящие множества счётны. Потому что из нуля можно бесхитростно нарожать счётное количество чисел, которые должны принадлежать множеству.
2. Множество Q+ подходит и счётно.
3. Ну а раз мы нашли одно такое множество, зачем искать что-то ещё?

Вот чисто для доведения до абсурда: пусть операция слияния выглядит так: x@y = x+y+15.
Натуральные числа, кратные 15 — подходят.
Натуральные числа, кратные 3 или 5 — опять подходят.
Натуральные числа, кратные 15 или 17 — тоже подходят, хотя откуда взялось 17? Да с потолка.
Все натуральные числа — подходят.
Что из этого добра выберем в качестве "минимального"?

К>>Но если мы напишем функцию F(M) = M U {x@y | x,y <- M}

К>>и найдём его неподвижные точки Sfix = F(Sfix) = F*(Sseed)
К>>то окажется, что между ними можно установить частичный порядок — что чьим подмножеством является. И очевидно, что если Sseed1 <= Sseed2, то Sfix1 <= Sfix2
К>>Абсолютный минимум в этом, топологическом, смысле — это пустое множество, но мы его не засчитываем.
К>>Самая маленькая затравка Sseed0 = {0} — по условию задачи.

V>Как написал уже рядом, похоже, что любая сумма fusible numbers так же выражается через "обязательное" применение формулы (x+y+1)/2, вычисляющей "необходимый обязательный минимум". То бишь, похоже, что объединение вообще всех (произвольных) мн-в, удовлетворяющих условию, будет совпадать с минимальным или являться его подмножеством.


Как это — "объединение всех" будет являться подмножеством минимального?!
Надмножеством — будет. Подмножеством максимального — будет. (А что возьмём за максимум?)
Перекуём баги на фичи!
Re[6]: Рациональные числа
От: vdimas Россия  
Дата: 05.04.17 13:45
Оценка: :)
Здравствуйте, Eugene Sh, Вы писали:

V>>А можно еще уточнить насчет "счетны"?

ES>Счётное множество

Ну тогда искомое мн-во не счетно, т.к. оно по-определению имеет мощность N2, где N-мощность мн-ва натуральных чисел.
Re[6]: Рациональные числа
От: vdimas Россия  
Дата: 05.04.17 13:53
Оценка: -1
Здравствуйте, Кодт, Вы писали:

К>Отсюда — парадоксы, например, о том, что множество чётных натуральных чисел эквивалентно множеству всех натуральных чисел. Хотя "на бытовом уровне" множество чётных "меньше" множества натуральных.


Ну, это я еще помню. ))
Коэф при мощности не считается, считаются степени/логарифмы.

Например, мощность мн-ва попарных сочетаний всех натуральных чисел будет больше мощности мн-ва натуральных чисел, выражается как N2, где N-мощность мн-ва натуральных чисел.


К>Поэтому топикстартер толкнул нас на тонкий лёд.

К>1. Все подходящие множества счётны.

Минимальное искомое мн-во прямо по условию имеет мощность N2.
Эту же мощность имеет мн-во рациональных чисел, т.е. представимых в виде простых дробей Na/Nb.

Поэтому и захотелось уточнить, почему счётно-то?


К>Вот чисто для доведения до абсурда: пусть операция слияния выглядит так: x@y = x+y+15.

К>Натуральные числа, кратные 15 — подходят.
К>Натуральные числа, кратные 3 или 5 — опять подходят.
К>Натуральные числа, кратные 15 или 17 — тоже подходят, хотя откуда взялось 17? Да с потолка.
К>Все натуральные числа — подходят.
К>Что из этого добра выберем в качестве "минимального"?

Там в этих рядах, порождаемых исходной рекуррентной формулой, слияние "хорошо работает" только до значения <2, т.е. когда одно и то же число генерится разными способами. Поэтому, там счётно только мн-во чисел <2.
Re[6]: Рациональные числа
От: vdimas Россия  
Дата: 05.04.17 14:00
Оценка:
Здравствуйте, Кодт, Вы писали:

V>>Как написал уже рядом, похоже, что любая сумма fusible numbers так же выражается через "обязательное" применение формулы (x+y+1)/2, вычисляющей "необходимый обязательный минимум". То бишь, похоже, что объединение вообще всех (произвольных) мн-в, удовлетворяющих условию, будет совпадать с минимальным или являться его подмножеством.

К>Как это — "объединение всех" будет являться подмножеством минимального?!

Попробую пояснить.

Есть некая ф-ия, которая постулирует наличие неких элементов в мн-ве, т.к. она говорит, что если p и q — элементы мн-ва и расстояние м/у ними <1, то x=F(p, q) — тоже элемент этого мн-ва. Еще дано, что 0 является элементом этого мн-ва, примем x0=0.

Итого, подставляя x0 в F, получим:
x0:1 = F(x0, x0).

Далее:
x0:2 = F(x0, x0:1).
x0:3 = F(x0, x0:2).
x1:2 = F(x0:1, x0:1).
x1:3 = F(x0:1, x0:2).
и т.д.

Т.е. необходимо попарно применить F ко всем имеющимся и получаемым на каждом шаге xi и xj, расстояние м/у которыми меньше 1. Полученное мн-во я рядом назвал "обязательным минимумом", т.е. оно и есть искомое минимальное мн-во.

Рассуждаем далее. Представим, что можно взять произвольное число r, "насильно" включить его в мн-во и так же попарно по формуле нагенерить еще элементы такого мн-ва. Так вот, если r не является числом, полученным по исходной рекуррентной формуле, то мы нагенерим большее мн-во чем "минимальное обязательное", ОК.

Просто я утверждал, что любое число, представимое в виде суммы элементов xi из минимального мн-ва, тоже волшебным образом входит в это мн-во.
Например:
x0:1+x0:1=1/2+1/2=1.
и предел ряда x0:n, n->oo тоже равен 1.

Еще:
x0:1+x0:2=1/2+3/4=5/4.
предел ряда x1:n, n->oo тоже равен 5/4.
и т.д.

Далее.
Есть еще такие наблюдения:
Для любого числа вида 2-x0:n обязательно найдётся ряд из того самого минимального мн-ва, сходящийся к этому числу.
Например:
2 — 1/2 = 3/2 — есть такой ряд.
2 — 3/4 = 5/4 — есть такой ряд.
2 — 7/8 = 9/8 — есть такой ряд.
2 — x0:n, n->oo = x0:n, n->oo = 1
2 — 0 = x3:n, n->oo = 2

И это почему-то верно для любого числа r >= 2.
Т.е, любое число r >= 2, во-первых, представимо в виде суммы элементов x из минимального мн-ва 1/2 <= x <= 3/2, во вторых, тоже входит в это минимальное мн-во при рекуррентном его вычислении.

Итого, для чисел из диапазона 1/2..1 достаточно узнать на принадлежность ряду:
1/2, 3/4, 7/8, ..., 1-2-n
Что элементарно, если рациональное число представить в виде натуральной дроби.

А вот для чисел из диапазона 1..2 "достаточно" узнать на принадлежность одному из рядов:
1.
1/2+3/2-1/2, 1/2+3/2-3/4, 1/2+3/2-7/8...
1/2+5/4-1/2, 1/2+5/4-3/4, 1/2+5/4-7/8...
1/2+9/8-1/2, 1/2+9/8-3/4, 1/2+9/8-7/8...
...
2.
3/4+3/2-1/2, 3/4+3/2-3/4, 3/4+3/2-7/8...
3/4+5/4-1/2, 3/4+5/4-3/4, 3/4+5/4-7/8...
...
3.
7/8+3/2-1/2, 7/8+3/2-3/4, 7/8+3/2-7/8...
n.
...
Пока что есть наблюдение, что в диагоналях каждой n-й матрицы содержатся одинаковые числа, т.е. каждую из них можно заменить на любой её столбец или строку.
Итого, группа матриц вырождается в одну матрицу, принадлежность к которой надо найти...

====
Интересно, а у ТС есть своё решение? ))
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.