[Algorytmy] Algorytm pewnej sumy

[sandra-91]

Witam, może się wydać śmieszne, bo to prosty algorytm. Ale jakoś coś źle myślę. Czy ktoś mógłby wskazać, co źle robię?

Chodzi o to, jakie mają wartości:
\(\displaystyle{ a=}\)?, \(\displaystyle{ b=}\)?, suma\(\displaystyle{ =}\)? dla \(\displaystyle{ n=3}\)

\(\displaystyle{ a\leftarrow 1}\);
suma \(\displaystyle{ \leftarrow 0}\);
for \(\displaystyle{ k \leftarrow 1}\) to \(\displaystyle{ n}\);
do \(\displaystyle{ a \leftarrow a \cdot k}\);
\(\displaystyle{ b \leftarrow 1}\);
for \(\displaystyle{ i \leftarrow 1}\) to \(\displaystyle{ n}\);
do \(\displaystyle{ b \leftarrow b \cdot 2}\);
suma \(\displaystyle{ \leftarrow suma+ a + b}\);
return suma;



Zrobiłam tak:

dla \(\displaystyle{ n=1}\)

wypisuje zmienne po kolei, które mogą ulec zmianom:
- \(\displaystyle{ a=1}\), bo \(\displaystyle{ a\leftarrow 1}\)

- \(\displaystyle{ suma=0}\), bo \(\displaystyle{ suma \leftarrow 0}\)

- \(\displaystyle{ a=1}\), bo \(\displaystyle{ k}\) ma wartość \(\displaystyle{ 1}\) to \(\displaystyle{ a \leftarrow 1 \cdot 1}\)

- \(\displaystyle{ b=1}\), bo \(\displaystyle{ b\leftarrow 1}\)

- \(\displaystyle{ b=2}\), bo \(\displaystyle{ b \leftarrow 1 \cdot 2}\)

- suma\(\displaystyle{ =3}\), bo \(\displaystyle{ \leftarrow 0+ 1 + 2}\);

czyli dla \(\displaystyle{ n=1}\) mamy, \(\displaystyle{ a=1}\), \(\displaystyle{ b=2}\), suma\(\displaystyle{ =3}\)


---------------------------
dla \(\displaystyle{ n=2}\)

- \(\displaystyle{ a=2}\), bo \(\displaystyle{ k}\) ma wartość \(\displaystyle{ 2}\) to \(\displaystyle{ a \leftarrow 1 \cdot 2}\)

- \(\displaystyle{ b=4}\), bo \(\displaystyle{ b \leftarrow 2 \cdot 2}\)

- suma\(\displaystyle{ =9}\), bo \(\displaystyle{ \leftarrow 3+ 2 + 4}\);

czyli dla \(\displaystyle{ n=2}\) mamy, \(\displaystyle{ a=2}\), \(\displaystyle{ b=4}\), suma\(\displaystyle{ =9}\)

Dalej nie robię, bo nie jestem pewna, czy dobrze rozumiem działanie algorytmu.

[royas]

Ciężko jest stwierdzić jak działa ten algorytm, bo jest niejednoznacznie zapisany.
Z jednej strony wygląda tak jakby wewnątrz for'ów były pojedyncze instrukcje (od "do" do najbliższego średnika). Z drugiej strony instrukcja suma:=suma+a+b sugerowałaby, że jest ona wewnątrz jakiejś pętli. Ale jeśli to jest zapisane bez klamer i bez wcięć to ciężko jest się domyślić co jest w czym zagnieżdżone.

[sandra-91]

A no tak, masz rację, to jeszcze raz napiszę z wcięciami:

Kod: Zaznacz cały

a  <-- 1
suma <-- 0
for  k <-- 1 to n
     do  a <-- a * k 
         b <-- 1
         for i <-- 1 to n
             do b <-- b * 2
         suma <-- suma + a + b
return suma

[royas]

Takie coś to najłatwiej po prostu zaimplementować i sprawdzić. Wartości w linii 8. w kolejnych przebiegach pętli po k.

Kod: Zaznacz cały

suma+a+b=nowasuma
0+1+8=9
9+2+8=19
19+6+8=33

Można też zauważyć, patrząc na sam algorytm, że w kolejnych przebiegach pętli for k, w linii 8. będzie zachodziło \(\displaystyle{ a=k!; b=2^n}\). Więc \(\displaystyle{ s(n)=\sum_{k=1}^n (k!+2^n)}\)

[sandra-91]

Dziękuję bardzo za odpowiedź.

Nie rozumiem, dlaczego \(\displaystyle{ b}\) ma cały czas wynik \(\displaystyle{ 8}\).

Mimo, że napisałeś \(\displaystyle{ b=2^n}\), to byłoby dla \(\displaystyle{ n=1 \Rightarrow 2}\), dla \(\displaystyle{ n=2 \Rightarrow 4}\), dla \(\displaystyle{ n=3 \Rightarrow 8}\)

[royas]

Ja wypisałem kolejne przebiegi głównej pętli (for k... z linii 3.-8.) ale dla \(\displaystyle{ n=3}\). Dla \(\displaystyle{ n=2}\) \(\displaystyle{ b}\) w 8. linii będzie zawsze równe \(\displaystyle{ 4}\). Wartość b zależy od n, czyli od parametru całego algorytmu, a nie od k czyli zmiennej w pętli. Popatrz co się dzieje w liniach 5.-7.