преобразовать дробь в строку, а также вставить [] для повторения части

Question

Вопрос для интервью:

Учитывая два целых N (числитель) и D (знаменатель), вернуть дробь в строке. если дробь повторяется, отобразите повторяющуюся часть в скобках.

Пример: Вход: N = 1, D = 3 выход: 0. [3]

Пример: Вход: N = 2, D = 5 выход: 0,4

Моя идея:

получить = N / D с двойным значением.

для части после десятичной точки, получить каждую цифру х 10 в процессе, если найдете повтор, запишите индекс и, наконец, вставьте [].

для части перед десятичной запятой, получить каждую цифру на / 10

Есть идеи получше?

спасибо

Answer 1

Я бы не использовал двойник, как чума.Из-за конечной точности он не даст вам правильного ответа.Придерживайтесь целочисленной арифметики и имитируйте длинное деление , отслеживая остаток.После того, как в числителе закончились цифры (то есть вы сбрасываете нули), также ведите историю остатков, и если вы видите остаток, который уже есть в истории, это говорит о том, что вы нажали повторяющуюся последовательность.Затем вы можете построить выходную часть в квадратных скобках.(Если вы, конечно, наберете нулевой остаток, это означает, что ответ является завершающей дробью.)

Answer 2

Для фиксированной точки просто умножьте числитель на 10 перед делением. Для плавающей запятой просто используйте деление, а затем modf, чтобы получить дробную часть. В любом случае, преобразуйте в строку, затем отформатируйте как предпочитаете (1 десятичный знак).

В C вы можете сделать что-то общее, которое обрабатывает фиксированную или плавающую точку, используя _Generic.

Простой пример без обработки ошибок:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

char* strfract_int (char* dst, int n, int d)
{
  sprintf(dst, "0.%d", n*10 / d);
  return dst;
}

char* strfract_double (char* dst, double n, double d)
{
  double dummy;
  sprintf(dst, "%.1f", modf(n/d, &dummy) );
  return dst;
}

#define strfract(dst, n, d)                   \
  _Generic((n),                               \
           int:    strfract_int,              \
           double: strfract_double)(dst,n,d)  \

int main (void)
{
  char buf [100];
  puts( strfract(buf, 1, 3) );
  puts( strfract(buf, 2, 5) );
  puts( strfract(buf, 1.0, 3.0) );
  puts( strfract(buf, 2.0, 5.0) );
}

В защищенной программе проверьте деление на ноль, результат malloc и т. Д. И т. Д.

Answer 3

Вот решение для ржавчины, которое имитирует длинное деление дробной части.

Повторяющаяся десятичная дробь будет иметь место только в том случае, если делитель имеет коэффициент, отличный от 2 и 5. Мы можем легко проверить это путем многократного деления на 2, пока все факторы 2 не будут удалены, а затем повторного деления на 5, пока все факторы 5 удалены. После деления, если результирующее число равно 1, повторяющегося десятичного числа не будет.

Чтобы обработать регистр для повторяющейся десятичной дроби, мы сохраняем хэш-набор остатков, которые мы видели до сих пор. Если остаток появляется снова, мы прекращаем вычисления.

#[allow(unused_variables)]

use std::collections::HashSet;
use std::io;

fn main() {
    let a = read_usize();
    let b = read_usize();
    println!("{}", long_division(a, b));
}

fn read_usize() -> usize {
    let mut input_string = String::new();
    io::stdin()
        .read_line(&mut input_string)
        .expect("failed to read from stdin");
    let trimmed = input_string.trim();
    let num = trimmed.parse::<usize>().unwrap();
    num
}

fn repeating_decimal(denominator: usize) -> bool {
    let mut d = denominator;
    while d % 2 == 0 {
        d /= 2;
    }
    while d % 5 == 0 {
        d /= 5;
    }
    if d == 1 { false } else { true }
}

fn long_division(a: usize, b: usize) -> String {
    let q = a / b;
    let r = (a % b) * 10;
    if r == 0 {
        return q.to_string();
    }
    if repeating_decimal(b) {
        format!("{}.({})",q,divide_repeating_decimal(r, b))
    } else {
        format!("{}.{}",q,divide_without_repeating_decimal(r, b))
    }

}

fn divide_repeating_decimal(mut r: usize, b: usize) -> String {
    let mut result = String::new();
    let mut seen: HashSet<usize> = HashSet::new();
    loop {
        if r < b {
            r *= 10;
            result.push_str(&"0".to_owned());
            continue;
        }
        let q = r / b;
        r = (r % b) * 10;
        result.push_str(&q.to_string());
        if seen.contains(&r) {
            break;
        }
        seen.insert(r.clone());

    }
    result
}

fn divide_without_repeating_decimal(mut r: usize, b: usize) -> String {
    let mut result = String::new();
    while r != 0 {
        if r < b {
            r *= 10;
            result.push_str(&"0".to_owned());
            continue;
        }
        let q = r / b;
        r = (r % b) * 10;
        result.push_str(&q.to_string());
    }
    result
}