Arrays and Lists Lab Problem 3. Last K numbers sum

StanimirPavlov 4 Точки

Arrays and Lists Lab Problem 3. Last K numbers sum

Здравейте,

На първо място - честита Коледа на всички.

Имам въпрос по задача 3 от Arrays and Lists - Lab.

Условие на задачата:

Enter two integers n and k. Generate and print the following sequence of n elements:

The first element is: 1
All other elements = sum of the previous k elements (if less than k are available, sum all of them)
Example: n = 9, k = 5 à 120 = 4 + 8 + 16 + 31 + 61

Решение: http://pastebin.com/NRtwc1yd

Не успях да стигна самостоятелно до решение, преписах кода от видео - урока към Arrays and Lists - Exercises. Не мога да разбера как се пълни масива numbers[]. Ясно ми е, че задавам в кода numbers[0] = 1, но как се определя numbers[j] при j !=0???

Предварително благодаря за съдействието.

Тагове:

27/12/2016 12:12:31 Fundamentals Module

ThePSXHive 436 Точки

Best Answer

В такава ситуация бих си обяснил случващото се чрез лист и химикал, като проследя изпълнението на блокът, който модифицира стойностите в масива, за да разбера какво всъщност се случва. В случаят, "магията" е на следния ред

numbers[i] = sum;

но нека проследим "завъртането" на циклите за първите две итерации. Имам предвид първите две итерации на външния цикъл, и как всяка от стойностите на променливите се променя. Ще използвам псевдокод (тук наблягам на "псевдо"), като с i(2) обозначавам текущата стойност на променливата, а с i(=2) означавам стойността, която ще бъде присвоена на променливата след изпълнението на дадена итерация в един цикъл. Нека видим какво се случва в циклите, като започнем след реда, в който се присвоява стойността на първият елемент:

Итерация -1-

(i = 1; i(1) < n(5); i(=2))
{
  sum = 0; 
  (j = i - 1 (1 - 1 = 0); j(0) >= 0 && j(0) >= i(1) - k(5); j(=-1))
  {
    sum = sum(0) + numbers[j(0)] = 0 + 1 = 1; 
  }
  numbers[i(1)] = sum(1); 
}

Тъй като стойността на j след първата итерация на вътрешния цикъл е -1, условието (цикълната инварианта) бива оценено като неистинно още през първата част (j(-1) >= 0), и останалата проверка, както и другите операции, се прекратяват, и се преминава към:

Итерация -2-

(i = 2; i(2) < n(9); i(=3))
{
  sum = 0; 
  (j = j - 1 (2 - 1 = 1); j(1) >= 0 && j(1) >= i(2) - k(5); j(=0))
  {
    sum = sum(0) + numbers[j(1)] = 0 + 1 = 1; 
  }
  numbers[i(2)] = sum(1); 
}

За разлика от първата итерация, след изпълнението на вътрешния цикъл, стойността на j позволява още едно "завъртане" на вътрешния цикъл (j(0) >= 0), и затова сега проследяваме изпълнението на вътрешния цикъл; процедираме по този начин докато условието му е истинно.

(j = 0; j(0) >= 0 && j(0) >= i(2) - k(5); j(=-1))
{
  sum = sum(1) + numbers[j(0)] = 1 + 1 = 2; 
}
numbers[i(2)] = sum(2);

Стойността на j отново не преминава отвъд първата проверка (j(-1) >= 0), и така се преминава към третата итерация на външния цикъл. Така би изглеждало (що-годе) и обяснението на хартия.

27/12/2016 13:47:27 27/12/2016 13:48:25

StanimirPavlov 4 Точки

Много благодаря за отговора. Уверявам Ви, че преди да пиша във форума се опитах "с лист и химикал" и се опасявам, че не успях да разбера (с което никак не се гордея :). Също така използвах debugger - a, видях какви стойности приемат променливите, но не можах да си обясня "магията", която ги кара да заемат тези стойности. Все още не разбирам:

sum = sum(0) + numbers[j(1)] = 0 + 1 = 1,

и по - конкретно - защо при j = 1, sum[j(1)] = 1? Разбирам, че при i = 2, в тази итерация на външния цикъл, j приема стойности 1 и 0 и при j = 0, sum = 1. Защо обаче при j = 1, sum[j(1)] = sum(0) + sum[j(1)] = 0(до тук всичко разбирам)+ 1(ето тази единица не разбирам защо се получава??).

Предварително благодаря за съдействието - знам, че въпросът не е "high level" и съм Ви благодарен, че отделяте от времето си да ми помогнете по това време на годината. Уверявам Ви, че опитах сам - не можах да се справя.

27/12/2016 16:43:17

ThePSXHive 436 Точки

Всичко е наред. Единицата във втората итерация се появява, защото използваме j като индекс за стойност в масива, която вече е известна и е установена. Преди първата итерация, когато сме присвоили стойност само на първата клетка, масивът изглежда така:

1 X X X X X X X X

Стойността на X не ни интересува, защото останалите клетки тепърва ще бъдат "запълвани" със стойностите на sum. По време на първата итерация, присвояваме стойност на втората клетка, като предварително изчисляваме стойността, която ще присвоим, и това се осъществява на следния ред

sum = sum(0) + numbers[j(0)] = 0 + 1 = 1;

Тук просто сумираме sum и елементът с индекс j (като текущата стойност на j e 0), а какво имаме в масивът на позиция 0? Единица. След като приключим с това сумиране, присвояваме резултатът на клетката с индекс i:

numbers[i(1)] = sum(1);

И така, масивът вече изглежда по следния начин:

1 1 X X X X X X X

При следващите итерации на двата цикъла, стойността на j отново се използва просто като индексираща стойност

sum = sum(0) + numbers[j(1)] = 0 + 1 = 1;

Горният израз може да бъде записан и без нотацията, естествено

sum = sum + numbers[1] = 0 + 1 = 1;

Тук отново сумираме sum и елементът с индекс текущата стойност на j, която е единица. А каква е стойността на клетката с индекс 1? Единица, и знаем това от предишната итерация, и в частност, от това присвояване:

numbers[i(1)] = sum(1);

На всяка следваща итерация на цикъла се възползваме от фактът, че предишната стойност в масивът вече е известна, изчислена.

P.S. Предполагам, че това вече Ви е известно, но все пак ще напомня, че този израз

sum += numbers[j];

е просто удобен начин да представите сумата на лявата операнда (sum) и дясната операнда (numbers[j]); алтернативен начин да бъде представен израза

sum = sum + numbers[j];

27/12/2016 17:17:07 27/12/2016 17:24:59

StanimirPavlov 4 Точки

:) Много благодаря за съдействието!

27/12/2016 23:37:27