Created
November 4, 2020 16:01
-
-
Save WhiteGrouse/0f226ce6f50003dcf8761273f7c29fed to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #[macro_use] | |
| extern crate lazy_static; | |
| mod console_io; | |
| use console_io::*; | |
| use std::fmt; | |
| use std::collections::HashMap; | |
| use std::ops::{Add, Shl, Shr, Mul}; | |
| fn main() { | |
| let a = Num::from_str(10, "987"); | |
| let b = Num::from_str(10, "123"); | |
| let c = a * b; | |
| let d = Num::from_str(2, "1111011").convert_base(10); | |
| //let num = Num::input(); | |
| println!("{}", d); | |
| } | |
| lazy_static! { | |
| static ref N2C: Vec<char> = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".chars().collect(); | |
| static ref C2N: HashMap<char, usize> = { | |
| let mut table = HashMap::new(); | |
| for i in 0..N2C.len() { | |
| table.insert(N2C[i], i); | |
| } | |
| table | |
| }; | |
| } | |
| #[derive(Clone)] | |
| struct Num { | |
| base: usize, | |
| num_array: Vec<usize>, | |
| } | |
| impl Num { | |
| fn new(base: usize, mut num_array: Vec<usize>) -> Num { | |
| if base < 2 || base > N2C.len() { | |
| panic!("サポートされていない基数です({})", base); | |
| } | |
| num_array = num_array.iter().skip_while(|n| **n == 0).cloned().collect(); | |
| if num_array.len() == 0 { | |
| num_array = vec![0]; | |
| } | |
| if num_array.iter().any(|&n| n >= base) { | |
| panic!("基数を越えた数字があります"); | |
| } | |
| Num { base, num_array } | |
| } | |
| fn from_str(base: usize, s: &str) -> Num { | |
| if base < 2 || base > N2C.len() { | |
| panic!("サポートされていない基数です({})", base); | |
| } | |
| let mut num_array: Vec<usize> = s.trim() | |
| .trim_start_matches(N2C[0]) | |
| .chars() | |
| .rev() | |
| .map(|c| *C2N.get(&c).expect(&format!("サポートされていない文字です({})", c))) | |
| .collect(); | |
| if num_array.len() == 0 { | |
| num_array = vec![0]; | |
| } | |
| if num_array.iter().any(|&n| n >= base) { | |
| panic!("基数を越えた数字があります"); | |
| } | |
| Num { base, num_array } | |
| } | |
| fn input() -> Num { | |
| print("base: "); | |
| let base = read_and_parse::<usize>(); | |
| print("str: "); | |
| let s = read_line(); | |
| Num::from_str(base, &s) | |
| } | |
| fn convert_base(&self, base: usize) -> Num { | |
| if self.base > base { | |
| self.convert_base_down(base) | |
| } | |
| else if self.base < base { | |
| self.convert_base_up(base) | |
| } | |
| else { | |
| self.clone() | |
| } | |
| } | |
| fn convert_base_up(&self, base: usize) -> Num { | |
| assert_eq!(self.base < base, true); | |
| let mut result = Num::new(base, vec![0]); | |
| let mut weight = Num::new(base, vec![1]); | |
| for i in &self.num_array { | |
| result = result + weight.clone() * Num::new(base, vec![*i]); | |
| weight = weight * Num::new(base, vec![self.base]); | |
| } | |
| result | |
| } | |
| fn convert_base_down(&self, base: usize) -> Num { | |
| assert_eq!(self.base > base, true); | |
| Num::new(10, vec![0]) | |
| } | |
| } | |
| impl fmt::Display for Num { | |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
| write!(f, "{}({})", self.num_array.iter().map(|&n| N2C.get(n).unwrap()).rev().collect::<String>(), self.base) | |
| } | |
| } | |
| impl Add for Num { | |
| type Output = Self; | |
| fn add(self, other: Self) -> Self { | |
| if self.base != other.base { | |
| panic!("基数が異なる値同士の加算はサポートしていません"); | |
| } | |
| let (arr_a, arr_b) = { | |
| if self.num_array.len() > other.num_array.len() { | |
| (&self.num_array, &other.num_array) | |
| } | |
| else { | |
| (&other.num_array, &self.num_array) | |
| } | |
| }; | |
| let mut num_array = Vec::with_capacity(arr_a.len() + 1); | |
| let mut carry = 0usize; | |
| for i in 0..arr_b.len() { | |
| let tmp = arr_a[i] + arr_b[i] + carry; | |
| num_array.push(tmp % self.base); | |
| carry = tmp / self.base; | |
| } | |
| for i in arr_b.len()..arr_a.len() { | |
| let tmp = arr_a[i] + carry; | |
| num_array.push(tmp % self.base); | |
| carry = tmp / self.base;//<=1 | |
| } | |
| if carry > 0 { | |
| num_array.push(carry); | |
| } | |
| Num::new(self.base, num_array) | |
| } | |
| } | |
| impl Shl<usize> for Num { | |
| type Output = Self; | |
| fn shl(self, n: usize) -> Self { | |
| let mut num = self.clone(); | |
| if num.num_array.len() > 1 || num.num_array[0] > 0 { | |
| for _ in 0..n { | |
| num.num_array.insert(0, 0); | |
| } | |
| } | |
| num | |
| } | |
| } | |
| impl Shr<usize> for Num { | |
| type Output = Self; | |
| fn shr(self, n: usize) -> Self { | |
| let mut num = self.clone(); | |
| if num.num_array.len() < n { | |
| num.num_array.clear(); | |
| } | |
| else { | |
| num.num_array.drain(0..n); | |
| } | |
| if num.num_array.len() == 0 { | |
| num.num_array.push(0); | |
| } | |
| num | |
| } | |
| } | |
| impl Mul for Num { | |
| type Output = Self; | |
| fn mul(self, other: Self) -> Self { | |
| if self.base != other.base { | |
| panic!("基数が異なる値同士の乗算はサポートしていません"); | |
| } | |
| let arr_a = &self.num_array; | |
| let arr_b = &other.num_array; | |
| let mut nums = Vec::new(); | |
| let mut shift = 0usize; | |
| for n_b in arr_b { | |
| let mut num_array = Vec::with_capacity(arr_a.len() + 1); | |
| let mut carry = 0usize; | |
| for n_a in arr_a { | |
| let tmp = n_a * n_b + carry; | |
| num_array.push(tmp % self.base); | |
| carry = tmp / self.base;//<=base-2 | |
| } | |
| if carry > 0 { | |
| num_array.push(carry); | |
| } | |
| let num = Num::new(self.base, num_array); | |
| nums.push(num << shift); | |
| shift += 1; | |
| } | |
| let mut result = nums.pop().unwrap(); | |
| for num in nums { | |
| result = result + num; | |
| } | |
| result | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment