Pchełki Powershell: Pętla kwadratów

Bierzemy liczbę całkowitą dodatnią.

Podnosimy każdą z jej cyfr do kwadratu.

Kwadraty sumujemy.

Wynik sumowania poddajemy tej samej operacji: każdą cyfrę podnosimy do kwadratu, kwadraty sumujemy  i tak dalej.

Co z tego wyjdzie?

Otóż albo wyjdzie z tego jedynka, albo trafimy na następującą pętlę:

… 4 => 16 => 37 => 58 => 89 => 145 => 42 => 20 => 4 …

Czemu tak?

Nie mam pojęcia. Ale wiem, jak to zweryfikować dla kilku początkowych liczb, a przy okazji pokazać parę tricków PowerShell.

No to lecimy:

Clear-Host
$petla = @(1,4,16,37,58,89,145,42,20)
$maxkrok = 0
$sumy = New-Object 'System.Collections.Generic.List[int32]'
(1..100000) | ForEach-Object {
    $sprawdz = $_
    $krok = 0
    $suma = 0
    $sumy.Clear()
    while(-Not $petla.Contains($suma)) {
        $suma = 0
        [int[]]$cyfry = $($sprawdz.ToString() -Split "")
        for($i = 0; $i -lt $cyfry.Length; $i++) {
            $suma += ($cyfry[$i] * $cyfry[$i])
        }
        $sprawdz = $suma
        $sumy.Add($suma)
        $krok += 1
    }
    if($krok -gt $maxkrok) {
        $maxkrok = $krok
        Write-Host $_ ":" $krok ":"  $sumy
    }
}

Powyższy kod działa w ten sposób, że dla kolejnych liczb zlicza ilość kroków potrzebnych na „wpadnięcie w pętlę” i wyświetla wyniki tylko wtedy, kiedy ilość kroków jest większa, niż poprzednie maksimum. Dzięki temu na ekranie widzimy tylko te „interesujące” przypadki:

1 : 1 : 1
3 : 5 : 9 81 65 61 37
6 : 9 : 36 45 41 17 50 25 29 85 89
112 : 10 : 6 36 45 41 17 50 25 29 85 89
269 : 11 : 121 6 36 45 41 17 50 25 29 85 89
15999 : 12 : 269 121 6 36 45 41 17 50 25 29 85 89

Jak widać między jedynką a stu tysiącami maksymalna ilość kroków potrzebna na „wpadnięcie w pętlę” to 12, dla 15999. Sprawdziłem też liczby większe, aż do miliona – nie ma tam dłuższej pętli.

Teraz kilka objaśnień dla tych z Czytelników, którzy jakimś cudem jeszcze trzymają pion:

Na początku czyścimy ekran za pomocą Clear-Host.

Następnie zapamiętujemy dziewięć „magicznych” wartości (osiem z pętli plus jedynka dziewiąta) w zmiennej $petla.

Zmienna $maxkrok będzie przechowywać największą znalezioną dotychczas liczbę kroków potrzebnych do zapętlenia (zaczynamy od zera).

Wreszcie dla każdej znalezionej pętli będziemy zapamiętywać ciąg kolejnych sum prowadzących do zapętlenia – zrobimy to za pomocą zmiennej $sumy, której deklaracja pokazuje jeden z bardzo ważnych aspektów języka PowerShell, a mianowicie możliwość korzystania z typów danych .Net (w tym przypadku: System.Collections.Generic.List[int32] czyli kolekcja obiektów typu int32). Używamy kolekcji zamiast standardowej powershellowej tablicy, ponieważ kolekcja działa o wiele szybciej.

No i teraz samo gęste, czyli:

(1..100000) – tutaj generujemy „w locie” tablicę wszystkich liczb całkowitych od 1 do 100000, a następnie iterujemy po niej za pomocą ForEach-Object.

Dla każdej liczby zapamiętujemy jej wartość w zmiennej $sprawdz (dla niezorientowanych: $_ to w PowerShell specjalna zmienna dostępna wewnątrz iteratorów, oznaczająca bieżący element iterowanej kolekcji).

Zerujemy zmienne $krok i $suma oraz czyścimy listę zapamiętanych sum (z poprzedniej iteracji).

Następnie – ponieważ wiemy na pewno, że prędzej czy później wpadniemy w pętlę – rozpoczynamy proces liczenia sum, za każdym razem sprawdzając, czy aktualnie wyliczona suma trafiła w pętlę, czy nie: while(-Not $petla.Contains($suma)).

Najpierw zerujemy sumę ($suma = 0), następnie dzielimy zmienną $sprawdz na pojedyncze cyfry za pomocą operatora -Split.

 Uwaga: ponieważ operator -Split wymaga użycia separatora, podanie pustego tekstu "" jako separatora sprawi, że $sprawdz zostanie podzielone na pojedyncze cyfry, czy czym – ponieważ "" występuje też przed pierwszą oraz po ostatniej cyfrze – na początku i na końcu zostanie dopisane 0. Innymi słowy „234” zostanie rozbite na cyfry jako (0,2,3,4,0), a „51203” jako (0,5,1,2,0,3,0). Nam to nie przeszkadza, ponieważ sumujemy kwadraty (kwadrat zera nie zmienia wyniku sumowania), ale warto zapamiętać ten efekt uboczny operatora -Split.
 

W kolejnym kroku sumujemy kwadraty poszczególnych cyfr, a więc otwieramy pętlę: for($i = 0; $i -lt $cyfry.Length; $i++) a następnie podnosimy każdą cyfrę do kwadratu i sumujemy: $suma += ($cyfry[$i] * $cyfry[$i]).

Wreszcie dopisujemy aktualną sumę kwadratów do listy $sumy, przepisujemy sumę do zmiennej $sprawdz (do kolejnego kroku) i zwiększamy licznik kroków o jeden.

Po zakończeniu pętli (a więc po trafieniu na jedną z dziewięciu wartości 1,4,16,37,58,89,145,42 lub 20) sprawdzamy, czy „pobiliśmy rekord” ilości kroków if($krok -gt $maxkrok) i jeżeli tak, zapamiętujemy tę rekordową liczbę kroków w zmiennej $maxkrok oraz wyświetlamy szczegóły „rekordu” na ekran: Write-Host $_ ":" $krok ":" $sumy.

Proste, prawda?

A na zakończenie dodam, że od niedawna mam gorący romans z Visual Studio Code, przez co mój (do niedawna) ulubiony PowerGUI poszedł w odstawkę.

PowerGUI Script Editor: recenzja

Przypuszczam, że za jakiś czas pojawi się tu recenzja tego niezwykle popularnego i dopracowanego, darmowego narzędzia do edycji kodu.


Dodaj komentarz

avatar
  Subscribe  
Powiadom o
%d bloggers like this: