Доброго времени суток!
Племянник принес из универа задачку - вывести в строку результат деления одного числа на другое. При этом, если получается периодическая дробь, то период нужно отобразить в скобках. Саму задачку я решил, но к задачке есть ещё вопрос, оценить сложность алгоритма. Что-то совсем забыл я как это делается. Подскажите плиз. Ниже код решения на Java.
| Код |
int[] remainder;
String getPeriod(int numerator, int denominator) {
int[] period;
int len;
remainder = new int[denominator + 1];
period=new int[denominator + 1];
int d = numerator, q = denominator;
int r, pos;
len = 1;
do {
r = d % q;
remainder[len] = r;
d /= q;
period[len] = d;
d= 10 * r;
len++;
pos = isInRemainder(r, len);
if (r == 0) break;
} while (pos == 0);
StringBuilder result = new StringBuilder(String.valueOf(period[1]));
if (numerator % denominator != 0)
result.append(",");
if (pos == 1) result.append("(");
for(r = 2; r < len; r++)
{
result.append(period[r]);
if (r == pos)
result.append("(");
}
if (pos >= 1) result.append(")");
return result.toString();
}
int isInRemainder (int ost, int len) {
for(int i=0;i<len-1;i++) {
if(remainder[i]==ost) return i;
}
return 0;
}
|
|