Loading...
StanimirPavlov avatar 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???

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

0
Fundamentals Module
ThePSXHive avatar 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), и така се преминава към третата итерация на външния цикъл. Така би изглеждало (що-годе) и обяснението на хартия.

0
27/12/2016 13:48:25
StanimirPavlov avatar 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" и съм Ви благодарен, че отделяте от времето си да ми помогнете по това време на годината. Уверявам Ви, че опитах сам - не можах да се справя.
 

0
ThePSXHive avatar 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]; 

 

0
27/12/2016 17:24:59
StanimirPavlov avatar StanimirPavlov 4 Точки

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

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.