Занятие 1

Задача 1. Двоичная дробь

Первый необходимый алгоритм – преобразование строки, содержащей двоичное представление числа, в целое значение:

int bin2int(const char s[])
{ int r=0;
  while(*s)
  { r=r*b+*s-'0';
    ++s;
  }
  return r;
}

Общий алгоритм показан на странице 4

Далее, после получения числителя и знаменателя дроби, получаем двоичную бесконечную дробь из дроби `a`/`b`. Чтобы узнать очередную цифру двоичного предствления, умножаем дробь на 2 и берем целую часть, повтрояем тоже с дробной частью результата. И так до тех пор пока не найдем период. Фактически при этом у дроби изменяется только числитель. Значения, которые может принять числитель, ограничены множеством чисел {0, 1, …, `b`-1} и зависят от занчения на предыдушем шаге, поэтому через несколько шагов мы получим уже рассматривавшееся значение. Чтобы не просматривать весь список значений для числителя для проверки, встречалось ли значение ранее, можно сделать массив, где для каждого значения будет храниться информация, на каком шаге оно было получено.

int when[10000];
char sa[20],sb[20];
char r[10000];
int main()
{ int i,j,a,b;
  scanf("%s%s",sa,sb);
  a=bin2int(sa);
  b=bin2int(sb);
  for(i=0; i<10000; ++i)
    when[i]=-1; // не встречалось
  i=0;
  while(1)
  { if(when[a]>=0) 
      break; // нашли период
    when[a]=i;
    a*=2;
    r[i++]=a/b; // очередная цифра
    a%=b;
  }
  // выводим ответ
  printf("0,");
  for(j=0; j<when[a]; j++)
    printf("%d",r[j]);
  printf("(");
  for(j=when[a]; j<i; j++)
    printf("%d",r[j]);
  printf(")\n");
  return 0;
}