Помощь - Поиск - Пользователи - Календарь
Полная версия: Задача на вероятнось
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Witaliy
Задание
Все чистые носки сохраняются в большой и глубокой коробке. Всего в ней находится 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
Цитата(Witaliy @ 25.02.2009 19:32) *
Понятия не имею как решаються подобные задачи
"Подобные задачи" решаются примерно так: smile.gif
var
i,m,n,a,b: integer;

begin
ReadLn(m,n);
a:=2*n*m;
b:=(n+m)*(n+m-1);
for i:=2 to (n+m)*(n+m-1) do while (a mod i=0)and(b mod i=0) do begin
a:=a div i;
b:=b div i
end;
WriteLn(a,'/',b);
ReadLn
end.
Witaliy
Отлично роботает, но есть тайм лимит... наверно в сокращении дроби.. помогите пожалуйста.
volvo
Ну, избавься от цикла: найди НОД a и b, и подели оба числа на него (так будет немного быстрее, чем гонять цикл)... Хотя я даже не представляю, что надо задать во входных данных, чтобы был тайм-лимит.
Witaliy
Для найдения НОД тоже нужно такой-же цикл
volvo
Нет, не такой же... Для того, чтобы найти НОД чисел 102 и 106, достаточно 7 итераций (то есть, всего 7 раз числа будут сравниваться с 0, и будет браться остаток от деления большего на меньшее)... В вышеприведенном задании (a mod i = 0) и (b mod i = 0) проверяется 43055 раз при тех же входных данных. А это и взятие остатка, и проверка на 0. Почувствуй разницу...
Witaliy
Да, єто правда.
Вот я вроде сделал:
var
m,n,a,b: int64;
i : longint;
begin
ReadLn(m,n);
a:=2*n*m;
b:=(n+m)*(n+m-1);
while (a mod 2 = 0) and (b mod 2 = 0) do
begin
a := a div 2;
b := b div 2;
end;
while (a mod 3 = 0) and (b mod 3 = 0) do
begin
a := a div 3;
b := b div 3;
end;
while (a mod 5 = 0) and (b mod 5 = 0) do
begin
a := a div 5;
b := b div 5;
end;
while (a mod 7 = 0) and (b mod 7 = 0) do
begin
a := a div 7;
b := b div 7;
end;
if (a=0) then
WriteLn(0,'/',1)
else
if (b=0) then
WriteLn(1,'/',0)
else

WriteLn(a,'/',b)
end.


Но где-то неверный ответ, подскажите пожалуйста в чем может быть проблема.
Спасибо.
volvo
А что, обязательно делать вручную? Между прочим, семеркой простые числа не заканчиваются, тогда и 11 проверяй, и 13, и так далее... Чего ты остановился?

Я бы сделал так:
function GCD (A: longint;  B: longint): longint;
begin
while (a <> 0) and (b <> 0) do
if 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
тут извините, N <= 1000000, я ошибся. Для 1 1000000 зависает программа (лимит времени 5 сек). В мое программе выше проходит тот тест, что с вашей не проходит, но на следующих северный ответ. Я понима. что ваш вариант отличен, но что-то в нем неверно.
Lapp
Цитата(Witaliy @ 26.02.2009 13:12) *
N <= 1000000 ... (лимит времени 5 сек)
Это нужно было сказать раньше (и не в скобках). Ессно, я расслабился при N<=106 ..
Деза, батенька!
Witaliy
Очень прошу извинения, не посмотрел..... помогите пожалуйста сделать что-то
спасибо.
volvo
Не знаю, чего там у тебя зависает, но:
function GCD (A: int64;  B: int64): int64;
begin
while (a <> 0) and (b <> 0) do
if 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 mod 2 = 0) and (b mod 2 = 0) do
begin
a := a div 2;
b := b div 2;
end;
while (a mod 3 = 0) and (b mod 3 = 0) do
begin
a := a div 3;
b := b div 3;
end;
while (a mod 5 = 0) and (b mod 5 = 0) do
begin
a := a div 5;
b := b div 5;
end;
while (a mod 7 = 0) and (b mod 7 = 0) do
begin
a := a div 7;
b := b div 7;
end;
if (a=0) then
WriteLn(0,'/',1)
else
if (b=0) then
WriteLn(1,'/',0)
else
WriteLn(a,'/',b)
end.

прекрасно выдает (причем мгновенно) оба ответа. И оба - одинаковые, что характерно... Ты типы параметров-то менял на int64???
Witaliy
Да, прошло (без моих художеств smile.gif )!!! Не понимаю только в чем разница...

Добавлено через 2 мин.
Наверно из-за типа longint в переменной nod

Добавлено через 5 мин.
Еше вопрос: можете дать еще какие-то формулы для задач с вероятностями.. если можете (и если еще какие-то есть)
Спасибо.
мисс_граффити
Классическое определение вероятности: Вероятность равна числу благоприятных исходов к общему числу возможных исходов.
Здесь больше ничего не надо. А вообще в теории вероятности довольно много формул... +комбинаторика еще.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.