Algorithmus in Pseudocode

Question

Aufgabe:

Schreiben Sie einen Algorithmus in Pseudocode, der zu einer gegebenen reellen Zahl \( x \in \mathbb{R} \) die kleinste Zahl \( n \) bestimmt, so dass \( \prod \limits_{i=1}^{n} \frac{3 i+3}{2 i} \) größer als \( x \) ist.

Problem/Ansatz:

Muss bis Morgen eine Hausaufgabe abgeben. Kann mir hier jemand Helfen ?

Answer 1

Hallo Tobi,

bevor man sowas codiert, sollte man sich das Produkt genauer anschauen$$\phantom{=} \prod \limits_{i=1}^{n} \frac{3 i+3}{2 i}\\ = \prod \limits_{i=1}^{n} \left(\frac{3}{2}\cdot \frac{i+1}{i}\right)\\ = \left(\frac{3}{2}\right)^n\cdot\prod \limits_{i=1}^{n} \left(\frac{i+1}{i}\right)\\ = \left(\frac{3}{2}\right)^n\cdot\left(\frac{2}{1}\cdot \frac{3}{2}\cdot \frac{4}{3}\cdot\,\dots \cdot \frac{n}{n-1}\cdot \frac{n+1}{n}\right)\\ = \left(\frac{3}{2}\right)^n(n+1)$$leider kann man eine Gleichung wie$$\left(\frac{3}{2}\right)^n(n+1)= x$$nicht ohne weiteres nach \(n\) auflösen. Aber trotzdem vereinfacht sich der Algorithmus:

function calc_n(x)
begin
  let n = 0
  let q = 1
  while not(x < q * (n + 1)) do
  begin
    n = n + 1
    q = q * 1.5
  end
  return n
end

der Algorithmus macht pro Schritt nur noch zwei Multiplikationen statt drei plus einer Division, wenn man es 'klassisch' lösen würde. Außerdem hat er eine Komplexität von \(O(n)\) statt \(O(n^2)\) wie z.B. der von döschwo ;-)

Gruß Werner

Comments

... nicht ohne weiteres nach \(n\) auflösen

falls Deine Programmierumgebung (wie z.B. diese) über die Lambert-W-Funktion verfügt, dann ginge auch dies:

function calc_n(x)
begin
  return floor(lambert_w0(x * 1.5 * log(1.5)) / log(1.5))
end

das wäre dann sogar \(O(1)\), vorausgesetzt dass lambert_w0 auch \(O(1)\) hat.

Answer 2

begin
n = 0
p = 1
while p <= x do
   begin
      p = 1
      n = n + 1
      for i = 1 to n step 1 do p = p * (3i+i) / (2i)
   end
print n
end