Экспертная система Delphi.int.ru

Сообщество программистов
Общение, помощь, обмен опытом

Здравствуйте, уважаемые эксперты!
Пожалуйста помогите решить задачу,очень надо для лабораторной...
Дано: var C: array [1..12,1..18] of char; k:integer;
Определить k-количество различных элементов массива C (т.е. повторяющиеся элементы считать один раз).

Вопрос задал: istra (статус: Посетитель) Вопрос отправлен: 3 декабря 2007, 20:05 Состояние вопроса: открыт, ответов: 2.

Ответ #1. Отвечает эксперт: Вадим К

Здравствуйте, istra!
Так как кол-во элементов типа char ограничено (не больше 256), то заводим буленовский массив и в нё будет отмечать найденные элементы. потом сосчитаем.
набросок решения

var i,j,k:integer;
    f:array[0..255] of boolean;
begin
//"обнулим"
for i:=0 to 255 do f[i] := false;
//ищем
for i:=1 to 12 do
for j :=1 to 18 do
f[ord(c[i,j])] := true;
// теперь считаем
k := 0;
for i:=0 to 255 do
if f[i] then k := k+1;
//выводим k

Ответ отправил: Вадим К (статус: Академик) Время отправки: 3 декабря 2007, 22:11 Оценка за ответ: 5

Ответ #2. Отвечает эксперт: Николай Рубан

Здравствуйте, istra!

Ну зачем же описывать целый логический массив, а потом заполнять его, как это сделал эксперт Вадим К, вполне достаточно использовать множество, да и проще на мой взгляд.
Смотрите код, на форме разместите два объекта Button1: TButton; (вкладка Standart) SGrid: TStringGrid; (вкладка Additional).

procedure TForm1.Button1Click(Sender: TObject);
const m=12; n=18;
var c: array [1..m,1..n] of char;
    i,j,kol:integer;
    c_set:set of char;
begin
  c_set:=[];
  kol:=0; //переменная которая хранит количество различных
  with SGrid do      //настраиваем StringGrid
  begin
    FixedCols:=0;
    FixedRows:=0;
    RowCount:=m;
    ColCount:=n;
    DefaultColWidth:=20;
    DefaultRowHeight:=20;
    Width:=(ColCount)*(DefaultColWidth+2);
    Height:=(RowCount)*(DefaultRowHeight+2);
  end;
  randomize;
  for i:=1 to m do
    for j:=1 to n do
    begin
      c[i,j]:=chr(random(255)); //заполняем массив произвольными символами
      SGrid.Cells[j-1,i-1]:=c[i,j]; //выводим элементы массива для удобства в StringGrid
    end;
  //непосредственно подсчет различных символов
  for i:=1 to m do
    for j:=1 to n do
      if not (c[i,j] in c_set) then
        begin
          include(c_set,c[i,j]);
          inc(kol);
        end;
  //выводим результат
  ShowMessage(format('количестко различных символов=%d',[kol]));
end;

Ответ отправил: Николай Рубан (статус: 10-ый класс) Время отправки: 3 декабря 2007, 23:11 Оценка за ответ: 4

Мини-форум вопроса

Вадим К (статус: Академик), 3 декабря 2007, 23:19 [#1]: to Николай Рубан Мало того, что человек под турбопаскаль пишет, вы привели пример на делфи, так в конечном счёте написали более длинный алгоритм и медленее. так ещё и по функциональности set of char практически эквивалентен буленовскому массиву. Галочка "подтверждения прочтения" - вселенское зло.

Николай Рубан (статус: 10-ый класс), 3 декабря 2007, 23:37 [#2]: Да согласен с тематикой я промазал - каюсь! Но по поводу эквивалентности и скорости, тут вопрос спорный... Помоему проверка входит ли элемент в множество быстрее проходит, чем проход массива... Или я ошибаюсь??

Вадим К (статус: Академик), 4 декабря 2007, 00:10 [#3]: если присмотреться внимательней, то я не прохожусь по массиву, для проверки, есть ли такой элемент, а индексирую его. это очень разные вещи. Потестировал производительность кода. мой в 3-4 раза быстрей при подсчёте считает. Хотя для препода думаю мой вариант будет проще. не все о множествах знают Галочка "подтверждения прочтения" - вселенское зло.

Николай Рубан (статус: 10-ый класс), 4 декабря 2007, 00:20 [#4]: И я провел такие не сложные испытания, вот код: f:array [0..255] of boolean; i,k,j:longint; sts:set of char; ... sts:=sts+['z']; k:=0; for i:=1 to 1000000 do if 'z' in sts then inc(k); writeln(k); ... Время исполнения 00 час(ов) 00 мин 00 сек 00 мсек (Celeron 1700). И такой код: f:array [0..255] of boolean; i,k,j:longint; sts:set of char; ... sts:=sts+['z']; k:=0; for i:=1 to 1000000 do if 'z' in sts then inc(k); writeln(k); ... Время исполнения 00 час(ов) 00 мин 02 сек 91 мсек(Celeron 1700) Что то неувязочка получается...

Николай Рубан (статус: 10-ый класс), 4 декабря 2007, 00:23 [#5]: ПРЕДЫДУЩЕЕ СООБЩЕНИЕ ПРОШУ УДАЛИТЬ!!! И я провел такие не сложные испытания, вот код: f:array [0..255] of boolean; i,k,j:longint; sts:set of char; ... sts:=sts+['z']; k:=0; for i:=1 to 1000000 do if 'z' in sts then inc(k); writeln(k); ... Время исполнения 00 час(ов) 00 мин 00 сек 00 мсек (Celeron 1700). И такой код: f:array [0..255] of boolean; i,k,j:longint; sts:set of char; ... f[ord('z')]:=true; k:=0; for i:=1 to 1000000 do for j:=0 to 255 do if f[j] then inc(k);} writeln(k); ... Время исполнения 00 час(ов) 00 мин 02 сек 91 мсек(Celeron 1700) Что то неувязочка получается...

Вадим К (статус: Академик), 4 декабря 2007, 00:43 [#6]: конечно неувязочка. в первом примере один цикл, в втором - два. В моем примере каждая буква стает строго на своё место. искать её по массиву не нужно! её индекс известен. поэтому строку for i:=1 to 1000000 do for j:=0 to 255 do if f[j] then inc(k); нужно писать так for i:=1 to 1000000 do if f[ord('z')] then inc(k); Галочка "подтверждения прочтения" - вселенское зло.

Николай Рубан (статус: 10-ый класс), 4 декабря 2007, 01:10 [#7]: Согласен возможно я просто неудачно привел пример, но вернемся к нашим начальным программам: Вадим К. for i:=1 to 12 do for j :=1 to 18 do f[ord(c[i,j])] := true; // теперь считаем k := 0; for i:=0 to 255 do if f[i] then k := k+1; Николай Рубан. for i:=1 to 12 do for j:=1 to 18 do if not (c[i,j] in c_set) then begin include(c_set,c[i,j]); kol:=kol+1; end; В Вашем алгоритме все-таки необходимо еще ОДИН раз пройти логический массив, чего в моем делать не стоит, так что в итоге вы выполняете лишние операции, так что я думаю что по скорости он также проиграет.... (имхо). Я просто хочу подчеркнуть то, что данная задача классическая для использования МНОЖЕСТВ.

Вадим К (статус: Академик), 4 декабря 2007, 01:23 [#8]: мой пример можно переписать так, что бы он соответсвовал вашему for i:=1 to 12 do for j:=1 to 18 do if not f[ord(c[i,j])] then begin f[ord(c[i,j])] := true; kol:=kol+1; end; Я думаю, что вам понятно, что взятие значения элемента по индексу быстрее, чем операция in Цитата: так что я думаю что по скорости он также проиграет вначале пробуем с компиляторм, а потом смотрим. Во вторых, не всегда больший код на внешний вид будет большим в скомпилированном виде. в третих, есть простое правило: либо код больше, но быстрее, либо наоборот. но это правило справедливо, когда оптимизация выжимает последние соки, а не просто три километра листинга сравнивать с двумя строками. Галочка "подтверждения прочтения" - вселенское зло.

Николай Рубан (статус: 10-ый класс), 4 декабря 2007, 01:31 [#9]: Вот тут согласен на все 100. Браво!

Вадим К (статус: Академик), 4 декабря 2007, 01:39 [#10]: Я думаю наша полемика весьма будет полезна для подрастающего поколения. Спасибо за конструктивную критику. Галочка "подтверждения прочтения" - вселенское зло.

Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.