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

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

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

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

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

Моя идея:

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

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

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

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

Благодарность


person user1002288    schedule 14.12.2011    source источник


Ответы (3)


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

person Ted Hopp    schedule 14.12.2011
comment
Ага. И код в этом ответе на другой связанный вопрос может помочь с длинным делением числителя и знаменателя и остатков. - person Alexey Frunze; 14.12.2011

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

Повторяющаяся десятичная дробь будет только в том случае, если делитель имеет множитель, отличный от 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
}
person ckousik    schedule 28.01.2019

Для фиксированной точки просто умножьте числитель на 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 и т.д.

person Lundin    schedule 28.01.2019