Конспект лекций по программированию для начинающих. Гладков В.П. - 148 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Составители: 

Рубрика: 

150
равен 2, во втором просмотре - индексы 2,6,10, шаг просмотра равен 4, в третьем
просмотре - индекс 4, шаг просмотра равен 8, в пятом просмотре - индекс 8, шаг
просмотра равен 16. Можно заметить, что шаг на каждом просмотре увеличивается
в два раза, следовательно, количество просмотров (z) конкретного массива,
зависящее от количества элементов в нем, можно определить из неравенств
2
z-1
<n≤2
z
. Отсюда z=]log
2
n[+1, а максимальное значение h=2
]log
2
n[+1
. На основе этого
можно переписать предыдущую схему нелинейного перебора элементов массива,
сведя ее к двум вложенным циклам. В первом цикле изменяется h, а во втором -
индекс массива k.
h:=2;
while h<=exp((trunc(ln(n)/ln(2))+1)*ln(2)) do
begin
k:=h div 2;
while k<=n do
begin
{обработка a[k]}
k:=k+h
end;
h:=h*2
end.
В данном примере свели нелинейное изменение индекса массива к изменению
двух переменных по закону арифметической прогрессии.
Пример 11.5. Напечатать те элементы одномерного массива, которые являются
полными квадратами. Здесь для вычисления индекса можно использовать две
переменные. P - индекс элемента массива, i - номер квадрата. Известен квадрат
натурального числа 1, он равен 1, тогда фрагмент нужной программы может быть
таким:
i:=1;
p:=sqr(i);
while p<=n do
begin
write(a[p]);
i:=i+1;
p:=sqr(i)
end.
Пример 11.6. Напечатать те элементы одномерного массива, индексы которых
являются числами Фибоначчи. Здесь для вычисления следующего значения
индекса нужно хранить два предыдущих, поэтому для вычисления значения
индекса будем использовать три переменных: a - текущее значение числа
Фибоначчи, b - предыдущее значение числа Фибоначчи, c - предпредыдущее
значение числа Фибоначчи.
c:=1;
b:=1;
while b<= n do
begin
write(a[b]); 
                                        150

равен 2, во втором просмотре - индексы 2,6,10, шаг просмотра равен 4, в третьем
просмотре - индекс 4, шаг просмотра равен 8, в пятом просмотре - индекс 8, шаг
просмотра равен 16. Можно заметить, что шаг на каждом просмотре увеличивается
в два раза, следовательно, количество просмотров (z) конкретного массива,
зависящее от количества элементов в нем, можно определить из неравенств
2z-1

Страницы