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ł?
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ł?
Samych takich ciągów jest wykładniczo wiele względem n (dla n = 100 dokładnie googol), więc to chyba oczywiste.
Prawdopodobnie chodzi o liczbę kombinacji jakie utworzysz a jest ich:
10 * 10 * 10… = 10^100 czyli słownie 1jeden i sto zer
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.
Przecież flash4gordon dokładnie to samo powiedział: - “googol”.
Ale ja wytłumaczyłem co i dlaczego