Problem ogólny (generowanie ciągów)


(Jedras121) #1

Uzasadnić że problem generowania wszystkich ciągów skończonych o długości 100 w alfabecie {0123456789} jest trudny obliczeniowo.

Ma ktoś jakiś pomysł?


(Marcin 110) #2

Samych takich ciągów jest wykładniczo wiele względem n (dla n = 100 dokładnie googol), więc to chyba oczywiste.


(przemo_li) #3

Prawdopodobnie chodzi o liczbę kombinacji jakie utworzysz a jest ich:

10 * 10 * 10.... = 10^100 czyli słownie 1jeden i sto zer :smiley:

A obliczasz to w prosty sposób:

Na pierwszym miejscu może być 10 kombinacji

Dla każdej kombinacji z 1 pola na drugim polu może być 10 liter alfabetu.

Więc już mamy 10 * 10

I tak dalej dla każdego pola.


([alex]) #4

Przecież flash4gordon dokładnie to samo powiedział: - "googol".


(przemo_li) #5

Ale ja wytłumaczyłem co i dlaczego :wink: