нахождение часто повторяющегося числа..., Хелп ми :) Опции

[QDe5n1K]

В общем, задание такое:
"Дан целочисленный массив.Найти самое часто повторяющееся в нем число"... Помогите, алгоритм примерно знаю, но реализовать не могу... напишите код, плз...
т.е. , если в массиве такие числа :45,32,67,21,32,33,32,0,32,0 то должно быть выведено число 32
В общем, промежуточный результат у меня такой:

Код

var
a,b,c:array[1..100] of integer;
size,numb1,numb2,x:integer;
begin
writeln(' Size: ');
readln(size);
for numb1:=1 to size do
    begin
 write(' Enter ', numb1, '-th data of array: ');
 readln(a[numb1]);
 b[numb1]:=0;
    end;
for numb1:=1 to size do
for numb2:=size downto numb1 do
    if a[numb1]=a[numb2] then
    begin
    b[numb1]:=b[numb1]+1;
    c[numb1]:=a[numb1];
    end;

for numb1:=1 to size do
for numb2:=size downto numb1 do
if b[numb1]>b[numb2] then
begin
x:=b[numb1];
b[numb1]:=b[numb2];
b[numb2]:=x;
end;
writeln(b[numb2]);


readln;
end.

т.е. я нашел, сколько раз повторяеться число, которого в массиве больше всего как же поступить дальше, как получить само это число? вопрос, конечно, ламерский, но в голову ничего не лезет.

Сообщение отредактировано: QDe5n1K - 29.10.2004 3:10

[volvo]

Я задал массив как константу...

Код

const
 n = 15;
 a: array[1 .. n] of integer =
   ( 45, 45, 45, 16, 32, 67, 21, 32, 33, 32, 0, 45, 0, 45, 17 );

var
 i, j, t: integer;
 min: integer;

 count, maxcount, value, maxvalue: integer;
begin
 for i :=1 to pred(n) do
   begin
     min := i;
     for j :=succ(i) to n do
       if a[j]<a[min] then
         min := j;
     t := a[min];
     a[min] :=a[i];
     a[i] := t;
   end;

 count := 0; maxcount := 0;
 value := a[1]; maxvalue := a[1];

 for i := 1 to n do
   begin
     if a[i] = value then inc(count)
     else
       begin
         if maxcount < count then
           begin
             maxcount := count;
             maxvalue := value;
           end;
         value := a[i]; count := 1;
       end;
   end;
 writeln( 'Значение: ', maxvalue );
 writeln( 'Встречается: ', maxcount, ' раз(а)' );
 readln
end.

[Amro]

Самый тупой и в то же время самый простой способ ....

Код

uses crt;
const
n = 15;
a: array[1 .. n] of integer =
  ( 42, 32, 42, 16, 32, 67, 21, 32, 33, 32, 42, 45, 7, 45, 17 );

var
i, j: integer;
count, maxcount, value, maxvalue: integer;
begin
clrscr;
maxcount:=1;
for i:=1 to n do
              begin
               value:=a[i]; count:=0; write(a[i]:3);
               for j:=1 to n do
                             if a[j] = value then inc(count);
     
               if count > maxcount then
                                     begin
                                        maxcount:=count;
                                        maxvalue:=a[i];
                                     end;

              end;
writeln;
writeln('Число',maxvalue);
writeln('Встречаеться',maxcount,'раз');
end.

[Digitalator]

А какие числа в массиве? если не более 1байта, то можно легко решить с помощью доп.массива, если 2 байта, то тоже можно, но потребудется много памяти.... Для очень больших массивов, с очень большими числами тоже есть достаточно быстрый алгоритм, но там используются динамические списки... так какой массив?

[volvo]

Digitalator

А что, у приведенных методов есть недостатки?

[Digitalator]

Да, если у вас массив из 1000000000 элементов

[volvo]

Digitalator

Приведите, пожалуйста Ваш вариант решения для массива из 1 млрд элементов типа LongInt(естественно, с описанием всех переменных - полностью работоспособную программу, которая будет работать в TP70) ;)

Сообщение отредактировано: volvo - 29.10.2004 21:36

[Digitalator]

Я к вам на работу не нанимался...

TP дает нам всего 640кб памяти (если использовать только возможности самого TP) 4гб тут никак, но если читать скажем из файлы по кускам, то можно. Опять же для хранения всех необходимых данных 640кб слишком мало для 4-байтового типа. но и тут их можно хранить в файле - но слишком медленно.
Решением такой проблемы будет индексирование всего нашего массива по часятм, при этом на каждой итерации нам не будет нужно слишком много памяти и работать бужет гораздо быстрее всех ваших алгоритмов. т.к. не будет вложенного цикла по одному массиву....
Я ясно изложил основные принципы подхода?

[volvo]

Digitalator
В таком случае посмотрите на код, который дал QDe5n1K. Из его кода ясно видно, что он пытается работать с массивом типа Integer из 100 элементов... Исходя из этого и была написана программа. Речи об очень больших размерах не было...

А вот грубить не надо... Я и без Ваших "изложений" способен разобраться в алгоритме... Но пользоваться такими алгоритмами стоит только там, где они действительно нужны, но не в таких задачах...

P.S. У меня в программе как раз нет никаких вложенных циклов.
(Тот, что есть - используется только для сортировки массива, но, Вам должно быть известно, что существуют ГОРАЗДО более эффективные алгоритмы сортировки)

Сообщение отредактировано: volvo - 29.10.2004 22:06

[Digitalator]

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

А вот грубить не надо...

Не собирался даже.. если вы считаете это грубостью, то хорошо, больше не буду применять подобных формулировок


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

ЗЫ: А сортировка здесь вообще не нужна, ни в каком виде

Сообщение отредактировано: Digitalator - 29.10.2004 22:11

[volvo]

Digitalator

Человек обратился в форум за помощью.

Помогите, алгоритм примерно знаю, но реализовать не могу... напишите код, плз...

А что Вы ему предлагаете?

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

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

А во вторых, если он действительно существует, почему бы Вам не предложить его автору топика?

P.S. Что именно в алгоритме кажется Вам крайне неэффективным.

Сообщение отредактировано: volvo - 30.10.2004 3:11

[Altair]

Digitalator, я делаю вам предупреждение!
Вы в нескольких топиках только критикуете не свои коды.
"В чужом глазу соломинку видите а в своем бревно не замечаете".
Если критикуете, доказывайте СВОИМ КОДОМ!

Что именно в алгоритме кажется Вам крайне неэффективным.

Я присоединяюсь к этому вопросу!

Да, если у вас массив из 1000000000 элементов

Digitalator , это вам не FPC и не 32 битная среда! Здесь никак не получиться использовать больше, чем позволяет память! НИКАК!

И вообще компьютер мало того дискретная машина, она еще имеет ограничение на обрабатываемые числа...

Примедите свой код, устраняющий недостатки, или согласитесь, что вы неправы!

[Digitalator]

Digitalator

Человек обратился в форум за помощью.


А что Вы ему предлагаете?



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

А во вторых, если он действительно существует, почему бы Вам не предложить его автору топика?

P.S. Что именно в алгоритме кажется Вам крайне неэффективным.

Неэффективным я считаю вложенный прогон по всему массиву!

to ADMIN

"В чужом глазу соломинку видите а в своем бревно не замечаете".

Дело в том что я вам показывал только один свой код в теме про двоичные деревья. Вы видите в нем недостатки?

Digitalator , это вам не FPC и не 32 битная среда! Здесь никак не получиться использовать больше, чем позволяет память! НИКАК!

вообще-то можно использовать стандартные 640кб, (ну чуть меньше) и держать временный файл (разиером до 2гб) - столько за глаза хватит, хоть и работает медленно.

И вообще компьютер мало того дискретная машина, она еще имеет ограничение на обрабатываемые числа...

такие ограничения устанавливаются стандартными типами, никто не мешает вам написать свои чилса произвольной длины и точности

Примедите свой код, устраняющий недостатки, или согласитесь, что вы неправы!

Хорошо я приведу вам код чуть позже, когда напишу... для этого мне придется скачать TP, т.к. я его давно уже потерял.....

[volvo]

Digitalator

Проснитесь наконец!!! Где Вы увидели у меня вложенный прогон по массиву?

[Digitalator]

ээээээ

Код

for i :=1 to pred(n) do {1-ый цикл}
  begin
    min := i;
    for j :=succ(i) to n do {2-й цикл}
      if a[j]<a[min] then
        min := j;
    t := a[min];
    a[min] :=a[i];
    a[i] := t;
  end;

Разве нет????????????? Я что-то неправильно понял?


http://www.khgec.net/maxint.zip
вот я написал прогу для нахождения частовсречающегося 2-х байтового знакового в файле (не будем же мы с клавиатуры миллиард чисел забивать )
Написал на делфи, т.к. че-то паскаль досявый не пашет.... но можно легко переделать прогу для паса. Используется менее 300кб памяти, все типы не длинее 4байт. В файле размером 2гб находит число менее чем за минуту. В архиве ехе-шник (если у кого делфей нет компилировать) и исходник. Проге нужен файл input.dat в тек. каталоге (не более 4гб т.к. используется longint для опр. размера, хотя прога будет работать и с файлами длиннее, просто будет некорректно работать ползунок )

[zx1024]

Это всё понятно. Школьная программа.
Лучше бы вот это

Для очень больших массивов, с очень большими числами тоже есть достаточно быстрый алгоритм, но там используются динамические списки... так какой массив

показал. Или ссылку. Интересно узнать.
Кстати
mod 256 = shr 8
div 256 = and 255

[Altair]

че-то паскаль досявый не пашет

Плохому .. . . . . . .мешают

Итак, Digitalator, ваши замечания будут приняты, если вы предоставите свой код на паскале 16 битном, работающий быстрее чем код
volvo, а пока его нет, решил задачу
volvo, а вы не сделали ничего, кроме пустых разговоров!

Неэффективным я считаю вложенный прогон по всему массиву!

Предложите свой алгоритм, реализованный на Паскале.
Пока его нет, ваши слова в серьез приниматься не будут!

ЦЕЛЬ ЛЮБОГО АЛГОРИТМА - РЕШЕНИЕ ЗАДАЧИ!! Она решена!

[Digitalator]

Предложите свой алгоритм, реализованный на Паскале.

Плохому .. . . . . . .мешают

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

Алгоритм который я вам предложил не использует ничего, чего незя сделать на Пасе! Только типы поменять и кое-что убрать. неужели вам лень заменить smallint на integer и убрать uses и нек. функции, не относящиеся к самому алгоритму а потом откомпиллировать?

Цитата 
Предложите свой алгоритм, реализованный на Паскале.
Пока его нет, ваши слова в серьез приниматься не будут!

Слушайте, давайте не будем ссориться - это никому не нужно. Алгоритм я вам написал, то что он на делфи не имеет значения т.к.
1. Используется меньше 300кб памяти. (на паскале можно побольше использовать)
2. Не используеьтся структур длинне 65кб
3. Типы не длинее 4 байт (нету тут 8-байтового ни одного)
Что еще надо чтоб работало на паскале????

Пока его нет, ваши слова в серьез приниматься не будут

Вон он по ссылке, что вам не нравится не пойму?

ЦЕЛЬ ЛЮБОГО АЛГОРИТМА - РЕШЕНИЕ ЗАДАЧИ!! Она решена!

Каждую задачу можно решить несколькими способами.

ЗЫ: давайте поговорим как разумные люди - если говорите что прога плохая, то покажите в каком месте, в какой строчке, нельзя под паскалем откомпилиировать.

Сообщение отредактировано: Digitalator - 31.10.2004 23:06

[Digitalator]

Я починил свою винду, теперь досявые проги работают (почему-то в system32 файл autoexec.nt битым оказался )

Вот тоже самое, что было на Делфи, только теперь на паскале....
http://www.khgec.net/maxint_dos.zip
в архиве исходник и ехе-шник...

работает с максимальным файлом в 2гб всего 3.5мин

[Altair]

Слушайте, давайте не будем ссориться - это никому не нужно.

Вот с этим согласен абслолютно! разумные вроде люди... :P