[Algorytmy] N-ty wyraz ciągu

[panczo12d]

Michał rozłożył sieć n- routerów w jednej linii. Po jakimś czasie zauważył ciekawą prawidłowość: do pierwszego routera był podłączony jeden komputer, do dwóch kolejnych po dwa komputery, do trzech następnych po 3 komputery, itd. Ile komputerów było połączonych z n-tym routerem?

Nie mogę rozgryźć tego zadania, jakieś wskazówki?

[bartek118]

Podpowiedź 1: ciąg arytmetyczny.

[panczo12d]

nadal nie umiem rozwiązać tego problemu.

[Vardamir]

A próbowałeś skorzystać z podanej wskazówki? Pokaż co Ci wychodzi.

[vpprof]

Mamy ciąg \(\displaystyle{ k_n}\), którego \(\displaystyle{ n}\)-ty wyraz jest równy liczbie komputerów podłączonych do \(\displaystyle{ n}\)-tego routera. Początkowe wyrazy tego ciągu to:
\(\displaystyle{ \begin{tabular}{cc}
n & k_n \\
1 & 1 \\
2 & 2 \\
3 & 2 \\
4 & 3 \\
5 & 3 \\
6 & 3 \\
7 & 4 \\
8 & 4 \\
9 & 4 \\
10 & 4 \\
11 & 5 \\
12 & 5 \\
13 & 5 \\
14 & 5 \\
15 & 5 \\
\end{tabular}}\)
Prawda? Łatwo zauważyć, że ostatnim wyrazem równym \(\displaystyle{ x}\) jest \(\displaystyle{ k_{\frac{x^2+x}{2}}}\) — taka jest suma liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ x}\), na przykład ostatnim numerem routera, który ma podłączone \(\displaystyle{ 5}\) komputerów jest \(\displaystyle{ \frac{5^2+5}{2}=15}\). Czyli jeśli nasze \(\displaystyle{ n}\) zawiera się w przedziale \(\displaystyle{ \left( \frac{\left( x-1\right)^2+x-1 }{2} \ ; \ \frac{x^2+x}{2}\right\rangle}\), to \(\displaystyle{ k_n=x}\).

Tyle że my chcemy stworzyć algorytm działający w drugą stronę, bo niby skąd komputer ma wiedzieć, jakie dobrać \(\displaystyle{ x}\), żeby \(\displaystyle{ n}\) znalazło się w zadanym przedziale?

Szczerze mówiąc, nie wpadłem na to sam, ale \(\displaystyle{ k_n=\left\lfloor \frac{1+ \sqrt{8n-7} }{2} \right\rfloor}\), gdzie \(\displaystyle{ \lfloor \ \rfloor}\) oznacza obcięcie miejsc dziesiętnych.

Oczywiście rozwiązanie „algorytmiczne” jest prostsze — po prostu brać kolejne \(\displaystyle{ x}\) i sprawdzać, czy \(\displaystyle{ n}\) znajduje się w zadanym powyżej przedziale, a jeśli tak, to \(\displaystyle{ k_n=x}\), jak napisałem…

[panczo12d]

Dzięki za odpowiedź, jestem w 2 lic i nie miałem jeszcze ciągów. Nawet nie domyśliłbym się że
\(\displaystyle{ 1+2+3+...+x = \frac{x^{2} +x}{2}}\)
Myślałem że to zadanie jest łatwe, bo pochodzi z konkursu informatycznego dla gimnazjum.
Mam jeszcze pytanie odnośnie oznaczeń w algorytmach.
Czym różni się:
\(\displaystyle{ \lfloor 1234.7 \rfloor}\) część całkowita z 1234,7 = 1234

\(\displaystyle{ [1234.7]}\) zaokrąglenie w dół do najbliższej liczby całkowitej z 1234,7 = 1234

Czy jest jakaś różnica między nimi, bo wg. mnie nie ma, tylko po co by były różne oznaczenia?

[vpprof]

Nie, nie ma między nimi różnicy, zaś oznaczenia są różne, bo ktoś może nie mieć właściwego znaczka i zastępuje sobie nawiasem kwadratowym. Tradycyjnie funkcję sufit (kalka z ang.), czyli zaokrąglenie z nadmiarem oznacza się \(\displaystyle{ \lceil \ \rceil}\), zaś funkcję podłoga, czyli zaokrąglenie z niedomiarem \(\displaystyle{ \lfloor \ \rfloor}\).