[Ollympiya]

Составить программу решения задачи на Delphi: Даны целые числа а1,..., аn. Для каждого из чисел, входящих в последовательность, выяснить сколько раз оно вхо¬дит в эту последовательность.

[Ollympiya]

Идея:

создаем массив x: array of Integer,
обнуляем его и каждому числу a[ i ] ставим в соответствие элемент массива x - x[ a[ i ] ]
допустим дана послед:
a[1] = 1
a[2] = 1
a[3] = 2
a[4] = 5
a[5] = 22
a[6] = 8
a[7]= 22
a[8] = 33
…

если a[1]=1, то в x[a[1]]=x[1] +1, т.е. x[1]:=x[1]+1, получили 1
если a[2]=1, то в x[a[2]]=x[1] +1, т.е. x[1]:=x[1]+1, получили 2
если a[3]=2, то в x[a[3]]=x[2] +1, т.е. x[2]:=x[2]+1, получили 1
если a[4]=5, то в x[a[4]]=x[5] +1, т.е. x[5]:=x[5]+1, получили 1
если a[5]=22, то в x[a[5]]=x[22] +1, т.е. x[22]:=x[22]+1, получили 1
если a[6]=8, то в x[a[6]]=x[8] +1, т.е. x[8]:=x[8]+1, получили 1
если a[7]=22, то в x[a[7]]=x[22] +1, т.е. x[22]:=x[22]+1, получили 2
если a[8]=33, то в x[a[8]]=x[33] +1, т.е. x[33]:=x[33]+1, получили 1
…

[lmikle]

А нельзя попроще?
Просто посчитать.
Нужны 2 массива одинкаовой размерности: массив с числами Ai и масив счетчиков.

Код:

const
  N = 100; // Длинна последовательности
var
  I, J : Integer;
  A, C : Array [1..N] Of Integer; // A - последовательность, C -счетчики
begin
  // Инициализация
  For I := 1 To N Do 
    Begin
      C[i] := 0; // Счетчик = 0 (еще не считали)
      A[i] := Random(1000) + 1; // Ai = [1..1000]
    End;

  // Считаем
  For I := 1 To N Do
    For J := 1 To N Do
       If A[i] = A[J] Then Inc(C[i]);

  // Здесь имеем кол-во вхождений Ai в последовательность.
  // Сложность алгоритма O = n^2
end;

В принципе если какой-то элемент входит несколько раз, то мы получим несколько повторений в массиве счетчиков. Тут вопрос в том, как выводить. можно исключить повторы. Можно, конечно, переработать алгоритм так, что он сначала составит список уникальных элементов, а потом уже будет считать, но, думаю, это будет излишне.

[Ollympiya]

// Сложность алгоритма O = n^2 ????

именно: элемент может входить несколько раз, тогда возникнут трудности вывода достоверного результата

вот еще вариант - упорядочить массив (по возрастанию/убыванию) и потом посчитать количество подряд стоящих одинаковых чисел

[lmikle]

1. Есть специальная теория, по которой рассчитывается сложность алгоритма (О большое). Данный алгоритм имеет сложность n^2, т.е. квадрат кол-ва итераций.

2. Нет. Ничего специально делать не надо. Просто при выводе надо контролировать что данные для элемента не выводились. Т.е. перебор мы делаем полный, а вот вывод - нет.

Например, для вывода в консоль:

Код:

const
  N = 100; // Длинна последовательности
var
  F : Boolean;
  I, J : Integer;
  A, C : Array [1..N] Of Integer; // A - последовательность, C -счетчики
begin
  For I := 1 To N Do
    Begin
      F := True;
      For J := 1 To I-1 Do
        Begin
           If A[i] = A[J] Then F := False;
           If Not F Then Break;
        End;
     If F Then WriteLn('Ai = ' + IntToStr(A[i]) + ' -> ' + IntToStr(C[i]) + ' вхождений');
    End;

Где-то так. просто при выворде контролируем, что данный элемент (по значению) еще не встречался. И все.

[lmikle]

И вообще, пора своей головой думать

[Ollympiya]

пасибки .. lmikle - модератор .... чмок