Określanie ciągłych ułamków pierwiastków kwadratowych

13

Ułamka z szeregu njest ułamkiem w następującej postaci:


zbieżny do n.

Sekwencja aw ciągłej części jest zazwyczaj zapisywana jako: [a 0 ; a 1 , a 2 , a 3 , ... a n ].
Napiszemy nasz w ten sam sposób, ale z powtarzającą się częścią między średnikami.

Twoim celem jest zwrócenie ciągłej części pierwiastka kwadratowego z n.
Wejście: Liczba całkowita, n. nnigdy nie będzie idealnym kwadratem. Wynik
: ciągły ułamek sqrt(n).

Przypadki testowe:
2 -> [1; 2;]
3 -> [1; 1, 2;]
19 -> [4; 2, 1, 3, 1, 2, 8;]

Najkrótszy kod wygrywa. Powodzenia!

beary605
źródło
1
Czy dane wyjściowe muszą być w tym samym formacie co przypadki testowe?
grc,
Nie. Tak długo, jak masz średnik, wszystko jest w porządku.
beary605
Hm, uzyskiwanie właściwych odpowiedzi, kłopoty ze stwierdzeniem, kiedy ułamek jest racjonalny, aby przestać. Czy to naprawdę tak proste, jak gdy <sub> 0 </sub> jest dwukrotnie większy niż sqrt oryginalnego wejścia?
JoeFish
Tak, to jest limit.
beary605
@ beary605 dzięki. Robiłem dużo więcej czytania, a teraz widzę, że ciągły ułamek pierwiastka kwadratowego jest trochę szczególnym przypadkiem. Fascynujące rzeczy! Nadal pracuję nad wersją nieprzecinkową.
JoeFish

Odpowiedzi:

3

GolfScript ( 66 60 znaków)

~:^,{.*^>}?(:?';'[1?{^1$.*-@/?@+.2$/@@1$%?\- 1$(}do;;]','*1$

Ostrzeżenie: większość ?tam jest zmienną reprezentującą floor(sqrt(input))raczej niż wbudowaną. Ale pierwszy to wbudowany.

Pobiera dane wejściowe na standardowe wejście i wyjścia na standardowe wyjście.

Psuedokod algorytmu (dowód poprawności pozostawiony jako ćwiczenie dla czytelnika):

n := input()
m := floor(sqrt(n))
output(m)
x := 1
y := m
do
  x := (n - y * y) / x
  output((m + y) / x)
  y := m - (m + y) % x
while (x > 1)

Po raz kolejny potrzebuję jednego operatora, który bierze a bstos i pozostawia a/b a%bna stosie.

Peter Taylor
źródło
1
Powiedziałbym, że naprawdę muszę się nauczyć GS ... ale potrzeba jest tu trochę za mocnym słowem;)
boothby
1
@boothby, nie szalej. Twoje życie nie będzie kompletne bez GS;)
Peter Taylor
3

Python, 95 97 (ale poprawne ...)

Wykorzystuje tylko arytmetykę całkowitą i podział na piętra. To da poprawne wyniki dla wszystkich dodatnich liczb całkowitych, chociaż jeśli ktoś chce użyć długiej, musiałby dodać znak; na przykład m=a=0L. I oczywiście ... poczekaj milion lat, aż podłoga mojego biednego mężczyzny się skończy.

z=x=m=1
while n>m*m:m+=1
m=y=m-1
l=()
while-z<x:x=(n-y*y)/x;y+=m;l+=y/x,;y=m-y%x;z=-1
print c,l

Wynik:

n=139
11 (1, 3, 1, 3, 7, 1, 1, 2, 11, 2, 1, 1, 7, 3, 1, 3, 1, 22)

edycja: teraz za pomocą algorytmu Petera Taylora. To do...whilebyło fajne.

boothby
źródło
Jaki jest cel *(c*c-n)?
Peter Taylor
@PeterTaylor, nie przeczytałem wystarczająco uważnie wyzwania i sprawiłem, że kod działał dla idealnych kwadratów.
stoisko
2

Python, 87 82 80

x=r=input()**.5
while x<=r:print"%d"%x+",;"[x==r],;x=1/(x%1)
print`int(r)*2`+";"

Pobiera jedną liczbę całkowitą i daje dane wyjściowe takie jak:

4; 2, 1, 3, 1, 2, 8;
grc
źródło
x-int(x) -> x%1. Jestem pod wrażeniem :)
beary605
Daje zły wynik dla √139 według Wolfram Alpha
breadbox
Zaktualizowałem go do pracy dla √139. Jeśli jednak długość sekwencji wydłuży się znacznie (√139 ma sekwencję 18 liczb), wynik prawdopodobnie zacznie tracić dokładność.
grc,
Uważam za niezwykle interesujące, że zawsze kończy się na 2 * int (sqrt (a)).
beary605
Kolejne interesujące jest to, że 3 z nas ma zepsuty kod dla 139 (moja wciąż nie gra w golfa i nie opublikowała).
JoeFish
2

Mathematica 33 31

c[n_]:=ContinuedFraction@Sqrt@n

Dane wyjściowe mają format listy, który jest bardziej odpowiedni dla Mathematica. Przykłady:

c[2]
c[3]
c[19]
c[139]
c[1999]

(* out *)
{1, {2}}
{1, {1, 2}}
{4, {2, 1, 3, 1, 2, 8}}
{11, {1, 3, 1, 3, 7, 1, 1, 2, 11, 2, 1, 1, 7, 3, 1, 3, 1, 22}}
{44, {1, 2, 2, 4, 1, 1, 5, 1, 5, 8, 1, 3, 2, 1, 2, 1, 1, 1, 1, 1, 1, 
  1, 14, 3, 1, 1, 29, 4, 4, 2, 5, 1, 1, 17, 2, 1, 12, 9, 1, 5, 1, 43, 
  1, 5, 1, 9, 12, 1, 2, 17, 1, 1, 5, 2, 4, 4, 29, 1, 1, 3, 14, 1, 1, 
  1, 1, 1, 1, 1, 2, 1, 2, 3, 1, 8, 5, 1, 5, 1, 1, 4, 2, 2, 1, 88}}
DavidC
źródło
1
O rany, całkowicie oczekiwałem tej odpowiedzi. Nie uważam tego za rzeczywistą odpowiedź, chyba że sam wygenerujesz ciągłą część.
beary605
@ beary605 Wystarczająco uczciwy.
DavidC
2
+1 jeszcze lepiej (25 znaków)ContinuedFraction@Sqrt@#&
dr belizariusz
Co dokładnie tu liczysz? Czy to program, który pobiera dane wejściowe ze standardowego wejścia? Ponieważ sposób, w jaki go używasz, wygląda na ciało funkcji bez definicji funkcji.
Peter Taylor
@Peter Taylor Proszę zobaczyć poprawkę.
DavidC
1

Python ( 136 133 96)

Standardowa metoda ciągłych frakcji, bardzo golfa.

a=input()**.5
D=c=int(a);b=[]
while c!=D*2:a=1/(a%1);c=int(a);b+=[c]
print D,";%s;"%str(b)[1:-1]
beary605
źródło
Możesz zapisać kilka znaków przy użyciu while 1:. Możesz także umieścić większość instrukcji w pętli while w jednym wierszu.
grc
Kiedy uruchamiam twój skrypt, otrzymuję wynik 8 ;1;dla 74 i 75; to nie wydaje się właściwe. Wisi na 76.
chleba chleba
^^ Tak. Naprawiłem mój kod.
beary605
Ta wersja daje zły wynik dla 139.
breadbox
@boothby Następnie usunę mój i nazwiemy go remisem :)
JoeFish
1

C, 137

Łącznie z nową linią, zakładając, że nie muszę wyrzucać własnego pierwiastka kwadratowego.

#include<math.h>
main(i,e){double d;scanf("%lf",&d);e=i=d=sqrt(d);while(i^e*2)printf("%d%c",i,e^i?44:59),i=d=1.0/(d-i);printf("%d;",i);}

Łamie się dla sqrt (139) i zawiera sporadyczne dodatkowe średniki w danych wyjściowych, ale jestem zbyt zmęczony, aby pracować nad tym jeszcze dziś wieczorem :)

5
2; 4;
19
4; 2,1,3,1,2,8;
111
10; 1,1,6,1,1,20;
JoeFish
źródło
1

Perl, 99 znaków

Czy nie zepsuć na 139, 151, itd. Testowane z numerem od 1 do 9 cyfr.

$"=",";$%=1;$==$-=($n=<>)**.5;
push@f,$==(($s=$=*$%-$s)+$-)/($%=($n-$s*$s)/$%)until$=>$-;
say"$-;@f;"

Uwaga: $%, $=, i $-są wszystkie zmienne całkowite wymuszeniem.

chlebak
źródło
1

APL (NARS), 111 znaków, 222 bajty

r←f w;A;a;P;Q;m
m←⎕ct⋄Q←1⋄⎕ct←P←0⋄r←,a←A←⌊√w⋄→Z×⍳w=0
L: →Z×⍳0=Q←Q÷⍨w-P×P←P-⍨a×Q⋄r←r,a←⌊Q÷⍨A+P⋄→L×⍳Q>1
Z: ⎕ct←m

Funkcja f jest oparta na algorytmie znalezionym na stronie http://mathworld.wolfram.com/PellEquation.html w celu rozwiązania równania Pell. Ta funkcja f ma na wejściu wszystkie liczby nieujemne (również ułamek typu). Możliwe, że coś poszło nie tak, pamiętam, że √ ma, jak widzę, problem dla dużych liczb ułamkowych, ponieważ

  √13999999999999999999999999999999999999999999999x
1.183215957E23 

więc byłaby jedna funkcja sqrti (). Z tego powodu ułamek wejściowy (i całkowity) musi być <10 ^ 15. test:

 ⎕fmt (0..8),¨⊂¨f¨0..8
┌9───────────────────────────────────────────────────────────────────────────────────────────────────────┐
│┌2─────┐ ┌2─────┐ ┌2───────┐ ┌2─────────┐ ┌2─────┐ ┌2───────┐ ┌2─────────┐ ┌2─────────────┐ ┌2─────────┐│
││  ┌1─┐│ │  ┌1─┐│ │  ┌2───┐│ │  ┌3─────┐│ │  ┌1─┐│ │  ┌2───┐│ │  ┌3─────┐│ │  ┌5─────────┐│ │  ┌3─────┐││
││0 │ 0││ │1 │ 1││ │2 │ 1 2││ │3 │ 1 1 2││ │4 │ 2││ │5 │ 2 4││ │6 │ 2 2 4││ │7 │ 2 1 1 1 4││ │8 │ 2 1 4│││
││~ └~─┘2 │~ └~─┘2 │~ └~───┘2 │~ └~─────┘2 │~ └~─┘2 │~ └~───┘2 │~ └~─────┘2 │~ └~─────────┘2 │~ └~─────┘2│
│└∊─────┘ └∊─────┘ └∊───────┘ └∊─────────┘ └∊─────┘ └∊───────┘ └∊─────────┘ └∊─────────────┘ └∊─────────┘3
└∊───────────────────────────────────────────────────────────────────────────────────────────────────────┘
  f 19
4 2 1 3 1 2 8 
  f 54321x
233 14 1 1 3 2 1 2 1 1 1 1 3 4 6 6 1 1 2 7 1 13 4 11 8 11 4 13 1 7 2 1 1 6 6 4 3 1 1 1 1 2 1 2 3 1 1 14 466 
  f 139
11 1 3 1 3 7 1 1 2 11 2 1 1 7 3 1 3 1 22 
  +∘÷/f 139
11.78982612
  √139
11.78982612

jeśli argument jest kwadratem liczby, zwróci jedną listę tylko jednego elementu, sqrt tej liczby

  f 4
2 

Gdyby to zależało ode mnie, w jednym ćwiczeniu bez „codegolf” wolałbym poprzednią edycję, która używa funkcji sqrti () ...

RosLuP
źródło
1
z pewnością możesz używać nazw jednoliterowych zamiast fqi a0. także: (a×Q)-P->P-⍨a×Q
ngn
Q←Q÷⍨- czy Nars obsługuje Q÷⍨←?
ngn
@ngn: Nie lubię używać „Q ÷ ⍨ ←” w łańcuchu formuły wielokrotnego przypisania ... do końca zgadzam się ... Możliwe, że tak mówię, ponieważ widziałem C Undefined Behavior
RosLuP