Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 02.04.2013, 22:23   #1
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию ГИА'шная\ЕГЭ'шная задача

Час добрый!

Снова я решил не прогулять информатику И получил там задание из части C4 (ГИА или ЕГЭ - история умалчивает) Собственно вот оно :
Цитата:
Имеется список сотрудников организации с указанием их фамилии,
имени и даты рождения. Администрация ежедневно поздравляет всех
сотрудников, родившихся в этот день. Напишите эффективную по
времени работы и по используемой памяти программу (укажите
используемую версию языка программирования, например, Borland
Pascal 7.0), которая будет определять, в какой из дней года родилось
больше всего сотрудников и выводить этот день (или несколько дней).
На вход программе в первой строке подается количество людей в списке N. Значение N может быть велико, например, может быть
больше 10.000. В каждой из последующих N строк находится
информация в следующем формате:
<Фамилия> <Имя> <Дата рождения>
где <Фамилия> – строка, состоящая не более, чем из 20 символов без
пробелов,
<Имя> – строка, состоящая не более, чем из 20 символов без пробелов,
<Дата рождения> – стока, имеющая вид ДД.ММ.ГГГГ, где ДД –
двузначное число от 01 до 31, ММ – двузначное число от 01 до 12, ГГГГ –
четырехзначное число от 1800 до 2100.
Пример входной строки:
Иванов Сергей 27.03.1993
Программа должна вывести один или несколько дней года (по одному
в строке) в формате ДД.ММ, при этом можно не выводить начальный
ноль в номере дня или месяца.
Пример выходных данных:
27.3
Мое решение :
Код:
const
     months : array [1..12] of Byte = (31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31);

type
    TDate = array [1..366] of Byte;

procedure ParseString (s : string; var day, month : Integer);
var
   p : Integer;
   
begin
     p := Pos ('.', s);
     
     day := (Ord(s[p-2]) - 48) * 10 + Ord(s[p-1]) - 48;
     month := (Ord(s[p+1]) - 48) * 10 + Ord(s[p+2]) - 48;
end;

procedure ConvertDate (date : Integer; var day, month : Integer);
var
   i, sum : Integer;
begin
     i := 1;
     sum := 0;
     
     while sum < date do begin
           sum := sum + months[i];
           Inc (i);
     end;
     
     month := i-1;
     day := date - sum + months[i-1]
     
end;

var
   n, i, j, day, month, CountOfDays, max : Integer;
   s : string;
   date : TDate;
   
begin
     ReadLn (n);

     for i := 1 to n do begin
         ReadLn (s);
         ParseString(s, day, month);

         CountOfDays := 0;

         for j := 1 to month-1 do
             CountOfDays := CountOfDays + months[i];
         Inc(CountOfDays, day);
         Inc (date[CountOfDays])
     end;

     max := date[1];
     
     for i := 1 to 366 do
         if date[i] > max then
            max := date[i];
            
     for i := 1 to 366 do
         if date[i] = max then begin
            ConvertDate (i, day, month);
            WriteLn (day, '.', month)
         end

end.
Вроде все работает, НО мне не нравится пара вещей :
1) Как-то избавиться от массива months?
2) Стоит более экономно расходовать память (не делать сразу массив на 366 элементов)?
3) В конце два цикла, кажется без них не обойтись, но может это только кажется?

Не подскажете, как решить проблемы с вышеупомянутыми пунктами?
Заранее спасибо!

Последний раз редактировалось Poma][a; 03.04.2013 в 07:08.
Poma][a вне форума Ответить с цитированием
Старый 02.04.2013, 23:16   #2
eoln
Старожил
 
Аватар для eoln
 
Регистрация: 26.04.2008
Сообщений: 2,689
По умолчанию

Цитата:
Сообщение от Poma][a Посмотреть сообщение
1) Как-то избавиться от массива months?
2) Стоит более экономно расходовать память (не делать сразу массив на 366 элементов)?
1) выровнить массив
2) 366 байт экономить? Нет, не стоит, не те времена. Кстати, именинником может быть в какой-то день более 255, поэтому word (integer и т.п.)

Цитата:
Сообщение от Poma][a Посмотреть сообщение
3) В конце два цикла, кажется без них не обойтись, но может это только кажется?
Это очень быстрые операции, всего какие-то миллисекунды.

Не проверял, могут быть мелкие или крупные или фатальные ошибки...
Если чуть увеличить массив выравнив его края, то можно обращаться к нему быстрее и проще (в плане вычисления адресов ячеек). Килобайтный массив в данной программе вполне эффективен. В массиве в ячейках с 0 по 30 хранятся кол-во дней рождений январских именинников, с 31 по 61 - февральских (ну и пусть 31 февраля нет ) и т.д
Код:
type
    TDate = array [0..31*12-1] of word;//считаем что есть 12 месяцев по 31 дню в каждом

var
   n, i, day, month, max : Integer;
   s : string;
   date : tdate;

procedure ParseString (s : string; var day, month : Integer);
var
   p : Integer;

begin
     p := Pos ('.', s);

     day := (Ord(s[p-2]) - 48) * 10 + Ord(s[p-1]) - 48;
     month := (Ord(s[p+1]) - 48) * 10 + Ord(s[p+2]) - 48;
end;

begin
     ReadLn (n);
     for i := 1 to n do begin
         ReadLn (s);
         ParseString(s, day, month);
         inc(date[(month-1)*31+day-1]);
     end;

     max := 0;//это позиция одного из макс

     for i := 1 to 31*12-1 do
         if date[i] > date[max] then
            max := i;

     for i := 0 to 31*12-1 do
         if date[i] = date[max] then begin
            WriteLn ({day}max mod 31 + 1, '.', {month}max div 31 + 1)
         end
end.
eoln вне форума Ответить с цитированием
Старый 03.04.2013, 07:18   #3
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Цитата:
1) выровнить массив
Точно! За сщет лишней памяти мы избавимся от лишних действий.
Цитата:
Кстати, именинником может быть в какой-то день более 255, поэтому word (integer и т.п.)
Ага. Мой косяк.
Цитата:
366 байт экономить? Нет, не стоит, не те времена.
На спичках не экономят
Цитата:
Код : <>
Огроменное спасибо!
Poma][a вне форума Ответить с цитированием
Старый 03.04.2013, 18:44   #4
s-andriano
Старожил
 
Аватар для s-andriano
 
Регистрация: 08.04.2012
Сообщений: 3,229
По умолчанию

Цитата:
Сообщение от Poma][a Посмотреть сообщение
1) Как-то избавиться от массива months?
Не нужно от него избавляться.
А вот хранить в нем нужно не длины месяцев, а номер перволго дня месяца, т.е. 0, 31, 59, 90...
Тогда вычисление смещения будет происходить за одну операцию сложения без цикла.
Цитата:
2) Стоит более экономно расходовать память (не делать сразу массив на 366 элементов)?
Вряд ли это целесообразно. А вот увеличить разрядность счетчиков хтя бы до двух байт, на мой взгляд, разумно. Что будет, если все 10000 окажутся родившимися в один день?

PS.
Цитата:
Значение N может быть велико, например, может быть
больше 10.000.
Улыбнуло.
s-andriano вне форума Ответить с цитированием
Старый 03.04.2013, 21:00   #5
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Цитата:
А вот хранить в нем нужно не длины месяцев, а номер перволго дня месяца, т.е. 0, 31, 59, 90...
Тогда вычисление смещения будет происходить за одну операцию сложения без цикла.
Очень интересный вариант! Спасибо!
Цитата:
А вот увеличить разрядность счетчиков хтя бы до двух байт, на мой взгляд, разумно. Что будет, если все 10000 окажутся родившимися в один день?
Ага. Что-то я косякнул.
Poma][a вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
задача на зачёт. проблема Задача на нобелевскую премию! Sabotage5 Паскаль, Turbo Pascal, PascalABC.NET 2 18.03.2013 15:18
Задача по подсчёту статистики использования букв. Другая задача - по длинной арифметике Pascal ABC kimberly Паскаль, Turbo Pascal, PascalABC.NET 3 24.12.2012 17:03
задача на структуру(struct)/задача на работу с файлом SevenArth Помощь студентам 0 26.04.2012 19:06
Задача на оптимальный расчет маршрута (задача в презентации) в табличном процессоре Excel Toofed Помощь студентам 0 30.11.2011 01:12
Задача минимизации дисбаланса на линии сборки (задача минимакса) LenZab Microsoft Office Excel 13 13.03.2011 22:51