Quadrate in den Quadraten

10

nSchreiben Sie bei gegebener Eingabe einer positiven Ganzzahl ein Programm, das den folgenden Vorgang abschließt.

  • Finden Sie die kleinste positive ganze Zahl größer als ndas ist ein perfektes Quadrat und ist die Verkettung von nund einer anderen Zahl. Die Reihenfolge der Ziffern von ndarf nicht geändert werden. Die Zahl n, mit der ein perfektes Quadrat erzeugt wird, kann aufgerufen werden r_1.
  • Wenn r_1es sich nicht um ein perfektes Quadrat handelt, wiederholen Sie den obigen Vorgang mit r_1als neue Eingabe für den Vorgang. Wiederholen, bis r_kein perfektes Quadrat angegeben ist s.
  • Drucken Sie den Wert von sqrt(s).

Die Eingabe kann in jedem Format erfolgen. Sie können davon ausgehen, dass dies neine positive Ganzzahl ist. Wenn r_keine führende Null (und r_k≠ 0) hat, kann die Null ignoriert werden.


Testfälle

Hier sind einige Testfälle. Der Prozess demonstriert die obigen Schritte.

Input:   23
Process: 23, 2304, 4
Output:  2

Input:   10
Process: 10, 100, 0
Output:  0

Input:   1
Process: 1, 16, 6, 64, 4
Output:  2

Input:   5
Process: 5, 529, 29, 2916, 16
Output:  4

Input:   145
Process: 145, 145161, 161, 16129, 29, 2916, 16
Output:  4

Input:   1337
Process: 1337, 13373649, 3649, 36493681, 3681, 368102596, 2596, 25969216, 9216
Output:  96

Das ist Code Golf. Es gelten Standardregeln. Die kürzeste Antwort (in Bytes) gewinnt.

Arcturus
quelle

Antworten:

2

Pyth, 26 Bytes

LsI@b2 fy=sh.fys+QZ1\0)@Q2

Testsuite

Die Ausgabe erfolgt als Float. Wenn die Ausgabe als int gewünscht wird, wäre dies 1 zusätzliches Byte.

Erläuterung:

LsI@b2 fy=sh.fys+QZ1\0)s@Q2
                               Q = eval(input())
L                              def y(b): return
   @b2                         Square root of b
 sI                            Is an integer.
       f              )        Find the first positive integer T that satisfies
           h.f     1\0         Find the first digit string Z that satisfies
                +QZ            Concatenation of Q and Z
               s               Converted to an integer
              y                Is a pergect square.
          s                    Convert the string to an integer
         =                     Assign result to the next variable in the code, Q
        y                      Repeat until result is a perfect square
                               (The space) Discard return value
                        @Q2    Take square root of Q and print.
isaacg
quelle
2

MATL , 35 44,0 Bytes

XK``x@2^tVKVXf1=a~]VKVnQ0h)UXKX^t1\

Probieren Sie es online aus!

XK        % implicit input: n. Copy to clipboard K
`         % do...while. Each iteration applies the algorithm
  `       %   do...while. Each iteration tests a candidate number
    x     %     delete top of stack
    @2^   %     iteration index squared
    t     %     duplicate
    V     %     convert to string                
    K     %     paste from clipboard K: n or r_k
    V     %     convert to string  
    Xf    %     find one string within another. Gives indices of starting matches, if any 
    1=a~  %     test if some of those indices is 1. If not: next iteration
  ]       %   end. We finish with a perfect square that begins with digits of n or r_k
  V       %   convert to string
  K       %   paste from clipboard K: n or r_k
  VnQ0h   %   index of rightmost characters, as determined by r_k
  )       %   keep those figures only
  U       %   convert to number. This is the new r_k
  XK      %   copy to clipboard K, to be used as input to algorithm again, if needed
  X^      %   square root
  1\      %   fractional part. If not zero: apply algorithm again
          % implitic do...while loop end
          % implicit display
Luis Mendo
quelle
2

Python 2, 98

i=input();d=o=9
while~-d:
 n=i;d=o+1;o=i=0
 while(n*d+i)**.5%1:i=-~i%d;d+=9*d*0**i
print'%d'%n**.5

Probieren Sie es online aus .

grc
quelle
Da wir sowieso im Gebiet des Float-Missbrauchs sind ... while x**.5%1:vielleicht?
Sp3000
@ Sp3000 danke! Ich habe es jetzt ein bisschen mehr gespielt.
Grc
@Ampora nur der ideone Link hat den Prozess gedruckt, aber das habe ich jetzt geändert.
Grc
1

Python, 200 198 178 Bytes

import math
def r(i):
 j=int(i**.5)+1
 while str(j*j)[:len(str(i))]!=str(i):j+=1
 return int(str(j*j)[len(str(i)):])
q=r(int(input()))
while math.sqrt(q)%1!=0:q=r(q)
print(q**.5)
ThereGoesMySanity
quelle
Sie könnten durch die Verkürzung eine gute Anzahl von Bytes speichern math.sqrtzu m.
Arcturus
@ Ampora Aww ja, 2 Bytes gespeichert
ThereGoesMySanity
1

Brachylog , 26 Bytes

{~a₀X√ℕ∧YcX∧Yh?∧Ybcℕ≜!}ⁱ√ℕ

Probieren Sie es online aus!

Der letzte Testfall wurde in der TIO-Verbindung weggelassen, da die Ausführung allein mehr als eine Minute dauert. Ich habe es auf meinem Laptop ausgeführt und das richtige Ergebnis wurde in nicht mehr als zwei Stunden erzielt.

{                             The input
 ~a₀                          is a prefix of
    X√                        X, the square root of which
      ℕ                       is a whole number.
       ∧YcX                   Y concatenated is X.
           ∧Yh?               The input is the first element of Y.
               ∧Yb            The rest of Y,
                  c           concatenated,
                      }       is the output
                   ℕ          which is a whole number.
                    ≜         Make sure that it actually has a value,
                     !        and discard all choice points.
{                     }ⁱ      Keep feeding that predicate its own output until
                        √     its output's square root
                         ℕ    is a whole number
                              which is the output.

Das vorletzte ist erforderlich, wenn die anfängliche Eingabe bereits ein perfektes Quadrat ist. Das erste perfekte Quadrat, das es als Präfix hat, ist also selbst und !ist erforderlich, um sicherzustellen, dass das Zurückverfolgen iteriert, anstatt ein größeres verkettetes Quadrat zu finden. aber ich weiß nicht wirklich warum das notwendig ist, ich weiß nur, dass 5 ohne sie eine falsche Antwort liefert.

Nicht verwandte Zeichenfolge
quelle
(Dank eines Fehlers im Parser ist dieses schreckliche Durcheinander benannter Variablen und s tatsächlich kürzer als die Verwendung eines Sandwichs.)
Nicht verwandte
0

Perl 6 , 101 Bytes

my&q={$^k;$_=({++($||=$k.sqrt.Int)**2}.../^$k/)[*-1];+S/$k//}
put (q(get),&q...!(*.sqrt%1))[*-1].sqrt
my &q = {
  $^k; # declare placeholder parameter
  # set default scalar to:
  $_ = ( # a list
    # code block that generates every perfect square
    # larger than the input
    { ++( $ ||= $k.sqrt.Int )**2 }
    ...   # produce a sequence
    /^$k/ # ending when it finds one starting with the argument
  )[*-1]; # last value in sequence

  # take the last value and remove the argument
  # and turn it into a number to remove leading zeros
  +S/$k//
}

put (     # print the result of:
  q(get),     # find the first candidate
  &q          # find the rest of them
  ...         # produce a sequence
  !(*.sqrt%1) # ending with a perfect square
)[*-1]        # last value in sequence
.sqrt         # find the sqrt
Brad Gilbert b2gills
quelle
0

ES7, 116 Bytes

n=>{do{for(i=n;!(r=(''+Math.ceil((i*=10)**0.5)**2)).startsWith(+n););n=r.replace(+n,'');r=n**0.5}while(r%1);return r}

Ja, ich könnte wahrscheinlich ein Byte mit verwenden eval.

Neil
quelle