Задачи с разбором
Təhlili ilə verilmiş məsələlər
В первых 5-ти задачах мы будем задавать массив в самой программе. Для следующих задач будем разрабатывать по 2 программы: в одной массив задается в программе, а в другой вводится из файла и сам массив в программе создается динамически.
Примечание. Программы, в которых массив задается в самой программе (например a:array [0..n-1] of integer=(6,-5,1,4,2,7,-4,2,1,-7);) или массив вводится с клавиатуры, с практической точки зрения являются абсолютно бесполезны. А если массив должен состоять из 1000 или 10000 элементов. Что, мы их будем все писать в программе или вводить с клавиатуры? Представляете, вводим с клавиатуры и в 621 элементе ошибаемся и начинаем все заново! Но эти программы очень нужны для демонстрации и отработки самого алгоритма. А вот когда алгоритм понят – можно и приступить к написанию практически значимой программы – это вторые программы задач с номерами больше 5.
1.
| Дан массив. Найти сумму и произведение его элементов. | Решение | Həlli | 2.
| Определите, симметричны ли значения элементов массива? | Решение | Həlli | 3.
| Дан массив. Найти максимальный элемент. | Решение | Həlli | 4.
| Дан массив. Найти номер максимального элемента. | Решение | Həlli | 5.
| Дан массив. Поменять в нем местами максимальный элемент среди отрицательных с минимальным элементом среди положительных. | Решение | Həlli | 6.
| Дан массив. Написать программу упорядочения массива методом выбора. | Решение | Həlli | 7.
| Дан массив. Написать программу упорядочения массива методом обмена (пузырек). |
Решение |
Həlli | 8.
| Дан массив. Написать программу упорядочения массива методом просеивания. |
Решение |
Həlli | 9.
| Дан массив. Написать программу упорядочения массива пирамидальным методом. |
Решение |
Həlli | 10.
| В неупорядоченной последовательности найти количество различных элементов массива. |
Решение |
Həlli | 11.
| Требуется переставить элементы массива в обратном порядке. |
Решение |
Həlli | 12.
| Требуется циклически сдвинуть элементы массива на одну позицию вправо |
Решение |
Həlli | 13.
| Требуется циклически сдвинуть элементы массива на К позиций вправо с затратой 0(n) действий (n-длина массива). | Решение
|
Həlli | 14.
| Каждый элемент массива (кроме первого и последнего) заменить на полу сумму соседних элементов. | Решение
|
Həlli | 15.
| Требуется сгруппировать положительные элементы массива в его начале, а отрицательные — в конце с сохранением их порядка. | Решение
|
Həlli | 16.
| Введите с клавиатуры число х и удалите из массива все элементы, превосходящие х, а оставшиеся уплотните (т.е. сдвиньте к началу массива с сохранением их порядка). | Решение
|
Həlli | 17.
| Требуется вставить между каждыми двумя положительными элементами исходного массива их среднее арифметическое. | Решение
|
Həlli | 18.
| Пусть элементы массива не убывают. Требуется бинарным поиском (методом деления пополам) определить принадлежит ли массиву заданный элемент х. | Решение
|
Həlli | 19.
| Даны 2 массива, упорядоченные по возрастанию. Требуется написать программу слияния этих двух массивов в третий массив (упорядоченный). | Решение
|
Həlli | 20.
| Для заданных натуральных чисел n и k (k<= n) вывести все представления числа n суммой k не нулевых слагаемых (без повторения комбинаций). Пример: для n=9 и k=4 имеем 5 комбинаций: 1+1+1+6, 1+1+2+5, 1+1+3+4, 1+2+2+4, 1+2+3+3. | Решение | Həlli | | 21. |
| Решение | Həlli
| | 22. |
| Решение | Həlli
| | 23. |
| Решение | Həlli
| | 24. | | Решение
| Həlli
| | 25. |
| Решение
| Həlli
|
Задачи для самостоятельного
решения
1. Дан массив. Найти минимальный элемент. 2. Дан массив. Найти номер минимального элемента. 3. Поменять местами максимальный и минимальный элементы массива. 4. Дано натуральное число. Переставить его цифры так, чтобы получить максимально возможное число, записанное теми же цифрами. 5. В неупорядоченной последовательности найти максимальное количество равных элементов массива. 6. Дан массив. Написать программу упорядочения массива методом слияния. 7. Дан массив. Написать программу упорядочения массива методом быстрой сортировки. 8. Дан массив из N элементов. Переставить в обратном порядке элементы массива с K-го по L (1<=K<=L<=N); 9. Каждый элемент массива (кроме первого и последнего) требуется заменить значением его суммы с соседними элементами, деленной на три. 10. Требуется заменить каждый отрицательный элемент исходного массива на три элемента, равных его абсолютной величине. 11. Дана последовательность натуральных чисел. Найти наименьшее натуральное число, которое отсутствует в последовательности 12. Введите с клавиатуры число х и удалите из массива каж¬дый элемент, делящийся нацело на х, а оставшиеся уплотните к на¬чалу массива. 13. Ввести с клавиатуры число х и удалите из массива все элементы, абсолют¬ное значение которых больше |х|. Оставшиеся уплотнить (сместить к началу с сохранением их порядка). 14. Требуется циклически сдвинуть элементы массива на одну позицию влево. 15. Пусть элементы массива не убывают. Требуется вставить в этот массив новый элемент х с сохранением упорядоченности все¬го массива. Местоположение нового элемента определить последова¬тельным поиском. 16. Массив длины N в случайном порядке заполнен целыми числами из диапазона от 0 до N. Каждое число встречается в массиве не более одного раза. Найти отсутствующее число (дырку). Есть очень простой и оригинальный способ решения. Сложность алгоритма O(N). А что, если в массиве две дырки? 17. В массиве длины N в случайном порядке записаны целые числа от 1 до N. Все числа попарно различны. Упорядочить массив по возрастанию. Сложность алгоритма O(N). 18. Перестановка сегментов неодинаковой длины (Д.Грис). Сегментом называется непрерывная последовательность элементов массива. Массив состоит из двух сегментов неодинаковой длины. Не используя дополнительную память, пропорциональную N, поменять сегменты местами. Сложность алгоритма O(N). Найти как можно больше способов решения задачи (не меньше 3, включая и рекурсивный алгоритм). Чем и в каких случаях опасна рекурсия? Рассмотреть также случай перестановки несмежных сегментов. 19. Количество различных чисел (А.Шень). Массив длины N заполнен в случайном порядке числами из диапазона от 1 до k < N. Не используя других массивов, подсчитать количество различных чисел. Число действий должно быть порядка N+k. 20. Количество значений общих элементов. Даны два упорядоченных массива А и В (не обязательно одинаковой длины). В каждом из массивов могут быть совпадающие элементы. Не используя дополнительной памяти, найти количество совпадающих значений элементов А и В (т.е. количество t, для которых t=A[i]=B[j]). Чем отличается аналогичная задача, в которой надо найти число различных элементов?
|
