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

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

StrongDollar (05.01.2012 1:35:23)

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

vostrik (05.01.2012 1:37:49)

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

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

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

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

vostrik (05.01.2012 1:49:32)

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 (05.01.2012 1:52:13)

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

vostrik (05.01.2012 1:58:15)

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

shty (05.01.2012 2:01:57)

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

vostrik (05.01.2012 2:10:52)

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

vostrik (05.01.2012 2:18:43)

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

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

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

vostrik (05.01.2012 2:21:51)

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

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

vostrik (05.01.2012 2:27:29)

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

vostrik (05.01.2012 2:29:46)

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

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

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

vostrik (05.01.2012 2:41:15)

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

shty (05.01.2012 2:49:46)

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

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

vostrik (05.01.2012 2:55:00)

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

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

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

vostrik (05.01.2012 2:58:04)

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

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

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

stolz (05.01.2012 3:02:37)

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

vostrik (05.01.2012 3:04:23)

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

vostrik (05.01.2012 3:04:55)

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

vostrik (05.01.2012 3:05:46)

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

stolz (05.01.2012 3:07:10)

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

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

vostrik (05.01.2012 3:14:10)

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

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

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

vostrik (05.01.2012 3:16:47)

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

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

stolz (05.01.2012 3:20:52)

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

vostrik (05.01.2012 3:21:14)

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

vostrik (05.01.2012 3:23:02)

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

Удачи :)

stolz (05.01.2012 3:23:08)

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

iBliss (05.01.2012 4:14:09)

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

segfault (05.01.2012 13:00:18)

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

vostrik (05.01.2012 13:01:04)

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

DNA_Seq (05.01.2012 13:20:51)

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

DNA_Seq (05.01.2012 13:23:59)

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

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

DNA_Seq (05.01.2012 13:27:26)

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

thelonelyisland (05.01.2012 14:19:01)

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

vostrik (05.01.2012 16:01:25)

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

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

vostrik (05.01.2012 16:02:24)

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

DNA_Seq (05.01.2012 16:08:45)

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

DNA_Seq (05.01.2012 16:10:03)