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

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

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

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

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

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

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

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

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

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

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

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

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

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

не распарсил.

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

Аааа....если голосует ровно 1000 человек, то результаты будут сразу с точностью до 0.1%, без округления.

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

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

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

17/998 даст периодическую десятичную дробь. man рациональные числа.

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

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

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

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

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

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

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

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

Вопрос для прояснения сути: какое нужное (по твоему мнению) число знаков для рац. числа 1/3 ?

Гхм. Т.е. если n = 7 и на входе 3.141593, то алгоритм должен говорить «пи»???? 0_о

vostrik

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

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

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

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

алгоритм должен говорить «упс, logged» и двигаться дальше

vostrik

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

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

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

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

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

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

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

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

vostrik

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

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

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

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

vostrik

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

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

vostrik

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

Удачи :)

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

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

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

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

А разве НОД имеет смысл для нецелых чисел?

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

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

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

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

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

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

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

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

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

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