Алгоритмы и программы. Методические указания для подготовительных курсов (стр. 6 )

Public Sub WhatIsIt()

Dim A(6,6) As Integer, m As Integer, n As Integer, k As Integer

n = 6

For i=1 To n

For j=1 To n

A(i, j) = InputBox("Введите элемент массива")

Next

Next

k = 0: m = A(1,1)

For i=1 To n

If m<A(i, i) Then: m = A(i, i)

If m<A(i, n-i+1) Then: m = A(i, n-i+1)

Next

For i=1 To n

For j=1 To n

If i<>j And j<>n-i+1 Then

If A(i, j)=m Then: k = k+1

End If

Next

Next

MsgBox k

End Sub

Ответ: программа вводит двумерный массив и считает количество недиагональных элементов массива, равных максимальному элементу ее диагоналей.

Комментарий решения

Задача сводится к определению алгоритма по заданному набору операторов. Поскольку всякий алгоритм пошагово преобразует исходный набор данных, для понимания задачи нужно проследить как меняется этот набор после исполнения каждого оператора. В данном случае в качестве данных в программе описаны три целые переменные (n, m,k) и двумерный массив А(6,6). Первые операторы: присваивание n=6, последующий вложенный цикл и присваивания k=0: m=A(1,1)определяют начальные значения объявленного набора данных.

Далее идет цикл, изменяющий значение переменной m. Первый условный оператор:

If m<A(i, i)Then: m=A(i, i) на каждом шаге цикла присваивает переменной m значение элемента A(i, i), если оно оказалось больше сохраненного в m значения, второй оператор:

If m<A(i n-i+1)Then: m=A(i, n-i+1) присваивает переменной m значение элемента A(i, n-i+1), если оно оказалось больше сохраненного в m. Таким образом, в цикле определяется наибольшее среди всех элементов A(i, i), A(i, n-i+1) значение, и оно сохраняется в переменной m. Выясним, где расположены эти элементы. Подставим вместо i значения, получаемые этим счетчиком в процессе прохождения цикла: i =1, 2, …, 6. Получим элементы А(1,1),А(2,2),…,А(6,6) и А(1,6),А(2,5),А(3,4),…,А(6,1), которые в точности соответствуют диагональным элементам двумерного массива (т. е. лежат на его главной и побочной диагоналях). Итог: первая часть программы находит максимум среди диагональных элементов введенного массива А.

Далее в программе вновь идет вложенный цикл, изменяющий значение переменной k. Цикл перебирает все недиагональные элементы массива А (условие i<>j And j<>n-i+1 выделяет только те A(i, j) , которые не находятся ни на главной диагонали, где i=j, ни на побочной диагонали, где j=n-i+1). Для этих элементов выясняется равны ли они полученному максимуму m и, если да, то k увеличивается на единицу. Периодическое увеличение какой-либо переменной на единицу обычно свидетельствует о том, что эта переменная является счетчиком чего-либо. В данном случае k считает элементы, равные найденному максимуму m. Итог: вторая часть программы находит количество недиагональных элементов массива А, равных максимальному элементу его диагоналей.

Поскольку далее идет оператор печати полученного значения счетчика k, то общий результат: заданная программа вводит двумерный массив А размером 6´6, находит максимум среди элементов его диагоналей и определяет количество равных этому числу значений среди остальных его элементов.

Пример П5. Определить ошибки или пропущенные строки в заданной программе.

Задана программа с пропущенными строками, решающая следующую задачу:

На квадратной карте-сетке размером 5´5, считанной с листа Excel, указаны (цифрой 1) прямолинейные траектории движения двух поездов, начинающиеся и заканчивающиеся на границах сетки. Известно, что один поезд шел путем, совпадающим с главной диагональю этого квадрата, а траектория второго пересекла этот путь под прямым углом. Определить координаты (номер строки и номер столбца) начала и конца траектории второго поезда.

Требуется заполнить пропущенные строки.

Public Sub tema10()

Dim A(5, 5) As Integer

For i=1 To 5

For j=1 To 5

A(i, j) = Cells(i, j)

Next: Next

______

If A(1,j) = 1 And A(1,j) = A(j,1) Then

MsgBox "1, " & CStr(j) & " и " & CStr(j) & ",1"

Exit For

End If

If Then

MsgBox "5, " & CStr(j) & " и " & CStr(j) & ",5"

Exit For

End If

Next

End Sub

Ответ: первая строка: For j=2 To 5, вторая строка: A(5,j)=1 And A(5,j)=A(j,5).

Комментарий решения

При выполнении таких задач необходимо по программе восстановить алгоритм, попытавшись вначале осознать возможные пути решения. Поскольку вторая траектория прямолинейна и пересекает первую (диагональную) под прямым углом, следовательно, ее элементы расположены симметрично относительно этой диагонали, например: А(1,2) и А(2,1); А(1,3) и А(3,1); А(1,4),А(2,3) и А(3,2),А(4,1) и т. д. Один из алгоритмов решения может состоять в том, чтобы проанализировать поочередно такие цепочки элементов на наличие у них значения, равного 1 (т. к. траектория «закрашена» цифрой 1). Более оптимальные алгоритмы могут проверять не всю цепочку целиком, а лишь два или даже один ее элемент, т. к. из условия следует, что первая и вторая траектории есть на карте и никаких других траекторий нет. Поэтому достаточно проверить «на единицу» только элементы первой строки и последнего столбца (или последней строки), чтобы определить один из концов искомой траектории, второй конец будет иметь симметричные координаты i, j. Чтобы уточнить, какой именно из этих алгоритмов реализован, обратимся к программе.

Очевидно, программа должна начинаться с определения исходных данных, здесь – нужно считать карту с листа Excel. Операторы первого (вложенного) цикла выполняют это. Скобки Next:Next указывают, что к моменту пропуска этот цикл полностью закрыт, карта считана. Дальнейший просмотр программы обнаруживает наличие операторов Exit For и закрывающей цикл For скобки Next, хотя такой цикл в имеющихся строках не открывался. Значит, первая пропущенная строка открывает цикл For. Внутри этого цикла фигурирует счетчик j в перечислении элементов карты A(i, j), счетчик же i отсутствует, значит открывался простой цикл (без вложенных): For j=. Последующие за первым пропуском операторы If и печати MsgBox свидетельствуют, что проверяются на значение 1 элементы первой строки и симметричные элементы 1-го столбца: A(1,j) и A(j,1). Значит, выбран алгоритм определения траектории по двум ее точкам. Так как анализируются элементы карты 5´5 и пятый элемент этой строки также может быть концом траектории, последнее значение счетчика j будет 5, т. е. пропущенный заголовок цикла имеет вид: For j= To 5. Осталось определить начальное значение счетчика. Так как элемент А(1,2) уже может принадлежать траектории, то претенденты на это значение – числа 1 или 2. Если подставить в условие If значение j=1, получим: условие истинно и будут напечатаны координаты диагонального элемента А(1,1) – вторая траектория выродилась в точку, что противоречит условию задачи. Значит, начало отсчета j есть 2, т. е. первая пропущенная строка: For j=2 To 5. Шаг Step можно не указывать, т. к. перебираются первые элементы каждого столбца.

При дальнейшем анализе обратим внимание на то, что если элемент траектории в первой строке обнаружен, то программа выходит на оператор End Sub, поскольку, если условие в If истинно, то сработает последующий за печатью результата оператор Exit For принудительного выхода из цикла. Этого достаточно, если один из концов траектории находится в первой строке или первом столбце. Если же это не так (например, концевой элемент А(2,5) или А(5,2), то требуются дальнейшие проверки – анализ на наличие единицы в 5-м столбце или 5-й строке. Последующий за вторым пропуском оператор печати подсказывает, что так и есть – анализируются А(j,5) или А(5,j) для всякого значения счетчика j. Значит, претендентами на начало второй пропущенной строки могут быть строки: A(5,j)=1 или A(j,5)=1. Любая из них дает правильный ответ. Но, если следовать логике предложенного решения задачи (анализ по двум точкам), то к полученной строке нужно «прицепить» еще одну проверку симметричной точки, получим строку: A(5,j)=1 And A(5,j)=A(j,5) или эквивалентную A(j,5)=1 And A(j,5)=A(5,j). Если придерживаться порядка, указанного в операторе печати MsgBox и «стиля» первого оператора If A(1,j)= … , то вторая пропущенная строка – это: A(5,j)=1 And A(5,j)=A(j,5).

2.2. Тестовые задачи с ответом

Пример П6 (задача на алгоритмизацию). Какую из задач решает данный алгоритм.

 

Варианты ответа:

1) нахождение номера первого максимального элемента одномерного массива размерности 15;

2) нахождение номера первого минимального элемента одномерного массива размерности 15;

3) нахождение номера последнего максимального элемента одномерного массива размерности 15;

4) нахождение номера последнего минимального элемента одномерного массива размерности 15.

Ответ: 3.

Пример П7. Что напечатает эта программа?

Sub MyProcOtvet()

Dim x As Integer, k As Integer

k = 2: x = k-3

If x > k Then

x = x–5

Else

x = x+5

End If

While x>0

x = k*2 + x^2

Wend

MsgBox x

End Sub

Ответ: ничего, программа зациклится, т. к. условие продолжения цикла всегда истинно.

Пример П8 (вложенные циклы и двумерные массивы). Какое значение будет иметь элемент A(1,5) и A(4,5) в результате выполнения следующей программы:

Public Sub matrixOtvet()

Dim A(5, 5) As Integer, x As Integer

x = 3

For j=1 To 5

A(1,j) = 2

Next

For i=2 To 5

For j=1 To 5

A(i, j) = A(i-1,j)*2 - x*A(1,j)+ i*j

Next

Next

End Sub

Ответ: A(1,5) = 2 и A(4,5) = 64

Пример П9( восстановление постановки задачи по заданной программе) . Какую задачу решает следующая программа:

Public Sub WhatIsItOtvet()

Dim A(5, 5) As Integer, m As Integer, B As Integer

For i=1 To 5

For j=1 To 5

A(i, j) = InputBox("Введите элемент массива ")

Next: Next

m = A(1,1)

For i=1 To 5

For j=1 To 5

If m<A(i, j) Then: m = A(i, j)

Next: Next

For i=1 To 5

If A(i, i)<m Then

B = A(i, i): Exit For

End If

Next

For i=1 To 5

A(i,3) = B: A(4,i) = B

Next

For i=1 To 5

For j=1 To 5

Cells(i, j) = A(i, j)

Next: Next

End Sub

Ответ: вводит двумерный массив размера 5´5 и заменяет значения элементов третьего столбца и четвертой строки на значение первого из элементов главной диагонали, меньшего максимального элемента всего массива. Результат выводит на лист Excel.

Пример П10. Определить ошибки или пропущенные строки в заданной программе.

Задана программа с пропущенными строками, решающая следующую задачу:

Дана квадратная сетка размером 8´8. Заполнить ее единицами, расположив их в шахматном порядке: первая клетка пуста, вторая равна 1, третья пуста и т. д. Результат вывести на лист Excel.

Требуется заполнить пропущенные строки.

Public Sub tema10Otvet()

Dim A(8,8) As Integer

For i=1 To 8

 

A(i, j) = 1

Cells(i, j) = A(i, j)

Next

 

End Sub

Ответ: первая строка: For j=i Mod 2 +1 To 8 Step 2, вторая строка: Next.

2.3. Упражнения по теме для самостоятельного решения

1. Составить блок-схему алгоритма для решения следующий задачи: дан одномерный массив размерности 20, найти сумму элементов массива до первого нуля.

2. Что напечатает эта программа?

Sub MyProcSamost()

Dim x As Single, y As Single, A As Integer, C As Integer

x = 9: A =6: C = А/2

y = (Sqr(x) + 2*A*x-3)/(x-C)^2

For i= 1 To y

x = x+1

Next

MsgBox x

End Sub

3. Какое значение будет иметь элемент A(3,5) и A(5,2) в результате выполнения следующей программы:

Public Sub matrixSamost()

Dim A(6,6) As Integer, x As Integer

x = 5

For i=1 To 6

A(i,1) = 3

Next

For i=1 To 6

For j=2 To 6

A(i, j) = A(i, j-1)*2 + x

x = x-1

Next

Next

For i=1 To 6

A(i,7-i) = 77

Next

End Sub

4. Задана программа с пропущенными строками, решающая следующую задачу:

На листе Excel задана квадратная сетка размером n´n (одна клетка соответствует одной ячейке листа, отсчет с начала листа). Сетка разделена диагоналями на четыре части, верхняя четверть заполнена единицами. Скопировать значения этой четверти на нижнюю, зеркально отображая строки (например, первую на последнюю, вторую на предпоследнюю и т. п.) и не копируя элементы оставшихся частей сетки. Решить для n=6.

Требуется заполнить пропущенные строки.

Public Sub tema10Samost()

Dim n As Integer, k As Integer

n = 6: k = 1

For i=4 To n

 

Cells(i, j) = Cells(i-k, j)

Next

 

Next

End Sub

2.4. Образцы тестов по программированию

Что напечатает программа? Dim r As Integer, t As Long r = 4000: t = 35000 If Not (t = r) Then Do r = r + 100 t = t - 100 Loop While r < 5000 End If r = t * 2 MsgBox r
1) 10000	2) 5000	3) ошибка переполнения памяти	4) синтакси-ческая ошибка в блоке If...	5) 68000	6) 20000	7) нет правиль-ного варианта ответа	8) 35000	9) 4000
Что напечатает программа? Dim p As Integer, s As Single Dim pr As Integer, porog As Integer p = CInt(110 Mod 50): porog = 79: s = 0 If p < (porog Mod 70) Then pr = 5: s = p + p * pr / 100 ElseIf p >= (porog Mod 6) + 9 And s > 0 Then pr = 4: s = p + p * pr / Else pr = 10: s = 2 * p + p * pr / 100 End If MsgBox s
1) 9.4	2) 10.5	3) 3	4) 21	5) 10	6) 9	7) нет правиль-ного варианта ответа	8) 85	9) 11
3.  Найти результат выполнения программы b = 2 a = b: c = 1 For i = 1 To 5 Step 2 a = a + b b = b - c c = a + c Next MsgBox (a + b + c + i)
1) 15	2) 0	3) 5	4) 3	5) нет правиль-ного варианта ответа	6) 2	7) 10	8) 1	9) -3
Что напечатает программа? Dim A() As Integer, n As Integer, m As Integer, s As Integer n = 4: m = 5 ReDim A(n, m): s = 0 For i = 4 To 1 Step -1 For j = 1 To 5 A(i, j) = i ^ 2 + j ^ 2: Cells(i, j) = A(i, j) If i = j Or Not (i ^ 2 < i * j) Then s = s + A(i, j) End If Next Next MsgBox s
1) 60	2) 150	3) сообщение об ошибке описания	4) зациклится	5) сообщение об ошибке выхода за пределы массива	6) нет правиль-ного варианта ответа	7) 25	8) 100	9) 200
Что напечатает программа? Dim A(7, 7) As Integer, F As Integer F = 1 For i = 1 To 7 For j = 1 To 7 A(i, j) = (i - j) ^ 2 If i = j Or j = 7 - i + 1 Then F = F + A(i, j) - j End If Next F = F + i Next MsgBox F
1) 82	2) 40	3) 89	4) 48	5) нет правиль-ного варианта ответа	6) 20	7) 55	8) 100	9) 300
6.  Найти результат выполнения программы Dim s As String s = "мир, труд, май!" n = Len(s): k = 0 For i = 1 To n - 3 If Mid(s, i, 1) = "р" Or Mid(s, i, 2) = "уд" Then k = k + InStr(1, s, "а") - 2 Else k = k + 10 End If Next MsgBox k
1) 83	2) 72	3) 123	4) 120	5) 211	6) 56	7) 121	8) 111	9) нет правиль-ного варианта ответа
Какую задачу решает программа? Dim a(10) As Integer, s As Integer For i = 1 To 10 a(i) = Cells(i, 1): Next For i = 1 To 10 s = 0 For j = 1 To 10 If i <> j And a(j) < a(i) Then s = s + a(j): End If Next Cells(i, 2) = s Next
1) для каждого элемента массива а находит сумму элементов этого массива, меньших данного и стоящих левее него	2) для каждого элемента массива а находит сумму элементов этого массива, меньших данного элемента	3) для каждого элемента массива а находит сумму элементов этого массива, меньших данного и стоящих правее него	4) находит сумму элементов массива, являющихся локальными максимумами	5) нет правильного варианта ответа	6) для каждого элемента массива а находит произве-дение элементов этого массива, меньших данного и стоящих левее него	7) для каждого элемента массива а находит сумму элементов этого массива, больших данного элемента	8) находит сумму элементов массива, не являющихся локальными максимумами	9) находит сумму элементов массива, являющихся локальными минимумами
Какую задачу решает программа? alf = "ABCDEFGHI" s = InputBox("Vvedi stroku"): n = Len(s) If n > 9 Then: MsgBox "Error": Exit Sub snew = Space(n) For i = 1 To Len(s) If Asc(Mid(s, i, 1)) > 57 Or _ Asc(Mid(s, i, 1)) < 49 Then MsgBox "Error input": Exit Sub End If: Next For i = 1 To n Mid(s, i, 1) = Mid(alf, CInt(Mid(s, i, 1)), 1) Next MsgBox s
1) кодирует заданную строку, не состоящую из цифр, буквами алфавита "ABCDEFGHI", стоящих на тех же позициях	2) кодирует заданную строку, состоящую из букв, буквами алфавита "ABCDEFGHI", стоящих на тех же позициях	3) нет правильного варианта ответа	4) кодирует заданную строку, состоящую из букв, цифрами, соответствующими кодировке букв алфавита "ABCDEFGHI" в Windows	5) кодирует заданную строку, состоящую из цифр, буквами алфавита "ABCDEFGHI", позиции которых соответствуют цифрам строки	6) кодирует заданную строку, состоящую из цифр, буквами алфавита "ABCDEFGHI", стоящих на тех же позициях	7) кодирует заданную строку, состоящую из цифр, буквами алфавита "ABCDEFGHI", позиции которых соответствуют цифрам строки в обратном порядке	8) кодирует заданную строку, состоящую из букв, буквами алфавита "ABCDEFGHI", стоящих на тех же позициях, но в обратном порядке	9) кодирует заданную строку, не состоящую из цифр, буквами алфавита "АБВГДЕЁЖЗ", стоящих на тех же позициях

Список использованной и рекомендуемой литературы

1.  Абрамян по программированию на языке Паскаль.–

Ростов-н/Д, 2004.

2.  Гарнаев VBA. – СПб.: BHV-Петербург, Санкт-Петербург, 2006.

3.  , Сенокосов : Учебник для 8-9 кл. –– М.: Просвещение, 1995.

4.  и др. Информатика. 10-11 кл. – М.: Просвещение, 2002.

5.  Информатика: Задачник-практикум в 2т. / Под ред. , . – М., 2001.

6.  , Семенов и упражнения по программированию.– Ростов-н/Д, 1996.

7.  Угринович и информационные технологии. 10-11 кл. – М.: Бином, 2003.