Алгоритмы с использованием условного оператора

Алгоритмы с ис­поль­зо­ва­ни­ем условного оператора

1. Дан фраг­мент про­грам­мы, об­ра­ба­ты­ва­ю­щий мас­сив А из 10 эле­мен­тов:

j := 1;

for i:=1 tо 10 do

if A[i] = A[j] then j := i;

s := j;

Чему будет равно зна­че­ние пе­ре­мен­ной s после вы­пол­не­ния этого ал­го­рит­ма?

1) 1
2) 10
3) ин­дек­су эле­мен­та, рав­но­го пер­во­му, и име­ю­ще­му наи­боль­ший ин­декс
4) ин­дек­су эле­мен­та, рав­но­го по­след­не­му, и име­ю­ще­му наи­мень­ший ин­декс

Решение.

Из­на­чаль­но эле­мент a[j]=a[1]. Усло­вие цикла го­во­рит нам о том, что если какой-то эле­мент а[i] мас­си­ва А сов­па­да­ет с пер­вым эле­мен­том этого мас­си­ва, то ин­дек­су j при­сва­и­ва­ет­ся зна­че­ние ин­дек­са i. Т. к. цикл про­бе­га­ет все зна­че­ния i в по­ряд­ке уве­ли­че­ния, то по­след­ним зна­че­ни­ем j ста­нет наи­боль­шее зна­че­ние ин­дек­са i такое, что a[i]=a[1]. Это зна­че­ние сов­падёт со зна­че­ни­ем пе­ре­мен­ной s после вы­пол­не­ния ал­го­рит­ма.

Пра­виль­ный ответ ука­зан под но­ме­ром 3.

2. Дан фраг­мент про­грам­мы, об­ра­ба­ты­ва­ю­щий двух­мер­ный мас­сив A раз­ме­ром nxn.

for i:=1 to n-1 do

for j:= i+1 to n do

if A[i,1] < A[j,1] then begin

k:=A[i,1];

A[i,1]:=A[j,1];

A[j,1]:=k;

end;

В этом фраг­мен­те:

1) упо­ря­до­чи­ва­ет­ся пер­вая стро­ка мас­си­ва по убы­ва­нию
2) упо­ря­до­чи­ва­ет­ся пер­вый стол­бец мас­си­ва по убы­ва­нию
3) за­ме­ня­ют­ся эле­мен­ты k-ого столб­ца таб­ли­цы
4) за­ме­ня­ют­ся эле­мен­ты k-ой стро­ки таб­ли­цы

Решение.

Об­ра­тим вни­ма­ние, что в двой­ном цикле пе­ре­мен­ная i из­ме­ня­ет­ся от 1 до n-1, а j - от 1 до n (на 1 шаг боль­ше). Это озна­ча­ет, что с эле­мен­том a[j,1] будут по оче­ре­ди срав­ни­вать­ся все эле­мен­ты столб­ца 1, кроме по­след­не­го. Они вы­строт­ся от са­мо­го боль­шо­го до са­мо­го ма­лень­ко­го свер­ху вниз, т.е. по убы­ва­нию.

Но чтобы вы­брать пра­виль­ный ответ, можно было рас­смот­реть дан­ный фраг­мент про­грам­мы:

...k:=A[i,1];

A[i,1]:=A[j,1];

A[j,1]:=k;

...

Эта опе­ра­ция ме­ня­ет ме­ста­ми два эле­мен­та пер­во­го столб­ца, а зна­чит все из­ме­не­ния про­ис­хо­дят толь­ко в нём. Ва­ри­ант от­ве­та, в ко­то­ром фи­гу­ри­ру­ет толь­ко пер­вый стол­бец, ука­зан под но­ме­ром 2.

Пра­виль­ный ответ ука­зан под но­ме­ром 2.

3. Зна­че­ния эле­мен­тов двух­мер­но­го мас­си­ва A[1..100,1..100] за­да­ют­ся с по­мо­щью сле­ду­ю­ще­го фраг­мен­та про­грам­мы:

for i:=1 to 100 do

for k:=1 to 100 do

if i > k then

A[i,k] := i

else A[i,k] := -k;

Чему равна сумма эле­мен­тов мас­си­ва после вы­пол­не­ния этого фраг­мен­та про­грам­мы?

1) 5000
2) 0
3) -5000
4) -5050

Решение.

Из дан­ной про­грам­мы мы по­лу­чим такую таб­ли­цу

-1 -2 -3 -4

2 -2 -3 -4

3 3 -3 -4

4 4 4 -4 и т. д.

Если смот­реть сим­мет­рич­ность таб­ли­цы, то от­но­си­тель­но глав­ной диа­го­на­ли ячей­ки будут вза­им­но уни­что­жать­ся, так что оста­нет­ся найти толь­ко сумму глав­ной диа­го­на­ли:

-1 - 2 - 3 - 4 - 5 -...- 98 - 99 - 100 = -(1 + 99) - (2 + 98) -...- (49 + 51) - 50 - 100 =

= -100 * 49 - 150 = -4 900 - 150 = -5 050.

Пра­виль­ный ответ ука­зан под но­ме­ром 4.

4. В про­грам­ме опи­сан од­но­мер­ный це­ло­чис­лен­ный мас­сив A с ин­дек­са­ми от 1 до 10. Ниже пред­став­лен фраг­мент этой про­грам­мы, в ко­то­ром зна­че­ния эле­мен­тов мас­си­ва сна­ча­ла за­да­ют­ся, а затем ме­ня­ют­ся.

for i:=1 to 10 do

A[i]:=5*i;

for i:=1 to 10 do begin

k:=A[i]-2;

A[10-i+1]:=k;

end;

Чему будут равны эле­мен­ты этого мас­си­ва?

1) 1 6 11 16 21 23 18 13 8 3
2) 3 8 13 18 23 28 33 38 43 48
3) 48 43 38 33 28 23 18 13 8 3
4) 1 6 11 16 21 26 31 36 41 46

Реше­ние.

Пер­вый цикл, за­пол­ня­ем мас­сив:

i=1: a[1]=5,

i=2: a[2]=10,

...

i=10: a[10]=50.

Вто­рой цикл, ме­ня­ем зна­че­ние эле­мен­тов:

i=1: k = a[1] - 2 = 3, a[11-1] = a[10] = 3,

i=2: k = a[2] - 2 = 8, a[11-2] = a[9] = 8,

i=3: a[8] = 13,

i=4: a[7] = 18,

i=5: a[6] = 23,

i=6: k = a[6] - 2 = 21, a[11-6] = a[5] = 21 (здесь и далее ис­поль­зу­ют­ся уже изменённые эле­мен­ты, а не ис­ход­ные),

i=7: k = a[7] - 2 = 16, a[11-7] = a[4] = 16,

...

i=10: k = a[10] - 2 = 3 - 2 = 1, a[1] = 1.

По­это­му в ре­зуль­та­те вы­пол­не­ни про­грам­мы эле­мен­ты мас­си­ва будут равны: 1, 6, 11, 16, 21, 23, 18, 13, 8, 3.

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

5. В про­грам­ме опи­сан од­но­мер­ный це­ло­чис­лен­ный мас­сив с ин­дек­са­ми от 0 до n. Ниже пред­став­лен за­пи­сан­ный на раз­ных язы­ках про­грам­ми­ро­ва­ния фраг­мент одной и той же про­грам­мы, об­ра­ба­ты­ва­ю­щей дан­ный мас­сив:

Чему будет равно зна­че­ние пе­ре­мен­ной s после вы­пол­не­ния дан­ной про­грам­мы? Ответ дол­жен быть вер­ным при любых зна­че­ни­ях эле­мен­тов мас­си­ва.

1) Ми­ни­маль­но­му эле­мен­ту в мас­си­ве A
2) Ко­ли­че­ству эле­мен­тов мас­си­ва A, мень­ших по­след­не­го эле­мен­та мас­си­ва
3) Сумме всех эле­мен­тов мас­си­ва А, мень­ших по­след­не­го эле­мен­та мас­си­ва
4) Ин­дек­су пер­во­го эле­мен­та мас­си­ва А, ко­то­рый мень­ше A[n]

Реше­ние.

Пе­ре­ме­ной z при­сва­и­ва­ет­ся зна­че­ние по­след­не­го эле­мен­та.

Внут­ри цикла все эле­мен­ты мас­си­ва срав­ни­ва­ют­ся с по­след­ним, при этом если эле­мент мень­ше по­след­не­го, то пе­ре­мен­ная s уве­ли­чи­ва­ет­ся на зна­че­ние дан­но­го эле­мен­та. Если в мас­си­ве x эле­мен­тов мень­ше по­след­не­го, то s при­мет зна­че­ние, рав­ное сумме зна­че­ний x эле­мен­тов, мень­ших по­след­не­го эле­мен­та мас­си­ва.

Пра­виль­ный ответ ука­зан под но­ме­ром 3.

6. В про­грам­ме опи­сан од­но­мер­ный це­ло­чис­лен­ный мас­сив с ин­дек­са­ми от 0 до 10. Ниже пред­став­лен за­пи­сан­ный на раз­ных язы­ках про­грам­ми­ро­ва­ния,фраг­мент одной и той же про­грам­мы, об­ра­ба­ты­ва­ю­щей дан­ный мас­сив:

В на­ча­ле вы­пол­не­ния этого фраг­мен­та в мас­си­ве на­хо­ди­лись числа 0, 10, 20, 30, 40, 50, 60, 70, 80. 90, 100, т.е. A[0] = 0, A[1] = 10 и т. д. Чему будет равно зна­че­ние пе­ре­мен­ной s после вы­пол­не­ния дан­ной про­грам­мы?

1) 60
2) 100
3) 150
4) 550

Реше­ние.

Цикл вы­пол­ня­ет­ся, пока раз­ность A[n − i] − A[i] боль­ше, чем A[i]. При i=0, 1, 2, 3, 4 по­лу­ча­ем:

i=0: A[10] − A[0] = 100 − 0 > A[0], s:=0 + 0 = 0;

i=1: A[9] − A[1] = 90 − 10 > A[1], s:=0 + 10 = 10;

i=2: A[8] − A[2] = 80 − 20 > A[2], s:=10 + 20 = 30;

i=3: A[7] − A[3] = 70 − 30 > A[3], s:=30 + 30 = 60.

Усло­вие A[n − i] − A[i] > A[i] пе­ре­ста­нет вы­пол­нять­ся на пятом шаге, когда 60 − 40 > 40 - не­вер­но. Таким об­ра­зом, при­сва­и­ва­ние s := s + A[i] вы­пол­нит­ся для пер­вых че­ты­рех эле­мен­тов. После вы­пол­не­ния про­грам­мы по­лу­чим s = 60.

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

7. В про­грам­ме опи­сан од­но­мер­ный це­ло­чис­лен­ный мас­сив с ин­дек­са­ми от 0 до 12. Ниже пред­став­лен за­пи­сан­ный на раз­ных язы­ках про­грам­ми­ро­ва­ния фраг­мент одной и той же про­грам­мы, об­ра­ба­ты­ва­ю­щей дан­ный мас­сив:

Бей­сик

Пас­каль

s = 0

n = 12

FOR i = 0 TO n

IF A(n-i) - A(i) = A(i) THEN

s = s+2*A(i)

END IF

NEXT i

s := 0;

n := 12;

for i:=0 to n do begin

if A[n-i] - A[i] = A[i] then

s:=s+2*A[i];

end;

Си

Ал­го­рит­ми­че­ский язык

s = 0;

n = 12;

for (i = 0; i <= n; i++) {

if (A[n-i] - A[i] == A[i])

s = s+2*A[i];

}

s := 0

n := 12

нц для i от 0 до n

если A[n-i] - A[i] = A[i]

то s := s+2*A[i]

все

кц

В на­ча­ле вы­пол­не­ния этого фраг­мен­та в мас­си­ве на­хо­ди­лись числа 0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, т. е. A[0] = 0, A[1] = 10 и т. д. Чему будет равно зна­че­ние пе­ре­мен­ной s после вы­пол­не­ния дан­ной про­грам­мы?

1) 60
2) 80
3) 100
4) 780

Реше­ние.

Дей­ствие «s:=s+2*A[i];» вы­пол­ня­ет­ся, если ис­тин­но усло­вие «if A[n-i] - A[i] = A[i]». Дан­ное усло­вие вы­пол­не­но толь­ко для i = 4, в этом слу­чае A[8] − A[4] = 80 − 40 = 40 = A[4]. Пе­ре­мен­ная s при­мет зна­че­ние s = 0 + 2 · 40 = 80.

Пра­виль­ный ответ ука­зан под но­ме­ром 2.

8. Зна­че­ния эле­мен­тов дву­мер­но­го мас­си­ва А были равны 0. Затем зна­че­ния не­ко­то­рых эле­мен­тов были из­ме­не­ны (см. пред­став­лен­ный фраг­мент про­грам­мы):

n := 0;

for i:=1 tо 5 do

for j:=1 tо 6-i do begin

n := n + 1;

A[i,j] := n;

end;

Какой эле­мент мас­си­ва будет иметь в ре­зуль­та­те мак­си­маль­ное зна­че­ние?

1) A[1,1]
2) A[1,5]
3) A[5,1]
4) A[5,5]

Реше­ние.

В пе­ре­мен­ной n на­кап­ли­ва­ет­ся сумма про­хо­дов цикла. Это число всё время растёт, сле­до­ва­тель­но, наи­боль­шим эле­мен­том мас­си­ва будет тот, зна­че­ние ко­то­ро­му будет при­сво­е­но по­след­ним. Это эле­мент A[5,1].