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

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

3.8. Алгоритмы, реализуемые
 с помощью циклов с предусловием

С помощью циклов с предусловием можно запрограммировать любые повторяющиеся фрагменты алгоритмов. Но на практике цикл этого типа чаще всего используют в двух следующих случаях:

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

Пример 3.19. Определить, является ли заданная последовательность различных чисел a1, a2, ..., an монотонно убывающей.

Пусть переменная Otvet принимает значение, равное 1, если последовательность является монотонно убывающей, и 0 - в противном случае.

Дано: n - размер массива; а[n] - числовой вещественный массив.

Найти Otvet = 1, если последовательность монотонно убывает; Otvet = 0, в противном случае.

Словесное описание алгоритма.

Присвоим переменной Otvet начальное значение, равное 1. В цикле последовательно сравниваем значения двух соседних элементов. Выход из цикла возможен в двух случаях:

  • просмотрены все элементы заданной последовательности. Это означает, что условие а[i] < а[i+1] никогда не выполнялось и последовательность является монотонно убывающей. Тогда Otvet = 1.
  • условие а[i] < а[i+1] выполнилось для пары соседних элементов, тогда Otvet = 0. Цикл прерывается. Следовательно, последовательность не является монотонно убывающей.

Приведем фрагмент блок-схемы и фрагмент алгоритма.

i = 1

Otvet = 1

пока (I <= n) и (Otvet = 1) повторять

нц

   Если(a[i] < a[i+1]) то

         Otvet = 0

   Иначе  i = i+1

   Все если

кц

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

№ теста

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

Данные

Результат

N

Массив А

Otvet

1

Является

3

(3, 2, 1)

1

2

Не является

3

(2, 3, 1)

0

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

№ теста

i

Otvet

(i <= n) и (Otvet = 1)

A[i] < A[i+1]

1

1

1

«Да»

 

2

«Да»

 

3

«Нет»

 

2

1

1

«Да»

«Да»

0

«Нет»

 

Пример 3.20. Вставить заданное число m в одномерный упорядоченный по возрастанию массив A[n] с сохранением упорядоченности.

Дано: n - размер массива; A[n] - числовой упорядоченный вещественный массив; число, равное m.

Найти новый упорядоченный массив A размера n + 1.

Словесное описание алгоритма.

Начинам просмотр массива с последнего элемента. Пока не просмотрены все элементы массива, ищем место нового элемента в упорядоченной последовательности, сдвигая элементы массива вправо на одну позицию. Пока не просмотрен последний элемент (i >= 1) и не найдено место нового элемента
(a[i] > m) будем переходить к следующему элементу (i = i - 1). Таким образом, мы закончим просмотр массива в одном из двух случаев: 1) найдено место нового элемента и новый элемент вставляется на это место; 2) весь массив просмотрен. Место нового элемента не найдено. Следовательно, этот элемент нужно поставить в начало массива.

i = n

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

пока (i >=1) и (a[i]> m) повторять

нц

    a[i+1] = a[i]

    I = i-1

кц

Включение числа m в последовательность

a[i+1] = m

 

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

Номер теста

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

Данные

Результат

m

Массив А

1

m ? A[i]

0

A = (1, 3, 5)

A = (0, 1, 3, 5)

2

A[i] < m < A[n]

4

A = (1, 3, 5)

A = (1, 3, 4, 5)

3

m >A[i]

6

A = (1, 3, 5)

A = (1, 3, 5, 6)

Посмотрим, как исполняется алгоритм.

№ теста

i

(i >= 1) и (A[i] > m)

Массив А

1

 

 

(1, 3, 5)

3

Да

(1, 3, 5, 5)

2

Да

(1, 3, 3, 5)

1

Да

(1, 1, 3, 5)

 

Нет

(0, 1, 3, 5)

2

 

 

(1, 3, 5)

3

Да

(1, 3, 5, 5)

2

Нет

(1, 3, 4, 5)

3

 

 

(1, 3, 5)

3

Нет

(1, 3, 5, 6)

Пример 3.21. Определить, если в  одномерном массиве отрицательный элемент.

Пусть переменная Otvet = 1, если в массиве есть отрицательный элемент, и Otvet = 0 - в противном случае.

Дано: n - размер массива; A[n] - числовой вещественный массив.

Найти Otvet = 1, если отрицательный элемент есть; Otvet = 0, в противном случае.

Словесное описание алгоритма.

Начинаем просматривать массив с первого элемента (i = 1). Пока не просмотрен последний элемент (i < n) и не найден отрицательный элемент (a[i] >= 0) будем переходить к следующему элементу (i = i + 1). Таким образом, мы закончим просмотр массива в одном из двух случаев: 1) просмотрели все элементы и не нашли отрицательного, тогда i > n, а Otvet = 0; 2) нашли нужный элемент, при этом i < n и Otvet = 1.

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

№ теста

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

Данные

Результат

N

Массив А

Otvet

1

Есть

3

(3, -2, 1)

1

2

Нет

3

(2, 3, 1)

0

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

№ теста

i

Otvet

(i < n) и (Otvet = 0)

а[i] < 0

1

1

0

Да

Нет

2

1

Да

Да

2

1

0

Да

Нет

2

0

Да

Нет

3

0

Да

Нет

4

0

Нет

 

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

1. Даны целые числа а1, а2,... Известно, что а1 > 0 и что среди а2, а3,... есть хотя бы одно отрицательное число. Пусть а1, ..., an - члены данной последовательности, предшествующие первому отрицательному члену (n заранее неизвестно). Получите:

а) max (a1,...,an);

б) min(a1 + a2, a2 + a3, ..., a n-1 + an);

в) количество нечетных чисел среди a1,..., an.

2. Найдите номер последнего отрицательного элемента массива.

3. Найдите номер первого положительного члена произвольной последовательности.

4. Найдите номер последнего нечетного члена произвольной последовательности.

5. Даны натуральное число n, действительные числа a1,..., an. В последовательности  определите число соседств: а) двух положительных чисел; b) двух чисел одного знака, причем модуль первого числа должен быть больше модуля второго числа.

6. Даны целые числа с1,..., cn. Определите, имеются ли в этой последовательности два идущих подряд нулевых члена.

7. Является ли заданная последовательность целых чисел знакопеременной?



 

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

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

Комментарии

Интересное




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

Партнёры