(an)=1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6...

0

Jes to zadanie bardziej matematyczne niż programistyczne...
Chodzi o to by znaleźć wzór na n'ty element ciągu (an).

(an)=1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 6 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8...

Tak ort! funkcja obliczająca a(n) napisana w c++:

int a(int n){
 int i=0,j=1;
 for(int c=0;c<n;c++){
  if(++i==j){
   i=1;
   j++;
  }
 }
 return i;
}

Powyższy algorytm ma złożoność O(n).
Chodzi o to by napisać funkcję o złożoności O(1) (zakładając, że stałe typu pi, e itp mamy dane a funkcje typu x^y, ln(x), sin(x), x!, +, -, /, floor(), itp są procedurami elementarnymi).

0

To mój własny wynalazek, ale mimo wszystko powinien działać.


```cpp
#include <math.h>

// numer/dlugosc bloku do którego należy liczba N
int index ( int N )
{
  return ( ( ( floor(sqrt( double(8*(N-1)+1) )) - 1 ) / 2 ) + 1 );
}

// początek bloku numer F
int start ( int F )
{
  return ( 1 + ( (F*(F-1)) / 2 ) );
}

// N-ty element ciągu
int element ( int N )
{
  return ( N + 1 - start( index(N) ) );
}

0

n-ty wyraz ciągu to
x[n] = n + round(sqrt(n2))(1-round(sqrt(n*2))) div 2

po oznaczeniu s(n) = round(sqrt(n2))
x[n] = n + s(n)
(1-s(n)) shr 1

gdyby s(n) to był naprawdę pierwiastek, a nie jego zaokrąglona postać, to można by poskracać wzór aż do postaci sqrt(n/2), no ale nie ma tak dobrze - round(sqrt(2*n)sqrt(2n)) to nie s(n)*s(n).

Zygfryd - jak długo myślałeś nad wzorem? Jestem ciekaw, bo sam siedziałem ponad 3 godziny, aż mnie kurwica zaczęła brać ;] a jak już policzyłem, to cholera pojawił się już post z odpowiedzią ;(

0

Tak z półtorej godzinki, ale kurcze ten mój sposób trochę przydługawy wygląda.
A nota bene, jak się już w końcu wpadło na rozwiązanie to takie proste się wydaje :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1