IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Задача на вероятнось
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

Репутация: -  0  +


Задание
Все чистые носки сохраняются в большой и глубокой коробке. Всего в ней находится 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

Понятия не имею как решаються подобные задачи, буду благодарен за любую помощь.
Спасибо.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(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.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

Репутация: -  0  +


Отлично роботает, но есть тайм лимит... наверно в сокращении дроби.. помогите пожалуйста.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Ну, избавься от цикла: найди НОД a и b, и подели оба числа на него (так будет немного быстрее, чем гонять цикл)... Хотя я даже не представляю, что надо задать во входных данных, чтобы был тайм-лимит.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

Репутация: -  0  +


Для найдения НОД тоже нужно такой-же цикл
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Нет, не такой же... Для того, чтобы найти НОД чисел 102 и 106, достаточно 7 итераций (то есть, всего 7 раз числа будут сравниваться с 0, и будет браться остаток от деления большего на меньшее)... В вышеприведенном задании (a mod i = 0) и (b mod i = 0) проверяется 43055 раз при тех же входных данных. А это и взятие остатка, и проверка на 0. Почувствуй разницу...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

Репутация: -  0  +


Да, єто правда.
Вот я вроде сделал:
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.


Но где-то неверный ответ, подскажите пожалуйста в чем может быть проблема.
Спасибо.

Сообщение отредактировано: Witaliy -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






А что, обязательно делать вручную? Между прочим, семеркой простые числа не заканчиваются, тогда и 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.
и ЧТО тут может не работать???
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

Репутация: -  0  +


тут извините, N <= 1000000, я ошибся. Для 1 1000000 зависает программа (лимит времени 5 сек). В мое программе выше проходит тот тест, что с вашей не проходит, но на следующих северный ответ. Я понима. что ваш вариант отличен, но что-то в нем неверно.

Сообщение отредактировано: Witaliy -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Witaliy @ 26.02.2009 13:12) *
N <= 1000000 ... (лимит времени 5 сек)
Это нужно было сказать раньше (и не в скобках). Ессно, я расслабился при N<=106 ..
Деза, батенька!


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

Репутация: -  0  +


Очень прошу извинения, не посмотрел..... помогите пожалуйста сделать что-то
спасибо.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






Не знаю, чего там у тебя зависает, но:
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???
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

Репутация: -  0  +


Да, прошло (без моих художеств smile.gif )!!! Не понимаю только в чем разница...

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

Добавлено через 5 мин.
Еше вопрос: можете дать еще какие-то формулы для задач с вероятностями.. если можете (и если еще какие-то есть)
Спасибо.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


Классическое определение вероятности: Вероятность равна числу благоприятных исходов к общему числу возможных исходов.
Здесь больше ничего не надо. А вообще в теории вероятности довольно много формул... +комбинаторика еще.


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 21:20
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name