algorytm liczacy 0 miedzy 1 w ciagu binarnym, prosze o pomoc

0

Witam,
Jest takie zadanie:

In the binary number "100100010000" there are at least two 0s between any two consecutive 1s.
In the binary number "100010000100010" there are at least three 0s between any two consecutive 1s.
A positive integer N is called K-sparse if there are at least K 0s between any two consecutive 1s in its binary representation.
For example, the binary number "100100010000" is 2-sparse. Similarly, "100010000100010" is 3-sparse. It is also 2-sparse, because 2 < 3. It is also 1-sparse and 0-sparse.
We assume that any power of 2 (i.e. "1", "10", "100", "1000", ...) is K-sparse for any K.
Write a function:
int sparse_binary_count(char *S, char *T, int K);
that, given:
string S containing a binary representation of some positive integer A,
string T containing a binary representation of some positive integer B,
a positive integer K.
returns the number of K-sparse integers within the range [A..B] (both ends included). If the result exceeds 1,000,000,006, the function should return the remainder from the division of the result by 1,000,000,007.
For example, given S = "101" (A = 5), T = "1111" (B=15) and K=2, the function should return 2, because there are just two 2-sparse integers in the range [5..15], namely "1000" (i.e. 8) and "1001" (i.e. 9).
Assume that:
K is an integer within the range [1..30];
the length of S is within the range [1..300,000];
the length of T is within the range [1..300,000];
string S consists only of the characters 0and/or 1;
string T consists only of the characters 0and/or 1;
S and T have no leading zeros;
A ≤ B.
Complexity:
expected worst-case time complexity is O(log(A+B));
expected worst-case space complexity is O(log(A+B)) (not counting the storage required for input arguments).
Notation used:
A − number represented by S;
B − number represented by T.

Maksymalna długość ciągu to 300,000 czyli 2300tys , nie ma tak duzej liczby w języku C, poniewaz long double to okolo 175000.
czyli trzeba wyłącznie na tablicy operować, zgadza się? Tzn. zamienić łancuch "101010" na tablice A[0]=1,A[1]=0.....itd. i napisac algorytm dodawania o 1(dziesietne) tylko bez przekształcania na liczbe dziesietna i operacje robic tylko na tablicy zer i jedynek.

Rozwiązanie powinno używać wyłącznie bibliotek z C.

0

Pomyśl dłużej nad tym zadaniem. Zwiększanie o jeden i sprawdzanie na pewno nie przejdzie. Mogę Ci podpowiedzieć to, że dla liczb 1-sparse możesz dla danej ilości cyfr rozróżnić liczby zaczynające się od 1 i od 0 (w metaforze liczbowej po prostu z pustymi wysokimi bitami). Oznaczmy dla liczby o długości n przez p1(n) ilość ciągów zaczynających się od 1, a przez p0(n) ilość ciągów zaczynających się od 0. Można zobaczyć, że p1(n)=p0(n-1) oraz p0(n)=p1(n-1)+p0(n-1), co robimy przez wstawienie cyfry na początek. Na tej samej zasadzie należy to rozszerzyć na wszystkie k.

0

Przepraszam ale nie rozumiem co piszesz troche nie moge powiazac tego z zadaniem.... wszystkie ciagi sie zaczynaja od 0 danym przedziale [A..B]....chodzi ci o wykorzystanie powiązania między długością każdego ciągu i tym że w sómie ile będzie np. "000" w ciągu 20 znakowym to zalezy wylącznie od własnie długosci tego ciagu...

reasumujac chodzi mi o to ze można to policzyć wyznaczajac algorytm który analizuje ile może takich możliwości wystąpić, w każdym ciągu, który sie zwiększa za każdym razem o długość 1(tym razem o dlugość a nie wartość dziesiętna, co znacznie przyspieszy działanie programu:)) ...

do konca nie zrozumialem o co Ci chodzilo ale udalo mi sie spojrzec inaczej na to zadanie dzieki tobie.

0

Witam, możecie mi wytłumaczyć bo nie bardzo rozumiem czemu w przykładzie liczba 8 czyli 1000 jest odpowiedzią skoro nie jest pomiędzy dwoma 1 ??

0
testowy napisał(a)

Witam, możecie mi wytłumaczyć bo nie bardzo rozumiem czemu w przykładzie liczba 8 czyli 1000 jest odpowiedzią skoro nie jest pomiędzy dwoma 1 ??

We assume that any power of 2 (i.e. "1", "10", "100", "1000", ...) is K-sparse for any K.

0

Sorry ale nadal nie rozumiem, K-spare to jest jakaś tam liczba 0 pomiędzy dwoma jedynkami ?? Parametr K odpowiada za ilość 0 po 1??
Pozdrawiam

0
testowy napisał(a)

K-spare to jest jakaś tam liczba 0 pomiędzy dwoma jedynkami
i dodatkowo
We assume that any power of 2 (i.e. "1", "10", "100", "1000", ...) is K-sparse for any K.

0

jakie jest właściwie pytanie?
Tak masz używać tylko tablicy char bez konwersji na liczbę binarną (jest to zbędne).
Łańcuch cstringa jest tablicą char, więc nie musisz konwertować czegokolwiek!

0
testowy napisał(a)

Sorry ale nadal nie rozumiem, K-spare to jest jakaś tam liczba 0 pomiędzy dwoma jedynkami ?? Parametr K odpowiada za ilość 0 po 1??
Pozdrawiam

Jest to wyjątek... w którym przyjmujemy ze dla K=0 wynik wynosi 1; K=1 wynik wynosi 1 dla K =2; 2^2 = 100(binarny) wynik 1 ... i tak dalej i to sa wyjatki. Dla K=100 wynik dalej bedzie 1 dla (100-spare);

1 użytkowników online, w tym zalogowanych: 0, gości: 1