Algorytm "wypisujący" wszystkie ciągi zero jedynkowe długości n

2018-12-15 16:21
0

Cześć, potrzebuję pseudokod lub schemat blokowy algorytmu który ma "wypisać" wszystkie ciągi zero jedynkowe długości n. N to liczba naturalna która sami zadajemy.

Dana jest liczba naturalna n. Wypisać wszystkie ciągi
zero-jedynkowe długości n

edytowany 1x, ostatnio: furious programming, 2018-12-15 17:44
Jak duże ma być n? - hauleth 2018-12-17 13:01

Pozostało 580 znaków

2018-12-15 17:24
0

Generalnie robisz 1 funkcję, która potrafi wyświetlić liczbę binarną długości n i 2gą funkcję, która potrafi dodać 1 do liczby binarnej. Potem robisz tak:

  1. a = 0, n = 8
  2. printAsBinary(a, n)
  3. add1ToVariable(a, n)
  4. if a != 0:
    4.1. goto 2

Zgodnie z arytmetyką binarną funkcja dodająca 1 powinna ustawić same 0 w zmiennej, jeśli ta by potrzebowała więcej bitów niż możliwe na zapis. To możesz wykorzystać do sprawdzenia, czy wypisałeś już wszystkie.


loop:
push 0FFFFFFFFh
call Sleep
jmp loop
edytowany 1x, ostatnio: hit02, 2018-12-15 17:25

Pozostało 580 znaków

2018-12-15 17:26
2

Idea jest taka: zaczynając od zera, Dodajesz 2 ^ (n - 1)razy jeden:
0000 -> + 1
0001 -> + 1
0010 -> + 1
0011 -> + 1
.... I tak dalej.


edytowany 2x, ostatnio: lion137, 2018-12-15 23:30

Pozostało 580 znaków

2018-12-17 09:50
1

Dla dużych n Wasze sposoby przekroczą zakres (dla tradycyjnych intów, ale w Pythonie3 już powinno działać). Natomiast można to zrobić rekurencyjnie:

ciag :: Integer -> [String]
ciag 0 = [""]
ciag n =
    [ ('0':x) | x <- ciag (n-1) ] ++
    [ ('1':x) | x <- ciag (n-1) ]

(przykład w Haskellu).

Który z kolei dla dużych N może się wyłożyć na rekurencji. - hauleth 2018-12-17 13:00
Jeśli zrealizować dodawanie na stringach czy tablicach zer i jedynek, to mój sposób nie przekroczy zakresu. - lion137 2018-12-17 13:14
@hauleth: Nie wiem o jak dużych N mówimy :) ale w Haskellu, dzięki leniwym obliczeniom (bo ta funkcja tu to jest generator, nie tworzy wszystkiego w miejscu...), działa bez problemu dla 700000 (5 zer) bitów. Dla większych już nie chciało mi się sprawdzać, bo trzeba poczekać trochę nawet na pierwszy wynik. - koszalek-opalek 2018-12-17 13:39
@koszalek-opalek: a używając rozwiązania @lion137 i tablicy u64 możesz to samo uzyskać zdecydowanie szybciej, bo wypisywanie wyniku masz zawsze w czasie stałym. - hauleth 2018-12-17 17:05
@hauleth: W czasie stałym, bo ograniczone rozmiarowo. Poza tym, chyba nie w czasie stałym. :) - koszalek-opalek 2018-12-18 12:20

Pozostało 580 znaków

Liczba odpowiedzi na stronę

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