Zagadka o stu przełącznikach, wersja w Pythonie

Dawno, dawno temu, wrzuciłem na bloga zagadkę matematyczną o stu przełącznikach. Zagadka cieszyła się umiarkowaną oglądalnością, ludzie bowiem trafiają do mnie szukając konkretów, a nie jakichś durnych zagadek. Niemniej jednak kilkanaście osób wpis przeczytało, a to już całkiem nieźle.

Dziś chciałbym pokazać, w jaki sposób zagadkę tę rozwiązać przy pomocy Pythona. Głównym celem będzie, oczywiście, nie rozwiązanie zagadki (która jest trywialna i przy odrobinie oleum między uszami może być rozwiązana między uszami), ale dlatego, żeby pokazać, jak w Pythonie działa rozwijanie list (tak się chyba tłumaczy „list comprehension”, nie jestem pewien) tudzież operator trójwartościowy ( a może potrójny? tu też nie jestem pewien polskiego nazewnictwa, po naszemu to jest „ternary operator”).

Najpierw przypomnę treść samej zagadki:

Mamy sto przełączników dwupozycyjnych (czyli takich, które mogą być albo włączone, albo wyłączone, tertium non datur). Następnie wykonujemy sto kroków, w każdym kroku przełączamy co N-ty przełącznik (gdzie N jest numerem kroku). Czyl iw pierwszym kroku przełączamy wszystkie, w drugim, tylko parzyste (co drugi), w trzecim kroku trzeci, szósty, dziewiąty i tak dalej aż do 99-go, w czwartym – co czwarty, i tak dalej, aż do setnego kroku, w którym przełączamy ostatni, setny przełącznik.

Pytanie: ile przełączników pozostanie włączonych po stu krokach?

Odpowiedź brzmi: dziesięć. Dlaczego akurat dziesięć? Proszę sobie znaleźć oryginalny wpis, tam jest szczegółowo i z przykładami wyjaśnione. Dziś napiszemy króciutką Pchełkę symulującą te nasze przełączniki.

Lecimy:

switches = [False for x in range(100)]
for j in range(100):
    switches = [not(switches[i]) if (i + 1) % (j + 1) == 0 else switches[i] for i in range(100)]
print(switches.count(True))

Tylko cztery linijki kodu, a ileż radości! Spróbujmy przeanalizować teraz, kawałek po kawałku, co tu się właściwie dzieje.

W pierwszej linii generujemy sobie stuelementową listę, poindeksowaną od 0 do 99, wypełnioną w całości wartością False (Fałsz, czyli wyłączony przełącznik). To jest nasza sytuacja początkowa.

Następnie w drugiej linii otwieramy pętlę FOR. Każde wykonanie pętli reprezentuje jeden krok naszego algorytmu.

Trzecia linia to samo gęste, czyli wykonujemy pojedynczy krok. Dla każdego przełącznika sprawdzamy, czy jego pozycja jest całkowitą wielokrotnością aktualnie wykonywanego kroku ((i+1)%(j+1)==0), jeżeli tak, negujemy przełącznik na tej pozycji, w przeciwnym wypadku pozostawiamy przełącznik bez zmian.

Właśnie tutaj widzimy rozwijanie list w akcji. Składnia: L = [e for z in E] oznacza podstawienie za zmienną L listy wygenerowanej za pomocą wyrażenia e opartego na zmiennej z zwróconej wielokrotnie z listy lub generatora E.

Bardzo to brzmi zawile, prawda?

No to zerknijmy na prosty przykład:

slownik = [x.strip('\n') for x in f.readlines()]

Tutaj wczytujemy do zmiennej slownik (lista) wartości zwrócone przez generator readlines() a następnie przepuszczone przez metodę strip().

Z tym, że – żeby nie było za nudno – tutaj mamy dodatkową atrakcję w postaci operatora potrójnego. Cały kawałek kodu, zaczynając od miejsca za otwierającym nawiasem kwaedratowym, aż do spacji poprzedzającej słówko for, to taki właśnie operator.

Spójrzmy na prostszy przykład:

a = 1
b = 2
c = 5 if a < b else 6

Powyższe trzy linie kodu sprawią, że do zmiennej c trafi piątka, bo jeden jest mniejsze niż dwa. Gdyby zamienić wartości a i b, do c trafiłaby szóstka.

Wszystko to bardzo piękne jest. No i daje dziesięć na wyjściu, czyli wszystko gra.

O. Śnieg za oknem. A ja się niedawno śmiałem z naszych szamanów…

Autor: xpil

Po czterdziestce. Żonaty. Dzieciaty. Komputerowiec. Krwiodawca. Emigrant. Rusofil. Lemofil. Sarkastyczny. Uparty. Mól książkowy. Ateista. Apolityczny. Nie oglądam TV. Uwielbiam matematykę. Walę prosto z mostu. Gram na paru instrumentach. Lubię planszówki. Słucham bluesa, poezji śpiewanej i kapel a’capella. || Kliknij tutaj po więcej szczegółów ||

Dodaj komentarz

2 komentarzy do "Zagadka o stu przełącznikach, wersja w Pythonie"

Powiadom o
avatar
Sortuj wg:   najnowszy | najstarszy | oceniany
raf
Gość

Zawsze podziwiam ludzi ktorzy ogarniaja ta nowomowe znaczy jezyki programowania. Nie mam zielonego pojecia jak to mozliwe co wiecej nauke japonskiego uwazam za latwiejsza niz tego calego pythona a ponoc musicie znac pare jezykow. Dlugo to tak Panu zajelo,przyswojenie tego i czy jest jakis sposob zeby to wchodzilo do glowy. Nie zebym zaczal to robic,pytam z ciekawosci.

wpDiscuz