Линейный поиск в упорядоченной таблице

@Argenta · Регистрация: 29.11.2017

Студворк — интернет-сервис помощи студентам

Измерение количества сравнений ключей. Таблица содержит в качестве ключей неотрицательные целые числа в диапазоне 0..32767. Данные
отсутствуют.
Построить график зависимости среднего количества сравнений ключей при удачном и неудачном поиске от:
a) Количества элементов, занесенных в таблицу (m).

Опыты провести для m (или n) = 1000, 2000, 3000, 4000, 5000, 6000.

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
program OrderedTable;
 
const 
   nmax = 32670;
   m = 1000;
type 
   tKey = integer;
   tData = string;
   tItem = record
      Key : tKey;
      data: tData;
   end;
   tTable = record 
      n: integer;
      a: array [1..nmax] of tItem;
   end;
   
 var 
    T : tTable;
    C, R, i : integer;
 
procedure Search (var T: tTable; K: tKey; var Res: integer; var m: integer);
begin
    i :=  T.n;
    while  (i  >  0)  and  (K  >  T.a[i].key)  do begin
       i  :=  i  -  1; 
       R := R + 1;
    if  (i > 0)  and  (K  =  T.a[i].key)  then begin
      Res := i; 
      C := C + 1;
      R := R + 1;
   end
   else  
      Res := 0;  
   end;
end;
 
 
begin 
   C := 0; { число удачного поиска}
   R := 0; { число сравнений }
   for i := 1 to m do begin 
    // T.a[i].Key := random (nmax);
   end
end.

как добавлять в таблицу упорядоченные ключи?

Добавлено через 8 минут

Pascal
1
 T.a[i].Key := i;

получается так?

не понимаю как написать чтоб рандомные числа искало(
как применить эту процедуру поиска

@Puporev · 31.05.2018, 11:03

Зачем в упорядоченном массива использовать линейный поиск, если специально для этого существует бинарный поиск?
А если поиск линейный, то зачем сортировать массив?

@Argenta · 03.06.2018, 16:44 **[ТС]**

так ведь это упорядоченная таблица
там все ключи по возрастанию должны быть
тогда таблицу вначале заполнять рандомными числами , а потом отсортировывать
и затем уже искать все ключи из диапазона?

@Puporev · 03.06.2018, 16:58

Это я к тому что в упорядоченных массивах применяют бинарный поиск, а не линейный.

@Argenta · 03.06.2018, 21:54 **[ТС]**

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
program OrderedTable;
 
const 
   nmax = 32670;
   delta = 1000;
type 
   tKey = integer;
   tData = string;
   tItem = record
      Key : tKey;
      data: tData;
   end;
   tTable = record 
      n: integer;
      a: array [0..nmax] of tItem;
   end;
   
 var 
    Res, m : integer; 
    T : tTable;
    Lucky, unLucky, C,  i : integer;
 
procedure AddToTable (var T: tTable; m: integer);
var
   i: integer;
begin 
   for i := 1 to m do begin
      Randomize;
      T.a[i].Key := random (nmax);
   end;
end;
 
procedure Sort (var T: tTable; m: integer);
var 
   i, j, jmin: integer;
   buf: tItem;
begin
   for i := 1 to m-1 do begin
      jmin := i;
      for j := i+1 to m do begin
         if T.a[j].Key < T.a[jmin].Key then
            jmin := j;
      end;
      buf := T.a[i];
      T.a[i] := T.a[jmin];
      T.a[jmin] := buf;
   end;
end;   
 
procedure Search (var T: tTable; K: tKey; var Res: integer; var С: integer);
begin
   i :=  T.n;
   while  (i  >  0)  and  (K  >  T.a[i].key)  do begin
      i  :=  i  -  1; 
      C := 1;
   if  (i > 0)  and  (K  =  T.a[i].key)  then begin
      Res := i; 
      C := 2;
   end
   else  
      Res := 0;  
   end;
end;
 
 
begin 
   m := 1000;
   while (m <= 6000) do begin 
     Lucky := 0; {число сравнений при неудачном поиске}
     unLucky := 0; {число сравнений при неудачном поиске}
     for i := 1 to m do 
       AddToTable(T, m);
       Sort(T, m);
     Search(T, i, Res, C);
     if Res = 0 then 
        unLucky := unLucky + C
     else 
        Lucky := Lucky + C; 
     Write (Lucky/m);
     Writeln (unLucky/(nmax - m):3);
     m := m + delta;
   end;
end.

Добавлено через 4 часа 13 минут
где тут ошибка?

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
program OrderedTable;
 
const 
   nmax = 32670;
   delta = 1000;
type 
   tKey = integer;
   tData = string;
   tItem = record
      Key : tKey;
      data: tData;
   end;
   tTable = record 
      n: integer;
      a: array [0..nmax] of tItem;
   end;
   
 var 
    Res, m : integer; 
    T : tTable;
    Lucky, unLucky, C,  i : integer;
 
procedure AddToTable (var T: tTable; m: integer);
 
begin 
      Randomize;
      T.a[i].Key := random (nmax);
end;
 
procedure Sort (var T: tTable; m: integer);
var 
   i, j, jmin: integer;
   buf: tItem;
begin
   for i := 1 to m-1 do begin
      jmin := i;
      for j := i+1 to m do begin
         if T.a[j].Key < T.a[jmin].Key then
            jmin := j;
      end;
      buf := T.a[i];
      T.a[i] := T.a[jmin];
      T.a[jmin] := buf;
   end;
end;   
 
procedure Search (var T: tTable; K: tKey; var Res: integer; var С: integer);
begin
   i :=  T.n;
   while  (i  >  0)  and  (K  >  T.a[i].key)  do begin
      i  :=  i  -  1; 
      C := 1;
   if  (i > 0)  and  (K  =  T.a[i].key)  then begin
      Res := i; 
      C := 2;
   end
   else  
      Res := 0;  
   end;
end;
 
 
begin 
   m := 1000;
   while (m <= 6000) do begin 
     Lucky := 0; {число сравнений при неудачном поиске}
     unLucky := 0; {число сравнений при неудачном поиске}
     for i := 1 to m do begin  
        Randomize;
        T.a[i].Key := random (nmax);
     end;
     for i := 1 to m do 
       Sort(T, m);
     for i:= 1 to nmax do begin
       Search(T, i, Res, C);
       if Res = 0 then 
          unLucky := unLucky + C
       else 
          Lucky := Lucky + C;
     end;
     Write (Lucky/m);
     Writeln (unLucky/(nmax - m):3);
     m := m + delta;
   end;
end.

Новые блоги и статьи Все статьи Все блоги /
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .

@Puporev Почетный модератор 64315 / 47611 / 32743 Регистрация: 18.05.2008 Сообщений: 115,167
	31.05.2018, 11:03
	Зачем в упорядоченном массива использовать линейный поиск, если специально для этого существует бинарный поиск? А если поиск линейный, то зачем сортировать массив? 0

@Argenta 3 / 3 / 2 Регистрация: 29.11.2017 Сообщений: 126
	03.06.2018, 16:44 [ТС]
	так ведь это упорядоченная таблица там все ключи по возрастанию должны быть тогда таблицу вначале заполнять рандомными числами , а потом отсортировывать и затем уже искать все ключи из диапазона? 0

@Puporev Почетный модератор 64315 / 47611 / 32743 Регистрация: 18.05.2008 Сообщений: 115,167
	03.06.2018, 16:58
	Это я к тому что в упорядоченных массивах применяют бинарный поиск, а не линейный. 0