LINUX.ORG.RU
решено ФорумTalks

поиск НОД из трех дробных чисел с неизвестной точностью


0

1

Короче я или туплю, или пытаюсь объять необъятное. Описываю ситуацию: есть наборы из трех долей единицы, округленных без нас до 3 знака. в сумме эти доли дают единицу. в процентах это условно 82,5%, 4,3% и 13,2%.
Вопрос: есть ли алгоритм определения НОД для всех трех этих чисел с учетом возможного округления?
И второй вопрос: есть ли смысл его искать?
Попытаюсь объяснить откуда вопрос: есть результаты голосования в процентах, округленные до первого знака после запятой (как в процентах выше). Известно, что в голосовании принимало участие очень небольшое количество людей (в примере с цифрами выше - не больше 50 человек). Необходимо найти минимальное количество людей, участвовавших в опросе, при котором такие проценты могли получиться. Я, наверное, слишком бухой, но мои расклады про 1/НОД(a,b,c) где a+b+c=100% упираются в неизвестность точных значений a, b и с.
Помогите кто чем могет, пасаны?

★★★☆

Последнее исправление: vostrik (всего исправлений: 3)

Ответ на: комментарий от StrongDollar

зато зная рецепт можно определить, сколько мяса ушло на килограмм котлет.

vostrik ★★★☆
() автор топика

Ну, минимально возможное количество человек, при котором получились те или иные результаты голосования, нестабильно ведет себя при округлениях. Пример:
1) 50%, 25%, 25% - 4 человека
2) 50.09%, 25%, 24.91% - гораздо больше людей, явно >10.

Так что исходная задача вряд ли решаема, имхо.

yura_ts ★★
()

Представляешь проценты в виде обыкновенной дроби, сокращаешь, находишь НОК для знаменатаелей.

nanonymous
()
Ответ на: комментарий от yura_ts

это понятно. но если мы задаемся теоретическим максимумом в 1000 человек - можно ли накидать алгоритм для проверки всех возможных вариантов? тем более, что изначально известно, что проценты не целые

vostrik ★★★☆
() автор топика

Use brute force, Luke

delta = 0.1 # поставить по вкусу
for i in range(1, 1000):
  d = i - (i*0.825+ i*0.043 + i *0.132)
  if delta <= d:
    print i, "дает", d
tailgunner ★★★★★
()
Ответ на: комментарий от nanonymous

я 4.3 могу представить как 4,3(3) и соответственно 13/3 или 4,3125 и 69/16. чуешь разницу?

vostrik ★★★☆
() автор топика

Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей.

как ты это собрался делать для нецелых чисел?

shty ★★★★★
()

короче тема свелась к переводу всех дробей с точностью до n знаков после запятой в обыкновенные дроби и проверке на знаменатель меньше m (максимальное число участников голосования) - дальше понятно. вопрос, как выкинуть из перевода иррациональные числа? это хотя бы реально?

vostrik ★★★☆
() автор топика
Ответ на: комментарий от vostrik

и сразу еще вопрос (ну извините, пьяный) а в голосовании 1000 человек вообще могут попасться числа, с точностью близкой к иррациональным?

vostrik ★★★☆
() автор топика
Ответ на: комментарий от yura_ts

ну даже хз как объяснить. то есть допустим у меня есть алгоритм перевода дроби в обыкновенную. есть алгоритм перевода периодической дроби в обыкновенную. а есть ли вероятность того, что мой алгоритм перевода дроби в обыкновенную упрется в дробь, которая до n знаков после запятой такая же, как иррациональная. и не сдохнет ли он на такой дроби?

vostrik ★★★☆
() автор топика
Ответ на: комментарий от yura_ts

а если чуть меньше 1000? 1000 это максимум, а надо перебрать все варианты до 1000. 17/998 даст непонятную непериодическую срань, например

vostrik ★★★☆
() автор топика
Ответ на: комментарий от vostrik

Так алгоритм есть или «допустим есть»? Как будет алгоритм, так и можно будет оценивать его возможные фэйлы. А вообще, для разминки: как реализовать на любимом ЯП такую штуку, как десятичные дроби, которые либо периодические, либо конечные? Длина дроби и периода чур произвольная.

yura_ts ★★
()
Ответ на: комментарий от yura_ts

ты мне манами не тыкай, я их тут до задницы почитал уже. если мы делаем алгоритм, то на каком-то числе знаков после запятой мы упираемся в те же цифры, что были раньше.
вопрос в том, как выбрать нужное число знаков для промежутка 1/2..1/1000 и как в этом числе знаков отсеять иррациональные дроби, если они там есть

vostrik ★★★☆
() автор топика
Ответ на: комментарий от vostrik

а ты НОД для нецелых чисел 1/3 и 1/6 себе представить не можешь?

с учётом того, что ищется делитель, который делит число нацело - не-а

shty ★★★★★
()
Ответ на: комментарий от vostrik

1) рациональные числа (т.е. числа вида n/m, n, m - целые) _всегда_ представляются периодической либо конечной десятичной дробью.
2) иррациональное число _никогда_ не запишется конечной десятичной дробью, в частности, десятичной дробью с n знаками.

yura_ts ★★
()
Ответ на: комментарий от shty

а с учётом того, что делитель не целый?

vostrik ★★★☆
() автор топика
Ответ на: комментарий от shty

Это как раз просто. Рациональное число x назовем делящимся на рациональное число y, если существует _целое_ a, такое что x = a*y.

Теперь легко определить НОД двух рациональных чисел - это такой их общий делитель, который делится на любой другой общий делитель.

yura_ts ★★
()
Ответ на: комментарий от yura_ts

так вот ты какой, кэп...
это я тоже знаю, мне нужен алгоритм отделения периодической дроби от иррациональной для конечного n знаков после запятой. и алгоритм определения n для 1/m m е [2..x]

vostrik ★★★☆
() автор топика
Ответ на: комментарий от vostrik

vostrik

вопрос в том, как выбрать нужное число знаков для промежутка 1/2..1/1000 и как в этом числе знаков отсеять иррациональные дроби, если они там есть

Иррациональных дробей не будет.

stolz
()
Ответ на: комментарий от yura_ts

в алгоритме? должно хватить 4*n которое я пока не знаю, как найти. если на этом промежутке периодически повторяется какая-то строка от десятичного представления 1/х - можем считать его периодическим и выкинуть для начала в отдельный массив, с которым будем разбираться своими методами. вопрос в том, как найти n для заданного m

vostrik ★★★☆
() автор топика
Ответ на: комментарий от vostrik

vostrik

хотелось бы просто иметь четкое доказательство этого

Ты никак не получишь иррациональную дробь от деления двух рациональных чисел, кои находятся в промежутке от 1 до 1000. Вот если бы у тебя были e, pi и квадратные корни из чисел - тогда да.

stolz
()
Ответ на: комментарий от vostrik

Ты хочешь невозможного. Если у тебя входные данные 3.141593, то нельзя понять, это приближение числа Пи или рациональное число 3141593/1000000.

yura_ts ★★
()
Ответ на: комментарий от vostrik

Имхо, правильней просто сделать тип данных - периодическая десятичная дробь. Очень нехилая задача по программированию, но она решает исходную задачу с избытком.

Да, размер неограничен. Нужно реализовать сложение/вычитание/умножение, этого хватит для всяких там НОД и проч.

yura_ts ★★
()
Ответ на: комментарий от stolz

это да. вопрос в том, как отличить часть десятичного числа от деления двух рациональных от начала десятичной записи иррационального числа. я же не знаю, откуда это число появилось. хотя, в принципе, я могу насобирать массив частных от деления 1/x и перебирать только их. и не париться о иррациональности вообще. вроде вариант, на трезвую голову надо подумать. всем спасибо.

vostrik ★★★☆
() автор топика
Ответ на: комментарий от vostrik

Ок, сам как думаешь в данном конкретном случае?
Я тебе назвал число - 3.141593. Я округлил Пи или записал число 3141593/1000000 безо всякого округления? А ну угадай, что именно из этих двух действий я сделал.

yura_ts ★★
()
Ответ на: комментарий от vostrik

vostrik

почему нельзя-то?

Потому что они будут совпадать до какого-то знака. Честно говоря я не понимаю, откуда ты берёшь иррациональные числа. У тебя их нигде не будет. Если выпало 3.1415, то это будет 31415/10000, но никак не Pi.

stolz
()
Ответ на: комментарий от yura_ts

ты пропустил одно условие - максимальный знаменатель задаю я, а числитель в алгоритме всегда равен единице. насколько я сейчас могу видеть, иррациональные дроби мне в данном случае не нужны вообще.

vostrik ★★★☆
() автор топика
Ответ на: комментарий от stolz

ага, уже догнал. просто сначала какой-то неадекватный алгоритм пытался придумать. все, сорри, я спать. хотя поискать решения для задачки в /0 без перебора всех 1/х не возбраняется :)

vostrik ★★★☆
() автор топика
Ответ на: комментарий от vostrik

vostrik

насколько я сейчас могу видеть, иррациональные дроби мне в данном случае не нужны вообще.

Да, абсолютно так.

vostrik

на трезвую голову надо подумать. всем спасибо.

Удачи :)

stolz
()

Как и с баблосами, выводишь 3 знака в целые умножением на коэфициент округления (правильно написал? походу праздную ещё). И считаешь. Всё решимо.

iBliss
()
Ответ на: комментарий от vostrik

а в голосовании 1000 человек вообще могут попасться числа, с точностью близкой к иррациональным?

А как, простите, вы вообще получите иррациональное число из рациональных с помощью сложения и деления?

segfault ★★★★★
()
Ответ на: комментарий от segfault

вопрос был не про то, но и на него ответ уже не важен.

vostrik ★★★☆
() автор топика
Ответ на: комментарий от vostrik

вопрос, как выкинуть из перевода иррациональные числа?

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

DNA_Seq ★★☆☆☆
()
Ответ на: комментарий от vostrik

Как вариант можно составить таблицу типичных дробей с заданной точностью типа:

33,333 == 1/3 и тд.

DNA_Seq ★★☆☆☆
()

НОД и НОК только для целых. Не трахай себе мозг, иди проспись.

thelonelyisland ★★★
()
Ответ на: комментарий от DNA_Seq

а что мешает домножить на 10^n десятичную дробь и работать с целыми? :)

vostrik ★★★☆
() автор топика
Ответ на: комментарий от DNA_Seq

там немного в другом затык был, это-то понятно. но опять же, это уже не важно.

//в этом мире кто-нибудь обращает внимание на то, решенная тема или нет?

vostrik ★★★☆
() автор топика
Ответ на: комментарий от vostrik

таблица будет весить не больше пары мегабайт (если брать до 1000/1000), думаю наиболее простое решение для обратного преобразования в дробь, естественно варианты вроде 2/4 в таблице будут отсутствовать. Написать скрипт для ее генерации будет гораздо проще чем думать над способами обратного преобразования десятичной дроби в натуральную

DNA_Seq ★★☆☆☆
()
Ответ на: комментарий от vostrik

и естественно каждому возможному значению десятичной дроби будет соответствовать единственно возможная строка таблицы

DNA_Seq ★★☆☆☆
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.