Einführung

Die Methode des mittleren Quadrats wird zur Erzeugung von Pseudozufallszahlen verwendet. Dies ist jedoch in der Praxis keine gute Methode, da ihre Dauer in der Regel sehr kurz ist und einige schwerwiegende Schwächen aufweist. Wie funktioniert das? Nehmen wir ein Beispiel:

Für den Samen wählen wir 123456:

Seed     123456

Das Samenquadrat (Samen × Samen) ist gleich:

Seed²  15241383936

Wir haben mit einer 6-stelligen Zahl begonnen. Das bedeutet, dass das Startquadrat eine 12-stellige Zahl liefern sollte . Ist dies nicht der Fall, werden führende Nullen hinzugefügt, um Folgendes zu kompensieren:

Seed²  015241383936

Wir nehmen dann den mittleren Teil der Zahl mit der gleichen Größe wie der Samen:

Seed²  015241383936
          ^^^^^^

Das ist dann unser neues Saatgut : 241383. Wir wiederholen den gleichen Vorgang wie oben gezeigt. Wir bekommen folgendes:

0:     123456
    015241383936
       |    |
1:     241383
    058265752689
       |    |
2:     265752
    070624125504
       |    |
3:     624125
    389532015625
       |    |
4:     532015
    283039960225
       |    |
5:     039960
    001596801600
       |    |
6:     596801

Und das geht noch eine Weile so ... Jetzt wissen wir, was die Mittelquadratmethode ist, und kommen zur Herausforderung:

Die Aufgabe

Jeder Same hat eine Periode . Die Periode eines n- stelligen Keims kann nicht länger als 8 ^{n sein} . Zum Beispiel den Samen 82. Dies würde die folgende Sequenz ergeben:

82 > 72 > 18 > 32 > 02 > 00 > 00 > 00 > 00 > 00
|____|____|____|____|____|____|____|____|____|___...
0    1    2    3    4    5    6    7    8    9

Sie können sehen, dass die Periode gleich 5 ist , bevor Sie wieder dieselbe Ziffer enthalten. Ihre Aufgabe ist es, bei einem Startwert größer als 0, der keine führenden Nullen enthält, die Periode des Startwerts auszugeben . In diesem Fall müssen Sie also ausgeben 5.

Ein anderes Beispiel ist 24:, das folgendes ergibt:

24 > 57 > 24
|____|____|___...
0    1    2

Wie Sie sehen, enden nicht alle Sequenzen in 0. Dieser Zyklus hat eine Periode von 1 .

Testfälle

Input   >   Output
24      >   1
82      >   5
123456  >   146
8989    >   68
789987  >   226

Die Pastebins mit den Sequenzen für 123456 , 8989 , 789987

Das ist Code-Golf , also gewinnt die Einsendung mit der geringsten Anzahl von Bytes!

Sie können davon ausgehen, dass der Eingang niemals eine ungerade Anzahl von Ziffern hat.

Jelly, 26 24 18 Bytes

³DL⁵*
²:¢½¤%¢µÐĿL’

Probieren Sie es online!

Wie es funktioniert

³DL⁵*         Helper link. No arguments.

³             Yield the original input.
 D            Convert from integer to base 10.
  L           Get l, the length of the decimal representation.
   ⁵*         Compute 10 ** l.


²:¢½¤%¢µÐĿL’  Main link. Input: n (integer)

²             Square n.
  ¢½¤         Call the helper link and take the square root of the result.
 :            Integer division; divide the left result by the right one.
      ¢       Call the helper link.
     %        Take the left result modulo the right one.
       µ      Convert the previous chain into a link, and begin a new chain.
        ÐĿ    Repeat the previous chain until the results are no longer unique,
              updating n in each iteration. Collect the intermediate results.
          L   Get the length of the list of results.
           ’  Decrement.

Pure Bash, 162 131 116 113 107

3 Bytes gespart mit $c...

Vielen Dank an @Dennis, dass Sie mir helfen, 6 weitere Bytes zu sparen.

---- begin middleSquare ----

for((b=$1;i[c=10#$b]<2;)){ a=${#b}
printf -v b %0$[a*2]d $[c*c]
b=${b:a/2:a};((i[10#$b]++))
};echo ${#i[@]}

---- end middleSquare ----

for testCase in 24 82 123456 8989 789987 111111;do
    printf "%12s: " $testCase
    bash middleSquare $testCase
  done
          24: 2
          82: 5
      123456: 146
        8989: 68
      789987: 226
      111111: 374

Quadratisch formatiert, 131

---- begin middleSquare ----

for((b=$1;i[
10#$b]<2;1))
do a="${#b}" 
printf -v b\
 %0$[a*2]d \
$[10#$b**2];
b=${b:a/2:a}
((i[10#$b]++
));done;ech\
o ${#i[@]:0}

---- end middleSquare ----

for testCase in 24 82 123456 8989 789987 111111;do
    printf "%12s: %9d\n" $testCase $(
        bash middleSquare $testCase)
  done
          24:         2
          82:         5
      123456:       146
        8989:        68
      789987:       226
      111111:       374

Alt aber mit ausgefallener Ausgabe, 162

---- begin middleSquare ----

for((b=$1;i[10#$b
]<2;1))do a=${#b}
printf -v b %0$[a
*2]d  $[10#$b**2]
b=${b:a/2:a};((i[
10#$b]++));print\
f "%9d %s\n" ${#\
i[@]} $b;done;ec\
ho -- ${#i[@]} --

---- end middleSquare ----

bash middleSquare 24
        1 57
        2 24
        2 57
-- 2 --

for testCase in 24 82 123456 8989 789987 111111
    do while read f v f
        do r=$v;done < <(
        bash middleSquare $testCase)
    printf "%12s: %11d\n" $testCase $r
  done
          24:           2
          82:           5
      123456:         146
        8989:          68
      789987:         226
      111111:         374

JavaScript (ES7), 82 Byte

f=(n,p={},m=-1,l=n.length)=>p[n]?m:f(`${n*n+100**l}`.substr(l/2+1,l,p[n]=1),p,++m)

Akzeptiert Eingaben in Form einer Zeichenfolge, z. B. "82", und gibt eine Ganzzahl zurück. Einfache rekursive Schwanz-Technik, um jeden Samen der Reihe nach gegen einen Hasch von Samen zu prüfen, die bereits gesehen wurden. Ich addiere 100 l ** zum Quadrat, um eine gleichmäßige Länge zu gewährleisten.

Python 3 2, 139 114 97 Bytes

Danke an Seeq für das Abschlagen von 25 Bytes und danke an Dennis für das Abschlagen von 17 Bytes! Code:

s=`input()`;u=[];l=len(s)/2
while not s in u:u+=[s];s=`int(s)**2`.zfill(l*4)[l:3*l]
print~-len(u)

Kann definitiv weiter golfen werden. Dies war auch der Code, mit dem die Testfälle erstellt wurden: P.

Pyth, 21 Bytes

tl.us_<>_`^N2/lz2lzsz

Probieren Sie es online aus: Demo oder Test Suite

edit: Habe den Edge Case gefunden 1000, der mit meinem vorherigen Code nicht funktioniert hat. Behob es für 1 Byte.

Erläuterung:

tl.us_<>_`^N2/lz2lzsz   implicit: z = input string
  .u               sz   apply the following instructions to N, starting with N = int(z), 
                        until it runs into a loop:
          ^N2              square it
         `                 convert it to a string
        _                  reverse order
       >     /lz2          remove the first len(z)/2
      <          lz        remove everything but the first len(z)  
     _                     reverse order
    s                      convert to int
  .u                   returns the list of all intermediate values
 l                     compute the length of this list
t                      minus 1

MATL , 33 35 40 Bytes

`t0)2^10GVnXK2/^/k10K^\vtun@>]n2-

Probieren Sie es online!

`           % do...while
  t         %   duplicate. Take input implicitly on first iteration
  0)        %   pick last value of array
  2^        %   square
  10        %   push 10
  GVn       %   number of digits of input
  XK        %   copy that to clipboard K
  2/        %   divide by 2
  ^         %   power
  /k        %   divide and floor. This removes rightmost digits from the square value
  10K^      %   10 ^ number of digits of input
  \         %   modulo. This takes the central part of the squared number
  v         %   concatenate this new number to array of previous numbers
  tun@>     %   does the number of unique values exceed the iteration index?
]           % if so: next iteration. Else: exit loop
n2-         % desired result is the amount of numbers minus 2. Implicitly display

Oracle SQL 11.2, 184 Byte

WITH v(v,p,n)AS(SELECT:1,'0',-1 FROM DUAL UNION ALL SELECT SUBSTR(LPAD(POWER(v,2),LENGTH(v)*2,0),LENGTH(v)/2+1,LENGTH(v)),v,n+1 FROM v)CYCLE v SET c TO 1 DEFAULT 0 SELECT MAX(n)FROM v;

Nicht golfen

WITH v(v,p,n) AS
(
  SELECT :1,'0',-1 FROM DUAL
  UNION ALL
  SELECT SUBSTR(LPAD(POWER(v,2),LENGTH(v)*2,0), LENGTH(v)/2+1, LENGTH(v)),v,n+1 FROM v
)
CYCLE v SET c TO 1 DEFAULT 0
SELECT MAX(n) FROM v;

Es verwendet die eingebaute Zykluserkennung, um die Rekursivität zu stoppen.

Julia, 64 Bytes

f(n,A=[],p=10^endof(dec(n)))=n∈A?-1:f(n^2÷√p%p,[A...n],p)+1

Probieren Sie es mit Coding Ground .

Mathematica, 80 Bytes

(a=10^⌊Log10@#+1⌋;Length@NestWhileList[⌊#^2/a^.5⌋~Mod~a&,#,Unequal,All]-2)&

CJam, 37 Bytes

q{__,W*:D;~_*sD2/<D>]___|=:A;~A}g],((

Stieß auf ein ärgerliches Problem mit der Stapelreihenfolge, das ich nicht sofort lösen kann. Es ist auch unglaublich langsam.

So funktioniert es: Bei jeder Iteration wird der neue Wert auf den Stapel verschoben. Anschließend wird der Stapel in ein Array eingebunden und überprüft, ob er mit seiner Vereinigung identisch ist (um festzustellen, ob er doppelte Elemente enthält). Wenn es doppelte Elemente gibt, halten Sie an und sehen Sie, wie viele Elemente sich im Stapel befinden.

Python 2, 82 Bytes

def f(n,A=[],l=0):l=l or len(`n`)/2;return-(n in A)or-~f(n*n/10**l%100**l,A+[n],l)

Probieren Sie es auf Ideone .

Python, 124 Bytes

def f(s,p=-1,n=0,m=[]):
 x=len(str(s))*2
 while n not in m:m+=[s];y=str(s*s).zfill(x);n=int(y[x/4:x*3/4]);p+=1;s=n
 return p

VBSCRIPT, 131 Bytes

s=inputbox(c):l=len(s):do:t=t&","&s:s=space(l*2-len(s*s))&s*s:s=mid(s,l/2+1,l):i=i+1:loop until instr(t,","&s)>0:msgbox i-1

Das Beste, was ich mit vbscript machen konnte, das erste Mal Poster, also mach es mir leicht!