Массивы. Одномерные массивы

Методические указания к решению задач контрольной работы

Пример 2.1.Постройте таблицу истинности для логического выражения

F = (A\/B) /\С

Решение.

1. В данной функции три логические переменные – А, В, С

2. количество строк таблицы = 2³ =8

3. В формуле 3 логические операции.

4. Расставляем порядок действий

1) А\/ В; 2) С;3) (AVB)/\С .

5. количество столбцов таблицы = 3 + 3 = 6

6.

А	В	С	A\/B	С	(A\/B) /\С

Пример 3.1

Решение.

Решение.

От пункта А есть прямая дорога в пункт В составляющая 7, от пункта В проложен маршрут в город С протяженностью 8, из С можно добраться в Е преодолев всего 15, таким образом длина пути равна 30.

 

От пункта А есть прямая дорога в пункт С составляющая 11, от пункта С проложен маршрут в город D протяженностью 6, из D можно добраться в Е преодолев всего 3, таким образом длина кратчайшего пути равна 20.

Ответ. 20

 

Задание 4. В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу.

Для обозначения логической операции «ИЛИ» в запросе используется символ «|», а для логической операции «И» - «&».

 

А	Пушкин
Б	Лермонтов
В	Пушкин |Лермонтов

 

Решение.

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Запрос	Найдено страниц (в тысячах)
Пушкин
Лермонтов
Пушкин |Лермонтов

Какое количество страниц (в тысячах) будет найдено по запросу

Пушкин & Лермонтов?

 

Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Решение: Через Ответ(Z) будем обозначать множество страниц, найденных по запросу Z, а через N(Z) – размер множества Ответ(Z), то есть количество страниц, найденных по запросу Z. В этих обозначениях множество Ответ(X&Y) - это пересечение множеств Ответ(X) и Ответ(Y), а множество Ответ (X | Y) – объединение Ответ(X) и Ответ(Y).

По запросу Пушкин |Лермонтов было найдено 4500 страниц. Среди них были страницы, содержавшие либо оба этих слова, либо только одно из них. Если сложить количество страниц, найденных по запросу Пушкин и количество страниц, найденных по запросу Лермонтов, то страницы, найденные по запросу Пушкин & Лермонтов будут учтены дважды. Поэтому верна формула:

N(Пушкин|Лермонтов) = N(Пушкин) + N(Лермонтов) –N(Пушкин & Лермонтов)

В соответствии с этой формулой и условием задачи получаем:

4500 = 3500+2000- N(Пушкин & Лермонтов)

N(Пушкин & Лермонтов) = 3500+2000-4500 = 1000

Ответ:1000

Замечание. Приведенные рассуждения отражают следующий простой факт из теории множеств. Применительно к нашей задаче его можно записать так. Для любых запросов X и Y выполнено:

N(X | Y) = N(X)+N(Y) – N(X&Y)

Задание 5. За­пи­ши­те зна­че­ние пе­ре­мен­ной k, по­лу­чен­ное в ре­зуль­та­те ра­бо­ты сле­ду­ю­щей про­грам­мы. Текст про­грам­мы при­ведён на трёх язы­ках про­грам­ми­ро­ва­ния.

Ал­го­рит­ми­че­ский язык	Бей­сик	Пас­каль
алг нач цел k, i k := 4 нц для i от 1 до 3 k := i + 2*k кц вывод k кон	DIM i, k AS INTEGER k = 4 FOR i = 1 TO 3 k = i + 2*k NEXT i PRINT k	Var k, i: integer; Begin k := 4; For i := 1 to 3 do k := i + 2*k; Writeln(k); End.

Решение.

Цикл «for i := 1 to 3 do» вы­пол­ня­ет­ся три раза. Каж­дый раз пе­ре­мен­ной k при­сва­и­ва­ет­ся зна­че­ние i + 2*k. Найдём зна­че­ния k после каж­до­го шага, учи­ты­вая, что из­на­чаль­но k = 4: 9; 20; 43.

Ответ: 43

 

 

Массивы. Одномерные массивы.

При работе с большим числом данных одного типа очень удобно использовать массивы. Массив, это разновидность переменной. Он дает возможность хранить сколько угодно значений под одним и тем же именем. К каждому конкретному значению массива, необходимо обращаться через числовой индекс.

Массив - это набор переменных, имеющих одинаковое имя (идентификатор), но различающихся порядковыми номерами (индексами).

Обычно массивы применяют для группировки переменных, имеющих много общих свойств. Например, если в классе 30 учеников, то имя каждого ученика можно было бы сохранить в отдельной строковой переменной: name1, name2, ... Но вводить 30 новых переменных крайне неудобно. Можно сделать проще: объявить один массив name(), имеющий 30 элементов. В скобках проставляется индекс, когда надо обратиться к какому-то конкретному элементу.

Отсчет элементов массива во многих языках начинается с нуля. Поэтому имя первого (по классному журналу) ученика будет храниться в переменной name(0), второго - в переменной name(1), а последнего (тридцатого) - в переменной name(29).

Для того чтобы использовать массив его надо сначала объявить в программе. Для этого используют оператор DIM. По умолчанию (если нет оператора DIM в программе) считается заданным массив из 10 элементов.

Пример:

DIM a(100) AS INTEGER
Это массив из ста элементов, каждый из которых может быть целым числом.
DIM name(30) AS STRING
DIM mas(20)
Это массив из 20 элементов, тип переменных явно не указан.

DIM mas1(10) AS INTEGER

Mas1

 

 

Обращение к элементам массива:

a(24)
name(5)
mas(2)
mas(3)

Основное преимущество массивов перед обычным набором разноименных переменных состоит в том. что индекс нужного элемента можно записывать не числом, а переменной или даже вычислять по выражению. Это дает возможность использовать массивы внутри циклов - собственно для этого они и были придуманы. Если в программе есть массив, то, скорее всего, в ней же вы найдете и цикл.

Можно также объявить массив и таким образом:

DIM mas2(1 TO 10) AS INTEGER

Mas2

или даже так:

DIM a2(5 TO 10) AS INTEGER

В данном случае индексация элементов массива начинается не с нуля, а с нужного вам индекса (в примере массив mаs2 имеет индексы от 1 до 10, массив а2 - от 5 до 10).

Допустим в классе 30 учеников. Предположим, что для хранения их оценок по предмету создан массив DIM mark(30) AS INTEGER. Следующая программа, поставит каждому учащемуся случайную оценку от 3 до 5. Конечно, так расставлять оценки нельзя, но этот пример показывает, что программа не становиться сложнее, если в классе не 30 учеников, а сто пятьдесят миллионов. Сочетание массивов и циклов позволяет достичь удивительной простоты.

REM Выставление оценок :)
DIM mark(30) AS INTEGER
FOR I=0 TO 29
mark(I)=3+INT(RND*3)
NEXT
END

 

Mark

...

...

Для создания случайных чисел в языке Basic служит стандартная функция RND. Она создает случайное число в диапазоне от 0 до 1. Умножив его на 3, мы получаем случайное число от 0 до 3. А взяв от него целую часть (с помощью функции INT), получим целое случайное число в диапазоне от 0 до 2. Прибавив к нему число 3, мы поучаем случайную оценку, которая не меньше 3 и не больше 5.

Пример: Составить программу заполнения массива из 15 элементов случайными числами в диапазоне от 1 до 10. Предусмотреть вывод массива на экран.

REM Заполнение и вывод массива
DIM mas(15) AS INTEGER
FOR I=0 TO 14
mas(I)=1+INT(RND*10)
NEXT
CLS
PRINT "Вывод массива"
FOR I=0 TO 14
PRINT mas(I);
NEXT
END

CLS - очистка экрана. Точка с запятой (;) в операторе PRINT позволяет выводить элементы массива в строку.

Тоже самое задание, но отличающиеся объявлением массива:

REM Заполнение и вывод массива
DIM mas(1 TO 15) AS INTEGER
FOR I=1 TO 15
mas(I)=1+INT(RND*10)
NEXT
CLS
PRINT "Вывод массива"
FOR I=1 TO 15
PRINT mas(I);
NEXT
END

Всё очень просто. Какой из вариантов использовать решать вам.

Пример: Вывести количество отрицательных элементов массива.

REM Вывести количество отрицательных элементов
INPUT "Введите число элементов массива", n
DIM mas(n) AS INTEGER
FOR I=0 TO n-1
INPUT "Введите элемент массива", mas(I)
NEXT
CLS
PRINT "Вывод массива"
FOR I=0 TO n-1
PRINT mas(I);
NEXT
FOR I=0 TO n-1
IF mas(I)<0 THEN k=k+1
NEXT
PRINT
PRINT "Число отрицательных элементов: ",k
END

Подсчет количества отрицательных элементов массива происходит в цикле:
FOR I=0 TO n-1
IF mas(I)<0 THEN k=k+1
NEXT

Пример: Составить программу для вычисления наибольшего элемента массива и его номера.

REM вычисления наибольшего элемента массива и его номера
INPUT "Введите число элементов массива", n
DIM mas(n) AS INTEGER
FOR I=0 TO n-1
INPUT "Введите элемент массива", mas(I)
NEXT
CLS
PRINT "Вывод массива"
FOR I=0 TO n-1
PRINT mas(I);
NEXT
max=mas(0)
nomer=1
FOR I=0 TO n-1
IF mas(I)>max THEN
max=mas(I)
nomer=I+1
END IF
NEXT
PRINT
PRINT "Максимальный элемент: ", max, " с номером ", nomer
END

Задание выполняется в строчках:

max=mas(0)
nomer=1
FOR I=0 TO n-1
IF mas(I)>max THEN
max=mas(I)
nomer=I+1
END IF
NEXT

Вначале примем за наибольший элемент - первый элемент массива mas(0). Затем перебирая все элементы по очереди сравниваем их со значение max и если mas(I)>max, то принимаем этот элемент за наибольший.

Иногда для ввода данных удобно использовать операторы DATA и READ.
DATA указывает значения для чтения последующими операторами READ. READ считывает эти значения и присваивает их переменным. RESTORE позволяет READ заново считать значения в указанном операторе DATA.