- 全排列代码
// 输出全排列--伪代码
int permutation(char a[]) {
int length = sizeof(a);
if (length == 0) {
return;
}
for (int i = 0; i < length;i++) {
cout << a[i];
// a.delete(a[i]); 删除a[i]
permutation(a);
}
}
- 日期转化与加减
- 数位拆解与进制转化
数位拆解：
十进制数 x 转换成 N 进制数 f :
while (x != 0){
A[i] = x % N ;
x = x / N;
i++;
}
f = A[i]A[i - 1]A[i - 2]...A[0]
N 进制数 f 转换成 十进制数 x :
x = 0;
while (i >= 0){
x += A[i] * N^i;
i--;
}
- 最小公倍数LCM与最大公约数GCD
a 和 b 的最大公约数也是 b 和 a mod b的最大公约数，所以循环直至其一为 0，则不为0的就是最大公约数。
int gcd(int a, int b) {
return b!=0? gcd(b, a%b) : a;
}
a 和 b 的最小公倍数和最小公约数的积等于a 和 b的积。
// lcm= a*b / gcd
int lcm(int a, int b) {
return a*b/gcd(a, b);
}
- 素数筛法与整数分解
分解素因数 ---- 整除问题
求正整数N(1<N<10^9)的质因数的个数。 相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。
输入：120
输出：5
/* 用 2 到 sqrt(N)内的质数逐个去除 N ，直到 N 为 1即被除尽，
或者质数全部除完，N不为 1， 但剩余的N必是大于 sqrt(N) 的质数。*/
#include<iostream>
#include<math.h>
using namespace std;
bool prime[100001];
void init(){
for (int i = 0; i < 100001; i++){
if (prime[i]){
continue;
}
else{
int num = sqrt(i);
for (int j = 2; j < num + 1; j++){
if (i%j == 0){
for (int k = i; k < 100001; k += i){
prime[k] = true;
}
break;
}
}
}
}
}
int main() {
int a;
int num = 0;
init();
cin >> a;
int i = 2;
do{
while (prime[i]){
i++;
}
while (a%i == 0){
num++;
a = a / i;
}
i++;
} while (a != 1&&i<100001);
if (a != 1){
num++;
}
cout << num << endl;
return 0;
}
整数拆解
所谓整数划分，是指把一个正整数n写成如下形式：
n=m1+m2+m3+....+mi;（其中mi为正整数，并且1<=mi<=n），则{m1,m2,m3,....,mi}为n的一个划分。
如果{m1,m2,m3,....,mi}中的最大值不超过m，即max{m1,m2,m3,....,mi} <= m，则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m)；
例如当n=4时，它有5个划分：{4}、{3,1}、{2,2}、{2,1,1}、{1,1,1,1}；
注意：4=1+3和4=3+1被认为是同一个划分。
该问题是求出n的所有划分个数，即f(n,n)。下面我们考虑求f(n,m)的方法。
解决方法：
根据n和m的关系，考虑下面几种情况：
（1）当n=1时，不论m的值为多少（m>0），只有一种划分，即{1}；（2）当m=1时，不论n的值为多少（n>0），只有一种划分，即{1,1,....1,1,1}；
（3）当n=m时，根据划分中是否包含n，可以分为两种情况：
（a）划分中包含n的情况，只有一个，即{n}；
（b）划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有（n-1）划分；
因此，f(n,n) = 1 + f(n, n - 1)。
（4）当n<m时，由于划分中不可能出现负数，因此就相当于f(n,n)；
（5）当n>m时，根据划分中是否包含m，可以分为两种情况：
（a）划分中包含m的情况，即{m,{x1,x2,x3,...,xi}}，其中{x1,x2,x3,...,xi}的和为n-m，可能再次出现m，因此是（n-m）的m划分，因此这种划分个数为f(n-m, m)；
（b）划分中不包含m的情况，则划分中所有值都比m小，即n的（m-1）划分，个数为f(n, m - 1)；
因此，f(n,m) = f(n - m,m) + f(n, m - 1)。
综合以上各种情况，可以看出，上面的结论具有递归定义的特征，其中（1）和（2）属于回归条件，（3）和（4）属于特殊情况，而情况（5）为通用情况，属于递归的方法，其本质主要是通过减少n或m以达到回归条件，从而解决问题。
其递归表达式如下所示。
image
参考：http://blog.csdn.net/u011889952/article/details/44813593
/* https://www.nowcoder.com/practice/376537f4609a49d296901db5139639ec?
tpId=40&tqId=21339&tPage=1&rp=1&ru=%2Fta%2Fkaoyan&qru=%2Fta%2Fkaoyan%2Fquestion-ranking
简单以上题为例子，实际该题目有更优解法。
f()函数是利用数组存值的递归函数，一定程度上减少了堆栈开销。
f2()函数动态规划由小到大计算数组，在f()的基础上进一步减少了开销。*/
#include<iostream>
#include<math.h>
#define ROW 1000001
#define COL 20
using namespace std;
int record[ROW][COL];
void init(){
for (int i = 0; i < COL; i++){
for (int j = 0; j < ROW; j++){
record[j][i] = 0;
}
}
for (int i = 0; i < COL; i++){
record[1][i] = 1;
}
for (int i = 0; i < ROW; i++){
record[i][0] = 1;
}
}
int f(int n, int m){
if (n == 1 || m == 0){
return 1;
}
int temp = pow(2, m);
if (n == temp){
if (record[n][m] == 0){
record[n][m] = (f(n, m - 1) + 1) % 1000000000;
}
}
else if (n > temp){
if (record[n][m] == 0){
record[n][m] = (f(n, m - 1) + f(n - temp, m)) % 1000000000;
}
}
else if (n < temp){
if (record[n][m] == 0){
record[n][m] = (f(n, m - 1)) % 1000000000;
}
}
return record[n][m] ;
}
int f2(int n, int m){
for (int i = 1; i <= n; i++){
for (int j = 0; j <= m; j++){
if (i == 1 || j == 0){
record[i][j] = 1;
}
int temp = pow(2, j);
if (i == temp){
record[i][j] = (record[i][j - 1] + 1) % 1000000000;
}
else if (i > temp){
record[i][j] = (record[i][j - 1] + record[i - temp][j]) % 1000000000;
}
else if (i < temp){
record[i][j] = (record[i][j - 1]) % 1000000000;
}
}
}
return record[n][m];
}
int main(){
int n;
cin >> n;
init();
int m = log10(n) / log10(2);
cout <<f2(n, m) << endl;
return 0;
}
- 大整数
- 大数相加
输入包括两个数a和b，其中a和b的位数不超过1000位。输出a+b的值。
输入：
10000000000000000000 10000000000000000000000000000000
输出：
10000000000010000000000000000000
// 将加法的输入和输出存放在string中，逐位计算求解。
// 代码尽量再优化。
#include<iostream>
#include<string>
using namespace std;
int main(){
string a, b;
int result[10001];
cin >> a >> b;
int num = 0;
int i = a.size() - 1, j = b.size() - 1;
int k = 0;
while (i >= 0 && j >= 0){
result[k] = (int)(a[i] - '0' + b[j] - '0') + num;
if (result[k] >= 10){
result[k] %= 10;
num = 1;
}
else{
num = 0;
}
i--;
j--;
k++;
}
while (i >= 0){
result[k] = (int)(a[i] - '0') + num;
if (result[k] >= 10){
result[k] %= 10;
num = 1;
}
else{
num = 0;
}
i--;
k++;
}
while (j >= 0){
result[k] = (int)(b[j] - '0') + num;
if (result[k] >= 10){
result[k] %= 10;
num = 1;
}
else{
num = 0;
}
j--;
k++;
}
for (int index = k - 1; index >= 0; index--){
cout << result[index];
}
cout << endl;
return 0;
}
- 大数阶乘
输入一个正整数N（<1000），输出N的阶乘。
输入：
15
输出：
1307674368000
// 将每次乘法的结果存放在int数组中，数组每个元素保存4位数。
#include<iostream>
#include<iomanip>
using namespace std;
int result[1000];
int size=1;
void mult(int b){
int carry = 0;
for (int i = 0; i < size; i++){
result[i] = result[i] * b + carry;
if (result[i] >= 10000){
carry = result[i] / 10000;
result[i] %= 10000;
}
else{
carry = 0;
}
}
if (carry != 0){
result[size] = carry;
size++;
}
}
int main(){
int n;
cin >> n;
result[0] = 1;
for (int i = 1; i <= n; i++){
mult(i);
}
for (int i = size - 1; i >= 0; i--){
if (i == size-1){
cout << result[i];
}
else{
cout << setw(4) << setfill('0') << result[i];
}
}
cout << endl;
return 0;
}
// 使用JAVA中的BigInteger类
// add() substract() multiply() divide() 对应加减乘除
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
BigInteger result = new BigInteger("1");
for(int i=1;i<=n;i++){
BigInteger temp = new BigInteger(i+"");
result = result.multiply(temp);
}
System.out.println(result);
}
}
