VPF::Проблема с оценкой сложности алгоритма

Ne1tr1n0

Дата 27.10.2015, 02:47 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 120
Регистрация: 1.3.2009

Репутация: нет
Всего: 8

Доброго времени суток!

Племянник принес из универа задачку - вывести в строку результат деления одного числа на другое. При этом, если получается периодическая дробь, то период нужно отобразить в скобках. Саму задачку я решил, но к задачке есть ещё вопрос, оценить сложность алгоритма. Что-то совсем забыл я как это делается. Подскажите плиз. Ниже код решения на 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;
}

Это сообщение отредактировал(а) Ne1tr1n0 - 27.10.2015, 02:47

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »