Задание Все чистые носки сохраняются в большой и глубокой коробке. Всего в ней находится N левых и M правых носков. Автор решил через нехватку времени избрать две наугад. Подсчитайте, какая вероятность того, что автор выбрал именно одну левую и один правый носок. Входные данные В единственной строке заданы два числа N и M – количество левых и правых носков в коробке. Исходные данные Выведите вероятность того, что избраны наугад два носка окажутся правыми и левыми, соответственно. Ответ следует вывести в виде несократимой арифметической дроби a/b. Ограничение: 0 <= N,M <= 106 2 <= N+M. Пример введения 1 4 5 Пример введения 2 7 0 Пример выведения 1 5/9 Пример выведения 2 0/1
Понятия не имею как решаються подобные задачи, буду благодарен за любую помощь. Спасибо.
Lapp
26.02.2009 13:09
Цитата(Witaliy @ 25.02.2009 19:32)
Понятия не имею как решаються подобные задачи
"Подобные задачи" решаются примерно так:
var
i,m,n,a,b: integer;
begin
ReadLn(m,n);
a:=2*n*m;
b:=(n+m)*(n+m-1);
for i:=2to (n+m)*(n+m-1) dowhile (a mod i=0)and(b mod i=0) dobegin
a:=a div i;
b:=b div i
end;
WriteLn(a,'/',b);
ReadLn
end.
Witaliy
26.02.2009 15:10
Отлично роботает, но есть тайм лимит... наверно в сокращении дроби.. помогите пожалуйста.
volvo
26.02.2009 15:32
Ну, избавься от цикла: найди НОД a и b, и подели оба числа на него (так будет немного быстрее, чем гонять цикл)... Хотя я даже не представляю, что надо задать во входных данных, чтобы был тайм-лимит.
Witaliy
26.02.2009 15:50
Для найдения НОД тоже нужно такой-же цикл
volvo
26.02.2009 15:58
Нет, не такой же... Для того, чтобы найти НОД чисел 102 и 106, достаточно 7 итераций (то есть, всего 7 раз числа будут сравниваться с 0, и будет браться остаток от деления большего на меньшее)... В вышеприведенном задании (a mod i = 0) и (b mod i = 0) проверяется 43055 раз при тех же входных данных. А это и взятие остатка, и проверка на 0. Почувствуй разницу...
Witaliy
26.02.2009 16:25
Да, єто правда. Вот я вроде сделал:
var
m,n,a,b: int64;
i : longint;
begin
ReadLn(m,n);
a:=2*n*m;
b:=(n+m)*(n+m-1);
while (a mod2 = 0) and (b mod2 = 0) dobegin
a := a div2;
b := b div2;
end;
while (a mod3 = 0) and (b mod3 = 0) dobegin
a := a div3;
b := b div3;
end;
while (a mod5 = 0) and (b mod5 = 0) dobegin
a := a div5;
b := b div5;
end;
while (a mod7 = 0) and (b mod7 = 0) dobegin
a := a div7;
b := b div7;
end;
if (a=0) then
WriteLn(0,'/',1)
elseif (b=0) then
WriteLn(1,'/',0)
else
WriteLn(a,'/',b)
end.
Но где-то неверный ответ, подскажите пожалуйста в чем может быть проблема. Спасибо.
volvo
26.02.2009 16:53
А что, обязательно делать вручную? Между прочим, семеркой простые числа не заканчиваются, тогда и 11 проверяй, и 13, и так далее... Чего ты остановился?
Я бы сделал так:
function GCD (A: longint; B: longint): longint;
beginwhile (a <> 0) and (b <> 0) doif a >= b then a := a mod b else b := b mod a;
GCD := a + b;
end;
var
m,n,a,b: longint;
nod: longint;
begin
ReadLn(m,n);
a:=2*n*m;
b:=(n+m)*(n+m-1);
nod := GCD(a, b);
writeln(a div nod, '/', b div nod);
ReadLn
end.
и ЧТО тут может не работать???
Witaliy
26.02.2009 17:12
тут извините, N <= 1000000, я ошибся. Для 1 1000000 зависает программа (лимит времени 5 сек). В мое программе выше проходит тот тест, что с вашей не проходит, но на следующих северный ответ. Я понима. что ваш вариант отличен, но что-то в нем неверно.
Lapp
26.02.2009 17:20
Цитата(Witaliy @ 26.02.2009 13:12)
N <= 1000000 ... (лимит времени 5 сек)
Это нужно было сказать раньше (и не в скобках). Ессно, я расслабился при N<=106 .. Деза, батенька!
Witaliy
26.02.2009 17:33
Очень прошу извинения, не посмотрел..... помогите пожалуйста сделать что-то спасибо.
volvo
26.02.2009 19:25
Не знаю, чего там у тебя зависает, но:
function GCD (A: int64; B: int64): int64;
beginwhile (a <> 0) and (b <> 0) doif a >= b then a := a mod b else b := b mod a;
GCD := a + b;
end;
var
m,n, a,b: int64;
nod : int64;
begin
ReadLn(m,n);
a:=2*n*m;
b:=(n+m)*(n+m-1);
nod := GCD(a, b);
writeln(a div nod, '/', b div nod);
// Ну, дальше уже твои художества...
while (a mod2 = 0) and (b mod2 = 0) dobegin
a := a div2;
b := b div2;
end;
while (a mod3 = 0) and (b mod3 = 0) dobegin
a := a div3;
b := b div3;
end;
while (a mod5 = 0) and (b mod5 = 0) dobegin
a := a div5;
b := b div5;
end;
while (a mod7 = 0) and (b mod7 = 0) dobegin
a := a div7;
b := b div7;
end;
if (a=0) then
WriteLn(0,'/',1)
elseif (b=0) then
WriteLn(1,'/',0)
else
WriteLn(a,'/',b)
end.
прекрасно выдает (причем мгновенно) оба ответа. И оба - одинаковые, что характерно... Ты типы параметров-то менял на int64???
Witaliy
26.02.2009 20:01
Да, прошло (без моих художеств )!!! Не понимаю только в чем разница...
Добавлено через 2 мин. Наверно из-за типа longint в переменной nod
Добавлено через 5 мин. Еше вопрос: можете дать еще какие-то формулы для задач с вероятностями.. если можете (и если еще какие-то есть) Спасибо.
мисс_граффити
28.02.2009 16:50
Классическое определение вероятности: Вероятность равна числу благоприятных исходов к общему числу возможных исходов. Здесь больше ничего не надо. А вообще в теории вероятности довольно много формул... +комбинаторика еще.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.