Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > Обрабока массивов

Автор: ufoman 9.2.2006, 16:34

Если кто знает Pascal... ПОМОГИТЕ, нужно срочно написать программу по обработке массивов, а именно:

- Ввод массивов;
- Сортировка массивов по возрастанию;
- Вывод массивов.

Написать нужно просто тект программы (Мне на эезамен нужно, а я Pascal вообще не знаю)...

!!!ПОЖАЛУЙСТО ПОМОГИТЕ!!!!

Автор: karataev 9.2.2006, 16:45

Тебе нужны массивы одномерные? двухмерные? в общем, скольки мерные???

Вот для одномерного:

Код


const max=1000; {Здесь максимальное число элементов, которое тебе нужно}

var a:array[1..max] of word; {Здесь тип массива, какой тебе нужен}
    i,j,n,t:word;

begin

{Ввод массива. n-требуемая длина массива}
readln(n);
for i:=1 to n do
 readln(a[i]);
end.

{Сортировка методом полного перебора (насколько я знаю, для экзамена именно она сойдет)}
for j:=1 to n-1 do
 for i:=j+1 to n do
  if a[i]<a[j] then {Это сортирует по возрастанию, по убыванию if a[i]>a[j] then}
   begin
   t:=a[j];
   a[j]:=a[i];
   a[i]:=t;
   end;

{Вывод массива на экран}
for i:=1 to n do
 writeln(a[i]);

end.

Автор: Palladin 15.2.2006, 01:31

Вот что у меня на месте учёбы раздали всем может тебе пригодится, тут по самы распростроннёным видам сотрировки массивов:
1. Метод извлечения
Фрагмент программы сортировки по неубыванию извлечем минимального элемента с просмотром слева направо имеет вид:

Код


For   I:=1   To N-1 Do
     Begin
       B: = A[i];
       M: = I;
For J: = I+1 To N Do
             If B›A [J]
                    Then
                      Begin
                        B: = A[J];
                        M: = J
                   End;
       A[M]: = A[I];
       A[I]: = B
End;

Для сокращения числа операций над элементами массива необходимо ввести вспомогательные переменные и прежде, чем менять местами найденный минимальный элемент (в данном случае A[M]) с A[i] элементом, целесообразно проверить, может быть этот минимальный элемент уже стоит на i-том месте. В результате получим следующий фрагмент программы:

Код

For   I:=1   To N-1 Do
     Begin
       B: = A[i];
       C: =B; M: = I;
For J: = I+1 To N Do
      Begin
           D: =A[J]   
           If B›A 
                    Then
                        Begin
                           B: = D; M: =J
                       End
             End;
       If  I‹› M
             Then
                 Begin
                      A[I]: = B
                      A[M] : = C
                    End   
End;

2. Метод включения
Фрагмент программы сортировки по неубыванию методом включения имеет вид:

Код

For i:=2   to n do
   Begin
         J:=i-1;
        L: = true
        While (l) and (j›=1) do
          If a[j] ‹ a[i] then
                                L: = false
                               Else
                                   J:=j-1;
        Z: = a[i];
        K:=i-1;
          If  l = true then
                                Begin
                                 While k›=1   do
                                   Begin
                                      A[k+1]: = a[k];
                                      K:=k-1
                                   End;
                                   A[1]:=z
                               End
                             Else
                              Begin
                                 While k›j do
                                    Begin
                                      A[k+1]: = a[k];
                                      K:=k-1
                                  End;
                               A[j+1]:=z
                            End
End;

3. Сортировка обменом
3.1. Обмен рядом стоящих элементов с фиксированным числом просмотров.
Фрагмент программы упорядочения по неубыванию элементов массива с просмотром слева направо имеет вид:

Код


For I: =N Down To 2 Do
     For J: =1 To I-1 Do
             If A[J] › A[J+1]
                   Then
                         Begin
                            B: =A[J];
                            A[J]: = A[J+1];
                            A[J+1]: =B;
                       End;

Этот метод называется сортировкой методом пузырька. Он основан на попарном сравнении смежных элементов данных; если порядок следования элементов в очередной паре неправилен, то эти элементы обмениваются местами.
В результате первого просмотра при i = n проверяются все пары от A[1], A[2] до A[n-1], A[n], т.е. будет выполнено2 (n-1) операций над элементами массива.
Если в программу ввести две вспомогательные переменные В и С, то количество операций над элементами массива сокращения. Так, при первом просмотре (i = n) для организации сравнения потребуется только n операций вместо 2(n-1). Фрагмент такой программы имеет вид:

Код

For i:=1 downto 2do
    Begin
             For j:=1 to i-1 do
                  Begin
                       B:=a[1];
                       C:=a[j+1];
                       If b› c then
                                         Begin
                                                 A[j]:= c;
                                                  A[j+1]: =b;
                                         End
                                        Else
                                                B: = c
                                     End
                End;

3.2. Обмен рядом стоящих элементов с необходимым числом просмотров.
Для прекращения просмотра после упорядочения массива вводится логическая переменная – переключатель (Р), который принимает значение TRUE, если был обмен и FALSE, если обмена не было. Фрагмент программы сортировки обменом с необходимым числом просмотров имеет вид:

Код

P: =true;
I: =1;
While (i ‹ = n-1) and (p) do
     Begin
             K: = 0;
             For j: = 1 to n-1do
              If a[j] › a[j+1]
                 Then
                       Begin
                               Z: = a[j];
                              A[j]: = a[j+1];
                              A[j+1]: =z
                         End
                     Else
                            K: = k+1;
           If k =n-i then p:= false
                         Else i: =i+1
End;

Аналогичные действия можно выполнить с помощью другой программы, располагающей элементы в убывающем порядке:

Код

P: = False;
While not p do
   Begin
        P: = true;
        For i: =1 to n –1 do
          If A[I] ‹ A[I -1]
             Then 
                  Begin
                     Z: = A[I];
                     A[I]: = A[I+1];
                     A[I+1]: = z;
                     P: = False
                 End
End;

Основной цикл прекращает выполняться, когда значение логической переменной Р становится равным TRUE. Это происходит в том случае, если ни одну пару элементов не удается переставить, что соответствует тому, что все элементы стоят на своих местах.
Если в данном примере использовать оператор REPEFT, то можно избавиться от присваивания начального значения переменной Р. Фрагмент такой программы имеет вид:

Код

Repeat
      P: =True;
      For  I:=1 to n –1 do
        If A[1]› A[I+1]
                Then
                   Begin
                   Z: =A[I];
                   A[I]:= A[I+1];
                   A[I+1]: =z;
                   P: = False
               End
Until P;

Автор: Fixin 15.2.2006, 22:05

4. Сортировка слиянием
4.1. Пусть даны два упорядоченных массива:
a[1] ≤ a[2] ≤ … ≤ a [n],
b [1] ≥ b[2] ≥… ≥b [m].

Требуется составить из указанных элементов новый массив, упорядоченный по возрастанию, т.е.
c[1] ≤ c[2] ≤ … ≤ c[n + m].
Фрагмент программы, реализуют данную сортировку будет следующим:

Код

I: =1;     j: =1;   k: =1;
While (i ‹ =m)  and (j‹ =n) do
           If  a[i] ‹ b[j] then
                                     Begin
                                              C[k]: =a[i];
                                               I: =i+1;
                                              K: =k+1
                                      End
                                 Else
                                     Begin
                                             C[k]: =b[j];
                                             J: =j+1;
                                            K: = k+1
                                     End;
While i ‹ =m do
             Begin
                     C[k]: =a[i];
                     I: =i+1;
                    K: =k+1
            End;
While j ‹ =m do
            Begin
                    C[k]: =b[j];
                    J: =j+1;
                   K: = k+1
             End;

4.2. Пусть даны два отсортированных в убывающем порядке массива:
a[1] ≥ a[2] ≥ … ≥ a [n],
b [1] ≥ b[2] ≥… ≥b [m].
Надо получить новый массив, отсортированный в том же порядке, т.е.
c[1] ≥ c[2] ≥… ≥ c[n + m].
Фрагмент программы этой сортировки имеет вид:

Код

I: =1; J: =1; K: =1;
While (I‹ =n) and (J‹ =m) do
      If  A[I] ‹ B[J]  then
                               Begin
                                  C[K]: = B[J];
                                  J: =J+1;
                                  K: =K+1
                               End
                             Else
                               Begin
                                 C[K]: = A[I];
                                  I: =I+1;
                                 K: =K+1
                              End;
While I ‹ =n do
    Begin
       C[K]: = A[I];
       I: =I+1;
      K: =K+1
End;
While J ‹ =m do
Begin
         C[K]: = B[J]                        
         J: =J+1;
        K: =K+1
End;

5. Сортировка распределением
Пусть дан массив A[1], A[2], ….,A[n] и множество различных значений (ключей): B= b[1], b[2],…b[m], причем A[I] ≤ B, т.е. каждый элемент массива А равен одному из элементов массива В. Кроме того, значения ключей упорядочены по возрастанию:
B[1] ‹ b[2] ‹ …‹ b[m].
Необходимо перераспределить элементы массива А таким образом, чтобы они располагались по убыванию.
Фрагмент программы, реализующий данное распределение имеет вид:

Код

For j: =1 to m do
      Begin
              K[j] : =0;
               For i: =1 to n do
                 If a[i] = b[j]
                  Then
                        K[j]: = k[j] +1
End;
1: =0;
for j: =1  to m do
            for i: =1 to k[j] do
                   begin
                          1: =1+1;
                          a[1]: =b[j]
end;

Другой вариант этой программы более эффективен, т.к. в нем уменьшено количество операций с элементами массива:

Код

For j: =1 to m do
       Begin
              1: =0
              c: =b[j];
              for i: =1 to n do
                   if a[i] =c
                          then
                                1: =1+1;
         k[i]: =1
 end;
1: =0;
for j: =1 to m do
        begin
                 c: =b[j];
                 p: =k[j];
                 for i: =1 to p do
                         begin
                                 1: =1+1;
                                 a[1]: =c
                         end
end;

6. Быстрая сортировка
Одним из методов быстрой сортировки является сортировка Шелла, которая требует выполнения N∙ Log2(N) операций, где N – число сортируемых элементов. Она похожа на метод пузырька, по в отличие от него, начинает сравнивать не смежные, а далеко стоящие друг от друга значения (примерно на N/2) и сортирует все эти значения, а затем уменьшает расстояние между сравниваемыми значениями. На последнем проходе расстояние между ними равно 1 и поэтому фактически этот проход выполняется по методу пузырька.
Такая сортировка предложена Д.А. Шеллом и основана на процедуре Дж. Бутройда.
Фрагмент программы сортировки элементов методом Шелла имеет вид:

Код

M: =n;  l: =true;
While l do
Begin
        M: =trunc (m/2); l1: =true;  l 2: =true;
        If  m‹ 1 then l: =false
       Else
       Begin
                K: =n-m;
                J: =0;
               While l 1 do
               Begin
                         J: = j+1;
                         If j›k then
                                 L 1: =false
                                 Else
                                 Begin
                                 I: =j; l 2: =true;
                                While l 2 do
                                 Begin
                                         If (i‹1) or (a[i] ‹= a[i+m])
                                         Then
                                           L 2: =false
                                     Else
                                          Begin
                                                  X: =a[i];
                                                  A[i]: =a[i+m];
                                                  A[i+m]: =x;
                                                   I: =i-m
                                         End
                             End;
                              L 1: =true
                     End 
            end 
    end 
end;

Сортировку элементов методом Шелла можно представить в виде программы, содержащей две метки. В этом случае программа сортировки имеет вид:

Код


Uses crt;
Lsbel 1, 2;
Var n, i, j, k, m, x: integer;
       a : array [1…100] of integer;
Begin
      Clrscr;
      Write (‘Введите N :’); readln (n);
      Writeln (‘Введите массив :’);

      For i:=1 to n do
            Begin
                     Write (‘a[‘, i, ‘] =’);  readln (a [i] );
            End;

Writeln (‘Исходный массив : ‘);
For i:=1 to n do write (a [i] : 5);
Writeln;

M: =n; 
 Repeat
            M: = trunc (m/2);
            If m‹ 1  then
                 Begin
                               Writeln (‘ Искомый массив : ’);
                               For i: =1 to n do write (a[i] : 5);
                               Halt (1)
                         End else
                         Begin
                                  K: =n-m;
                                  J: =0;
                                 1: j: =j+1
               end
until j‹ =k;
i:=j;
2:  if  i‹1  then goto 1
          else
                    if  a[i] ‹ =a [i+m] then goto 1
                                                 else
                                                       begin
                                                                    x: =a[i];
                                                                    a[i]: = a[i+m];
             
                                                          a[i+m]: =x;
                                                                       i: =i-m;
                                                                       goto 2
                                                                end;
end.

Добавлено @ 22:06
Разделил, из-за превышения лимита размера сообщения.