Numere rotunde

[•Patrunjel]

Salut, am gasit o problema care suna cam asa: Se citeste de la tastatura un numar natural n.Sa se afiseze numerele rotunde mai mici decat n.(Un numar rotund este un numar care, reprezentat in binar, are acelasi numar de cifre de 0 si de 1)
Scurt pe doi: Cum se rezolva?
Adica ideea este sa fac o functie care sa verifice cum arata un numar in binar, sau ceva de genu.Ma gandeam la un for care sa ia numerele mai mici decat n, apoi sa le verifice sa vada daca indeplinesc conditia data, insa nu stiam ce conditie sa pun la for (ma gandisem la i<=n), insa ma temeam sa nu-mi scape cateva numere
Singura idee care mi-a venit este sa iau numarul n, sa il scriu in binar, apoi sa gasesc toate combinatiile posibile de 0 si 1, apoi sa transform fiecare combinatie in numar in baza 10, insa sunt sigur ca nu e cea mai buna metoda, si nici nu a ajuns materia pana aici (problema e din subprograme).Ma poate ajuta cineva cu o idee?

[•sima_cotizo]

Din moment ce stii sa scrii un numar in binar... 

[•chera_lary]

In primul rand imi pare a tema!
Ideea este destul de simpla. In niciun caz nu vei genera toate posibilitatile de 0 si 1, care se genereaza prin met BackTracking ci rezolvarea se bazeaza pe reprezentarea numerelor in baza 2! Nu este nevoie sa convertesti un numar in baza 2 pentru ca pc-ul a facut-o deja pentru tine!

Cod:

#include <math.h>

int nr0=0, nr1=0;
for(int i=0;i<n;i++)
{
    nr0=nr1=0;
    for(int j=0;j<(int)(log(i)/log(2))+1;j++)
        (i&(1<<j))?nr1++:nr0++;
    if(nr1 == nr0) cout<<i<<" ";
}

Sper sa mearga, nu am verificat! Succes!

[•Patrunjel]

Multumesc mult, vad daca merge si revin cu un LE.
Nu, nu e tema, in clasa suntem abea la matrici patratice )

[•klamathix]

In primul rand imi pare a tema!
Ideea este destul de simpla. In niciun caz nu vei genera toate posibilitatile de 0 si 1, care se genereaza prin met BackTracking ci rezolvarea se bazeaza pe reprezentarea numerelor in baza 2! Nu este nevoie sa convertesti un numar in baza 2 pentru ca pc-ul a facut-o deja pentru tine!

Cod:

#include <math.h>

int nr0=0, nr1=0;
for(int i=0;i<n;i++)
{
    nr0=nr1=0;
    for(int j=0;j<(int)(log(i)/log(2))+1;j++)
        (i&(1<<j))?nr1++:nr0++;
    if(nr1 == nr0) cout<<i<<" ";
}

Sper sa mearga, nu am verificat! Succes!

Totusi, de ce nu ar folosi in niciun caz backtracking? Pe valori mai mari ale lui n , back-ul se comporta mai bine.

[•chera_lary]

Nu am incercat! Nu sunt sigur ca back-ul are viteza mai buna decat log-ul! Stiam ca logul are rezolvare liniara! Backul are exponentiala plus ca daca aplici varianta recursiva mai ingreuneaza si ea!

[•klamathix]

Varianta ta nu e liniara in functie de n , pentru ca mai faci log() operatii pt fiecare numar. E drept ca back-ul are complexitate exponentiala, dar in cazul asta exponentiala in functie de log(n).
Daca generezi direct comb(i , i / 2 ) cu i par si i <= [log ( 2 , n )] , iesi mai bine.

Sigur, pentru problema asta probabil nu merita efortul. Zic doar sa nu desfiintam back-ul pur si simplu fiindca stim noi ca e 'cea mai ineficienta metoda de programare'. Cateodata solutia care ne pare mai buna epuizeaza si ea la fel de multe stari , sau chiar mai multe decat back-ul , daca acesta e facut cat de cat ok. Mi-am amintit si de galagia care se facea pe forum dupa oji anul trecut , ca 'Vai de mine eu stiam back, dar n-am implementat fiindca stiam ca e cea mai ineficienta metoda. Cum sa se dea la olimpiada?'