Глава 3. Алгоритмы, использующие одномерные массивы - 3.9. Использование вложенных циклов

E-mail Печать PDF
Рейтинг пользователей: / 10
ХудшийЛучший 
Индекс материала
Глава 3. Алгоритмы, использующие одномерные массивы
3.2 Задачи заполнения массива
3.3. Задачи анализа массива
3.4. Нахождение элементов, обладающих определенным свойством
3.5. Изменение значений некоторых элементов
3.6. Обмен значений элементов
3.7. Удаление и вставка элементов массива
3.8. Алгоритмы, реализуемые с помощью циклов с предусловием
3.9. Использование вложенных циклов
Все страницы

3.9. Использование вложенных циклов

Возможны случаи, когда внутри тела цикла необходимо повторить некоторую последовательность операторов, т.е. организовать внутренний цикл. Такая структура называется цикл в цикле или вложенные циклы. Глубина вложения циклов (количество вложенных друг в друга циклов) может быть различной.

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

Пример 3.22. Определить, имеется ли в заданном целочисленном массиве хотя бы одна пара совпадающих по значению чисел.

Алгоритм реализуется с использованием вложенных циклов пока.

Пока <условие 1> повторять

нц

кц

При выполнении цикла для каждого значения параметра внешнего цикла, параметр внутреннего цикла пробегает все значения.

Пусть переменная Flag = 1, если пара совпадающих чисел найдена и Flag = 0, если пара совпадающих чисел не найдена.

Во внешнем цикле берем очередное число (номер числа i меняется от 1 до
n - 1)и сравниваем его с оставшимися j числами (j изменяется от i + 1 до n).

Внутренний цикл может закончиться в двух случаях:

1) пара совпадающих чисел найдена (т.е. выполнилось условие a[i] = a[j]) и тогда Flag = 1. На этом просмотр массива заканчивается.

2) совпадающие числа не найдены, при этом Flag = 0.

Система тестов

№ теста

Проверяемый
случай

Данные

Результат

n

Массив А

Otvet

1

Имеется

4

(1, 3, 2, 3)

«Есть совпадающие числа»

2

Не имеется

3

(1, 2, 3)

«Нет совпадающих чисел»

Исполнение алгоритма

№ теста

i

Flag

(i?n-1) и (Flag=0)

j

(j ?n) и (Flag=0)

A[i] = A[j]

Otvet

1

1

0

Да

2

Да

Нет

 

3

Да

Нет

 

4

Да

Нет

 

5

Нет

 

 

2

1

Да

3

Да

Нет

 

4

Да

Да

 

 

Нет

 

 

3

Нет (кц)

 

 

 

«Есть»

2

1

0

Да

2

Да

Нет

 

3

Да

Нет

 

4

Нет

Нет

 

2

Да

3

Да

Нет

 

4

Нет

Нет

 

3

 

Нет (кц)

 

 

 

«Нет»

Пример 2.23. Упорядочить по возрастанию элементы заданного числового массива.

Мы воспользуемся простым алгоритмом: будем сравнивать попарно числа между собой и при необходимости менять их местами. Для реализации алгоритма нам необходим воженный цикл. Поскольку количество повторений циклов известно к началу их выполнения, то используем вложенный арифметический цикл «для». Схема такого цикла выглядит так:

 
 

Для  i от iнач  до iкон; выполнить

Это не самый лучший алгоритм сортировки, но эффективность алгоритма нас в данном случае не интересует. Наша цель - продемонстрировать структуру вложенных арифметических циклов.

Фрагмент блок-схемы алгоритма

Исполнение алгоритма

 

i

j

A[i] > A[j]

Массив А

 

1

2

Да

2, 5, 7, 1

 

 

3

Нет

 

 

 

4

Да

1, 5, 7, 2

 

2

3

Нет

 

 

 

4

Да

1, 2, 7, 5

 

3

4

Да

1, 2, 5, 7

 

 

 

 

 
 
 
 
 

Мы видим, что при выполнении вложенного цикла типа «для» внутренний цикл выполняется полностью для всех значений параметра внешнего цикла. Общее число повторений циклов будет равно ? (n - 1).

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

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

2. Заданный массив А сдвиньте циклически на m элементов вправо. Дополнительный массив не используйте. Например, при сдвиге массива А(1, 2, 3, 4, 5, 6, 7) вправо на 3 позиции получаем массив А(5, 6, 7, 1, 2, 3, 4).

3. В заполненном наполовину массиве продублируйте все элементы с сохранением порядка их следования. Например, из массива А(1, 2, 3,...) нужно получить массив А(1, 1, 2, 2, 3, 3,...).

4. Дан массив целых чисел. Найдите в этом массиве минимальный элемент m и максимальный элемент M. Получите в порядке возрастания все целые числа из интервала (m; M).

5. Даны две последовательности: А размером n и B размером m (m < n). В каждой из них члены различны. Верно ли, что все члены второй последовательности входят в первую последовательность?

6. В массиве целых чисел найдите сумму трех минимальных чисел массива.

7. Даны два упорядоченных массива А и В. Объедините их в один упорядоченный массив. Рассмотрите два случая: когда исходные массивы упорядочены одинаково и когда - по-разному. Размеры массивов не совпадают.

8. В одномерном массиве все отрицательные элементы поместите в начало массива, а все положительные - в конец с сохранением порядка их следования. Дополнительный массив использовать не разрешается.

9. Дан массив целых чисел. Определите, если в массиве простые числа. Если да, то выведите номера этих чисел.

10. Дана последовательность целых чисел. Найдите количество различных чисел в этой последовательности.

11. Вставьте последний элемент массива после первого отрицательного элемента этого же массива.

12. Дан одномерный массив. Найдите максимальный элемент среди отрицательных элементов одномерного массива. Вставьте новый элемент с произвольным значением после максимального элемента (или после всех максимальных элементов, если их несколько).

13. Замените все отрицательные элементы массива средним значением положительных элементов этого же массива.

14. Дан одномерный массив. Найдите максимальную сумму трех идущих подряд элементов массива.

15. В заданном массиве замените нулями все отрицательные элементы, непосредственно предшествующие его максимальному элементу.

16. Вставьте в заданный упорядоченный массив новое значение с сохранением его упорядоченности.

17. Дан произвольный массив целых чисел. Удалите из массива все одинаковые значения, оставив их первые вхождения. Например, из массива (1, -3, 5, 1, 5. 4, 4, 10) должен получиться массив (1, -3, 5, 4, 10).

 

да

 
 

 

Добавьтe Ваш комментарий

Ваше имя (псевдоним):
Ваш адрес почты:
Заголовок:
Комментарий:

Комментарии

Интересное




Похожие материалы

Партнёры