Задачи, советы и ответы - часть 13

Совет 3 (общий)

Третий алгоритм базируется на использовании массива индикаторов. Так как значения элементов исходного массива принадлежат интервалу [0,32767], то заводится 32 768 битовых индикаторов (4096 байт). В начале все индикаторы сбрасываются в нуль, а затем выполняется цикл одноразового просмотра элементов исходного массива. Для значения каждого элемента a[i] проверяется соответствующий бит в массиве индикаторов и, если он равен 0, в него заносится 1 и к счетчику разных чисел добавляется единица. Если проверяемый бит индикаторов отличен от нуля, то соответствующее значение уже встречалось.

Совет 4 (Си)

Массив индикаторов (b) можно явным образом запрашивать при входе в подпрограмму и освобождать при выходе, хотя локальные данные в процедурах и функциях все равно выделяются и освобождаются автоматически. Но в библиотеке Си есть полезная функция calloc, которая одновременно выделяет память и чистит ее. Переменные byte и bit использованы для определения байта и бита в массиве индикаторов, соответствующих анализируемому значению a [i].

Программа 4_09a.bas

DECLARE SUB SORT (A() AS INTEGER, N%)

DECLARE FUNCTION DIFFERENCE% (A() AS INTEGER, N%)

DEFINT A-Z

DIM A(5)

DATA 0,0,0,0,0

DATA 1,1,1,1,1

DATA 0,1,1,1,1

DATA 0,0,1,1,2

DATA 0,1,2,3,4

DATA 1,2,3,4,5

CLS

FOR k=1 TO 5

FOR I=0 TO 4: READ A(I): NEXT I

PRINT "Количество разных чисел в массиве ";k;" = ";

PRINT DIFFERENCE(A(), 5} NEXT k END

FUNCTION DIFFERENCE (A() AS INTEGER, N%)

SORT A(),N%

M=l

FOR I=0 TO N%-2

IF A(I)<>A(I+1) THEN M=M+1

NEXT I

DIFFERENCE=M

END FUNCTION

SUB SORT(A() AS INTEGER,N%)

REM тело любой процедуры сортировки

END SUB

Программа 4_09b.bas

DECLARE SUB SORT (A() AS INTEGER, N%)

DECLARE FUNCTION DIFFERENCE% (A() AS INTEGER, N%)

DEFINT A-Z

DIM A0(5),A1{5),A2(5),A3(5},A4(5),A5(5)

DATA 0,0,0,0,0

FOR I=0 TO 4: READ А0(I): NEXT I

DATA 1,1,1,1,1

FOR I=0 TO 4: READ A1(I): NEXT I

DATA 0, 1,1, 1, 1

FOR I=0 TO 4: READ A2(I): NEXT I

Содержание Назад Вперед