КИТА unofficial

Ваши интересы => Викторины и конкурсы => Тема начата: LazarusLong от Май 22, 2007, 08:21:19

Название: Искусство программирования. (5)
Отправлено: LazarusLong от Май 22, 2007, 08:21:19

Что-то я смотрю викторины по техническим предметам сошли на нет. Нехорошо это как-то ;). Попытаемся реанимировать этот жанр:

Дано целое число K. Определить размер периода в десятичном представлении 1/K. Использовать только целочисленные переменные.
К примеру:
1/13 = 0,076923076923076923076923076923077 Период - 076923 - его размер - 6

1/6 = 0,16666666666666666666666666666666 Период - 6 его размер -1

и т.п.

Название: Re: Искусство программирования. (очередная)
Отправлено: chilik от Май 22, 2007, 10:31:36

Код:

int period (int k)
{int ost[200];
int o=10;
for (int i=0;;i++)
 {ost[i]=o;
  o=(o%k)*10;
  if (o==0) return 0;
  for (int j=0;j<=i;j++)
    if (o==ost[j])
      return 1+i-j;
 }
}

Название: Re: Искусство программирования. (очередная)
Отправлено: chilik от Май 22, 2007, 10:36:19

Off-Topic - помечено автором как "не соответствует обсуждаемой теме"

а почему у меня половина сообщения курсивом отображается??

Название: Re: Искусство программирования. (очередная)
Отправлено: naxellar от Май 22, 2007, 10:41:56

Off-Topic - помечено автором как "не соответствует обсуждаемой теме"

Код:

{ost[i]=o;

Код:

[i]

- курсив ВВ.
Используй тэгу "Код"

Название: Re: Искусство программирования. (очередная)
Отправлено: chilik от Май 22, 2007, 10:44:10

Off-Topic - помечено автором как "не соответствует обсуждаемой теме"

да, действительно, не заметил =) щас исправлю

Название: Re: Искусство программирования. (очередная)
Отправлено: LazarusLong от Май 22, 2007, 11:02:38

Хм... вычисляет правильно, но не выполнено граничное условие - использовать только переменные целочисленного типа.
Ведь int [] != int.
Увы...

Название: Re: Искусство программирования. (очередная)
Отправлено: chilik от Май 22, 2007, 11:07:20

хм, я думал, что это подразумевает не использовать флоат. ну лана, буду менять

Название: Re: Искусство программирования. (очередная)
Отправлено: chilik от Май 22, 2007, 11:35:36

Код:

int period (int k)
{int ost=10;
for (int j=0;;j++)
  {int o=10;
   for (int i=j;i<=200;i++)
    {o=(o%k)*10;
     if (o==0) return 0;
     if (o==ost) return 1+i-j;
    }
   ost=(ost%k)*10;
  }
}

Название: Re: Искусство программирования. (очередная)
Отправлено: LazarusLong от Май 22, 2007, 11:42:22

Совсем другое дело! +1 ;)

Название: Re: Искусство программирования. (очередная)
Отправлено: LazarusLong от Май 22, 2007, 11:44:50

:(
Извините, Вы не можете повторно изменить карму этому пользователю. Необходимо подождать 48 часов.

Название: Re: Искусство программирования. (очередная)
Отправлено: chilik от Май 22, 2007, 11:46:40

последний релиз, оптимальнее немного =)

Код:

int period (int k)
{int ost=10;
for (int i=0;;i++)
  {ost=(ost%k)*10;
   if (ost==0) return 0;
   int o=10;
   for (int j=0;j<i;j++)
     {o=(o%k)*10;
      if (o==ost) return i-j;
     }
  }
}

PS +1 будешь должен ;)

Off-Topic - помечено автором как "не соответствует обсуждаемой теме"

вот и подкрался мой первый серьезный юбилей - 100 сообщений =)

Название: Re: Искусство программирования. (очередная)
Отправлено: naxellar от Май 22, 2007, 11:48:29

Я паставлю. Не против, LazarusLong??

Название: Re: Искусство программирования. (очередная)
Отправлено: LazarusLong от Май 22, 2007, 11:49:10

Цитировать

PS +1 будешь должен

Проценты нарастают? :D

naxellar - ставь!

Название: Re: Искусство программирования. (очередная)
Отправлено: LazarusLong от Май 23, 2007, 02:29:14

Еще чуть-чут оптимальнее (не меняя алгоритма, конечно) было бы заменить строку

if (ost==0) return 0;

На

if (!ost) return 0;

:-)

Название: Re: Искусство программирования. (очередная)
Отправлено: naxellar от Май 23, 2007, 02:32:58

Цитата: LazarusLong от Май 23, 2007, 02:29:14

Еще чуть-чут оптимальнее (не меняя алгоритма, конечно) было бы заменить строку

if (ost==0) return 0;

На

if (!ost) return 0;

:-)

И что быстрее будет

Название: Re: Искусство программирования. (очередная)
Отправлено: LazarusLong от Май 23, 2007, 02:35:38

Константа не используется, хотя оптимальность данных выражений зависит от деталей реализации конкретного компилятора.

Название: Re: Искусство программирования. (очередная)
Отправлено: Sochin от Май 23, 2007, 04:24:56

Цитата: LazarusLong от Май 23, 2007, 02:35:38

имхо, современный компилятор произведет оптимизацию обоих вариантов.

Название: Re: Искусство программирования. (очередная)
Отправлено: LazarusLong от Май 23, 2007, 06:03:57

Конечно. Компилятор, скорее всего, причешет оба варианта и приведет их к общему знаменателю. Но ведь наверняка мы (я, по крайней мере) этого не знаем. Поэтому лучше сразу писать как можно оптимальнее. Без фанатизма конечно ;)

Название: Re: Искусство программирования. (очередная)
Отправлено: Sochin от Май 23, 2007, 06:15:27

Цитата: LazarusLong от Май 23, 2007, 06:03:57

Без фанатизма конечно ;)

Саша, ну вот это

Цитата: LazarusLong от Май 23, 2007, 02:29:14

Еще чуть-чут оптимальнее (не меняя алгоритма, конечно) было бы заменить строку

if (ost==0) return 0;

На

if (!ost) return 0;

:-)

думаю уже недалеко от фанатизма. )) Тем более, что речи о языке реализации не было, а предлагаемое тобой усовершенствование для реализации на С++ подходит, а вот например для реализации на С# аж никак не подходит. ))

Название: Re: Искусство программирования. (очередная)
Отправлено: NunTerix от Май 23, 2007, 06:53:16

Цитата: LazarusLong от Май 23, 2007, 02:29:14

Еще чуть-чут оптимальнее (не меняя алгоритма, конечно) было бы заменить строку

if (ost==0) return 0;

На

if (!ost) return 0;

:-)

Код будет аж на 2 символа меньше :D

Название: Re: Искусство программирования. (очередная)
Отправлено: LazarusLong от Май 23, 2007, 08:02:53

Sochin

Ну не знаю не знаю.... , я к примеру, всегда так пишу ;).

Хотя тут еще ладно, все таки переменная ost типа int, а ведь бывает еще иногда пишут что-то вроде if (a==false) ;)

И не думаю, что chilik писал на С# ::)
NunTerix

Как мне представляется, оптимальность кода выражается не в количестве символов в тексте программы, а в количестве выполняемых операций и занимаемой программой памяти.

Название: Re: Искусство программирования. (очередная)
Отправлено: NunTerix от Май 23, 2007, 08:18:28

Цитата: LazarusLong от Май 23, 2007, 08:02:53

NunTerix

Как мне представляется, оптимальность кода выражается не в количестве символов в тексте программы, а в количестве выполняемых операций и занимаемой программой памяти.

Это ясненько... а фактически? Разве замена (!ost) на (ost==0) или наоборот уменьшает количество выполняемых операций? Или уменьшает занимаемую память??

Название: Re: Искусство программирования. (очередная)
Отправлено: LazarusLong от Май 23, 2007, 10:12:29

По видимому уменьшает занимаемую память - так как не требуется хранение в памяти константы 0, используемой для сравнения. Конечно, как заметил Sochin, компилятор должен этот момент оптимизировать, но все-таки ;)

Название: Re: Искусство программирования. (очередная)
Отправлено: NunTerix от Май 23, 2007, 11:54:10

Я склоняюсь к мнению что (!ost) лишь "удобнописная" замена частного случая - (ost==0). Т.К. условие равенства переменной нулю - является одним из наиболее частых случаев в написании кода. А уменьшение занимаемой памяти = врядли ставилась такая задача при создании языка.

Название: Re: Искусство программирования. (очередная)
Отправлено: vimmax от Май 24, 2007, 02:31:15

гы))) это оптимизация программы для компиляции. Компилятору приходится меньше оптимизировать, если программист оптимизировал код перед компиляцией. Экономится время компиляции.

Название: Re: Искусство программирования. (очередная)
Отправлено: Sochin от Май 24, 2007, 02:39:53

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