|
|
Регистрация | << Правила форума >> | FAQ | Пользователи | Календарь | Поиск | Сообщения за сегодня | Все разделы прочитаны |
|
Опции темы | Поиск в этой теме | Опции просмотра |
#1
|
|||
|
|||
Задачи с массивами ....
Составить программу решения задачи на Delphi: Даны целые числа а1,..., аn. Для каждого из чисел, входящих в последовательность, выяснить сколько раз оно вхо¬дит в эту последовательность.
|
#2
|
|||
|
|||
Идея:
создаем массив 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 … |
#3
|
|||
|
|||
А нельзя попроще?
Просто посчитать. Нужны 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; В принципе если какой-то элемент входит несколько раз, то мы получим несколько повторений в массиве счетчиков. Тут вопрос в том, как выводить. можно исключить повторы. Можно, конечно, переработать алгоритм так, что он сначала составит список уникальных элементов, а потом уже будет считать, но, думаю, это будет излишне. |
#4
|
|||
|
|||
// Сложность алгоритма O = n^2 ????
именно: элемент может входить несколько раз, тогда возникнут трудности вывода достоверного результата вот еще вариант - упорядочить массив (по возрастанию/убыванию) и потом посчитать количество подряд стоящих одинаковых чисел |
#5
|
|||
|
|||
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; Где-то так. просто при выворде контролируем, что данный элемент (по значению) еще не встречался. И все. |
#6
|
|||
|
|||
И вообще, пора своей головой думать
|
#7
|
|||
|
|||
пасибки .. lmikle - модератор .... чмок
|