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)

 ← 1 2 →
Ответ на: комментарий от vostrik

а если десятичной дроби нет в таблице (а соответствие будет далеко не для всех чисел) не то соответственно в опросе не могло участвовать менее 1000 человек что соответственно программа и выведет

DNA_Seq ★★☆☆☆
()

если всего 3 знака после запятой, то можно же их как целые числа брать, и искать НОД уже целых чисел, не?

TheAnonymous ★★★★★
()

есть наборы из трех долей единицы, округленных без нас до 3 знака. в сумме эти доли дают единицу. в процентах это условно 82,5%, 4,3% и 13,2%. Необходимо найти минимальное количество людей, участвовавших в опросе, при котором такие проценты могли получиться.

$ bc -lq
for (i=1; i < 1000; i++) a[i]=b[i]=c[i]=0
for (i=1; i < 1000; i++) for (j=1; j <  50; j++) if ((j/i-0.043)^2<=.0005^2) a[i]=j
for (i=1; i < 1000; i++) for (j=1; j < 900; j++) if ((j/i-0.825)^2<=.0005^2) b[i]=j
for (i=1; i < 1000; i++) for (j=1; j < 150; j++) if ((j/i-0.132)^2<=.0005^2) c[i]=j
for (i=1; i < 1000; i++) if ((a[i]!=0)&&(b[i]!=0)&&(c[i]!=0)) print i," "; print "\n"
234 257 280 302 303 325 326 348 349 371 372 394 395 400 416 417 418 \
423 439 440 441 446 462 463 468 469 485 486 491 492 508 509 514 515 \
530 531 532 536 537 538 553 554 555 559 560 561 576 577 582 583 584 \
599 600 604 605 606 607 622 623 627 628 629 630 634 635 644 645 646 \
650 651 652 653 657 658 667 668 669 673 674 675 676 680 681 690 691 \
692 696 697 698 699 702 703 704 713 714 718 719 720 721 722 725 726 \
727 736 737 741 742 743 744 748 749 750 759 760 764 765 766 767 770 \
771 772 773 775 782 783 785 787 788 789 790 793 794 795 796 798 800 \
805 806 808 810 811 812 813 816 817 818 819 821 823 828 832 833 834 \
835 836 838 839 840 841 842 844 846 847 851 853 855 856 857 858 859 \
861 862 863 864 865 868 869 870 874 876 878 879 880 881 882 884 885 \
886 887 888 889 891 892 893 897 899 901 902 903 904 906 907 908 909 \
910 911 912 914 915 916 920 921 922 924 925 926 927 929 930 931 932 \
933 934 935 936 937 938 939 941 944 945 946 947 948 949 950 951 952 \
953 954 955 956 957 958 959 960 961 962 963 964 967 968 969 970 971 \
972 973 974 975 976 977 978 979 982 983 984 985 986 987 988 989 990 \
991 992 993 994 995 996 997 998 999

Как видим, ответ таки 234 человека. Но это ведь могло получиться и при 257 человеках тоже, и при 280 и при 302-303... В переделах 1000 есть 282 варианта количества человек, включая 1000.

Кроме того, неизвестен метод округления, а от него ответ тоже зависит.

Xenius ★★★★★
()

Кстати, мой алгоритм можно упростить, снизив число вариантов перебора, так как искать j можно в окрестности i*percent, но в данном случае программа всё равно работает меньше минуты даже при полном переборе.

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

я в итоге сделал так: 

 require 'optparse'
(1..1000).each do |n|
d1 = ARGV[0].to_f
d2 = ARGV[1].to_f
d3 = ARGV[2].to_f
people = ARGV[3]
p1 = (n*d1).round
p2 = (n*d2).round
p3 = (n*d3).round
if p1+p2+p3 == n && (p1.to_f/n).round(3) == d1 && (p2.to_f/n).round(3) == d2 && (p3.to_f/n).round(3) == d3
print p1.to_s + " + " + p2.to_s + " + " + p3.to_s + " = " + n.to_s + " " + people + "\n"
print ((p1.to_f/n).round(3)).to_s + " " + ((p2.to_f/n).round(3)).to_s + " " + ((p3.to_f/n).round(3)).to_s
break
end
end
учитывая, что мне нужен минимум (который в два раза больше максимального числа респондентов, ЧТД) - вроде адекватно. а до 250 все равно 1 человек вносит слишком большую погрешность, явно больше 0,5%. с ceil(2) получается вообще 1000 минимум, остальные варианты округления я выкинул по причине неадекватности

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