2008-07-26 ден на админския махмурлук
July 26th, 2008 by Vasil KolevСнощи в средно пияно състояние около един спор с Гунински (дължа му една бира) написах едно тестово програмче…
Въпросът беше следния – ако имаме две множества с 2^16 елемента, като всеки елемент може да е от 0 до 2^32, какъв е шансът сечението на двете множества да не е празното множество. Понеже количеството алкохол не предразполагаше към математика (а червото само ни препсува и отказа да го сметне), написах следното нещо, което да вади някаква статистика:
(да се отбележи, за пръв път успявам да използвам qsort() :) )
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/fcntl.h>
#include <stdlib.h>
#define LEN 65536
#define NTEST 100
static int compare(const void *a, const void *b)
{
if (*((int *) a) > *((int *) b)) return 1;
if (*((int *) a) < *((int *) b)) return -1;
return 0;
}
int do_whatever()
{
int s0[LEN],s1[LEN];
int i=0,j=0;
int rndsrc;
rndsrc=open("/dev/urandom",O_RDONLY);
read(rndsrc,s0,(sizeof(int)*LEN));
read(rndsrc,s1,(sizeof(int)*LEN));
close(rndsrc);
qsort (s0,LEN,sizeof(int),compare);
qsort (s1,LEN,sizeof(int),compare);
while ( (s0[i]!=s1[j]) && (i<LEN) && (j<LEN))
{
if (s0[i]<s1[j]) { if (!i<LEN) i++; }
else {if (!j<LEN) j++;};
}
if (s0[i]==s1[j]) return 1;
return 0;
}
int main()
{
int i,num=0;
for (i=0;i<NTEST;i++)
num+=do_whatever();
printf ("tests %d true %d false %d\n",NTEST,num,NTEST-num);
return 0;
}
Гунински твърдеше, че шансът клони към 1, и е прав – според програмката излиза над 1:2, което си клони към 1 :)
А, да, Шопов, как можа да ме черпиш две бири, след като бях пил толкова. Половината сутрин ми се искаше да съм умрял :).
Който помни повече от празнуването – да пише.