1

一个面试题：

给定两个 int N（分子）和 D（分母），返回字符串中的分数。如果分数重复，则在括号中显示重复部分。

示例：输入：N=1，D=3 输出：0.[3]

示例：输入：N=2，D=5 输出：0.4

我的想法：

得到双值的 a = N/D。

对于小数点后的部分，在这个过程中每个数字乘10，如果发现重复，记录索引，最后插入[]。

对于小数点前的部分，将每个数字乘以/ 10

有更好的想法吗？

谢谢

4

3 回答 3

4

我会避免使用像瘟疫一样的替身。由于有限的精度，它不会给你正确的答案。坚持整数运算并模拟长除法，跟踪余数。在您用完分子中的数字后（因此您要降低零），还要保留余数的历史记录，如果您看到历史记录中已经存在余数，则表明您已经达到了重复序列。然后，您可以构造括号中的输出部分。（当然，如果你的余数为零，这意味着答案是一个终止分数。）

于 2011-12-14T06:49:51.260 回答
0

这是一个模拟小数部分的长除法的锈溶液。

如果除数的因数不是 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
}
于 2019-01-28T11:38:44.657 回答
0

对于定点，只需在除法前将分子乘以 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 的结果等。

于 2019-01-28T12:06:30.353 回答