一个面试题:
给定两个 int N(分子)和 D(分母),返回字符串中的分数。如果分数重复,则在括号中显示重复部分。
示例:输入:N=1,D=3 输出:0.[3]
示例:输入:N=2,D=5 输出:0.4
我的想法:
得到双值的 a = N/D。
对于小数点后的部分,在这个过程中每个数字乘10,如果发现重复,记录索引,最后插入[]。
对于小数点前的部分,将每个数字乘以/ 10
有更好的想法吗?
谢谢
我会避免使用像瘟疫一样的替身。由于有限的精度,它不会给你正确的答案。坚持整数运算并模拟长除法,跟踪余数。在您用完分子中的数字后(因此您要降低零),还要保留余数的历史记录,如果您看到历史记录中已经存在余数,则表明您已经达到了重复序列。然后,您可以构造括号中的输出部分。(当然,如果你的余数为零,这意味着答案是一个终止分数。)
这是一个模拟小数部分的长除法的锈溶液。
如果除数的因数不是 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
}
对于定点,只需在除法前将分子乘以 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 的结果等。