4294

Освоение приемов объявления, обращения и использования массивов при решении задач

Лабораторная работа

Информатика, кибернетика и программирование

Цель работы: освоение приемов объявления, обращения и использования массивов при решении задач. Типовые алгоритмы обработки одномерных массивов Рассмотрим некоторые типовые алгоритмы обработки массивов. Положим, что в декларативной части программы о...

Русский

2012-11-15

64.5 KB

16 чел.

Цель работы: освоение приемов объявления, обращения и использования массивов при решении задач.

Типовые алгоритмы обработки одномерных массивов

Рассмотрим некоторые типовые алгоритмы обработки массивов. Положим, что в декларативной части программы описаны следующие переменные: одномерные массивы А и В, переменные целого типа n, i и j и вспомогательные переменные типа элементов массива.  

1. Суммирование элементов массива

Реализация:

s:=0;    

for i:=1 to n  do

             s:=s+a[i];

writeln('Сумма  элементов=  ', s);

2. Суммирование элементов массива по ключу

Реализация:

s:=0;    

writeln(‘ Введите ключ’);

readln( key);

for i:=1 to n  do

             if a[i]=key then s:=s+a[i];

writeln('Сумма  элементов= ', s);

3. Подсчет элементов массива по ключу

Реализация:

kol:=0;    

writeln(‘ Введите ключ’);

readln( key);

for i:=1 to n  do

             if a[i]=key then kol:=kol+1;

writeln('Количество  элементов= ', kol);

4. Поиск минимального (максимального) элемента

Данный алгоритм заключается в следующем: вначале запоминаем номер первого элемента массива, принимая его за минимальный (максимальный) элемент. Далее, начиная со второго, все элементы сравниваются с предполагаемым минимумом (максимумом) и если какой-нибудь из них меньше (больше) предполагаемого минимума (максимума), то запоминается номер этого элемента. Эти действия повторяются до тех пор, пока не закончатся элементы массива. Ниже написан фрагмент программы для поиска минимального элемента. Для реализации алгоритма введем еще один объект программы n_min, переменную, в которой будет храниться номер минимального элемента.

Реализация:

writeln(‘ Введите количество элементов массива’);

readln(n);

write(' Введите элементы массива’);

for i:=1 to n do readln(a[i]);

{ Пусть первый элемент минимальный }

 n_min:=1;

for i:=2 to n do

         if a[i]<a[n_min] then  n_min:=i;

writeln('Минимальный элемент массива:  ', a[n_min]);

writeln('Номер элемента: ', n_min);

5. Формирование нового массива из элементов исходного массива

Для формирования нового массива из элементов исходного необходимо, прежде всего, подготовить переменную целого типа, которая будет, является индексом элементов для нового массива, и увеличивать значение номера элемента после того, как очередной элемент помещен в новый массив. Рассмотрим два алгоритма: формирование нового массива из элементов исходного массива, удовлетворяющих заданному условию (< key); слияние двух упорядоченных массивов в один упорядоченный.

Реализация:

{Формирование нового массива по ключу}

writeln(‘ Введите ключ’);

readln( key);

j:=0; {индекс нового массива}

For i:=1 to n do

                   If a[i] < key then

                                           begin

                                             j:=j+1;

                                             b[j]:=a[i]

                                            end;

{Печать сформированного массива}

for i:=1 to j do writeln(‘b[‘, i, ‘]= ’, b[i]);

6. Поиск элемента в массиве по ключу

Df: Процесс нахождения элемента в последовательности по значению одного или более чем одного поля называется поиском в последовательности. Линейный поиск заключается в последовательном просмотре всех элементов массива до тех пор пока либо будет найден искомый элемент, либо пока не закончатся элементы массива. Для реализации алгоритма заведем переменную логического типа flag, с помощью которой можно будет выйти из цикла в случае нахождения искомого элемента.

Реализация:

write(' Введите образец для поиска');

readln(key);

flag:=FALSE; {совпадений нет}

i:=1;

repeat

       if  a[i] = key   then flag:=TRUE     {совпадение с образцом}

                              else i:=i+1;         {переход к следующему элементу}

until (i>n) or flag; {окончание цикла, если произошло совпадение с образцом или проверены все элементы массива}

if flag   then writeln(' Совпадение с элементом номер которого = ', i)       

           else writeln(' Совпадений с образцом нет');

7. Инвертирование массива

Суть алгоритма, состоит в перестановке элементов массива в обратном порядке, т.е. меняет местами первый с последним элементом, второй с предпоследним элементом массива и т.д. Число перестановок  равно n div 2, т.к. если менять местами элементы n раз, то все элементы массива встанут на свои места.

Реализация:

   for i:=1 to n div 2  do

             begin

             { Обменяем i-й и (n-i+1)-й элементы}

                 temp:=a[i];

                 a[i]:=a[n-i+1];

                 a[n-i+1]:=temp

              end;

8. Циклический сдвиг элементов массива  вправо (влево) на М позиций

При решении задач, в которых необходимо вставить элемент в массив используется циклический сдвиг элементов. В этом алгоритме сначала запоминаем последний элемент, если сдвиг будем делать вправо (первый элемент, если сдвиг влево). Затем сдвигаем элементы, т.е. на n место ставим n-1 элемент, на n-1 ставим n-2,  и т.д. на 2-е место ставим 1-й элемент, тем самым как бы освободив первую позицию. Наконец, на первое место записываем последний элемент, который хранится во вспомогательной переменной.  Подобные действия повторяются m раз, т.е. число раз, на которое необходимо осуществить сдвиг. Мы рассмотрели циклический сдвиг на m позиций вправо.

Реализация:

{Циклический сдвиг на m позиций вправо}

writeln(‘ Введите число сдвигов’);

readln( m);

for i:=1 to m do

              begin

              {Запоминаем последний элемент массива}

                temp:=a[n];

              {Сдвиг элементов массива на одну позицию вправо}

                for j:= n downto 2 do  a[j]:=a[j-1];

                a[1]:= temp

               end;

{Печать измененного массива}

for i:=1 to n do writeln(‘a[‘, i, ‘]= ’, a[i]);

9. Сортировка массива

Df: Под сортировкой будем понимать процесс перестановки объектов заданного массива в определенном порядке. Сортировка выбором. Этот метод основан на поиске элемента. Выбирается элемент с наименьшим ключом и меняется местами с первым элементом. Затем выбирается элемент с наименьшим ключом среди оставшихся n-1 элементов и меняется местами со вторым и т.д. Алгоритм  сортировки основан на типовом алгоритме поиска минимума (максимума).

Реализация:

{Сортировка массива по возрастанию методом выбора}

for i:=1 to n-1 do

    begin

        { Поиск минимального элемента в части массива от a[i] до a[n]}

         n_min:=i;

         for j:=i+1 to n do

              if a[j]<a[n_min] then n_min:=j;

         { Поменяем местами a[n_min] и a[i] }

         temp:=a[i];

         a[i]:=a[n_min];

         a[n_min]:=temp

    end;

{Выведем отсортированный массив}

for i:=1 to n do write(a[i],'  ');

Задания для самостоятельного решения.

Вариант 1.

1. Одномерный массив А длиной N<=20 заполнить случайными числами из диапазона [–10..55]. Составить программу определения:

  •  первого максимального элемента массива;
    •  количество максимальных элементов в массиве;
    •  всех элементов, кратных 3-м или 5-и.

2. Дан одномерный массив. Переместить нулевые элементы массива в конец, сдвинув остальные элементы влево.

3. Имеются сведения о количестве проданных билетов в 17-ти вагонах поезда. Найти наименее загруженный вагон, учитывая, что количество мест в вагоне зависит от типа вагона: в мягком и купейном вагонах — по 36 мест, а в плацкартном — 46 мест.

Вариант 2. 

1. Одномерный массив А длиной N<=50 заполнить случайными числами из диапазона [–5..30]. Составить программу определения:

  •  последнего максимального элемента;
    •  на каких позициях находятся максимальные элементы;
    •  сколько элементов массива превосходят по модулю заданное число M?

2. Дан одномерный массив. Переместить нулевые элементы массива в начало, сдвинув остальные элементы вправо.

3. Даны сведения о двухстах абитуриентах: фамилии и оценки, полученные на трех вступительных экзаменах. Напечатать список будущих студентов при условии, что норма приема — 40 человек, а зачисляются абитуриенты, набравшие наибольшую сумму баллов.

Вариант 3.

1. Одномерный массив А длиной N<=30 заполнить случайными числами из диапазона [-10..60]. Составить программу определения:

  •  последнего минимального элемента;
    •  на каких позициях находятся минимальные элементы;
    •  есть ли в данном массиве два соседних положительных элемента? Найти номера первой пары.

2. Дан одномерный массив. Переместить минимальные элементы в начало, сдвинув остальные элементы вправо.

3. Известно количество денег у каждого из N учеников, а также стоимость 4 комплексных обедов в школьной столовой. Напечатать сколько каких обедов будет куплено и сколько учеников останутся голодными, если каждый ученик выбирает наиболее дорогой обед, который он может купить.

Вариант 4.

1. Одномерный массив А длиной N<=20 заполнить случайными числами из диапазона [–15..80]. Составить программу определения:

  •  первого минимального элемента массива;
    •  количества и суммы  минимальных элементов;
    •  есть ли в данном массиве два соседних отрицательных элемента? Найти номера последней пары.

2. Дан одномерный массив. Переместить максимальные элементы в конец, сдвинув остальные элементы влево.

3. Имеются сведения о 40-и регионах страны: название региона и информация об уровне безработицы в регионе. Определите три наиболее благополучных и три неблагополучных района.

Вариант 5.

1. Одномерный массив А длиной N<=20 заполнить случайными числами из диапазона [–15..-5]. Составить программу определения:

  •  суммы положительных элементов массива;
    •  количества четных элементов массива;
    •  минимального из элементов, значения которых лежат в диапазоне [y1..y2].

2. Дан одномерный массив. Переместить максимальные элементы в начало, сдвинув остальные элементы вправо.

3. Имеется информация о 100 предприятиях города в виде: название предприятия, число работающих, прибыль. Определить предприятие с максимальной прибылью с учетом количества работающих на нем людей.

Вариант 6.

1. Одномерный массив А длиной N<=50 заполнить случайными числами из диапазона [–15..20]. Составить программу определения:

  •  первого отрицательного элемента массива;
    •  суммы четных элементов массива.
    •  количества элементов, значения которых лежат в диапазоне [y1..y2].

2. Дан одномерный массив. Переместить минимальные элементы в конец, сдвинув остальные элементы влево.

3. Имеются сведения об обеспеченности жильем N работников предприятия: фамилия работника, количество человек в семье, количество кв. метров жилой площади. Также известно количество K новых квартир, которые получает предприятие. Требуется отпечатать список K работников, претендующих на новое жилье, полагая, что у всех работников разное количество кв. метров на человека.

Вариант 7.

1. Одномерный массив А длиной N<=40 заполнить случайными числами из диапазона [–25..10]. Составить программу определения:

  •  первого четного элемента массива;
    •  суммы элементов массива значения, которых лежат в диапазоне [y1..y2];
    •  количества элементов массива больших заданного значения M.

2. Дан одномерный массив. Переместить четные элементы в конец, сдвинув остальные элементы влево.

3. В конкурсе «Мисс Очаровашка» участвуют 100 девушек. Известен балл, набранный каждой девушкой в ходе первого тура конкурса. Определить десять девушек вышедших во второй тур конкурса.

Вариант 8.

1. Одномерный массив А длиной N<=25 заполнить случайными числами из диапазона [–18..10]. Составить программу определения:

  •  первого положительного элемента массива;
    •  максимального среди четных элементов массива;
    •  количества отрицательных элементов массива значения, которых лежат в диапазоне [y1..y2].
  1.  Дан одномерный массив. Переместить нечетные элементы в начало, сдвинув остальные элементы вправо.
  2.  Известно количество голосов, поданных за каждого из 10 кандидатов на пост мэра Челябинска. Выяснить, избран ли мэр, если для избрания требуется набрать более 50 % голосов “за” или какие два кандидата вошли во второй тур (если никто из кандидатов не набрал 50 % голосов).

Вариант 9.

1. Одномерный массив А длиной N<=55 заполнить случайными числами из диапазона [–30..30]. Составить программу:

  •  определить первый элемент массива кратный 5-и;
    •  найти среднее значение максимального и минимального элементов массива;
    •  заменить первые k элементов на противоположные по знаку.

2. Дан одномерный массив. Переместить положительные элементы в конец, сдвинув остальные элементы влево.

3. Известна балансовая стоимость 100 станков завода. Определить десять станков с максимальной   балансовой стоимостью, а также вычислить амортизационные отчисления завода, если за каждый станок они составляют 10% его стоимости.

Вариант 10.

1. Одномерный массив А длиной N<=40 заполнить случайными числами из диапазона [–20..50]. Составить программу:

  •  определить последний положительный элемент массива кратный 3-м;
    •  заменить максимальный по модулю отрицательный элемент нулем;
    •  найти все индексы отрицательных элементов массива.

2. Дан одномерный массив. Переместить отрицательные элементы в начало, сдвинув остальные элементы вправо.

3.  Руководство ведет каждый месяцам учет расходов фирмы. Получена информация за n месяцев. Расставить данные по расходам в порядке в их возрастания.

Отчет должен содержать:

  •  Математическую или логическую модель задачи.
  •  Функциональную структуру алгоритма.
  •  Программный код задачи.
  •  Тесты для проверки правильности работы программного кода.

Контрольные вопросы:

  1.  Дайте определение понятию массив.
  2.  Назовите и охарактеризуйте свойства массива.
  3.  Какие типы массивов существуют, и чем они отличаются друг от друга?
  4.  Что такое логическое и физическое представление массива?
  5.  Как осуществляется доступ к элементу одномерного массива?
  6.  Опишите одномерный массив, состоящий из 30 элементов целого типа.

7. Дан массив целых чисел {Xi}=1, 2, -9, 0, -34, 7. Чему будет равно значение k=_____________?

k:=0;

for i:=1 to n do

if (X[i]>0) then k:=k+1;

8. Если элементы массива D[1..7] равны соответственно 4, 0, 7, 5, 6, 2, 4 то значение выражения D[ D[1] ] + D[ D[3] ] равно ...

9. Определите, что будет результатом выполнения фрагмента программы:

k:=1;

for i:=1 to 10 do

if A[i]> A[k] then k:=i;

10. Определите, что будет результатом выполнения фрагмента программы:

s:=0;

for i:=1 to 10 do

if A[i]>s then s:=A[i];


 

А также другие работы, которые могут Вас заинтересовать

32389. Содержание, задачи, функции, методы, основные направления и этические принципы работы практического психолога в системе образования 13.8 KB
  Осуществление работы по направлениям личности. Методы работы: Индивидуальная форма работы для детей игра и рисунок. Групповая форма работы для детей ролевые игры и психодрама.
32390. Общие представления о мышлении 16.24 KB
  Физиологические основы мышления выявить и исследовать достаточно трудно это объяснятся той специфической ролью которую мышление играет в психологической деятельности человека. Следовательно для функционирования мышления необходимы отделы коры головного мозга отвечающие за познавательные процессы. Установлено также что особую значимую роль для процессов мышления играет лобная доля и речевые центры коры головного мозга. Функции мышления: Понимание решение проблемы и задачи целеобразование рефлексия деятельность человеческого...
32391. Особенности развития личности ребенка на различных возрастных этапах 14.83 KB
  Внутри этого вида деятельности формируется новая ведущая деятельность характерная для следующего этапа возрастного развития. ведущая деятельность способствует появлению характерных только для этого возраста качественных особенностей. Ведущая деятельность: непосредственно эмоциональное общение внутри и на фоне которой формируются ориентировочные и сенсомоторные манипулятивные действия т. Ведущая деятельность: предметноманипулятивная в процессе которой ребенок овладевает общественными выработанными способами действий с предметами в...
32392. Метод эксперимента 15.17 KB
  Отличительные признаки эксперимента: Исследователь не дожидается проявлений интересующих его психических свойств а сам создает условия чтобы вызвать их у испытуемых. В эксперименте обязателен строгий учет и регистрация условий протекания исследования. Эксперимент может быть повторен другими исследователями и в другое время что позволяет проверить результаты исследования.
32393. Психодиагностика как наука. История, предмет и методы психодиагностики. Классификация методов психодиагностического исследования 16.22 KB
  Задачи психодиагностики: Разработка теоретических принципов оценки и измерения индивидуальных психологических свойств человека. Этапы становления психодиагностики: Донаучный до начала 19 века Стихийное использование некоторых заданий для определения индивидуальных особенностей человека. Пифагор допускал в свою школу лишь тех кто проходил череду испытаний смех и походка считались отражением характера человека. Экспериментальная психология накопила огромное количество методик для исследования психических функций человека многие из...
32394. Представление о личности в отечественной и зарубежной психологии. Личность и индивидуальность 14.43 KB
  Личность и индивидуальность. Личность специфическое человеческое образование производится общественными отношениями в которых индивид вступает в своей деятельности. Личность понятие социальное возникает в результате культурного и социального развития есть своя позиция жизни к которой пришел в итоге большой сознательной работы; самостоятельность мысли; глубина и богатство связей с миром с другими людьми; разрыв этих связей самоизоляция опустошают. Личность как субъект межличностных социальных отношений и сознательной деятельности...
32395. Взаимоотношение детей со сверстниками на различных возрастных этапах 13.05 KB
  Положительные личностные качества становятся одним из мотивов выбора детьми друг друга для совместной деятельности и общения. Стремление к сверстникам жажда общения с ними делают группу сверстников чрезвычайно ценной и привлекательной. В подростковом и юношеском возрасте психология общения строится на основе противоречивого переплетения двух потребностей: обособления приватизации и принадлежности аффиляции. Специфика общения подростков преодоление коммуникативных трудностей застенчивость.
32396. История и характеристика тестов интеллекта 14.22 KB
  Общие признаки интеллектуальных тестов: Носят эмпирический характер отсутствует базисная теория интеллекта. Тесты интеллекта являются одними из наиболее распространенных в психодиагностике и применяются для выявления уровня развития отдельных психических функций комплексов или уровня развития интеллекта в целом: Тесты интеллекта направлены на установление уровня интеллектуального развития человека метрические шкалы БинеСимона интеллектуальные шкалы Векслера. Тесты специальных способностей предназначены для измерения уровня...
32397. Представление о личности в экзистенциально-гумманистической психологии 13.83 KB
  Исходит из уникальности конкретной жизни человека где каждый ответственен за свои действия Я есть мой выбор есть субъективная реальность. Субъективный опыт основной феномен в изучении и понимании человека который не может быть сведен к универсальным правилам. Рассматривается проблема человека которая рефлектирует и подтверждает себя в процессе обретения смыслов. В центр внимания ставятся и внещние силы обуславливающие поведение человека но его собственная индивидуальность которая себя не знает Хайдеггер проверяет Сарт или...