Сообщение Re[9]: Рациональные числа от 04.04.2017 13:56
Изменено 04.04.2017 16:07 vdimas
Re[9]: Рациональные числа
Здравствуйте, kfmn, Вы писали:
V>>Там неточность условия в том, что в формуле (p+q+1)/2 должно было оговариваться, что p и q — это уникальные элементы множества.
K>Уникальные, значит различные?
Именно.
K>nikov про это в условии не писал
Об этом моё замечание.
K>и любое определение fusible numbers открой — там этого нет.
Открыл — есть:
http://googology.wikia.com/wiki/Fusible_number
По условию, данному по ссылке, нет смысла проводить идентичные манипуляции с разными фитилями, т.к. по условию они идентичны и сгорают полностью за одно и то же время.
K>>>К тому же по условию ноль содержится в S.
V>>При условии уникальности p и q — да.
V>>Иначе получалось противоречие сходу, т.к. 1/2 не является элементом мн-ва.
K>Откуда это?
Из условия. Иначе получается растущее вправо бесконечное мн-во, т.е. речи о его минимальности быть не может.
Т.е., мн-во fusible numbers бесконечно.
Тогда принадлежность к нему определяется элементарно (ответил сразу же):
Итого, решение:
V>>Там неточность условия в том, что в формуле (p+q+1)/2 должно было оговариваться, что p и q — это уникальные элементы множества.
K>Уникальные, значит различные?
Именно.
K>nikov про это в условии не писал
Об этом моё замечание.
K>и любое определение fusible numbers открой — там этого нет.
Открыл — есть:
http://googology.wikia.com/wiki/Fusible_number
По условию, данному по ссылке, нет смысла проводить идентичные манипуляции с разными фитилями, т.к. по условию они идентичны и сгорают полностью за одно и то же время.
K>>>К тому же по условию ноль содержится в S.
V>>При условии уникальности p и q — да.
V>>Иначе получалось противоречие сходу, т.к. 1/2 не является элементом мн-ва.
K>Откуда это?
Из условия. Иначе получается растущее вправо бесконечное мн-во, т.е. речи о его минимальности быть не может.
Т.е., мн-во fusible numbers бесконечно.
Тогда принадлежность к нему определяется элементарно (ответил сразу же):
Если оно при этом рациональное, то знаменатель будет степенью двойки после сокращения дроби.
Итого, решение:
bool isFusible(uint numerator, uint denominator) {
assert(denominator);
uint a = numerator, b = denominator;
while(a!=b) if(a>b) a-=b; else b-=a;
if(a) denominator/=a;
return !(denominator&(denominator-1));
}
Re[9]: Рациональные числа
Здравствуйте, kfmn, Вы писали:
V>>Там неточность условия в том, что в формуле (p+q+1)/2 должно было оговариваться, что p и q — это уникальные элементы множества.
K>Уникальные, значит различные?
Именно.
K>nikov про это в условии не писал
Об этом моё замечание.
K>и любое определение fusible numbers открой — там этого нет.
Открыл — есть:
http://googology.wikia.com/wiki/Fusible_number
По условию, данному по ссылке, нет смысла проводить идентичные манипуляции с разными фитилями, т.к. по условию они идентичны и сгорают полностью за одно и то же время.
K>>>К тому же по условию ноль содержится в S.
V>>При условии уникальности p и q — да.
V>>Иначе получалось противоречие сходу, т.к. 1/2 не является элементом мн-ва.
K>Откуда это?
Из условия. Иначе получается растущее вправо бесконечное мн-во, т.е. речи о его минимальности быть не может.
Т.е., мн-во fusible numbers бесконечно.
Тогда принадлежность к нему определяется элементарно (ответил сразу же):
Итого, решение:
UPD (сравнить с 0-лем и с нижней границей 1/2):
V>>Там неточность условия в том, что в формуле (p+q+1)/2 должно было оговариваться, что p и q — это уникальные элементы множества.
K>Уникальные, значит различные?
Именно.
K>nikov про это в условии не писал
Об этом моё замечание.
K>и любое определение fusible numbers открой — там этого нет.
Открыл — есть:
http://googology.wikia.com/wiki/Fusible_number
По условию, данному по ссылке, нет смысла проводить идентичные манипуляции с разными фитилями, т.к. по условию они идентичны и сгорают полностью за одно и то же время.
K>>>К тому же по условию ноль содержится в S.
V>>При условии уникальности p и q — да.
V>>Иначе получалось противоречие сходу, т.к. 1/2 не является элементом мн-ва.
K>Откуда это?
Из условия. Иначе получается растущее вправо бесконечное мн-во, т.е. речи о его минимальности быть не может.
Т.е., мн-во fusible numbers бесконечно.
Тогда принадлежность к нему определяется элементарно (ответил сразу же):
Если оно при этом рациональное, то знаменатель будет степенью двойки после сокращения дроби.
Итого, решение:
UPD (сравнить с 0-лем и с нижней границей 1/2):
bool isFusible(uint numerator, uint denominator) {
assert(denominator);
if(!numerator) return true;
if(numerator*2<denominator) return false;
uint a = numerator, b = denominator;
while(a!=b) if(a>b) a-=b; else b-=a;
if(a) denominator/=a;
return !(denominator&(denominator-1));
}