Главная » Просмотр файлов » Иванова Г.С., Ничушкина Т.Н. - Разработка алгоритмов простейших программ

Иванова Г.С., Ничушкина Т.Н. - Разработка алгоритмов простейших программ (1075619), страница 5

Файл №1075619 Иванова Г.С., Ничушкина Т.Н. - Разработка алгоритмов простейших программ (Иванова Г.С., Ничушкина Т.Н. - Разработка алгоритмов простейших программ) 5 страницаИванова Г.С., Ничушкина Т.Н. - Разработка алгоритмов простейших программ (1075619) страница 52017-12-28СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Для этого параметр цикла обхода необходимо менять на 2 единицы. После обнаружения требуемого элемента следует обеспечить сдвиг всехоставшихся элементов, при этом все четные элементы окажутся на нечетных местах и для правильного добавления необходимо перейти через три элемента, а нечерез два. Необходимо также посчитать количество добавленных элементов, чтобы в конце распечатать весь массив, и конечно следует предусмотреть свободноеместо в массиве, куда можно добавлять элементы.

Окончательный вариант алгоритма представлен на рисунке 3.12.НачалоВводn, А(n)k:=2 n1:=0i:=1,n div 2данетдаA[k] > 0нетj:=n,k+1даA[j+1]:=A[j]A[k+1]:=0n1:=n1+1k:=k+2k:=k+3ВыводA(n+n1)КонецРисунок 3.12 – Схема алгоритма добавления элементов в массив31Одновременная обработка нескольких массивов или подмассивовК этому типу относятся задачи по слиянию массивов, переписи элементоводного массива, отвечающих определенному условию или имеющих некоторыйпризнак, в другой, формирование нового массива из элементов исходного, преобразованных по некоторой формуле или подчиняющиеся определенному закону.Особенностью задач этого класса является то, что у каждого массива свой индекс,свой закон и диапазон его изменения. При программировании задач этого классаможно использовать как счетные, так и циклы с пред или пост условием, причемвыбор зависит от того каков закон изменения индексов и как легче организоватьих изменение.Пример 3.9. Даны два массива, отсортированные по возрастанию.

Объединить их в третий массив, сохраняя сортировку.В алгоритме (см. рисунок 3.13) для каждого массива используется свой индекс и своя граница индекса.3.1.5НачалоВвод n,m,А(n),B(m)i:=1 j:=1k:=1iÖn&jÖmдаданетA[i] > B[j] нетC[k]:=A[i]C[k]:=B[j]i := i+1j := j+1k :=k+1нетi>nдаi:=i,nдаj:=j,mдаC[k]:=A[i]C[k]:=B[j]k:=k+1k:=k+1ВыводC(k-1)КонецРисунок 3.13 – Схема алгоритма слияния сортированных массивов32Сначала мы сравниваем элементы массивов и пишем в результирующиймассив минимальный элемент из исходных массивов, а затем, когда один из массивов заканчивается – переписываем в массив С оставшиеся элементы второгомассива.3.1.6 Поиск в массиве единственного элемента, отвечающего некоторомуусловиюПримерами подобного рода задач могут служить поиск первого отрицательного, первого положительного и любого первого элемента, отвечающего некоторому условию, поиск первого или единственного элемента, равного некоторомуконкретному значению.

Особенность задач этого класса в том, что нет необходимости просматривать весь массив. Просмотр нужно закончить сразу, как толькотребуемый элемент будет найден. При этом может производиться как поэлементный просмотр, так и выборочная обработка массива. Однако, в худшем случае,для поиска элемента требуется просмотреть весь массив. Такой тип поиска называется линейным. Если массив не очень большой, затраты времени линейного поиска не столь заметны. Но при солидных объемах информации время поиска становится серьезным показателем.

Поэтому существуют методы, позволяющиеуменьшить время поиска: поиск с барьером и двоичный поиск. Чаще всего припрограммировании поисковых задач используются циклы с пред или пост условием, в которых условие выхода формируется из двух условий. Одно условие - покаэлемент не найден, а второе - пока есть элементы массива. После выхода из циклаосуществляется проверка, по какому из условий произошел выход.Рассмотрим следующие примеры.Пример 3.10. Задан целочисленный массив из n элементов.

Присвоить переменной k значение true, если в массиве существуют два одинаковых элемента,стоящих рядом, и false в противном случае.Эту задачу можно решить, например, если последовательно сравнить каждый элемент массива с последующим. Так как рассматриваются все элементы, тоодно условие – это достижение конца массива, а другое – обнаружение двух одинаковых соседних элементов.

Схему алгоритма для решения этой задачи см. нарисунке 3.14.33НачалоВводn, А(n)i:=1i Ö n-1 & нетA[i] ≠A[i+1]даi :=i+1нетiÖnk:=falseдаk:=trueВыводkКонецРисунок 3.14 – Схема алгоритма поиска пары одинаковых элементов в массивеПример 3.11. Необходимо определить среди элементов, стоящих на четныхместах первый отрицательный элемент.НачалоВводn, А(n)i:=2iÖn&A[i] > 0данетi :=i+2нетiÖnдаВыводA[i]Вывод‘Нет отр. эл.’КонецРисунок 3.15 – Схема алгоритма поиска в массиве первого отрицательного элемента3.2Приемы обработки матрицДвумерными называются массивы, имеющие два типа индексов.

По аналогии с математикой, иногда такие массивы называют матрицами. Для простотыизложения в дальнейшем будем придерживаться именно этой терминологии.34Рассмотрим наиболее распространенные приемы программирования обработки матриц. Следует отметить, что программирование всех классов задач дляматриц имеет свою специфику, основанную на том, что матрица, фактически, является массивом одномерных массивов. Это значит, что в каждом классе имеетсягораздо больше различных вариантов решений, да и самих задач тоже.

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

Однако, возможно появление и некоторых новых приемов, связанных со спецификой матриц.Рассмотрим некоторые типовые алгоритмы задач первого класса.Пример 3.12. Задана квадратная целочисленная матрица размера nn. Найтинаибольший элемент матрицы и количество таких элементов.Для решения этой задачи нужно организовать цикл для перебора всех элементов матрицы. Так как матрица является двумерным массивом, то потребуетсядва цикла (один для перебора строк, второй – столбцов). В остальном, алгоритмрешения этой задачи (см. рисунок 3.16) схож с алгоритмом нахождения максимального элемента одномерного массива.НачалоВводn,m,А(n,m)max:=A[1,1]k:=1i:=1,nj:=1,mA[i,j]>maxнетA[i,j]=maxдаданетmax:=A[i,j]k:=1k:=k+1Выводmax,kКонецРисунок 3.16 – Схема алгоритма поиска максимальных элементов матрицы35Пример 3.13.

Задана целочисленная матрица A(m,n). Вычислить сумму каждой стоки и результат записать в массив B(n).Для вычисления суммы элементов некоторой строки с номером i необходимо организовать цикл для перебора всех элементов данной строки. Поэтому параметром этого цикла следует выбрать номер столбца j. Перед циклом с параметромj необходимо задать начальное значение суммы S=0. После окончания цикла результат присваивается соответствующему элементу массива b. Для обеспеченияобхода всех строк матрицы параметром внешнего цикла следует выбрать номерстроки i (см. рисунок 3.17).НачалоВводn,m,А(n,m)i:=1,nS:=0j:=1,mS:=S+A[i,j]B[i]:=SВыводB(n)КонецРисунок 3.17 – Схема алгоритма поиска максимальных элементов матрицы3.2.2 Изменение порядка следования элементов без изменения размеров исходной матрицы.В качестве примеров задач данного типа для матриц рассмотрим задачу перемещения элементов.Пример 3.14. Дана действительная квадратная матрица порядка 2n.Получить новую матрицу, переставляя ее блоки размера nn в соответствии с рисунком.Для решения этой задачи нужно определить правило, по которому будутпреобразовываться индексы матрицы.

Будем считать, что после преобразованияполучается новая квадратная матрица размерности 2n. Тогда внимательно изучивсоответствие между элементами матрицы A и матрицы B, получаем следующийзакон преобразования:36 A (i A (iB (i , j )   A (i A (i n , j  n ),есл иi  n , j  n; n , j  n ),есл иi  n , j  n; n , j  n ),есл иi  n , j  n; n , j  n ),есл иi  n , j  n.Схема алгоритма решения представлена на рисунке 3.18.НачалоВводn,А(2n,2n)i:=1,2nj:=1,2nдадаB[i,j]:=A[i+n,j+njÖnнетiÖnнетдаB[i,j]:=A[i+n,j-n]B[i,j]:=A[i-n,j+n]jÖnнетB[i,j]:=A[i-n,j-n]ВыводВ(2n,2n)КонецРисунок 3.18 – Схема алгоритма перестановки элементов матрицыПри решении задач с матрицами прочих типов также используются приемы, применяемые при обработке одномерных массивов, поэтому отдельно они внастоящем пособии рассматриваться не будут.Литература1.

Г.С. Иванова. Программирование. Учебник для ВУЗов. – М.: Кнорус,2013..

Характеристики

Список файлов книги

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6513
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее