17.11.2018, 17:04 [+3 UTC]
в нашей команде: 3 112 чел. | участники онлайн: 14 (рекорд: 17)

:: РЕГИСТРАЦИЯ

:: задать вопрос

:: все разделы

:: правила

:: новости

:: участники

:: доска почёта

:: форум

:: блоги

:: поиск

:: статистика

:: наш журнал

:: наши встречи

:: наша галерея

:: отзывы о нас

:: поддержка

:: руководство

Версия системы:
7.55 (06.11.2018)

Общие новости:
24.09.2018, 16:49

Форум:
08.11.2018, 13:36

Последний вопрос:
17.11.2018, 15:12

Последний ответ:
17.11.2018, 17:02

Последняя рассылка:
17.11.2018, 16:46

Писем в очереди:
0

Мы в соцсетях:

Наша кнопка:

RFpro.ru - здесь вам помогут!

Отзывы о нас:
22.02.2010, 10:27 »
Dimon4ik
Ту версию, что у Вас установил - все заработало. Там так много интересных компонентов... Спасибо. [вопрос № 176827, ответ № 259638]
19.05.2010, 09:31 »
Botsman
Огромное спасибо! Как всегда, вовремя, красиво и правильно! [вопрос № 178455, ответ № 261478]

РАЗДЕЛ • Pascal / Delphi / Lazarus

Создание программ на языках Pascal, Delphi и Lazarus.

[администратор рассылки: Зенченко Константин Николаевич (Модератор)]

Лучшие эксперты в этом разделе

Зенченко Константин Николаевич
Статус: Модератор
Рейтинг: 684
Степанов Иван /REDDS
Статус: 4-й класс
Рейтинг: 26
Асмик Гаряка
Статус: Советник
Рейтинг: 6

Перейти к консультации №:
 

Консультация онлайн # 176552
Раздел: • Pascal / Delphi / Lazarus
Автор вопроса: Кусмарцев Андрей Валерьевич
Отправлена: 07.02.2010, 18:37
Поступило ответов: 3

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

Сортировки оформить в виде отдельных подпрограмм.
Спасибо

Состояние: Консультация закрыта

Ответ # 259295 от Verena

Здравствуйте, Кусмарцев Андрей Валерьевич.
Программа в приложении. Смысл должен быть понятен из комментариев, но ещё описание алгоритмов можете посмотреть здесь:
Сортировка пузырьком
Сортировка методом прямого включения
Функция Random
Удачи!
PS: Проверила, random (x) возвращает всё-таки от 0 до x-1, так что поменяла на random (100).

Приложение:


Консультировал: Verena
Дата отправки: 07.02.2010, 19:27

5
нет комментария
-----
Дата оценки: 08.02.2010, 05:21

Рейтинг ответа:

0

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Ответ # 259297 от Micren

Здравствуйте, Кусмарцев Андрей Валерьевич.
Программа. Компилировал FreePascal.

program P_176552;

{ Константы }
const
    NUM_CNT=100;    { Количество чисел }
    NUM_LO=1;       { Минимальное значение }
    NUM_HI=100;     { Максимальное значение }

{ Типы }
type
    TArray=array[1..NUM_CNT] of Integer;    { Массив }
    { Процедура сортировки
      Sequence - последовательность
      Comparisions - сравнений
      Permutations - перестановок }
    TSortProc=procedure(var Sequence:TArray;var Comparisions,Permutations:Integer);

{ Заполняет массив случайными значениями в диапазоне [NUM_LO..NUM_HI] }
procedure CreateArray(var Sequence:TArray);
var
    i:Integer;
begin
    for i:=1 to NUM_CNT do begin
        Sequence[i]:=Random(NUM_HI-NUM_LO+1)+NUM_LO;
    end;
end;

{ Выводит массив }
procedure PrintArray(Message:String;Sequence:TArray);
var
    i:Integer;
begin
    WriteLn(Message);
    for i:=1 to NUM_CNT do begin
        Write(Sequence[i]:4,' ');
    end;
    WriteLn;
end;

{ Пузырьковая сортировка }
procedure BubbleTest(var Sequence:TArray;var Comparisions,Permutations:Integer);
var
    i,j,Tmp:Integer;
begin
    { Обнулим счетчики }
    Comparisions:=0;
    Permutations:=0;
    for i:=1 to NUM_CNT-1 do begin
        for j:=1 to NUM_CNT-i do begin
            Inc(Comparisions);
            if Sequence[j]>Sequence[j+1] then begin
                Inc(Permutations);
                Tmp:=Sequence[j];
                Sequence[j]:=Sequence[j+1];
                Sequence[j+1]:=Tmp;
            end;
        end;
    end;
end;

{ Сортировка включением }
procedure InclusionTest(var Sequence:TArray;var Comparisions,Permutations:Integer);
var
    i,j,item:Integer;
begin
    { Обнулим счетчики }
    Comparisions:=0;
    Permutations:=0;
    for i := 2 to NUM_CNT do begin
        item:=Sequence[i];
        j:=i-1;
        Inc(Comparisions);
        { Ищем куда вставить }
        while (j>0) and (item<=Sequence[j]) do begin
            Inc(Comparisions);
            Inc(Permutations);
            Sequence[j+1]:=Sequence[j];
            Dec(j);
        end;
        Inc(Permutations);
        Sequence[j+1]:=item;
    end;
end;

{ Помогает нам оформить вывод }
procedure Test(Message:String;Sequence:TArray;Proc:TSortProc);
var
    Comparisions,Permutations:Integer;
begin
    WriteLn;
    Proc(Sequence,Comparisions,Permutations);
    WriteLn(Message);
    PrintArray('Массив после сортировки:',Sequence);
    WriteLn('Сравнений:',Comparisions);
    WriteLn('Перестановок:',Permutations);
end;

var
    Sequence:TArray;

begin
    Randomize;
    { Заполним массив }
    CreateArray(Sequence);
    { Выведем его }
    PrintArray('Исходный массив:',Sequence);
    { Проверяем }
    Test('Пузырьковая сортировка.',Sequence,@BubbleTest);
    Test('Сортировка включением.',Sequence,@InclusionTest);
end.

Пример работы:
~/projects/Pascal> ./P_176552
Исходный массив:
  61   69   74   91   28   39   13   35   77   78   42   62   12   43   37   72 
  34   24   70  100   23   60   27    1   63   72   60   27   24   90   83   25 
  60   37   52  100   11   69   71   12   52   78   81   94   64   36   32   21 
  86   64   77   70   42   17   13   64    3   12   23   64   33    9   88   49 
   8   99   68   26   15   66   38   28   86   77   98   66    8   28   59   37 
  49   24   82   87    3   65   19   95   94   68   27   37   55   73   68   42 
   6   71   60    6 

Пузырьковая сортировка.
Массив после сортировки:
   1    3    3    6    6    8    8    9   11   12   12   12   13   13   15   17 
  19   21   23   23   24   24   24   25   26   27   27   27   28   28   28   32 
  33   34   35   36   37   37   37   37   38   39   42   42   42   43   49   49 
  52   52   55   59   60   60   60   60   61   62   63   64   64   64   64   65 
  66   66   68   68   68   69   69   70   70   71   71   72   72   73   74   77 
  77   77   78   78   81   82   83   86   86   87   88   90   91   94   94   95 
  98   99  100  100 
Сравнений:4950
Перестановок:2512

Сортировка включением.
Массив после сортировки:
   1    3    3    6    6    8    8    9   11   12   12   12   13   13   15   17 
  19   21   23   23   24   24   24   25   26   27   27   27   28   28   28   32 
  33   34   35   36   37   37   37   37   38   39   42   42   42   43   49   49 
  52   52   55   59   60   60   60   60   61   62   63   64   64   64   64   65 
  66   66   68   68   68   69   69   70   70   71   71   72   72   73   74   77 
  77   77   78   78   81   82   83   86   86   87   88   90   91   94   94   95 
  98   99  100  100 
Сравнений:2666
Перестановок:2666


Консультировал: Micren
Дата отправки: 07.02.2010, 20:04

4
нет комментария
-----
Дата оценки: 08.02.2010, 14:38

Рейтинг ответа:

+1

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Ответ # 259301 от Орловский Дмитрий (Мастер-Эксперт)

Здравствуйте, Кусмарцев Андрей Валерьевич.

Предлагаю еще один вариант.

program Psort;

{$APPTYPE CONSOLE}

const
  n=100;

type
  XArray = array[1..n] of integer;

var
  x,y:XArray;
  i:integer;
  c,m:integer;

procedure InitData;
var
  i: integer;
begin
  Randomize;
  for i:=1 to n do begin
    x[i]:=Random(n)+1;
    y[i]:=x[i];
  end;
end;

procedure DirectIncludeSort;
var
  i,j,tmp:integer;
begin
  for i:=2 to n do begin
    tmp:=x[i];
    j:=i;
    while (j>1)and(tmp<x[j-1]) do begin
      x[j]:=x[j-1];
      j:=j-1;
      m:=m+1;
      c:=c+1;
    end;
    c:=c+1;
    x[j]:=tmp;
    m:=m+1
  end
end;

procedure BubbleSort;
var
  i,j,tmp:integer;
begin
  for i:=1 to n-1 do
    for j:=n downto i+1 do
    begin
      if y[j-1]>y[j] then
      begin
        tmp:=y[j];
        y[j]:=y[j-1];
        y[j-1]:=tmp;
        m:=m+1;
      end;
      c:=c+1
    end
end;

begin
  InitData;
  for i:=1 to n do write('x[',i,']=',x[i],' ');
  writeln;
  c:=0;
  m:=0;
  DirectIncludeSort;
  writeln('c=',c,' m=',m);
  for i:=1 to n do write('x[',i,']=',x[i],' ');
  writeln;
  c:=0;
  m:=0;
  BubbleSort;
  Writeln('c=',c,' m=',m);
  for i:=1 to n do write('x[',i,']=',y[i],' ');
  writeln;
  readln
end.




Консультировал: Орловский Дмитрий (Мастер-Эксперт)
Дата отправки: 07.02.2010, 23:42

5
нет комментария
-----
Дата оценки: 08.02.2010, 14:37

Рейтинг ответа:

0

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Мини-форум консультации № 176552

Посетитель

ID: 307880

# 1

= общий = | 07.02.2010, 18:40 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

желательно попроще и с коментариями


Посетитель

ID: 256539

# 2

= общий = | 07.02.2010, 20:07 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Кусмарцев Андрей Валерьевич:
Если используете Turbo Pascal(я использовал FreePascal) и возникнут проблемы напишите тут в мини-форуме.


Посетитель

ID: 301080

# 3

= общий = | 07.02.2010, 20:24 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Verena:
Здравствуйте, Verena!

© Цитата:
a[i]:= random (99)+1; {random генерирует число от 0 до параметра, поэтому берём от 99 и +1}

random(N) возвращает значение от 0 до N-1.
Поэтому, мне кажется, правильнее будет:
a[i]:= random (100)+1


Посетитель

ID: 24617

# 4

= общий = | 07.02.2010, 20:40 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Максим Юрьевич:
Я всегда думала, что random возвращает от 0 до N, ориентируясь по этому источнику.


Посетитель

ID: 307880

# 5

= общий = | 08.02.2010, 05:38 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

star9491:
процедура Initdata, это как я понял запись 100 случайных чисел?


Посетитель

ID: 307880

# 6

= общий = | 08.02.2010, 05:45 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Verena:
Вы на какой версии паскаля писали, а то мой тип word не знает

Орловский Дмитрий
Мастер-Эксперт

ID: 319965

# 7

= общий = | 08.02.2010, 09:55 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Кусмарцев Андрей Валерьевич:
Initdata формирует массив случайных чисел x[i] для процедуры DirectIncludeSort и его копию y[i] для процедуры BubbleSort.


Посетитель

ID: 24617

# 8

= общий = | 08.02.2010, 14:33 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Кусмарцев Андрей Валерьевич:
Turbo Pascal 7.0, а у вас какой?


Посетитель

ID: 24617

# 9

= общий = | 08.02.2010, 14:34 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Кусмарцев Андрей Валерьевич:
Можете заменить на integer, если какие-то проблемы.


Посетитель

ID: 307880

# 10

= общий = | 08.02.2010, 14:39 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Verena:
Pascal abc, но все нормально работает

Сергей Бендер
Профессионал

ID: 304622

# 11

= общий = | 10.02.2010, 14:35 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Verena:

© Цитата:
Я всегда думала, что random возвращает от 0 до N, ориентируясь по этому источнику.


Главный источник в TP -- это Ctrl-F1. ;)


Посетитель

ID: 24617

# 12

= общий = | 10.02.2010, 16:52 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Сергей Бендер:
У меня урезанная версия, хелпа нет :)

Сергей Бендер
Профессионал

ID: 304622

# 13

= общий = | 10.02.2010, 21:12 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Verena:

© Цитата:
У меня урезанная версия, хелпа нет


В-ва-х-х! Turbo Pascal 7.0? Может выслать?

 

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

Яндекс Rambler's Top100

главная страница | поддержка | задать вопрос

Время генерирования страницы: 0.22393 сек.

© 2001-2018, Портал RFPRO.RU, Россия
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.55 от 06.11.2018