VPF::порядковые статистики - Форум программистов

Andrez

Дата 3.1.2006, 22:47 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 24.9.2005

Репутация: нет
Всего: нет

Помогите написать прогу на Builder`e вычисления порядковых статистик за линейное време в худшем случае.

yaja

Дата 4.1.2006, 14:07 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 98
Регистрация: 30.3.2005
Где: Санкт-Петербург

Репутация: нет
Всего: 1

Это в смысле алгоритм Кнута-Мориса-Ривеста-Тарьяна??? smile

podval

Дата 4.1.2006, 16:16 (ссылка)

(нет голосов)

Загрузка ...

Где я? Кто я?

Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62

Andrez
В чем проблема?

- незнание статистики
- неумение программировать в Билдере
- нежелание делать все это самому

smile

Andrez

Дата 4.1.2006, 22:28 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 24.9.2005

Репутация: нет
Всего: нет

Нашел алгоритм,в котором массив надо делить на n/5 частей и т.д., а разобраться в нем немогу.

esperant0

Дата 5.1.2006, 00:41 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 714
Регистрация: 20.5.2005

Репутация: 4
Всего: 14

пусть тебе нужно найти средний элемент.

выбираешь случайный элемент и считаешь сколько элемнтов и какие меньше него.

пусьт меньше него четверть элементов

значит теперь рекурсивно ищешь 1\3 статистику среди элементов больщих выбранного

--------------------

Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer

Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором а затем стерто и которое он - пользователь не мог видеть.

yaja

Дата 5.1.2006, 19:40 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 98
Регистрация: 30.3.2005
Где: Санкт-Петербург

Репутация: нет
Всего: 1

esperant0 твой алгоритм будет работать в O(nlog(n)) в лучшем случае, а в худшем квадрат, если все время будем выбирать максимальный или минимальный элемент в массиве...

Andrez да, это алгоритм Кнута-Мориса-Ривеста-Тарьяна, в Кормэне написано про него...

Это сообщение отредактировал(а) yaja - 5.1.2006, 19:49

esperant0

Дата 5.1.2006, 22:01 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 714
Регистрация: 20.5.2005

Репутация: 4
Всего: 14

Цитата(yaja @ 5.1.2006, 19:40)

Мой алгоритм будет работать за время o(n) с вероятностью подчти 1.

и худшего случая у него нет.

доказательство можете процесть у Ранджвани.

с уважением

--------------------

Andrez

Дата 5.1.2006, 22:25 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 24.9.2005

Репутация: нет
Всего: нет

помогите найти ошибку в проге, правда она немного корявая. но все же

Код


unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, ExtCtrls, ComCtrls;

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    Edit1: TEdit;
    Button1: TButton;
    Edit2: TEdit;
    Memo2: TMemo;
    Button2: TButton;
    Edit3: TEdit;
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;
const n = 20000;
type mas= array[1..n] of Longint;
type buf= array[1..5]of longint;
var
  Form1: TForm1;
  i,j,k: Longint;
  ar,m,b: mas;
  s:Longint;
implementation

{$R *.dfm}

procedure init(var a:mas; N:Longint);
var i:Longint;
begin
randomize;
for i:=1 to n do
    a[i]:=random(100);
end;

procedure insertsort(var a:mas);
var i,j: Longint;
    x: Longint;
begin
 for i:=2 to 5 do
   begin
      x:=a[i];j:=i-1;
      while((x<a[j])and (j>0)) do
          begin
            a[j+1]:=a[j];
            dec(j);
          end;
      a[j+1]:=x;
   end;
end;

procedure med(var a:mas;count:Longint);
var s,t,i:Longint;
begin
 s:=0;
 t:=0;
 for i:=1 to count do
  begin
   for t:=(5*i-4) to (5*i) do
    begin
     inc(s);
     b[s]:=a[t];
    end;
   insertsort(b);
   m[i]:=b[3];
   s:=0;
  end;
end;

function partition(var a:mas;p:Longint;r:Longint;x:Longint):Longint;
var temp:longint;
    i,j:longint;
begin
i:=p; j:=r;
while i<j do
  begin
    repeat dec(j); until a[j]<x;
    repeat inc(i); until a[i]>x;
    if i<j then
      begin
        temp:=a[i];a[i]:=a[j];a[j]:=temp;
      end
    else partition:=j;
  end;
end;

function select(var a:mas;index:longint):Longint;
var count,m_of_m:Longint;
    k:Longint;
    stat:longint;
begin
   if (sizeof(a) mod 5)<> 0 then count:=(n div 5)+1
                    else count:=n div 5;
   med(a,n);
   m_of_m:=select(m,(count+1)div 2);
   k:=partition(a,1,n,m_of_m);
   if index<=k then stat:=select(a,index)
               else stat:=select(a,index-k);
select:=a[stat];
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
Memo1.Clear;
j:=StrToInt(Edit1.Text);
init(ar,j);
for i:=1 to j do memo1.Lines.Add(inttostr(ar[i]));
end;

procedure TForm1.Button2Click(Sender: TObject);
var x:Longint;
begin
s:=StrToInt(Edit2.Text);
for i:=1 to j do memo2.Lines.Add(inttostr(ar[i]));
x:=select(ar,s);
edit3.Text:=inttostr(x);
end;

end.

podval

Дата 6.1.2006, 11:19 (ссылка)

(нет голосов)

Загрузка ...

Где я? Кто я?

Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62

podval

Что за прога? К обсуждаемой теме она имеет отношение?

Andrez

Дата 6.1.2006, 13:02 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 24.9.2005

Репутация: нет
Всего: нет

прога по алгоритму из кормена, только что-то неправильно, а что не пойму

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »