Фонд Освітніх та Інформаційних Технологій

Скачати 136.35 Kb.

Назва	Фонд Освітніх та Інформаційних Технологій
Дата	11.08.2013
Розмір	136.35 Kb.
Тип	Документи

bibl.com.ua > Інформатика > Документи

1.2. Масиви.
У наступних завданнях змінні x, у, z передбачаються опісанними як array [1..n] of integer (n - деяке натуральне число, більше 0), якщо інше не обумовлене явно.
1.2.1. Заповнити масив x нулями. (Це означає, що потрібне скласти фрагмент програми, після виконання якого все значенія x[1]..x[n] дорівнювали б нулю, незалежно від початкового значення змінної x.)
Рішення.
i := 0;

{інваріант: перші i значень x[1]..x[i] рівні 0}

while i <> n do begin

| i := i + 1;

| {x[1]..x[i-1]= 0}

| x[i]:= 0;

end;
1.2.2. Підрахувати кількість нулів в масиві x. (Скласти

фрагмент програми, що не міняє значення x, після виконання ко-

торого значення деякої цілої змінної до дорівнювало б числу

нулів серед компонент масиву x.)
Рішення.

...

{інваріант: k= число нулів серед x[1]...x[i] }

...
1.2.3. Не використовуючи оператора привласнення для масивів

скласти фрагмент програми, еквівалентний операторові x:=y.
Рішення.
i := 0;

{інваріант: значення у не змінилося, x[l]= у[l] при l <= i}

while i <> n do begin

| i := i + 1;

| x[i]:= у[i];

end;
1.2.4. Знайти максимум з x[1]..x[n].
Рішення.

i := 1; max := x[1];

{інваріант: max = максимум з x[1]..

x[i]} while i <> n do begin

| i := i + 1;

| {max = максимум з x[1]..x[i-1]}

| if x[i]> max then begin

| | max := x[i];

| end;

end;
1.2.5. Даний масив x: array [1..n] of integer, прічсм x[1]

<= x[2] <= ... <= x[n]. Знайти кількість різних чисел

елементів цього масиву.
Рішення. (1 варіант)
i := 1; до := 1;

{інваріант: до - кількість різних чисел серед x[1]..x[i]}

while i <> n do begin

| i := i + 1;

| if x[i] <> x[i-1] then begin

| | до := до + 1;

| end;

end;
(2 варіант) Шукане число на 1 більше кількості тих чисел

i з 1..n-1, для яких x[i] <> x[i+1].
до := 1;

for i := 1 to n-1 do begin

| if x[i]<> x[i+1] then begin

| | до := до + 1;

| end;

end;
1.2.6. (Повідомив А.Л.Брудно.) Прямокутне поле m на n раз-

бито на mn квадратних кліток. Деякі клітки пофарбовані в чер-

ний колір. Відомо, що всі чорні клітки можуть бути розбиті на

декілька непересічних загальних вершин чорних пря-, що не мають

моугольников. Вважаючи, що кольори кліток дані у вигляді масиву типу

array [1..m] of array [1..n] of boolean;

підрахувати число чорних прямокутників, про які йшла мова.

Число дій повинне бути порядку m*n.
Рішення. Число прямокутників рівне числу їх лівих верхніх

кутів. Чи є клітка верхнім кутом, можна дізнатися, подивившись

на її колір, а також колір верхнього і лівого сусідів. (Не за-

будьте, що їх може не бути, якщо клітка з краю.)
1.2.7. Даний масив x: array [1..n] of integer. Знайти колі-

чество різних чисел серед елементів цього масиву. (Число

дій повинно бути порядку n*n.)
1.2.8. Те ж завдання, якщо потрібний, щоб кількість

дій було порядку n* log n. (Вказівка. Дивися розділ про сорті-

ровке.)
1.2.9. Те ж завдання, якщо відомо, що всі елементи масси-

ва - числа від 1 до до і число дій повинне бути порядку n+k.
1.2.10. Даний масив x [1]..x[n] цілих чисел. Не використовуючи

інших масивів, переставити елементи масиву в зворотному поряд-

ке.
Рішення. Числа x [i] і x [n+1-i] потрібно поміняти місцями для

всіх i, для яких i < n + 1 - i, тобто 2*i < n + 1 <=> 2*i <= n

<=> i <= n div 2:

for i := 1 to n div 2 do begin

| ...обміняти x [i] і x [n+1-i];

end;
1.2.11. (з книги Д.Гріса) Даний масив цілих чисел

x[1]..x[m+n], що розглядається як з'єднання два його відрізань:

почала x[1]..x[m] довжини m і кінця x[m+1]..x[m+n] довжини n. Не іс-

пользуя додаткових масивів, переставити почало і кінець.

(Число дій порядку m+n.)
Рішення. (1 варіант). Перевернемо (розташуємо в зворотному по-

рядку) окремо почало і кінець масиву, а потім перевернемо весь

масив як єдине ціле.
(2 варіант, А.Г.Кушніренко). Розглядаючи масив записаним

по кругу, бачимо, що необхідна дія - поворот круга. Як із-

вестно, поворот є композиція двох осьових симетрій.
(3 варіант). Розглянемо більш загальне завдання - обмін два

ділянок масиву x[p+1]..x[q] і x[q+1]..x[s]. Припустимо, що

довжина лівої ділянки (назвемо його A) не більше довжини правого

(назвемо його B). Виділимо в B початок тієї ж довжини, що і A, назо-

вем його B1, а залишок B2. (Отже B = B1 + B2, якщо позначати

плюсом приписування масивів один до одного.) Нам треба з A + B1 +

B2 отримати B1 + B2 + A. Міняючи місцями ділянки A і B1 - вони іме-

ют однакову довжину, і зробити це легко, - отримуємо B1 + A + B2

і залишилося поміняти місцями A і B2. Тим самим ми звели справу до

перестановці два отрзков меншої довжини. Отже, отримуємо таку

схему програми:
p := 0; q := m; r := m + n;

{інваріант: залишилося переставити x[p+1]..x[q], x[q+1]..x[s]}

while (p <> q) and (q <> s) do begin

| {обидві ділянки непорожні}

| if (q - p) <= (s - q) then begin

| | ..переставити x[p+1]..x[q] і x[q+1]..x[q+(q-p)]

| | pnew := q; qnew := q + (q - p);

| | p := pnew; q := qnew;

| end else begin

| | ..переставити x[q-(r-q)+1]..x[q] і x[q+1]..x[r]

| | qnew := q - (r - q); rnew := q;

| | q := qnew; r := rnew;

| end;

end;
Оцінка часу роботи: на черговому кроці що залишився для обработ-

ки ділянка стає коротшою на довжину A; число дій при цьому

також пропорційно довжині A.
1.2.12. Коефіцієнти многочлена зберігаються в масиві а: array

[0..n] of integer (n - натуральне число, ступінь многочлена).

Обчислити значення цього многочлена в точці x (тобто а[n]*(x в

ступені n)+...+a[1]*x+a[0]).
Рішення. (Описуваний алгоритм називається схемою Горнера.)
до := 0; у := а[n];

{інваріант: 0 <= до <= n

y= а[n]*(x в ступені до)+...+a[n-1]*(x в ступені

k-1)+...+ + а[n-k]*(x в ступені 0)}

while k<>n do begin

| до := до + 1;

| у := у * x + а [n - до];

end;
1.2.13. (Для знайомих з основами аналізу. Повідомив А.Г.Куш-

ніренко.) Доповнити алгоритм обчислення значення многочлена

заданій точці по схемі Горнера обчисленням значення його проїз-

водною в тій же крапці.
Рішення. Додавання нового коефіцієнта відповідає пере-

ходу від многочлена P(x) до многочлена P(x)*x + с. Його похідна

у крапці x рівна P'(x)*x + P(x). (Це рішення володіє забавним

властивістю: не треба знати заздалегідь ступінь многочлена. Якщо требо-

вать виконання цієї умови, та ще просити обчислювати тільки

значення похідної, не згадуючи про сам многочлен, виходить

не таке вже просте завдання.)
1.2.14. У масивах

a:array [0..k] of integer і b: array [0..l] of integer

зберігаються коефіцієнти двох многочленів ступенів до і l. Помес-

тіть в масив з: array [0..m] of integer коефіцієнти їх проїз-

ведення. (Числа до, l, m - натуральні, m = до + l; елемент мас-

сива з індексом i містить коефіцієнт при x в ступені i.)
Рішення.
for i:=0 to m do begin

| з[i]:=0;

end;

for i:=0 to до do begin

| for j:=0 to l do begin

| | з[i+j]:= з[i+j]+ а[i]*b[j];

| end;

end;
1.2.15. Запропонований вище алгоритм перемножування многочленів

вимагає порядку n*n дій для перемножування двох многочленів

ступені n. Придумати ефективніший (для великих n) алгоритм

якому достатньо порядку (n в ступені (log 4)/(log 3))

дій.

Вказівка. Уявимо собі, що треба перемножити два многоч-

лена ступені 2k. Їх можна представити у вигляді

A(x)*x^k + B(x) і C(x)*x^k + D(x)

(тут x^k позначає x в ступені до). Твір їх рівно

A(x) C(x)*x^{2k} + (A(x) D(x)+B(x)C(x))*x^k + B(x) D(x)

Природний спосіб обчислення AC, Ad+bc, BD вимагає чотири ум-

ноженій многочленів ступеня до, проте їх кількість можна сокра-

тіть до трьох за допомогою такої хитрості: обчислити AC, BD і

(A+b)(C+d), а потім відмітити, що Ad+bc=(A+b)(C+d) -ac-bd.
1.2.16. Дано два зростаючі масиви x: array [1..k] of

integer і у: array [1..l] of integer. Знайти кількість загальних

елементів в цих масивах (тобто кількість тих цілих t, для ко-

торих t = x[i]= у[j] для деяких i і j). (Число дій по-

рядка k+l.)
Рішення.
k1:=0; l1:=0; n:=0;

{інваріант: 0<=k1<=k; 0<=l1<=l; шукана відповідь = n

+ кількість загальних елементів в x[k1+1]...x[k] і

у[l1+1]..y[l]}

while (k1 <> до) and (l1 <> l) do begin

| if x[k1+1]< у[l1+1] then begin

| | k1 := k1 + 1;

| end else if x[k1+1]> у[l1+1] then begin

| | l1 := l1 + 1;

| end else begin {x[k1+1]= у[l1+1]}

| | k1 := k1 + 1;

| | l1 := l1 + 1;

| | n := n + 1;

| end;

end;

{k1 = до або l1 = l, тому одна з множин, згаданих в

інваріанті, порожньо, а n рівне шуканій відповіді}
Зауваження. У третій альтернативі досить було б збільшувати

одну із змінних k1, l1; друга додана для симетрії.
1.2.17. Вирішити попередню задачу, якщо відомо лише, що

x[1] <= ... <= x[k] і у[1] <= ... <= у[l](зростання замінене

неубуванням).
Рішення. Умова зростання була використана в третій

альтернативі вибору: зрушивши k1 і l1 на 1, ми тим самим уменьша-

чи на 1 кількість загальних елементів в x[k1+1]...x[k] і

x[l1+1]...x[l]. Тепер це доведеться робити складніше.
...

end else begin {x[k1+1]= у[l1+1]}

| t := x [k1+1];

| while (k1

| | k1 := k1 + 1;

| end;

| while (l1

| | l1 := l1 + 1;

| end;

end;
Зауваження. Ця програма має дефект: при перевірці умови

(l1

(або другого, аналогічного) при помилковій першій дужці друга ока-

жется безглуздою (індекс вийде за межі масиву) і возник-

немає помилка. Деякі версії паскаля, обчислюючи (A and B), снача-

ла обчислюють A і при помилковому A не обчислюють B. (Так поводиться

наприклад, система Turbo Pascal, 5.0 - але не 3.0.) Тоді опісан-

ная помилка не виникне.

Але якщо ми не хочемо покладатися на таку властивість іспользу-

емой нами реалізації паскаля (не передбачене його автором

Н.Віртом), то можна поступити так. Введемо додаткову пере-

менную b: boolean і напишемо:
if k1 < до then b := (x[k1+1]=t) else b:=false;

{b = (k1

while b do begin

| k1:=k1+1;

| if k1 < до then b := (x[k1+1]=t) else b:=false;

end;
Можна також зробити інакше:
end else begin {x[k1+1]= у[l1+1]}

| if k1 + 1 = до then begin

| | k1 := k1 + 1;

| | n := n + 1;

| end else if x[k1+1]= x [k1+2]

then begin | | k1 := k1 + 1;

| end else begin

| | k1 := k1 + 1;

| | n := n + 1;

| end;

end;
Так буде коротше, хоча менш симетрично.
Нарешті, можна збільшити розмір масиву в його описі

включивши в нього фіктивні елементи.
1.2.18. Дано два неубутні масиви x: array [1..k] of

integer і у: array [1..l] of integer. Знайти число різних еле-

ментів серед x[1],...,x[k], у[1],...,y[l]. (Число дій по-

рядка k+l.)
1.2.19. Дано два масиви x[1] <= ... <= x[k] і у[1] <= ...

<= у[l]. "З'єднати" їх в масив z[1] <= ... <= z[m](m = k+l;

кожен елемент повинен входити в масив z стільки раз, скільки

раз він входить в цілому в масиви x і у). Число дій

порядку m.
Рішення.
k1 := 0; l1 := 0;

{інваріант: відповідь вийде, якщо до z[1]..z[k1+l1]

приписати справа з'єднання масивів x[k1+1]..x[k] і у[l1+1]..

y[l]} while (k1 <> до) or (l1 <> l) do begin

| if k1 = до then begin

| | {l1 < l}

| | l1 := l1 + 1;

| | z[k1+l1]:= у[l1];

| end else if l1 = l then begin

| | {k1 < до}

| | k1 := k1 + 1;

| | z[k1+l1]:= x[k1];

| end else if x[k1+1] <= у[l1+1] then begin

| | k1 := k1 + 1;

| | z[k1+l1]:= x[k1];

| end else if x[k1+1] >= у[l1+1] then begin

| | l1 := l1 + 1;

| | z[k1+l1]:= у[l1];

| end else begin

| | { такого не буває }

| end;

end;

{k1 = до, l1 = l, масиви сполучені}
Цей процес можна пояснити так. Хай у нас є дві стопки

карток, відсортованих за абеткою. Ми сполучаємо їх в одну

стопку, вибираючи кожного разу ту з верхніх карток обох стопок

яка йде раніше в алфавітному порядку.
1.2.20. Дано два масиви x[1] <= ... <= x[k] і у[1] <= ...

<= у[l]. Знайти їх "перетин", тобто масив z[1] <= ... <=

z[m], що містить їх загальні елементи, причому кратність кожного

елементу в масиві z дорівнює мінімуму з його кратностей в мас-

сивах x і у. Число дій порядку k+l.
1.2.21. Дано два масиви x[1]<=...<=x[k] і у[1]<=...<=y[l]

і число q. Знайти суму виду x[i]+y[j], найбільш близьку до числа

q. (Число дій порядку k+l, додаткова пам'ять - фіксиро-

ванне число цілих змінних, самі масиви міняти не разрешаєт-

ця.)

Вказівка. Треба знайти мінімальну відстань між елемента-

мі x[1]<=...<=x[k] і q-y[l]<=..<=q-y[1], що неважко зробити в

ході їх злиття в один (уявний) масив.
1.2.22. (з книги Д.Гріса) Деяке число міститься в

кожному з трьох цілочисельних неубутних масивів x[1] <= ... <=

x[p], у[1] <= ... <= у[q], z[1] <= ... <= z[r]. Знайти одне

таких чисел. Число дій повинне бути порядку p + q + r.
Рішення.
p1:=1; q1=1; r1:=1;

{інваріант: x[p1]..x[p], у[q1]..y[q], z[r1]..

z[r] містять загальний елемент }

while not ((x[p1]=y[q1]) and (у[q1]=z[r1]))

do begin | if x[p1]<�у[q1] then begin

| | p1:=p1+1;

| end else if у[q1]

| | q1:=q1+1;

| end else if z[r1]

| | r1:=r1+1;

| end else begin

| | { так не буває }

| end;

end;

{x[p1]= у[q1]= z[r1]}

writeln (x[p1]);
1.2.23. Те ж завдання, тільки заздалегідь не відомо, существу-

чи ет загальний елемент в трьох неубутних масивах і потрібне це

з'ясувати (і знайти один із загальних елементів, якщо вони є).
1.2.24. Елементами масиву а[1..n] є неубутні

масиви [1..m] цілих чисел (а: array [1..n] of array [1..m] of

integer; а[1][1] <= ... <= а, ..., а[n][1] <= ... <=

а[n][m]). Відомо, що існує число, що входить у все масси-

ви а[i] (існує таке х, що для всякого i з [1..n]

найдстся j з [1..m], для якого а[i][j]=x). Знайти одне з та-

ких чисел х.
Рішення. Введемо масив b[1]..b[n], що відзначає почало "оста-

ющейся частини" масивів а[1]..a[n].
for k:=1 to n do begin

| b[k]:=1;

end;

eq := true;

for до := 2 to n do begin

| eq := eq and (а[1][b[1]]= а[k][b[k]]);

end;

{інваріант: частини, що залишилися, перетинаються,

тобто існує таке х, що для всякого i з [1..n] найдстся

j з [1..m], не менше b[i], для якого а[i][j]= х; eq

<=> перші елементи частин, що залишилися, рівні}

while not eq do begin

| s := 1; до := 1;

| {а[s][b[s]] - мінімальне серед а[1][b[1]]..a[k][b[k]]}

| while до <> n do begin

| | до := до + 1;

| | if а[k][b[k]]< а[s][b[s]] then begin

| | | s := до;

| | end;

| end;

| {а[s][b[s]] - мінімальне серед а[1][b[1]]..a[n][b[n]]}

| b [s] := b [s] + 1;

| for до := 2 to n do begin

| | eq := eq and (а[1][b[1]]= а[k][b[k]]);

| end;

end;

writeln (а[1][b[1]]);
1.2.25. Приведене рішення попередньої задачі вимагає по-

рядка m*n*n дій. Придумати спосіб з числом дій порядку

m*n.

Вказівка. Доведеться пожертвувати симетрією і вибрати одну

з рядків за основну. Рухаючись по основному рядку, підтримуваний

таке співвідношення: у решті всіх рядків відмічений макси-

мальний елемент, що не перевершує поточного елементу основної

рядки.
1.2.26. (Двійковий пошук) Дана послідовність x[1] <=

... <= x[n] цілих чисел і число а. З'ясувати, чи міститься а в

цій послідовності, тобто чи існує i з 1..n, для ко-

торого x[i]=a. (Кількість дій порядку log n.)
Рішення. (Припускаємо, що n > 0.)
l := 1; r := n+1;

{якщо а є взагалі, тобто і серед x[l]..x[r-1], r > l}

while r - l <> 1 do begin

| m := l + (r-l) div 2 ;

| {l < m < r }

| if x[m] <= а then begin

| | l := m;

| end else begin {x[m]> а}

| | r := m;

| end;

end;

(Звернете увагу, що і у разі x[m]= а інваріант не наруша-

ется.)

Кожного разу r-l зменшується приблизно удвічі, звідки і витека-

ет необхідна оцінка числа дій.

Зауваження.

l + (r-l) div 2 = (2l + (r-l)) div 2 = (r+l) div 2.
1.2.27. (З книги Д.Гріса) Даний масив x: array [1..n] of

array [1..m] of integer, впорядкований по "рядках" і по

"стовпцям":

x[i][j] <= x[i+1][j]

x[i][j] <= x[i][j+1]

і число а. Потрібно з'ясувати, чи зустрічається а серед x[i][j].
Рішення. Уявляючи собі масив а як матрицю (прямо-

косинець, заповнений числами), ми виберемо прямокутник, в ко-

тором тільки і може міститися а, і його звужуватимемо.

Прямо- косинець цей міститиме x[i][j] при 1<=i<=l і k<=j<=m.

1 до m

-----------------------------------

1| |***********|

| |***********|

| |***********|

l| |***********|

|---------------------------------|

| |

n| |

-----------------------------------

(допускаються порожні прямокутники при l = 0 і до = m+1).
l:=n; k:=1;

{l>=0, k<=m+1, якщо а є, то в описаному прямокутнику}

while (l > 0) and (до < m+1) and (x[l][k] <> а) do begin

| if x[l][k]< а then begin

| | до := до + 1; {лівий стовпець не містить а,

видаляємо його}

| end else begin {x[l][k]> а}

| | l := l - 1; {нижній рядок не містить а, видаляємо її}

| end;

end;

{x[l][k]= а або прямокутник порожній }

answer:= (l > 0) and (до < m+1) ;
Зауваження. Тут та ж помилка: x[l][k] може опинитися не-

визначеним. (Ес виправлення надається читачеві.)
1.2.28. (Московська олімпіада по програмуванню) Даний не-

убуваючий масив позитивних цілих чисел а[1] <= а[2] <=...<=

а[n]. Знайти найменше ціле позитивне число, не представі-

моє у вигляді суми декількох елементів цього масиву (кожен еле-

мент масиву може бути використаний не більше одного разу). Число

дій порядку n.
Рішення. Хай відомо, що числа, уявні у вигляді

суми елементів а[1],...,a[k], заповнюють відрізок від 1 до некото-

рого N. Якщо а[k+1]> N+1, то N+1 і буде мінімальним числом, не

уявним у вигляді суми елементів масиву а[1]..a[n]. Якщо ж

а[k+1] <= N+1, то числа, уявні у вигляді суми елементів

а[1]..a[k+1], заповнюють відрізок від 1 до N+a[k+1].
до := 0; N := 0;

{інваріант: числа, уявні у вигляді суми елементів

масиву а[1]..a[k], заповнюють відрізок 1..N}

while (до <> n) and (а[k+1] <= N+1) do begin

| N := N + а[k+1];

| до := до + 1;

end;

{(до = n) або (а[k+1]> N+1); у обох випадках відповідь N+1}

writeln (N+1);
(Знову той же дефект: у умові циклу за помилкової першої умови

друге не визначене.)
1.2.29. (Для знайомих з основами алгебри) У цілочисельному

масиві а[1]..a[n] зберігається перестановка чисел 1..n (кожне з

чисел зустрічається по одному разу).

(а) Визначити парність перестановки. (І в (а), і в (б) ко-

лічество дій порядку n.)

(б) Не використовуючи інших масивів, замінити перестановку

зворотну (якщо до роботи програми а[i]=j, то після повинно бути

а[j]=i).
Вказівка. (а) Парність перестановки визначається колі-

чеством циклів. Щоб відрізняти вже пройдені цикли, у їх еле-

ментів можна, наприклад, міняти знак. (б) Звернення проводимо по

циклам.
1.2.30. Даний масив а[1..n] і число b. Переставити числа

масиві так, щоб зліва від деякої межі стояли

числа, менші або рівні b, а праворуч від межі - великі або

рівні b.
Рішення.
l:=0; r:=n;

{інваріант: а[1]..a[l]<=b; а[r+1]..

a[n]>=b} while l <> r do begin

| if а[l+1] <= b then begin

| | l:=l+1;

| end else if а[r] >=b then begin

| | r:=r-1;

| end else begin {а[l+1]>b; а[r]

| | поміняти а[l+1] і а[r]

| | l:=l+1; r:+r-1;

| end;

end;
1.2.31. Те ж завдання, але потрібний, щоб спочатку йшли еле-

менти, менші b, потім рівні b, а лише потім великі b.
Рішення. Тепер буде потрібно три межі: до першої будуть

йти елементи, менші b, від першої до другої - рівні b, потім

невідомо які до третьої, а після третьої - великі b. (Більш

симетричне рішення використовували б чотири межі, але навряд чи

гра коштує свічок.) Як черговий даного елемен-

та беремо елемент праворуч від середньої межі.
l:=0; m:=0; r:=n;

{інваріант: а[1..l]

a[n]>b} while m <> r do begin

| if а[m+1]=b then begin

| | m:=m+1;

| end else if а[m+1]>b then begin

| | обміняти а[m+1] і а[r]

| | r:=r-1;

| end else begin {а[m+1]

| | обміняти а[m+1] і а[l+1]

| | l:=l+1; m:=m+1;

end;
1.2.32. (варіант попереднього завдання, названий в книзі

Дейкстри завданням про голландський прапор) У масиві коштують числа 0, 1

і 2. Переставити їх в порядку зростання, якщо єдиною

дозволеною операцією (крім читання) над масивом є пе-

рестановка двох елементів.
1.2.33. Даний масив а[1]..a[n] і число m<=n. Для кожної

групи з m членів, що стоять поряд (таких груп, очевидно, n-m+1)

обчислити її суму. Загальне число дій повинне бути порядку n.
Рішення. Переходячи від групи до сусідньої, ми додаємо один

член, а іншою віднімаємо.
1.2.34. Дана квадратна таблиця а[1..n][1..n] і число m<=n.

Для кожного квадрата розміру m на m в цій таблиці обчислити

суму чисел, що стоять в нім. Загальне число дій повинне бути по-

рядка n*n.
Рішення. Спочатку для кожного горизонтального прямокутника

розміром n на 1 обчислюємо суму чисел, що стоять в нім. (При зрушенні

такого прямокутника по горизонталі на 1 потрібно додати одне

число і одне відняти.) Потім, використовуючи ці суми, обчислюваний

суми в квадратах. (При зрушенні квадрата по вертикалі додається

смужка, а інша смужка збавляється.)

Oleksa.Inc

Схожі:

Фонд Освітніх та Інформаційних Технологій Обробка послідовності дробових чисел'); writeln('Після введення кожного числа натискайте '); sum:=0	Фонд Освітніх та Інформаційних Технологій Оголосите змінні, необхідні для обчислення вартості покупки, що складається з декількох зошитів, олівців і лінійки
Фонд Освітніх та Інформаційних Технологій Дані дві цілі змінні а, b. Скласти фрагмент програми, після виконання якого значення змінних поменя	Фонд Освітніх та Інформаційних Технологій Середнє зростання: ',sred: 6: 1', см'; writeln ГУ ',m,'-x учнів зростання перевищує ', 'середній.'
Фонд Освітніх та Інформаційних Технологій Проте, в Turbo Pascal аргумент функції Sin повинен бути виражений в радіанах (1 радий. = 180 1415925, де 1415926 число "ПІ").)	Фонд Освітніх та Інформаційних Технологій Проте, в Turbo Pascal аргумент функції Sin повинен бути виражений в радіанах (1 радий. = 180 1415925, де 1415926 число "ПІ").)
ВИКОРИСТАННЯ НОВІТНІХ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ НА УРОКАХ ФІЗИКИ Для гармонійного поєднання останніх досягнень інформаційних технологій та шкільного курсу вивчення фізики постає проблема створення...	Фонд Освітніх та Інформаційних Технологій Якщо на одну шальку терезів посадити Даринку, яка важить кілограмів, і Наталку, яка важить на 5 кілограмів менше, а на іншу насипати...
СТВОРЕННЯ ОСВІТНЬОГО СЕРЕДОВИЩА ДЛЯ ПІДГОТОВКИ ПЕДАГОГІВ ЗАСОБАМИ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ Т педагогічних наук, доцент кафедри інноваційних та інформаційних технологій. Шевченко Людмила Станіславівна – кандидат педагогічних...	Лекція Інформатизація діяльності інформаційних установ Лекція Інформатизація діяльності інформаційних установ. Електронний документний фонд як модель управління інформаційними ресурсами....

Додайте кнопку на своєму сайті:
Портал навчання