Искусство программирования. (5)

[LazarusLong]

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

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

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

и т.п.

[chilik]

Код:

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;
 }
}

[chilik]

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

[naxellar]

Код:

{ost[i]=o;

Код:

[i]

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

[chilik]

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

[LazarusLong]

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

[chilik]

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

[chilik]

Код:

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;
  }
}

[LazarusLong]

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

[LazarusLong]

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

[chilik]

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

Код:

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 будешь должен

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

[naxellar]

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

[LazarusLong]

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

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

naxellar - ставь!

[LazarusLong]

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

if (ost==0) return 0;

На

if (!ost) return 0;

:-)

[naxellar]

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

if (ost==0) return 0;

На

if (!ost) return 0;

:-)

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

[LazarusLong]

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

[Sochin]

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

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

[LazarusLong]

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

[Sochin]

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

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

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

if (ost==0) return 0;

На

if (!ost) return 0;

:-)

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

[NunTerix]

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

if (ost==0) return 0;

На

if (!ost) return 0;

:-)

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

[LazarusLong]

Sochin

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

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

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

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

[NunTerix]

NunTerix

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

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

[LazarusLong]

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

[NunTerix]

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

[vimmax]

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

[Sochin]

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