- 全排列代碼
// 輸出全排列--偽代碼
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);
}
}
- 日期轉(zhuǎn)化與加減
- 數(shù)位拆解與進(jìn)制轉(zhuǎn)化
數(shù)位拆解：
十進(jìn)制數(shù) x 轉(zhuǎn)換成 N 進(jìn)制數(shù) f :
while (x != 0){
A[i] = x % N ;
x = x / N;
i++;
}
f = A[i]A[i - 1]A[i - 2]...A[0]
N 進(jìn)制數(shù) f 轉(zhuǎn)換成 十進(jìn)制數(shù) x :
x = 0;
while (i >= 0){
x += A[i] * N^i;
i--;
}
- 最小公倍數(shù)LCM與最大公約數(shù)GCD
a 和 b 的最大公約數(shù)也是 b 和 a mod b的最大公約數(shù)，所以循環(huán)直至其一為 0，則不為0的就是最大公約數(shù)。
int gcd(int a, int b) {
return b!=0? gcd(b, a%b) : a;
}
a 和 b 的最小公倍數(shù)和最小公約數(shù)的積等于a 和 b的積。
// lcm= a*b / gcd
int lcm(int a, int b) {
return a*b/gcd(a, b);
}
- 素?cái)?shù)篩法與整數(shù)分解
分解素因數(shù) ---- 整除問題
求正整數(shù)N(1<N<10^9)的質(zhì)因數(shù)的個(gè)數(shù)。 相同的質(zhì)因數(shù)需要重復(fù)計(jì)算。如120=2*2*2*3*5，共有5個(gè)質(zhì)因數(shù)。
輸入：120
輸出：5
/* 用 2 到 sqrt(N)內(nèi)的質(zhì)數(shù)逐個(gè)去除 N ，直到 N 為 1即被除盡，
或者質(zhì)數(shù)全部除完，N不為 1， 但剩余的N必是大于 sqrt(N) 的質(zhì)數(shù)。*/
#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;
}
整數(shù)拆解
所謂整數(shù)劃分，是指把一個(gè)正整數(shù)n寫成如下形式：
n=m1+m2+m3+....+mi;（其中mi為正整數(shù)，并且1<=mi<=n），則{m1,m2,m3,....,mi}為n的一個(gè)劃分。
如果{m1,m2,m3,....,mi}中的最大值不超過m，即max{m1,m2,m3,....,mi} <= m，則稱它屬于n的一個(gè)m劃分。這里我們記n的m劃分的個(gè)數(shù)為f(n,m)；
例如當(dāng)n=4時(shí)，它有5個(gè)劃分：{4}、{3,1}、{2,2}、{2,1,1}、{1,1,1,1}；
注意：4=1+3和4=3+1被認(rèn)為是同一個(gè)劃分。
該問題是求出n的所有劃分個(gè)數(shù)，即f(n,n)。下面我們考慮求f(n,m)的方法。
解決方法：
根據(jù)n和m的關(guān)系，考慮下面幾種情況：
（1）當(dāng)n=1時(shí)，不論m的值為多少（m>0），只有一種劃分，即{1}；（2）當(dāng)m=1時(shí)，不論n的值為多少（n>0），只有一種劃分，即{1,1,....1,1,1}；
（3）當(dāng)n=m時(shí)，根據(jù)劃分中是否包含n，可以分為兩種情況：
（a）劃分中包含n的情況，只有一個(gè)，即{n}；
（b）劃分中不包含n的情況，這時(shí)劃分中最大的數(shù)字也一定比n小，即n的所有（n-1）劃分；
因此，f(n,n) = 1 + f(n, n - 1)。
（4）當(dāng)n<m時(shí)，由于劃分中不可能出現(xiàn)負(fù)數(shù)，因此就相當(dāng)于f(n,n)；
（5）當(dāng)n>m時(shí)，根據(jù)劃分中是否包含m，可以分為兩種情況：
（a）劃分中包含m的情況，即{m,{x1,x2,x3,...,xi}}，其中{x1,x2,x3,...,xi}的和為n-m，可能再次出現(xiàn)m，因此是（n-m）的m劃分，因此這種劃分個(gè)數(shù)為f(n-m, m)；
（b）劃分中不包含m的情況，則劃分中所有值都比m小，即n的（m-1）劃分，個(gè)數(shù)為f(n, m - 1)；
因此，f(n,m) = f(n - m,m) + f(n, m - 1)。
綜合以上各種情況，可以看出，上面的結(jié)論具有遞歸定義的特征，其中（1）和（2）屬于回歸條件，（3）和（4）屬于特殊情況，而情況（5）為通用情況，屬于遞歸的方法，其本質(zhì)主要是通過減少n或m以達(dá)到回歸條件，從而解決問題。
其遞歸表達(dá)式如下所示。
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
簡單以上題為例子，實(shí)際該題目有更優(yōu)解法。
f()函數(shù)是利用數(shù)組存值的遞歸函數(shù)，一定程度上減少了堆棧開銷。
f2()函數(shù)動(dòng)態(tài)規(guī)劃由小到大計(jì)算數(shù)組，在f()的基礎(chǔ)上進(jìn)一步減少了開銷。*/
#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;
}
- 大整數(shù)
- 大數(shù)相加
輸入包括兩個(gè)數(shù)a和b，其中a和b的位數(shù)不超過1000位。輸出a+b的值。
輸入：
10000000000000000000 10000000000000000000000000000000
輸出：
10000000000010000000000000000000
// 將加法的輸入和輸出存放在string中，逐位計(jì)算求解。
// 代碼盡量再優(yōu)化。
#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;
}
- 大數(shù)階乘
輸入一個(gè)正整數(shù)N（<1000），輸出N的階乘。
輸入：
15
輸出：
1307674368000
// 將每次乘法的結(jié)果存放在int數(shù)組中，數(shù)組每個(gè)元素保存4位數(shù)。
#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() 對(duì)應(yīng)加減乘除
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);
}
}
