Erstellen Sie eine Funktion, die eine natürliche Zahl (beginnend mit 0 einschließlich) annimmt und ein Paar positiver Ganzzahlen zurückgibt, die der Zähler bzw. der Nenner sind. Verwenden Sie die diagonale Durchquerung. Zuvor gezählte Nummern müssen übersprungen werden. (Sie können sich die übersprungenen Werte merken)

Diagramm:

Rot sind übersprungene Werte

Werte:

• f (0) = 1, 1
• f (1) = 2, 1
• f (2) = 1, 2
• f (3) = 1, 3
• f (4) = 3, 1 (beachten Sie das Überspringen)
• f (5) = 4, 1
• f (6) = 3, 2
• f (7) = 2, 3
• f (8) = 1, 4
• f (9) = 1, 5
• f (10) = 5, 1 (beachten Sie das Überspringen)

Sie können die Rational-Datenstruktur und ihre Operationen verwenden, falls vorhanden. Der kürzeste Code gewinnt.

J, 41 36 Zeichen

Nimmt eine ganze Zahl und gibt einen Vektor zurück, der zwei ganze Zahlen umfasst. Meine erste Lösung, die weder ganz stillschweigend noch ganz explizit ist.

{3 :'~.;<`(<@|.)/.(,%+.)"0/~1+i.1+y'

Hier ist die Lösung mit gegebenenfalls eingefügten Leerzeichen:

{ 3 : '~. ; <`(<@|.)/. (, % +.)"0/~ 1 + i. 1 + y'

Eine Erklärung:

1. x (, % +.) y–Ein Vektor der Länge 2, der den Bruch darstellt, wobei Zähler xund Nenner yauf den kleinsten Nenner reduziert sind
2. 1 + i. 1 + y–Ein Vektor von ganzen Zahlen von 1bisy + 1
3. (, % +.)"0/~ 1 + i. 1 + y–Eine Matrix aller reduzierten Brüche mit nicht reduziertem Nenner und Zähler im Bereich von 1bis y + 1.
4. <`(<@|.)/. y–Eine Anordnung der schrägen Diagonalen der Matrix y, die diagonal umgedreht sind
5. ~. ; y–Eine Anordnung von Diagonalen kollabierte zu einem Vektor von Elementen, wobei Duplikate entfernt wurden
6. x { y–Der Gegenstand an Position xiny
7. (u v) y–Das gleiche wie y u v y. In diesem speziellen Anwendungsfall uist {und vist3 : '~. ; <`(<@|.)/. (, % +.)"0/~ 1 + i. 1 + y'

Haskell, 78 Zeichen

q(r,f)=[(r-b,b)|b<-f[1..r-1],r`gcd`b==1]
d=reverse:id:d
f=((zip[2..]d>>=q)!!)

Probelauf:

> map f [0..10]
[(1,1),(2,1),(1,2),(1,3),(3,1),(4,1),(3,2),(2,3),(1,4),(1,5),(5,1)]
> f 100
(17,1)
> f 1000
(3,55)

• Edit: (100 → 87) dumm mich, nur das Testen der GCD ist genug!
• Bearbeiten: (87 → 85) cleverer Trick mit cycleund Funktionen zum Wechseln der Zeilenreihenfolge
• Bearbeiten: (85 → 82) durch cycledie handgefertigte unendliche Liste ersetzend
• Bearbeiten: (82 → 78) angewandte gcdIdentität, wie von Matías vorgeschlagen

Python, 144 Zeichen

def F(i):
 r,d,z=[1],1,[]
 while z[:i]==z:z+=[(x,y)for x,y in zip(r[::d],r[::-d])if all(x%j+y%j for j in r[1:])];d=-d;r+=[r[-1]+1]
 return z[i]

Ruby 1.9, 109 106

F=->n{x=y=d=1
e=0
n.times{(x+=d).gcd(y+=e)>1&&redo
x<2?d<0?d=0:(d,e=1,-1):y<2?e<0?e=0:(d,e=-1,1):0}
[x,y]}

OCaml + Batterien, 182 168 Zeichen

Dies wäre in Haskell natürlich, in OCaml jedoch kaum möglich:

open LazyList
let rec r(i,j)=lazy(let a,b=if(i+j)mod 2=0then i,j else j,i in
Cons((a,b),filter(fun(c,d)->a*d<>c*b)(r(if j=1 then 1,i+1else i+1,j-1))))
let f=nth(r(1,1))

Bearbeiten: Die Diagonale ist nicht erforderlich

Perl 6 , 75 Bytes

{(({|(1…($+=2)…1)}…*)Z/(1,{|(1…(($||=1)+=2)…1)}…*)).unique[$_]}

Probier es aus

Dies erzeugt im Grunde die gesamte Folge von rationalen Werten und stoppt erst, wenn der indizierte Wert erzeugt wurde.

(Basierend auf meinem Golf zu einer anderen Herausforderung.)

Erweitert:

{  # bare block lambda with implicit parameter $_

  (
      ( # sequence of numerators

        {
          |( # slip into outer sequence (flatten)

            1      # start at one
            …
            (
              $    # state variable
              += 2 # increment it by two each time this block is called
            )
            …
            1      # finish at one
          )

        }
        … * # never stop generating values
      )


    Z/   # zip using &infix:« /  » (generates Rats)


      ( # sequence of denominators

        1,  # start with an extra one

        {
          |( # slip into outer sequence (flatten)

            1
            …
            (
              ( $ ||= 1 ) # state variable that starts with 1 (rather than 0)
              += 2        # increment it by two each time this is called
            )
            …
            1
          )
        }
        … * # never stop generating values
      )


  ).unique                # get only the unique values
  .[ $_ ]                 # index into the sequence
}

({1…($+=2)…1}…*)erzeugt die unendliche Folge von Zählern ( |(…)wird oben zum Abflachen verwendet)

(1 2 1)
(1 2 3 4 3 2 1)
(1 2 3 4 5 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1)
…

(1,{1…(($||=1)+=2)…1}…*) erzeugt die unendliche Folge von Nennern

1
(1 2 3 2 1)
(1 2 3 4 5 4 3 2 1)
(1 2 3 4 5 6 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 10 11 10 9 8 7 6 5 4 3 2 1)
…