常用算法

一、高精度计算

1. 阶乘运算

/*
 ============================================================================
 Name        : ch1_inputandoutput.c
 Author      : Adam Zam
 Version     :
 Copyright   : Your copyright notice
 Description : Hello World in C, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>
#define MAXN 1000
const int maxm = 3000;
int f[maxm];
int main()
{
    int i,j,n;
    scanf("%d",&n);
    memset(f,0,sizeof(f));
    f[0]=1;
    for(i=2;i<=n;i++)
    {
        int c=0;
        for(j=0;j<maxm;j++)
        {
            int s= f[j]*i+c;
            f[j]=s%10;
            c=s/10;
        }
    }
    for(j=maxm-1;j>=0;j--) if(f[j])break;
    for(i=j;i>=0;i--)printf("%d",f[i]);
    printf("\n");
    return 0;
}

2. C++类

//============================================================================
// Name        : highaccuracy.cpp
// Author      : Adam Zam
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;
const int maxn = 1000;
struct bign
{
    int len,s[maxn];
    bign(){
        memset(s,0,sizeof(s));
        len=1;
    }
    bign operator = (const char*num){
        len = strlen(num);
        for(int i=0;i<len;i++){
            s[i]=num[len-i-1]-'0';
        }
        return*this;
    }
    bign operator = (int num){
        char s[maxn];
        sprintf(s,"%d",num);
        *this = s;
        return *this;
    }
    bign operator +(const bign &b) const
    {
        bign c;
        c.len=0;
        for(int i=0,g=0;g||i<max(len,b.len);i++)
        {
            int x=g;
            if(i<len) x+=s[i];
            if(i<b.len)x+=b.s[i];
            c.s[c.len++] = x%10;
            g=x/10;//进位位
        }
        return c;
    }
    bign operator +=(const bign&b){
        *this=*this+b;
        return *this;
    }

    bign(int num){
        *this = num;
    }
    bign(const char*num){
        *this = num;
    }
    string str() const
    {
        string res = "";
        for(int i=0;i<len;i++)
        {
            res = (char)(s[i]+'0')+res;
        }
        if(res=="") res="0";
        return res;
    }
    istream& operator >> (istream &in, bign &x)
    {
        string s;
        in>>s;
        x=s.c_str();
        return in;
    }
    ostream& operator << (ostream &out, const bign &x)
    {
        out<<x.str();
        return out;
    }
};
int main() {
    bign x;
    x=100;
    cout<<x;
    //cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
    return 0;
}

3. 冒泡排序

int get_next(int num)
{
    int n;
    int min,max;
    //int i,j;
    char s[10];
    sprintf(s,"%d",num);
    printf("%c\n",s[0]);//此处存储方式为s[0],s[1],s[2],s[3]:1,2,3,4
    n=strlen(s);
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++)
        {
            if(s[i]>s[j])
            {
                SWAP(s[i],s[j]);
            }
        }
    }
    //printf("%s\n",s);
    sscanf(s,"%d",&min);
    for(int i=0;i<n/2;i++)
    {
        SWAP(s[i],s[n-1-i]);
    }
    sscanf(s,"%d",&max);
    return max-min;
}

注意sprintf和sscanf保存数字的方式为字符串低位对应数字高位

4. 判断一个点是否在三角形区域内

求解（坐标）行列式值表示的面积和是否相等，尽量避免浮点数直接比较大小，而是判断差值是否小于一个给定的数
例如

fabs(a-b)<1e-9

另外，尽量不要使用海伦公式，可能会引入浮点误差。