Забавная задачка

Код (Text):

1. if((signed char)a>(unsigned char)b)

Какая вероятность того что это условие будет истинным при случайных a и b?
Если это условие входит в реальную программму для обработки текстов, то в какой стране вероятность его истинности будет наибольшей?

 

Black_mirror
Ппц.. Создай одну тему с названием типа 'Головоломки' и там пости эту погань.

 

0.125

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

 

Ну я для чего ещё эта ветка нужна?
всё равно же без дела стоять будет...

 

А не 0.5 ?

 

нет
1) я может размышлял не совсем правильно,но по-простому:
в случае (unsigned char)a > (unsigned char)b вер-сть будет 0.5
в случае |(signed char)a| > (unsigned char)b вер-сть будет 0.25 (|это| модуль)
в случае (signed char)a > (unsigned char)b вер-сть будет 0.125
2) эксперимент )

Код (Text):

1. #include <stdio.h>
2. #include <stdlib.h>
3.  
4. int main()
5. {
6.     int i,c,a,b;
7.     double x = 0,y = 0;
8.    
9.     for (i = 0; i < 1000000; i++) {
10.         a = rand() % 0xff;
11.         b = rand() % 0xff;
12.         if ((signed char)a > (unsigned char)b)
13.             x++;
14.         else
15.             y++;
16.     }
17.            
18.     printf("%.3f\n",x/(x+y));
19.     return 0;
20. }

дает около 0.125

ps. из-за строго неравенства там наверное погрешность какая-то будет, т.е. вер-сть будет чуть меньше 0.125, но я думаю не на много.

 

Ra!N
Можно решить проще:
Если b>127 или a<0 , это это условие истинным быть не может. Когда 0<=a,b<=127 условие будет истинным с вероятностью 1/2. Вероятность что а и b попадают в этот интервал 1/2*1/2. То есть общая вероятность будет 1/8. А если считать точнее, то 127/1024.


Новые задачки:

a=b+c;
Какая вероятность переполнения при случайных b,c:
1) если они имеют тип unsigned?
2) если они имеют тип signed?


A - число длиной n разрядов.
F(A)=1 если в двоичном представлении числа A содержится нечётное число единиц, и F(A)=0 если чётное.
Какая вероятность того, что при увеличении A на 1, результат функции F изменится?
Как вычислить вероятность изменения результата функции F для случая прибавления фиксированной константы С?

 

Я не заметил что знак разный.

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

А ещё проще квадрат на бумаге нарисовать (по вертикали a, по горизонтели b), потом выделить область где a,b и прикинуть площадь. Делается почти в уме и почти невозможно ошибиться =)

 

Сорри за кривой подход, у меня с математикой плохо, но вобщем так:

пусть b фиксировано, тогда c должно быть <= 255-b, если просуммировать все это (т.е. (b=0 И c<=255) ИЛИ (b=1 И c<254) ИЛИ...), то получим p = 1/256*sum((255-b)/255, b=1..255) = 0.5
п.с. эксперимент дает почти 0.5

Код (Text):

1.     unsigned int i,b,c;
2.     double x = 0,y = 0;
3.    
4.     for (i = 0; i < 1000000; i++) {
5.         b = rand() % 0xff;
6.         c = rand() % 0xff;
7.         if (b + c > 0xff)
8.             x++;
9.         y++;
10.     }
11.     printf("%.3f\n",x/y);

 

с решением чето у меня туго... Но прога сказала, что ~0.875

Код (Text):

1.     int i,a,b,c;
2.     double x = 0,y = 0;
3.     for (i = 0; i < 1000000; i++) {
4.         b = rand() % 0xff;
5.         c = rand() % 0xff;
6.         if ((a = b + c) > 127 || a < -128)
7.             x++;
8.         y++;
9.     }
10.     printf("%.3f\n",x/y);

 

Ra!N
Первое решение правильное, а вторая прога врёт. А вообще эти задачки проще всего действительно графически решать.

 

зря я раньше не попробовал... только я не с квадратом решал, а просто с числовой прямой.
1) Сначала более простой способ решения про беззнаковые:
переполнение, когда a=b+c>255, b>255-c, введем d=255-c, d принадлежит [0,255] - тоже беззнаковый char. Ну а p(b>d)=0.5 очевидно.
2) Теперь со знаковыми. Переполнение, когда
a) a=b+c>127, b>127-c, d=127-c принадлежит [0,255]. Чтобы b>d, b должно быть в [1,127], d в [0,126], вер-сть этого (127/256)^2 ~ 0.25. В этом промежутке p(b>d)=0.5, т.о. в итоге получаем вер-сть p(b+c>127) ~ 0.125
б) a=b+c<-128, b<-128-c=d, d в [-255,0], там аналогично... получаем p(b+c<-128)~0.125
итог) p= p(b+c>127) + p(b+c<-128) ~ 0.25

п.с. да, в проге там ошибка, вот исправленная:

Код (Text):

1.     int i,a,b,c;
2.     double x = 0,y = 0;
3.     for (i = 0; i < 1000000; i++) {
4.         b = rand() % 0xff;
5.         c = rand() % 0xff;
6.         if ((a = (signed char)b + (signed char)c) > 126 || a < -128)
7.             x++;
8.         y++;
9.     }
10.     printf("%.3f\n",x/y);

говорит около 0.25, совпадает с результатом выше.

 

Рассмотрим двузначные двоичные числа. Вот табличка:
A; F(A); A+1; F(A+1);
---------------------
00; 0; 01; 1;
01; 1; 10; 1;
10; 1; 11; 0;
11; 0; 100; 1;
т.е. если 2 младших разряда равны 00 или 10, то F() меняется, если 01 - то не меняется, если 11 - то изменяется с вер-стью 0.5 (** не верно, см.ниже)
Получаем p(F(A+1) отличается от F(A)) = 1/4+1/4+0/4+1/8 = 5/8 = 0.625

добавлено:
п.с. для проверки тоже написал прогу, она упорно говорит 0.664, нашел ошибку в моих рассуждениях - если число оканчивается в двойчной СС на 11, то при прибавлении 1 ф-ция f изменится _не_ вер-стью 0.5. Для этих целей тоже накатал прогу, говорит, что вер-сть этого 0.656, и действительно, подставляя в формулу p = 1/4+1/4+0.6563/4=0.664 !
тока вот теоретически найти вер-сть 0.656 у меня не получается. хелп,плиз.

 

Ra!N
Вот точная формула:
p(f(a)<>f(a+1))=((2^n*2+1) div 3) / 2^n

[add]В формуле есть бага, она неработает если n=1, и всё потому что в этом случае чётность меняется даже если число оканчивается на нечётное число единиц.

А вот как считать для произвольной константы, я пока не знаю.
[/add]

 

А вы считаете с переполнением и wrap to zero или переносом единицы в n-ый разряд?

Мой вариант:
Если считать 11...1 + 1 = 100...0, то
n - четное: (2^(n+1) + 1) / (3*2^n)
n - нечетное: (2^(n+1) - 1) / (3*2^n)
Если считать 11...1 + 1 = 00...0, то
n - четное: (2^(n+1) - 2) / (3*2^n)
n - нечетное: (2^(n+1) + 2) / (3*2^n)


Верно ли, что:
если ввести функцию Q(c) : Q(0) = 0, Q(c) = 1 if c нечетное, Q(2c) = 1 - Q(c),
то (уже в случае без wrap to zero, когда мое решение совпадает с решением Black_mirror) для n-разрядных чисел полученная вероятность равна сумме по i от 0 до 2^n слагаемых Q(i), деленной на 2^n ?

 

Если у нас есть p1 = p(F(A) != F(A+1), то
p2 = p1+p1-p1*p1
p3 = p1+p2-p1*p2
p4 = p1+p3-p1*p3
... т.е. рекурсивная ф-ла
только надо учитывать еще изменение разрадности числа.

 

Я тоже так хотел сначала - не согласуется с практикой. Это ведь как - вероятность события А ИЛИ события Б. В нашем случае скорее XOR вместо ИЛИ, но не сильно меняет дело. А все потому, что мы постепенно выползаем за диапазон 0..2^n-1.
Для трехразрядных
p1 = 5/8
p2 = 5/8+5/8-5/8*5/8 = ? = 55/64 ?!, когда 3/4

Давайте нашу искомую вероятность для n-разрядных обозначать K(n, 1), где 1 - та самая прибавляемая константа. Тогда если константа есть 2^q при q < n, K(n, 2^q) = K(n - q, 1). Для остальных труднее

 

del

 

Black_mirror

Рассмотрим случай, когда к произвольному числу A прибавляется какая-то константа B. Все вычисления ограничены n разрядами. Известно, что

A + B = A^B + (A AND B)<<1

таким образом

F(A+B) = F(A^B + (A AND B)<<1) = F((A^B AND 111...10) + (A AND B)<<1) + F(A^B AND 1)

просто вынесли последний бит. Теперь обозначим для краткости
C -- (A^B AND 111...10) + (A AND B)<<1
D -- A^B AND 1
и распишем вероятность для двух слагаемых

P(F(A+B) != F(A)) = P(F(C) != F(A AND 111...10)) * P(F(D) == F(A AND 1)) + P(F(C) === F(A AND 111...10)) * P(F(D) != F(A AND 1))

Вероятность того, что последний бит A^B будет равен последнему биту A, очевидно 1/2. То есть

P(F(D) == F(A AND 1)) = P(F(D) != F(A AND 1)) = 1/2.

Кроме того, для вероятностей выполняется P(X) = 1 - P(NOT X), поэтому упростим

P(F(A+B) != F(A)) = P(F(C) != F(A AND 111...10))*1/2+ (1 - P(F(C) != F(A AND 111...10)))*1/2
= 1/2 - 1/2*P(F(C) != F(A AND 111...10)) + 1/2*P(F(C) != F(A AND 111...10))
= 1/2.

Вот так, оказывается P(F(A+B) != F(A)) равна всегда 1/2. Найдите ошибку в рассуждениях

 

Сомневаюсь.. Мне неочевидно
Последний бит A = посл.бит A^B <=> посл.бит A^(A^B) = 0 <=> посл.бит B = 0, а вероятность этого либо 1, если B четное, либо 0, если B нечетное.