La méthode du carré moyen

19

introduction

La méthode du carré central est utilisée pour la génération de nombres pseudo-aléatoires. Cependant, ce n'est pas une bonne méthode dans la pratique, car sa période est généralement très courte et présente de graves faiblesses. Comment cela marche-t-il? Prenons un exemple:

Pour la graine, nous choisissons 123456:

Seed     123456

La graine au carré (graine × graine), est égale à:

Seed²  15241383936

Nous avons commencé avec un numéro à 6 chiffres . Cela signifie que la graine au carré doit fournir un nombre à 12 chiffres . Si ce n'est pas le cas, des zéros de tête sont ajoutés pour compenser:

Seed²  015241383936

Nous prenons ensuite la partie médiane du nombre, de la même taille que la graine:

Seed²  015241383936
          ^^^^^^

Voici donc notre nouvelle semence : 241383. Nous répétons le même processus que celui indiqué ci-dessus. Nous obtenons ce qui suit:

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

Et cela continue dans un certain temps ... Maintenant que nous savons ce qu'est la méthode du carré central, relevons le défi:


La tâche

Chaque graine a une période . La période d'une graine à n chiffres ne peut pas dépasser 8 n . Par exemple, la graine 82. Cela donnerait la séquence suivante:

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

Vous pouvez voir que la période est égale à 5 , avant de contenir à nouveau le même chiffre. Votre tâche consiste, si une graine supérieure à 0 ne contient pas de zéros non significatifs, à sortir la période de la graine . Donc, dans ce cas, vous devez sortir 5.

Un autre exemple est:, 24qui donne ce qui suit:

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

Comme vous pouvez le voir, toutes les séquences ne se terminent pas 0. Ce cycle a une période de 1 .


Cas de test

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

Les bacs à pâte avec les séquences pour 123456 , 8989 , 789987

C'est du , donc la soumission avec le moins d'octets gagne!

Vous pouvez supposer que l'entrée n'aura jamais un nombre impair de chiffres.

Adnan
la source
10
Nit pick: Ce n'est pas une période. La période implique que la séquence retrouve finalement son état initial. 24est périodique (avec la période 2, je dirais), 82est finalement périodique (avec la période 1).
Dennis
1
Donc "période" est l'indice 0 du dernier état qui est différent de tous les états précédents?
Luis Mendo
@LuisMendo Oui, c'est exact. Mes connaissances mathématiques ne sont pas les meilleures: p.
Adnan
Ce serait plus comme «le nombre d'itérations avant qu'il ne se stabilise»
ASCII uniquement
1
@WashingtonGuedes Voir cette pastebin . Est-ce que cela le rend plus clair?
Adnan

Réponses:

3

Gelée, 26 24 18 octets

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

Essayez-le en ligne!

Comment ça fonctionne

³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.
Dennis
la source
5

Bash pur, 162 131 116 113 107

Enregistré 3 octets en utilisant $c...

Merci @Dennis de m'aider à économiser 6 octets supplémentaires.

---- 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

Format carré, 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

Vieux mais avec une sortie fantaisie, 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
F. Hauri
la source
3

JavaScript (ES7), 82 octets

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)

Accepte l'entrée sous la forme d'une chaîne, par exemple "82", et retourne un entier. Technique récursive simple de queue pour comparer chaque graine à son tour contre un hachage de graines qui ont déjà été vues. J'ajoute 100 ** l au carré pour assurer une longueur homogène.

Neil
la source
@Downgoat Accepte l'entrée sous la forme d'une chaîne .
Neil
1
oh ouais, je suppose que je ne peux pas lire: |
Downgoat
@WashingtonGuedes Non, cela ne fonctionne pas lorsque la valeur intermédiaire commence avec suffisamment de zéros. (C'est pourquoi j'ai "gaspillé" 7 octets en ajoutant 100 ** l.)
Neil
1
@WashingtonGuedes Il y a des cas où cela ne fonctionne pas, par exemple essayez de suivre la chaîne de 5288.
Neil
3

Python 3 2, 139 114 97 octets

Merci à Seeq pour avoir joué au golf sur 25 octets et merci à Dennis pour avoir joué au golf sur 17 octets! 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)

Peut certainement être joué plus loin. C'était aussi le code utilisé pour réaliser les cas de test: P.

Adnan
la source
2

Pyth, 21 octets

tl.us_<>_`^N2/lz2lzsz

Essayez-le en ligne: démonstration ou suite de tests

edit: Trouvé le cas de bord 1000, qui ne fonctionnait pas avec mon code précédent. Correction de 1 octet.

Explication:

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
Jakube
la source
une raison d'utiliser szau lieu de Q?
Ven
@ user1737909 Si j'utilise Q, je dois remplacer tous les lzpar l`Qs.
Jakube
mh, il semble surprenant que Pyth ne partage pas input. Je suppose que c'est vraiment destiné à permettre une deuxième lecture stdin ..?
Ven
@ user1737909 Oui. La seule possibilité de partager une entrée est avec .zet .Q, bien qu'ils lisent plusieurs lignes d'entrée et les stockent dans des listes. Mais je n'ai pas vu quelqu'un utiliser cette fonctionnalité. Ce n'est qu'un octet pour évaluer une chaîne ou pour stringifier un nombre.
Jakube
D' accord, vous pouvez lire stdin au plus 4 fois Pyth, Qz.Q.z?
Ven
2

MATL , 33 35 40 octets

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

Essayez-le en ligne!

`           % 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
Luis Mendo
la source
2

Oracle SQL 11.2, 184 octets

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;

Non golfé

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;

Il utilise la détection de cycle intégré pour arrêter la récursivité.

Jeto
la source
2

Julia, 64 octets

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

Essayez-le avec Coding Ground .

Dennis
la source
1

Mathematica, 80 octets

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

CJam, 37 octets

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

Ran dans un problème ennuyeux d'ordre de pile que je ne vois pas immédiatement comment résoudre. C'est aussi incroyablement lent.

Comment cela fonctionne: chaque itération pousse la nouvelle valeur au-dessus de la pile, puis nous enveloppons la pile dans un tableau et voyons si elle est la même que son union avec elle-même (pour voir si elle contient des éléments en double). Lorsqu'il contient des éléments en double, arrêtez-vous et voyez combien d'éléments se trouvent dans la pile.

A Simmons
la source
1

Python 2, 82 octets

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)

Essayez-le sur Ideone .

Dennis
la source
1

Python, 124 octets

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
Argenis García
la source
1

VBSCRIPT, 131 octets

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

Le mieux que je puisse faire avec vbscript, première affiche, alors allez-y doucement avec moi!

Traceur
la source
Bienvenue à la programmation d'énigmes et d'échange de pile de golf de code! Excellent premier post! J'ai un peu édité la mise en forme de votre message pour le rendre plus lisible et plus conforme à nos standards. Bon golf!
GamrCorps