Види циклів, Детальна інформація

o

Fаписати цикл for, тіло якого виконується аж ніяк не при значеннях параметра циклу, указаних у заголовку. Наприклад, для обчислення функції n!!, означеної за непарного n як 1\xF0D7 3\xF0D7 …\xF0D7 n і як 2\xF0D7 4\xF0D7 …\xF0D7 n за парного, в Турбо Паскаль можна, здавалося б, зробити такий трюк:

ff:=1; if odd(n) then lb:=1 else lb:=2;

{n і lb або обидва парні, або обидва непарні}

for k := lb to n do

begin ff:=ff*k; k:=k+1 end

Але це неправильно! Між двома послідовними виконаннями ff:=ff*k значення k збільшується двічі на 1 (явно і неявно), і, поки kn, тому k збільшується неявно, і повторення тіла циклу продовжуються! Зрештою при черговому обчисленні ff*k одержується значення, більше maxint. Комп'ютер такого "не розуміє", і програма аварійно завершується.

Отже, краще не ризикувати й не задавати в тілі явні зміни параметра циклу. Нехай він буде чимось на зразок "священної корови" в індусів.

Наведемо "безпечне" розв'язання задачі про n!!. Очевидно, що серед чисел 1, 2, 3, … , n множниками в шуканому добутку повинні стати парні за парного n або, навпаки, непарні за непарного n. Можна перебрати всі ці числа, пропустивши непотрібні, у тому числі й 1:

ff:=1;

for k := 2 to n do

if odd(k)=odd(n) then ff:=ff*k.

Оператор циклу переліком має ще одну форму:

for ім'я := вираз1 downto вираз2 do оператор,

де всі позначення мають той самий зміст, що й у першій формі. Слово downto замість слова to задає не збільшення, а зменшення на 1 значення параметра циклу після виконання його тіла. Крім того, тіло циклу не виконується жодного разу, якщо спочатку значення виразу1 менше значення виразу2. Наприклад, обчислення n!! за допомогою цього оператора задається так:

ff:=n;

for k := n-1 downto 2 do

if odd(k)=odd(n) then ff:=ff*k.

називаються біноміальними. Напишемо функцію C обчислення біноміального коефіцієнта за значеннями n і k. Використовуючи функцію fct обчислення Факторіала, можна написати:

C:=fct(n)/(fct(k)*fct(n-k))

Важко придумати щось гірше. Це все одно, що їхати з Берліна в Париж через джунглі Амазонії, піддаючи себе всіляким небезпекам. По-перше, ми змушуємо комп'ютер обчислювати ті самі значення тричі. По-друге, функція n! зростає дуже швидко за зростання n. Наприклад, 8!=40320, а в деяких системах програмування це вже більше, ніж maxint.

Подивимося уважніше на формулу біноміального коефіцієнта:

.

При використанні будь-якої з рівностей треба обчислити два добутки й знайти їх частку, яка за означенням є цілою. Позначимо їх num і den – скорочення від англійських numerator і denumerator (чисельник і знаменник). За другою з рівностей обчислення очевидні:

num := n; den := 1;

for i := 2 to k do

begin num := num*(n-i+1); den := den*i end;

C := num div den

вже закладено обчислення послідовності значень

d0=1, d1=n/1, d2=n(n-1)/(1\xF0D7 2), ... , dk=n(n-1)\xF0D7 ... \xF0D7 (n-k+1)/(1\xF0D7 2\xF0D7 ... \xF0D7 k).