Массивы
Задача 1. Дан массив х: array[1..n] of integer, причем x[1]<=x[2]<=...<=x[n]. Найти количество различных чисел среди элементов массива. Решение: i:=1; k:=1; while i<>n do begin Другой вариант решения: Задача 2. Дан массив x: array[1..n] of integer. Найти количество различных чисел среди элементов этого массива. Число действий должно быть порядка n2. Решение: Задача3. Дан массив x: array[1..n] of integer. Не используя других массивов, переставить элементы массива в обратном порядке. Решение: Каждый i-й элемент нужно поменять с (n+1-i)-м элементом местами. Для которых i<n+1-i, то есть 2i<n+1 <=> 2i<=n <=> i<= n div 2. for
i:=1 to n div 2 do Многочленом от одной переменной x
будем называть выражение вида Задача 4. Коэффициенты многочлена лежат в массиве
a: array[0..n] of integer (n - натуральное число, степень многочлена).
Вычислить значение многочлена в точке x, то есть Решение:
Для 0<=k<=n
вычисляем y=a[n]·xk+a[n-1]·xk-1+..+a[n-k]·x0. Задача 5. Даны два возрастающих массива x: array[1..k] of ihteger и y: array[1..h] of ihteger.Найти количество общих элементов в этих массивах, то есть количество тех элементов, для которых x[i]=y[j] для некоторых i и j. Число действий порядка k+h. Решение: Возьмем дополнительные переменные
0<=k1<=k и 0<=h1<=h. k1:=0;
h1:=0; n:=0; Цикл повторяется k+h раз. В теле цикла выполняется или одна, или три операции присваивания. В любом случае число действий порядка k+h. Задача 6. Даны два массива x[1]<=...<=x[k] и y[1]<=...<=y[h]. "Соединить" их в массив z[1]<=...<=z[m] (m=k+h, каждый элемент должен входить в массив z столько раз, сколько раз он входит в общей сложности в массивы x и y). Число действий порядка m. Решение: Пусть у нас есть две стопки карточек, отсортированных по алфавиту. Мы соединяем их в одну стопку, выбирая каждый раз ту из верхних карточек обеих стопок, которая идет раньше в алфавитном порядке. Если в одной стопке карточки кончились, берем их из другой стопки. k1:=0;
h1:=0; При каждом вхождении в цикл (их m=k+h) выполняется только одно из условий и число операций равно двум. Значит общее число действий - 2m. Задача7. Некоторое число содержится в каждом из трех целочисленных неубывающих массивов x[1]<=...<=x[p], y[1]<=...<=y[q], z[1]<=...<=z[r]. Найти одно из таких чисел. Число действий должно быть порядка p+q+r. Решение: Как и в предыдущей задаче число вхождений в цикл равно p+q+r, где выполняется только один оператор присваивания. Задача 8. Дан целочисленный массив x[1]<=...<=x[n] и число a. Выяснить, содержится ли a в этой последовательности, то есть найти такое i из 1..n, для которого x[i]=a. Количество действий порядка log2n. Решение: Метод двоичного поиска: Рассмотрим отрезок 1..n. Делим его пополам и выбираем ту половину, в которой может находиться такое i, что x[i]=a. (см. Н.Вирт "Алгоритмы и структура данных") q:=1; r:=n; while r-q<>1 do begin m:=(r+q) div 2; if x[m]<=a then q:=m else r:=m; end; if (x[q]=a) or (x[r]=a) then writeln('есть') else writeln('нет'); Каждый раз r-q уменьшается примерно вдвое, поэтому количество действий не превосходит 2·log2 n. Задача 9. Дан массив x:array[1..n,1..m] of integer, упорядоченный по строкам и по столбцам и число a. Требуется выяснить, встречается ли a среди x[i,j]. Решение:
h:=n;k:=1; while (h>0) and (k<m+1) and (x[h,k]<>a) do if x[h,k]<a then k:=k+1 else h:=h-1; answer:=(h>0) and (k<m+1);
Задача 10. Дан неубывающий массив положительных целых чисел a[1]<=a[2]<=...<=a[n]. Найти наименьшее целое положительное число, не представимое в виде суммы нескольких элементов этого массива (каждый элемент массива может быть использован не более одного раза). Число действий порядка n. Решение: Пусть известно, что числа, представимые в виде суммы элементов a[1],...,a[k], заполняют отрезок от 1 до некоторого R. Если a[k+1]>R+1, то R+1 и будет минимальным числом, не представимым в виде суммы элементов массива. Если же a[k+1]<=R+1, то числа, представимые в виде суммы элементов a[1],...,a[k+1], заполняют отрезок от 1 до R+a[k+1]. k:=0;R:=0; while (k<>n) and (a[k+1]<=R+1) do begin R:=R+a[k+1]; k:=k+1; end; writeln(R+1); Очевидно, что число действий не превосходит 2·n. Задача 11. Дан массив x[1..n] и число b. Переставить числа в массиве таким образом, чтобы слева от некоторой границы стояли числа, меньшие или равные b, а справа от границы - большие или равные b. Решение: h:=0;r:=n; while h<>r do if a[h+1]<=b then h:=h+1 else if a[r]>=b then r:=r-1 else begin m:=a[h+1]; a[h+1]:=a[r]; a[r]:=m; h:=h+1;r:=r-1; end;
1. Решить задачу 5, если известно, что x[1]<=...<=x[k], y[1]<=...<=y[h]. 2. Даны два неубывающих массива x: array[1..k] of integer и y: array[1..h] of integer. Найти количество различных элементов среди x[1],...,x[k],y[1],...,y[h]. Число действий порядка k+h. 3. Даны два массива x[1]<=...<=x[k] и y[1]<=...<=y[h]. Найти их "пересечение", то есть массив z[1]<=...<=z[m], содержащий их общие элементы, причем кратность каждого элемента в массиве z равняется минимуму из его кратностей в массивах x,y. Число действий порядка k+h. 4. Дан массив a[1..n] и число b. Переставить числа в массиве таким образом, чтобы сначала шли элементы меньшие b, затем равные b, затем большие b. 5. Дана квадратная таблица x[1..n,1..n] и число m<n. Для каждого квадрата m на m в этой таблице вычислить сумму стоящих в нем чисел. Число действий порядка n2. 6. В массиве a[1]...a[n] встречаются по одному разу все целые числа от 0 до n, кроме одного. Найти пропущенное число за время порядка n и с конечной дополнительной памятью. Замечание: При решении задач не использовать сортировки. |