Форум программистов, компьютерный форум, киберфорум
Turbo Pascal
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 17.12.2010
Сообщений: 88
1

Дихотомический поиск по близости

18.10.2011, 23:45. Показов 913. Ответов 1
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Есть такая процедура:
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
procedure Search (var T: Table; n: Integer);
var
  x, : Integer;
  o: integer;
  data: string;
  ng, vg, i, i1, i2: integer;
  fl: boolean;
begin
  Sort(T, n); // сортировка методом "пузырька"
  begin
  readln(x);
  // в x - искомое
  ng := 1; vg := n;
  i1 := 0; i2 := 0;
  fl := False;
  while (ng <= vg) and not(fl) do
  begin
    i := (ng + vg) div 2;
    if(x < t[i].GDP) then
      vg := i-1;
    if(x > t[i].GDP) then
      ng := i+1;
    if (x = t[i].GDP) then
      fl := True;
    Writeln;
    if not(fl) then
      PrintTabGr(T, n, ng, vg);
    Readln;
  end;
 
  if not(fl) then
  begin
    o := Abs(x - t[i].GDP);
    i1 := i; i2 := i;
    while (i1>1) and (Abs(x - t[i1-1].GDP) = o) do
      i1 := i1 - 1;
    while (i2<n) and (Abs(x - t[i2+1].GDP) = o) do
      i2 := i2+1;
    writeln;
    Writeln('Найдены следующие страны: ');
    for i := i1 to i2 do
      Writeln('|', T[i].name:10, '|':5 ,T[i].GDP:10, '|':5);
    end
    else
    begin
      Writeln('Точное совпадение: ');
      Writeln('|', T[i].name:10, '|':5 ,T[i].GDP:10, '|':5);
    end;
    Readln;
end;
Которая ищет ближайшие значение в таблице T. Вот ее работа на примерах:
Дано:
34 45 49 89
, а нужно найти значения ближайшие к 47. Ответом будет 45, 49.

Если ищется 45, то ответом и будет 45.

Но есть одна мелочь. Если в таблице будет такая последовательность значений
23 45 65
, а найти нужно 64, то ответом будет 45, вместо ожидаемых 65. Как улучшить такой алгоритм?

Сразу прошу обратить внимание на эти строки кода:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 while (ng <= vg) and not(fl) do
  begin
    i := (ng + vg) div 2;
    if(x < t[i].GDP) then
      vg := i-1;
    if(x > t[i].GDP) then
      ng := i+1;
    if (x = t[i].GDP) then
      fl := True;
    Writeln;
    if not(fl) then
      PrintTabGr(T, n, ng, vg);
    Readln;
  end;
Проблема заключается скорее в правильном вычислении i. То есть самого ближайшего значения к искомому.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.10.2011, 23:45
Ответы с готовыми решениями:

Дихотомический поиск одномерного массива
помогите решить задачи 1)Дихотомический поиск одномерного массива(последовательность должна быть...

Дихотомический поиск
Составить рекурсивную функцию, реализующую алгоритм дихотомического поиска элемента с заданным...

Как реализовать дихотомический поиск
В общем вот мое задание, я вообще не понимаю как его делать, даже на пальцах, помогите, объясните...

Дихотомический поиск корня уравнения
Разработать подпрограмму, которая получает в качестве параметров три значения a, b, Delta и...

1
Почетный модератор
64300 / 47595 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
19.10.2011, 12:33 2
Цитата Сообщение от Vilian Посмотреть сообщение
Проблема заключается скорее в правильном вычислении i. То есть самого ближайшего значения к искомому.
Нужно задать минимальную разность, для начала например между искомым и первым числами,
Pascal
1
mn:=abs(x-t1);
а критерий поиска будет
Pascal
1
if abs(x-t[i])<mn then
0
19.10.2011, 12:33
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.10.2011, 12:33
Помогаю со студенческими работами здесь

Массив и мера близости.
Здравствуйте форумчани, нужна ваша помощь. Знаю Паскаль, а с Бейсиком(как это не смешно)...

Организовать связь слов по их контекстной близости
Привет! Я не могу точно сказать туда ли я пишу, но как минимум сейчас я представляю хранение в...

Отсортировать массив по близости элементов к единице с помощью анонимной функции
Помогите, пожалуйста, с задачей: Для элементов одномерного массива, заполненных случайными целыми...

переупорядочить заданный одномерный массив так, чтобы его элементы шли в порядке возрастания их близости к целым числам
не могу сделать задачу.....помогите пожалуйста ))))))))) задача: переупорядочить заданный...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru