Jump to content
Byte-ul

Generarea unui numar aleator

By Byte-ul, in Challenges (CTF)

Recommended Posts

Byte-ul Newbie

Byte-ul

Posted
Posted (edited)

Se presupune ca avem o functie "zerounu" care returneaza in mod aleator 0 sau 1.

Sa se foloseasca aceasta functie in generarea unui numar aleator intre 0 si 999 (inclusiv).

  • Fiecare numar trebuie sa aiba o sansa de 1/1000% sa fie generat. (sanse egale)
  • Nu aveti voie sa folositi alte functii pentru a genera numere aleatoare in exteriorul functiei zerounu.

Codul poate fi in orice limbaj de programare atat timp cat face ceea ce trebuie.

Au rezolvat:

@TheTime

Edited by Byte-ul
sudo Newbie

sudo

Posted
Posted (edited)

@xVIRal: Nu ai inteles, trebuie sa te folosesti de functia zerounu care iti va returna 0 sau 1. Revin si eu cu o rezolvare daca reusesc.


function zerounu(){

    return rand(0,1);    

}

-->asta este functia, xVIRal.

Iar asta ar fi codul meu, cand am vazut zerounu mi-a mers gandul la binare, deci, numarul maxim de pozitii ale unui numar din intervalul [0,999] scris binar ar fi 10, de aceea am folosit un for impreuna cu functia zerounu si la fiecare pas am generat o pozitie din numarul binar. sansele sunt corecte, dupa mintea mea de 2 noaptea.

Asta ar fi codul.


<?php

function zerounu(){

    return rand(0,1);    

}

$num = 0;
for($i=1; $i<=10;$i++)
  $num = $num*10+zerounu();
echo bindec($num);
?>

Edited by sudo
Ganav Newbie

Ganav

Posted
Posted (edited)

@Byte-ul 999 poate fi codificat in 10 biti(2^9 = 512 < 999 < 2^10 = 1024). Presupunand ca gunctia zerounu are o aleotropie satisfacatoare, spre exemplu, rezultatul furnizat de catre un apel nu este dependent de cele de dinaintea sa atunci solutia este:


start:
pentru i = 0, nr = 0, i < 10, i++       // ne trebuiesc 10 biti
          nr ^= zerounu()                  // alegem cate unul in mod arbitrar
          nr <<= 1                           // inmultim cu 2(shift-are spre stanga practic crestem numarul cu o pozitie binara. 0110 devine 1100)
gata

daca nr   > 1111100111               // ne asiguram ca numarul nu este mai mare ca si 999
       goto start                       
gata

Edited by Ganav
gigiRoman Proficient

gigiRoman

Posted
Posted

static void Generate()

{

Random random = new Random();

string bytenumber = "";

for (int i = 0; i < 10; i++)

{

if (bytenumber.Length > 5)

{

if (bytenumber.Substring(0, 4) == "11111")

{

bytenumber = "1111100";

i += 2;

}

}

else

bytenumber += random.Next(0, 2).ToString();

}

Console.WriteLine(Convert.ToInt32(bytenumber, 2));

}

TheTime Newbie

TheTime

Posted
Posted
@Byte-ul 999 poate fi codificat in 10 biti(2^9 = 512 < 999 < 2^10 = 1024). Presupunand ca gunctia zerounu are o aleotropie satisfacatoare, spre exemplu, rezultatul furnizat de catre un apel nu este dependent de cele de dinaintea sa atunci solutia este:


pentru i = 0, nr = 0, i < 10, i++       // ne trebuiesc 10 biti
          nr ^= zerounu()                  // alegem cate unul in mod arbitrar
          nr <<= 1                           // inmultim cu 2(shift-are spre stanga practic crestem numarul cu o pozitie binara. 0110 devine 1100)
gata

daca nr   > 1111100111               // ne asiguram ca numarul nu este mai mare ca si 999
        nr &= 1111100111                       
gata

Codul tau nu asigura o distributie uniforma. Numarul 1111100111 are sanse mai mari sa fie obtinut decat 0000000000, spre exemplu.

Pentru a obtine 0, trebuie sa obtii 0000000000.

Pentru a obtine 999, poti obtine random 1111100111, 1111110111, 1111101111, 1111111111.

Sper ca intelegi care e problema.

Uniformitatea este asigurata pe intervalul 0 - 1023, nu pe intervalul 0 - 999. Un workaround simplu ar fi sa generam pana cand obtinem un numar in intervalul dorit. Daca este in afara intervalului, mai generam o data. Recursivitate FTW!


int generate () {
	int nr = 0;

	for (int i=0 ; i<9 ; i++) {
		nr = nr * 2 + zerounu();
	}

	if (nr < 1000)
		return nr;
	else
		return generate();
}

Daca nu va place ideea de recursivitate, pentru ca "Nu aveti voie sa folositi alte functii pentru a genera numere aleatoare in exteriorul functiei zerounu", avem si o solutie mai putin eleganta.


int nr = 0;

for (int i=0 ; i<9 ; i++) {
	nr = nr * 2 + zerounu();

	if (nr > 999) { /* nu vrem sa iesim din for pana nu obtinem un numar in intervalul dorit. for recursiv?  */
		i = 0;
		nr = 0;
	}
}

em Newbie

em

Posted
Posted

Nice challenge.

Netestat, matematic imi pare OK.


cauta(int min, int max) {
  if(min == max)
    return min;
  int median = (mid + max)/2;
  if(zerounu() == 1) {
    /* search upper */
    cauta(median, max);
  else
    /* search lower */
    cauta(min, median);
}

int main() {
  cauta(0, 999);
}

tjt Rookie

tjt

Posted
Posted (edited)

Varianta mea:

import java.util.*;
import java.lang.*;
import java.io.*;

class Challenge
{

        public static int zerounu()
	{
		Random rand = new Random();
		return rand.nextInt(2);
	}

	public static int randNumar()
	{
		int i = 0;
		int numar = 0;
		while(i++ != 3) // 3 -> nr maxim de cifre al numarului
		{
			int cifra = 0;
			for(int j = 1; j<=9; j++)
			{
				cifra += zerounu();
			}
			numar = numar*10 + cifra;
		}
		return numar;
	}

	public static void main (String[] args) 
	{
		System.out.println("" + Challenge.randNumar());
	}
}

Edited by tjt
TheTime Newbie

TheTime

Posted
Posted
Nice challenge.

Netestat, matematic imi pare OK.


cauta(int min, int max) {
  if(min == max)
    return min;
  int median = (mid + max)/2;
  if(zerounu() == 1) {
    /* search upper */
    cauta(median, max);
  else
    /* search lower */
    cauta(min, median);
}

int main() {
  cauta(0, 999);
}

Poate ma insel, dar matematic nu imi pare OK. Per total, numerele din jumatatea inferioara sunt putin avantajate fata de cele din jumatatea superioara, pentru ca nu poti asigura o distributie egala de numere pentru /* search upper */ si /* search lower */. In plus, algoritmul tau nu va obtine niciodata 999

## Pentru a obtine 0: (functia zerounu() trebuie sa returneze doar 0)

Dupa prima iteratie: median = (0 + 999) / 2 = 499

Dupa a 2-a iteratie: median = (0 + 499) / 2 = 249

Dupa a 3-a iteratie: median = (0 + 249) / 2 = 124

Dupa a 4-a iteratie: median = (0 + 124) / 2 = 62

Dupa a 5-a iteratie: median = (0 + 62) / 2 = 31

Dupa a 6-a iteratie: median = (0 + 31) / 2 = 15

Dupa a 7-a iteratie: median = (0 + 15) / 2 = 7

Dupa a 8-a iteratie: median = (0 + 7) / 2 = 3

Dupa a 9-a iteratie: median = (0 + 3) / 2 = 1

Dupa a 10-a iteratie: median = (0 + 1) / 2 = 0

## Pentru a obtine 999: (functia zerounu() trebuie sa returneze doar 1)

Dupa prima iteratie: median = (0 + 999) / 2 = 499

Dupa a 2-a iteratie: median = (499 + 999) / 2 = 749

Dupa a 3-a iteratie: median = (749 + 999) / 2 = 874

Dupa a 4-a iteratie: median = (874 + 999) / 2 = 936

Dupa a 5-a iteratie: median = (936 + 999) / 2 = 967

Dupa a 6-a iteratie: median = (967 + 999) / 2 = 983

Dupa a 7-a iteratie: median = (983 + 999) / 2 = 991

Dupa a 8-a iteratie: median = (991 + 999) / 2 = 995

Dupa a 9-a iteratie: median = (995 + 999) / 2 = 997

Dupa a 10-a iteratie: median = (997 + 999) / 2 = 998

Dupa a 11-a iteratie: median = (998 + 999) / 2 = 998

@tjt,

Nu ai obtinut o distributie uniforma, ci mai de graba ceva ce are forma clopotului lui Gauss.

Pentru a avea ultima cifra 0, trebuie sa obtii de 10 ori consecutiv 0 (0+0+0+0+0+0+0+0+0+0).

Pentru a avea ultima cifra 1, poti obtine:

1+0+0+0+0+0+0+0+0+0 sau

0+1+0+0+0+0+0+0+0+0 sau

0+0+1+0+0+0+0+0+0+0 sau

0+0+0+1+0+0+0+0+0+0 sau

0+0+0+0+1+0+0+0+0+0 sau

0+0+0+0+0+1+0+0+0+0 sau

0+0+0+0+0+0+1+0+0+0 sau

0+0+0+0+0+0+0+1+0+0 sau

0+0+0+0+0+0+0+0+1+0 sau

0+0+0+0+0+0+0+0+0+1 sau

Deja este de 10 ori mai probabil sa obtii cifra 1 decat sa obtii cifra 0, ceea ce nu este OK.

Ganav Newbie

Ganav

Posted
Posted
Codul tau nu asigura o distributie uniforma. Numarul 1111100111 are sanse mai mari sa fie obtinut decat 0000000000, spre exemplu.

Pentru a obtine 0, trebuie sa obtii 0000000000.

Pentru a obtine 999, poti obtine random 1111100111, 1111110111, 1111101111, 1111111111.

Sper ca intelegi care e problema.

Uniformitatea este asigurata pe intervalul 0 - 1023, nu pe intervalul 0 - 999. Un workaround simplu ar fi sa generam pana cand obtinem un numar in intervalul dorit. Daca este in afara intervalului, mai generam o data. Recursivitate FTW!


int generate () {
	int nr = 0;

	for (int i=0 ; i<9 ; i++) {
		nr = nr * 2 + zerounu();
	}

	if (nr < 1000)
		return nr;
	else
		return generate();
}

Daca nu va place ideea de recursivitate, pentru ca "Nu aveti voie sa folositi alte functii pentru a genera numere aleatoare in exteriorul functiei zerounu", avem si o solutie mai putin eleganta.


int nr = 0;

for (int i=0 ; i<9 ; i++) {
	nr = nr * 2 + zerounu();

	if (nr > 999) { /* nu vrem sa iesim din for pana nu obtinem un numar in intervalul dorit. for recursiv?  */
		i = 0;
		nr = 0;
	}
}

In principiu da e corect(rulam din nou algoritmul daca am iesit din interval):


start:
pentru i = 0, nr = 0, i < 10, i++       // ne trebuiesc 10 biti
          nr ^= zerounu()                  // alegem cate unul in mod arbitrar
          nr <<= 1                           // inmultim cu 2(shift-are spre stanga practic crestem numarul cu o pozitie binara. 0110 devine 1100)
gata

daca nr   > 1111100111               // ne asiguram ca numarul nu este mai mare ca si 999
       goto start                       
gata

Codul de mai sus returneaza un numar in afara multimii {0, ... , 999} cu probabilitatea (1024 - 999) / 1000 = 25 / 1000 = 1 / 40. Deci sansele ca doua numere generate succesiv sa fie in afara intervalului sunt: 1 / 40 ^ 2, ca trei sa fie in afara 1 / 40 ^ 3. Deci functia este neglijabila(scade mai repede decat orice functie polinomiala).

sudo Newbie

sudo

Posted
Posted (edited)

Am omis noaptea trecuta generarea numerelor peste 999, din oboseala.

Varianta finala:


<?php

function zerounu(){

    return rand(0,1);    

}
function generate(){
	$num = 0;
for($i=1; $i<=10;$i++)
  $num = $num*10+zerounu();
return bindec($num);
}

$cont = TRUE;
while($cont){
	$curr = generate();
	if(generate()<999)
		$cont = FALSE;
}
echo $curr;
?>

Edited by sudo
S.L.C Newbie

S.L.C

Posted
Posted (edited)

Sper ca nu este atat de tarziu incat sa fie considerat bumping.

Implementatie C++(11) (implementatia actuala este c/c++ normal) testat cu MinGW GCC 5.2.0 x32

#include <ctime>
#include <cmath>
#include <bitset>
#include <random>
#include <iostream>

// helper functor to randomly generate numbers between 0 and 1
struct Random
{
    std::mt19937 Generator;
    std::bernoulli_distribution Distribution;
    Random(double ratio = 0.5d)
        : Generator(static_cast<std::mt19937::result_type>(std::time(nullptr)))
        , Distribution(ratio)
    {

    }

    int operator () (void)
    {
        return static_cast<int>(Distribution(Generator));
    }
};

static Random zerounu;

int Generate();

int main(int argc, char **argv)
{
    std::bitset<1000> nums;
    int num = 0;
    std::size_t tries = 0;

    /* 'tries' has a chance of overflow! hopefully it won't reach there */
    for (; !nums.all(); ++tries)
    {
        num = Generate();

        if (!nums.test(num))
        {
            nums.set(num, true);
        }

        std::cout << nums.count() << ", ";
    }

    std::cout << "\nit took " << tries << " tries to generate every number between 0 - 999 at least once\n";

    return EXIT_SUCCESS;
}


int Generate()
{
    int num = 0x5555;

    for (int i = 0; i < 16; ++i)
    {
        num ^= (zerounu() << i);
    }

    num = abs(num);

    // 2048 and not 999 number is used to reduce favor of higher numbers
    while (num > 2048)
    {
        num /= 2;
    }

    return num > 999 ? abs(num - 1049) : num;
}

Edited by S.L.C

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
Go to topic listing
×
×
  • Create New...