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

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

Логин:
Пароль:
Регистрация | Забыли пароль?

Delphi.int.ru Expert

Другие разделы портала

Переход к вопросу:

#   

Статистика за сегодня:  


Лучшие эксперты

DNK
I. DNK
Баллы: 5

Подробнее »



Вопрос # 1 170

/ вопрос открыт /

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

istra Вопрос ожидает решения (принимаются ответы, доступен мини-форум)

Вопрос задал: 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;

Good Luck!!!

Приложение:
  1.  
  2. unit Unit1;
  3.  
  4. interface
  5.  
  6. uses
  7. Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  8. Dialogs, Grids, StdCtrls;
  9.  
  10. type
  11. TForm1 = class(TForm)
  12. Button1: TButton;
  13. SGrid: TStringGrid;
  14. procedure Button1Click(Sender: TObject);
  15. private
  16. { Private declarations }
  17. public
  18. { Public declarations }
  19. end;
  20.  
  21. var
  22. Form1: TForm1;
  23.  
  24. implementation
  25.  
  26. {$R *.dfm}
  27.  
  28. procedure TForm1.Button1Click(Sender: TObject);
  29. const m=12; n=18;
  30. var c: array [1..m,1..n] of char;
  31. i,j,kol:integer;
  32. c_set:set of char;
  33. begin
  34. c_set:=[];
  35.  
  36.  
  37. begin
  38. FixedCols:=0;
  39. FixedRows:=0;
  40. RowCount:=m;
  41. ColCount:=n;
  42. DefaultColWidth:=20;
  43. DefaultRowHeight:=20;
  44. Width:=(ColCount)*(DefaultColWidth+2);
  45. Height:=(RowCount)*(DefaultRowHeight+2);
  46. end;
  47. randomize;
  48. for i:=1 to m do
  49. for j:=1 to n do
  50. begin
  51.  
  52.  
  53. end;
  54.  
  55. for i:=1 to m do
  56. for j:=1 to n do
  57. if not (c[i,j] in c_set) then
  58. begin
  59. include(c_set,c[i,j]);
  60. inc(kol);
  61. end;
  62.  
  63.  
  64. end;
  65.  
  66. end.
  67.  


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


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

Всего сообщений: 10; последнее сообщение — 4 декабря 2007, 01:39; участников в обсуждении: 2.
Вадим К

Вадим К (статус: Академик), 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]:

Я думаю наша полемика весьма будет полезна для подрастающего поколения.
Спасибо за конструктивную критику.
Галочка "подтверждения прочтения" - вселенское зло.

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

Версия движка: 2.6+ (26.01.2011)
Текущее время: 21 августа 2017, 14:57
Выполнено за 0.07 сек.
Рейтинг@Mail.ru