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

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

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

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 12.07.2012, 10:23   #1
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию Наименьшая с.с.

И так господа программисты, поскольку поток студентов\школьников-хомячков закончился, а душа жаждет программирования, то вопрос : как бы Вы решили данную задачу (с точки хрения красоты и эффективности)? http://acmp.ru/index.asp?main=task&id_task=315 (опять же сорри за не очень красивую ссылку, т.к. пишу с "работы")

Для нелюбителей ссылок: Известно, что основанием позиционной системы счисления называют количество различных символов, используемых для записи чисел в данной системе счисления. Также известно, что любое число x в b-ичной системе счисления имеет вид x=a0∙b0+a1∙b1+…+an∙bn, где b ≥ 2 и 0 ≤ ai < b.

Для записи чисел в b-ичной системе счисления, где b ≤ 36, могут быть использованы первые b символов из следующего списка 0,1,…, 9, A, B, …, Z. Например, для записи чисел в троичной системы используются символы 0, 1, 2, а в двенадцатеричной - 0,1,…, 9, A, B.

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


Данную задачу я решил вот так :
Код:
const
    CC = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';

var
    s : string;
    i, max, check : Integer;


begin
    assign(input, 'input.txt'); reset(input);
    assign(output, 'output.txt'); rewrite(output);

            ReadLn (s);

    check := 1;
    for i := 1 to Length(s) do
        if not (s[i] in ['0'..'9', 'A'..'Z']) then  
        if check = 1 then begin
                        WriteLn ('-1');                         
                        check := 0
        end;


    if check =  1 then begin
        max := Ord ('0');
        for i := 1 to Length(s) do begin
        if Ord(s[i]) > max then
            max := Ord(s[i]);
        end;
        i := Pos (Chr (max), CC);
           if (i = 1) or (i = 2) then
            WriteLn (2)
        else
            WriteLn (i)
        end

end.
Я простой школьник, интересующийся программированием, у которого в планах дальнейшее обучение на также программиста, вот и хочется набраться опыта у Тру Папок Великого Искусства Программирования....

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

Я бы чуть упростил
Код:
const
    CC = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
var
  s : string;
  d, i, max : Integer;
begin
  assign(input, 'input.txt'); reset(input);
  assign(output, 'output.txt'); rewrite(output);
  Readln (s);
  max := 2;
  for i := 1 to Length(s) do begin
    d:=pos(s[i], CC);
    if d = 0 then begin
      max := -1;                         
      break
    end else 
      if  d > max then max := d
  end;
  WriteLn (max)
end.

Последний раз редактировалось eoln; 12.07.2012 в 12:30. Причина: ошибка
eoln вне форума Ответить с цитированием
Старый 12.07.2012, 13:27   #3
s-andriano
Старожил
 
Аватар для s-andriano
 
Регистрация: 08.04.2012
Сообщений: 3,229
По умолчанию

Я бы не решился назвать замену алгоритма O(N) на O(N^2) упрощением.
s-andriano вне форума Ответить с цитированием
Старый 12.07.2012, 14:50   #4
eoln
Старожил
 
Аватар для eoln
 
Регистрация: 26.04.2008
Сообщений: 2,689
По умолчанию

s-andriano, Вы наверное к максимальной оптимизации стремитесь? В магазин не со своими атомными весами ходите?

Упростить, значит сделать жизнь проще, а не быстрее. Код компактный, быстродействие (учитывая макс. длину строки 255 символов) хорошее.

P.S. Не собираюсь спорить по вопросы оптимизации, в данном случае она не критична.
eoln вне форума Ответить с цитированием
Старый 12.07.2012, 17:04   #5
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Цитата:
Я бы не решился назвать замену алгоритма O(N) на O(N^2) упрощением.
Цитата:
как бы Вы решили данную задачу (с точки хрения красоты и эффективности)?
Вот господин eoln решил с точки зрения красоты, за что ему огромное спасибо!
Но за хороший комент, s-andriano Вам не менее огромное спасибо!
Poma][a вне форума Ответить с цитированием
Старый 12.07.2012, 19:04   #6
s-andriano
Старожил
 
Аватар для s-andriano
 
Регистрация: 08.04.2012
Сообщений: 3,229
По умолчанию

Цитата:
Сообщение от eoln Посмотреть сообщение
s-andriano, Вы наверное к максимальной оптимизации стремитесь? В магазин не со своими атомными весами ходите?
eoln, откуда столько агрессии?
Если Вы предлагаете решение, которое лучше по всем параметрам - нет вопросов. Но если Ваше решение кроме плюсов имеет и явные минусы - это нужно, минимум оговаривать.
Я не утверждаю, что менее оптимальные решения не стоит приводить, я лишь предостерегаю от однозначных характеристик (типа "проще") в явно неоднозначных случаях.
Цитата:
P.S. Не собираюсь спорить по вопросы оптимизации, в данном случае она не критична.
Ну откуда Вы знаете? Может, этот алгоритм понадобится для проверки нескольких миллионов строк?
Впрочем, и обратного я не утверждаю: вполне вероятно, ТС Ваше решение подойдет больше. Но о том, что ему критично, а что - нет, решать ему.
s-andriano вне форума Ответить с цитированием
Старый 12.07.2012, 20:40   #7
eoln
Старожил
 
Аватар для eoln
 
Регистрация: 26.04.2008
Сообщений: 2,689
По умолчанию

Цитата:
Сообщение от s-andriano Посмотреть сообщение
eoln, откуда столько агрессии?
Не-не-не. Смайлик в конце предложения умножает агрессию на 0.

Цитата:
Сообщение от s-andriano Посмотреть сообщение
Может, этот алгоритм понадобится для проверки нескольких миллионов строк?
Если так, то полностью согласен - ускорять однозначно.
eoln вне форума Ответить с цитированием
Старый 12.07.2012, 20:44   #8
Somebody
Участник клуба
 
Регистрация: 08.10.2007
Сообщений: 1,185
По умолчанию

Цитата:
Сообщение от s-andriano Посмотреть сообщение
Я бы не решился назвать замену алгоритма O(N) на O(N^2) упрощением.
Где N^2? Не вижу...
Somebody вне форума Ответить с цитированием
Старый 12.07.2012, 20:49   #9
eoln
Старожил
 
Аватар для eoln
 
Регистрация: 26.04.2008
Сообщений: 2,689
По умолчанию

Код:
  for i := 1 to Length(s) do begin
    d:=pos(s[i], CC);
Видимо тут. Правда не N^2, а N*36 (циклический поиск в pos'e)
eoln вне форума Ответить с цитированием
Старый 12.07.2012, 21:02   #10
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Для сравнения эффективности алгоритмов решил выложить время по тестам :
Poma][a
:
Код:
Тест	Результат	Время	
1	Accepted	0,087	         
2	Accepted	0,159	         
3	Accepted	0,165          
4	Accepted	0,179	         
5	Accepted	0,166	         
6	Accepted	0,164	         
7	Accepted	0,172	         
8	Accepted	0,161	         
9	Accepted	0,17	         
10	Accepted	0,163

eoln
Код:
Тест	Результат	Время	
1	Accepted	0,093	        
2	Accepted	0,277         
3	Accepted	0,199	       
4	Accepted	0,198	       
5	Accepted	0,201	        
6	Accepted	0,191         
7	Accepted	0,191         
8	Accepted	0,186	        
9	Accepted	0,189     	
10	Accepted	0,185
Poma][a вне форума Ответить с цитированием
Ответ


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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
даны три квадратные матрицы третьего порядка.вывести на экран ту из них,норма которой наименьшая. в качестве нормы матрицы взять м ayoka Паскаль, Turbo Pascal, PascalABC.NET 0 16.05.2012 18:28
Массив (наименьшая сумма) Dmitriy_B C++ Builder 4 18.02.2012 01:25
наименьшая цифра числа в delphi SALOmandra Помощь студентам 2 22.04.2008 15:57