Помощь - Поиск - Пользователи - Календарь
Полная версия: нахождение часто повторяющегося числа...
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
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.

т.е. я нашел, сколько раз повторяеться число, которого в массиве больше всего smile.gif как же поступить дальше, как получить само это число? вопрос, конечно, ламерский, но в голову ничего не лезет.
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
Самый тупой и в то же время самый простой способ .... smile.gif
Код
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 байта, то тоже можно, но потребудется много памяти.... Для очень больших массивов, с очень большими числами тоже есть достаточно быстрый алгоритм, но там используются динамические списки... так какой массив? smile.gif
volvo
Digitalator

А что, у приведенных методов есть недостатки? huh.gif
Digitalator
Да, если у вас массив из 1000000000 элементов
volvo
Digitalator

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

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

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

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

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

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


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

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

Человек обратился в форум за помощью.
Цитата
Помогите, алгоритм примерно знаю, но реализовать не могу... напишите код, плз...


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

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


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

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

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

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

Я присоединяюсь к этому вопросу!
Цитата
Да, если у вас массив из 1000000000 элементов

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

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

Примедите свой код, устраняющий недостатки, или согласитесь, что вы неправы!
Digitalator
Цитата(volvo @ 30.10.04 3:07)
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-х байтового знакового в файле (не будем же мы с клавиатуры миллиард чисел забивать smile.gif )
Написал на делфи, т.к. че-то паскаль досявый не пашет.... но можно легко переделать прогу для паса. Используется менее 300кб памяти, все типы не длинее 4байт. В файле размером 2гб находит число менее чем за минуту. В архиве ехе-шник (если у кого делфей нет компилировать) и исходник. Проге нужен файл input.dat в тек. каталоге (не более 4гб т.к. используется longint для опр. размера, хотя прога будет работать и с файлами длиннее, просто будет некорректно работать ползунок smile.gif)
zx1024
Это всё понятно. Школьная программа.
Лучше бы вот это
Цитата
Для очень больших массивов, с очень большими числами тоже есть достаточно быстрый алгоритм, но там используются динамические списки... так какой массив

показал. Или ссылку. Интересно узнать.
Кстати
mod 256 = shr 8
div 256 = and 255
Altair
Цитата
че-то паскаль досявый не пашет

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

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

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

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

ЦЕЛЬ ЛЮБОГО АЛГОРИТМА - РЕШЕНИЕ ЗАДАЧИ!! Она решена!
Digitalator
Цитата
Предложите свой алгоритм, реализованный на Паскале.


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

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

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

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


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

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

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

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

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

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

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

работает с максимальным файлом в 2гб всего 3.5мин
Altair
Цитата
Слушайте, давайте не будем ссориться - это никому не нужно.

Вот с этим согласен абслолютно! разумные вроде люди... smile.gif :P
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.