Learn-Algorithms/9 Algorithms Job Interview/4.1 数值-加减乘除.md

# 数值-加减乘除


* 等差数列
* 阶乘



## 求1+2+…+n

要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?B:C）。

思路：这是等差数列求和公式， 1+2+3.......+N =（n+1）n/2

分析：
1. 不能使用循环，那就用递归
2. 递归需要终止递归的条件判断语句，这里也不能用if,想其他办法，可以使用 &&逻辑与 运算符（在n>0条件满足是，才会指向后面的递归语句）

```
int sum(n){
    int sum=0;
    (n>0) && sum=n+factorial(n-1)
    return sum;
}
```




## 大数阶乘(factorial)

> 阶乘 n*(n-1)*(n-2)*...*1

主要考虑算出来的结果肯定会大于int表达的范围，这时候怎么处理？

```
int factorial(n){
    int sum=0;
    (n>0) && sum=n+factorial(n-1)
    return sum;
}
```

考虑整数溢出情况

```
char[] factorial(int n){
    int sum=0;
    return sum;
}

```


## 1024! 末尾有多少个0？

分析：
末尾0的个数取决于2和5的个数
能被2整除的数比能被5整除的数要多得多，因此只统计被5整除的数的个数




## 大整数乘法（或 大整数阶乘）

请使用代码计算`1234567891011121314151617181920*2019181716151413121110987654321` 。

1. 注意结果可能超出长整形的最大范围 2^64-1
2. 采用分治算法，将大整数相乘转换为小整数计算

规律分析：任意位数的整数相乘，最终都可以转化为2位数相乘






## 实现两个正整数的除法(和取模)

编程实现两个正整数的除法，当然不能用除法操作符。
```
int div(const int x, const int y) 
```

1. 循环减被除数，减到不能再减，当除数很大，被除数小时，效率很低
2. 位运算




## 两个数相乘，小数点后位数没有限制，请写一个高精度算法