20、大数运算处理基本函数#include#includeusing namespace std;const int N = 1100;struct big_num{    int ele[N];    int front;};typedef struct big_num bigNum;void print_bigNum(const bigNum& num){    for(int i = num.front; i < N; ++i)        printf("%d", num.ele[i]);}void println_bigNum(const bigNum& num){    for(int i = num.front; i < N; ++i)        printf("%d", num.ele[i]);    printf("\n");}bigNum multi_bigNum(const bigNum& num1, const bigNum& num2){    bigNum temp;    bigNum num3;    int i, j, carry;    int temp_int;    num3.front = num1.front + num2.front - N;    for(i = num3.front; i < N; ++i)        num3.ele[i] = 0;    for(i = N - 1; i >= num1.front; --i)    {        carry = 0;        for(j = N - 1; j >= num2.front; --j)        {            temp_int = num2.ele[j] * num1.ele[i] + carry;            temp.ele[j] = temp_int % 10;            carry = temp_int / 10;        }        temp.front = num2.front;        if(carry != 0)            temp.ele[--temp.front] = carry;        carry = 0;        for(j = N - 1; j >= temp.front; --j)        {            temp_int = num3.ele[i + j + 1 - N] + temp.ele[j] + carry;            if(temp_int >= 10)            {                num3.ele[i + j + 1 - N] = temp_int - 10;                carry = 1;            }            else            {                num3.ele[i + j + 1 - N] = temp_int;                carry = 0;            }        }        while(carry == 1)        {            temp_int = num3.ele[i + j + 1 - N] + carry;            if(temp_int >= 10)            {                num3.ele[i + (j--) + 1 - N] = temp_int - 10;                carry = 1;            }            else            {                num3.ele[i + (j--) + 1 - N] = temp_int;                carry = 0;            }        }    }    while(num3.ele[num3.front] == 0 && num3.front < N - 1)        ++num3.front;    return num3;}bigNum add_bigNum(const bigNum& num1, const bigNum& num2){    bigNum num3;    num3.front = num1.front;    if(num3.front < num2.front)        num3.front = num2.front;    int carry = 0;    int i;    for(i = N - 1; i >= num3.front; --i)    {        num3.ele[i] = num2.ele[i] + num1.ele[i] + carry;        carry = num3.ele[i] / 10;        num3.ele[i] %= 10;    }    if(num3.front == num2.front)    {        num3.front = num1.front;        for(; i >= num3.front; --i)        {            num3.ele[i] = num1.ele[i] + carry;            carry = num3.ele[i] / 10;            num3.ele[i] %= 10;        }        if(carry == 1)        {            --num3.front;            num3.ele[num3.front] = 1;        }    }    else    {        num3.front = num2.front;        for(; i >= num3.front; --i)        {            num3.ele[i] = num2.ele[i] + carry;            carry = num3.ele[i] / 10;            num3.ele[i] %= 10;        }        if(carry == 1)        {            --num3.front;            num3.ele[num3.front] = 1;        }    }    return num3;}void string_to_bigNum(bigNum& num, const char s[]){    num.front = N - strlen(s);    for(int i = num.front; i < N; ++i)        num.ele[i] = s[i - num.front] - ''0'';}// 0 <= a <= 10void muti_by_one(const bigNum& num1, int a, bigNum& num2){    int temp;    int carry = 0;    int i;    if(a == 0)    {        num2.ele[N - 1] = 0;        num2.front = N - 1;        return;    }    if(a == 10)    {        for(i = num1.front; i < N; ++i)            num2.ele[i - 1] = num1.ele[i];        num2.ele[N - 1] = 0;        num2.front = num1.front - 1;    }    for(i = N - 1; i >= num1.front; --i)    {        temp = a * num1.ele[i] + carry;        num2.ele[i] = temp % 10;        carry = temp / 10;    }    if(carry == 0)        num2.front = num1.front;    else    {        num2.front = num1.front - 1;        num2.ele[i] = carry;    }}int comp_bigNum(const bigNum& num1, const bigNum& num2){    int i;    if(num1.front != num2.front)    {        if(num1.front < num2.front)            return 1;        else            return -1;    }    for(i = num1.front; i < N; ++i)        if(num1.ele[i] != num2.ele[i])        {            if(num1.ele[i] > num2.ele[i])                return 1;            else                return -1;        }    return 0;}bool comp_bigNum_0(const bigNum& num1){    return (num1.ele[N - 1] == 0) && (num1.front == N - 1);}//这里只能让大数减小数，如果num1 < num2 则交换num1 和 num2 的顺序bigNum minus_bigNum(const bigNum& num1, const bigNum& num2){    bigNum num3;    int temp;    int i;    temp = comp_bigNum(num1, num2);    if(temp < 0)    {        num3 = minus_bigNum(num2, num1);        return num3;    }    if(temp == 0)    {        num3.front = N - 1;        num3.ele[N - 1] = 0;        return num3;    }    int carry = 0;    for(i = N - 1; i >= num2.front; --i)    {        temp = num1.ele[i] - num2.ele[i] - carry;        if(temp < 0)        {            temp += 10;            carry = 1;        }        else            carry = 0;        num3.ele[i] = temp;    }    while(i >= num1.front)    {        temp = num1.ele[i] - carry;        if(temp < 0)        {            temp += 10;            carry = 1;        }        else            carry = 0;        num3.ele[i] = temp;        --i;    }    num3.front = num1.front;    while(num3.ele[num3.front] == 0)        ++num3.front;    return num3;}//需要再调用前检查num2是否为0bigNum div_bigNum(const bigNum& num1, const bigNum& num2, bigNum& num4){    bigNum num3;    if(comp_bigNum(num1, num2) < 0)    {        num4 = num1;        num3.front = N - 1;        num3.ele[N - 1] = 0;        return num3;    }    int num[N];    int num_end = 0;    int num1_cur = num1.front + N - 1 - num2.front;    int i;    bigNum temp_bigNum;    bigNum cut_bigNum;    bigNum pre_bigNum;    cut_bigNum.front = num2.front + 1;    for(i = num1.front; i < num1_cur; ++i)        cut_bigNum.ele[cut_bigNum.front + i - num1.front] = num1.ele[i];    while(num1_cur < N)    {        if(!comp_bigNum_0(cut_bigNum))        {            for(i = cut_bigNum.front; i < N; ++i)                cut_bigNum.ele[i - 1] = cut_bigNum.ele[i];            --cut_bigNum.front;        }        cut_bigNum.ele[N - 1] = num1.ele[num1_cur++];        temp_bigNum.front = N - 1;        temp_bigNum.ele[N - 1] = 0;        for(i = 1; i <= 10; ++i)        {            pre_bigNum = temp_bigNum;            muti_by_one(num2, i, temp_bigNum);            if(comp_bigNum(temp_bigNum, cut_bigNum) > 0)                break;        }        num[num_end++] = i - 1;        cut_bigNum = minus_bigNum(cut_bigNum, pre_bigNum);    }    num4 = cut_bigNum;    num3.front = N;    for(i = num_end - 1; i >= 0; --i)        num3.ele[--num3.front] = num[i];    while(num3.ele[num3.front] == 0)        ++num3.front;    return num3;}/*void print_bigNum(const bigNum&);void println_bigNum(const bigNum& num);bigNum multi_bigNum(const bigNum& num1, const bigNum& num2);bigNum add_bigNum(const bigNum& num1, const bigNum& num2);void string_to_bigNum(bigNum& num, const char s[]);void muti_by_one(const bigNum& num1, int a, bigNum& num2);int comp_bigNum(const bigNum& num1, const bigNum& num2);bool comp_bigNum_0(const bigNum& num1);bigNum minus_bigNum(const bigNum& num1, const bigNum& num2);bigNum div_bigNum(const bigNum& num1, const bigNum& num2, bigNum& num4);*/int main(){    bigNum num1, num2, num3, num4;    char s[550];    while(cin >> s)    {        string_to_bigNum(num1, s);        cin >> s;        string_to_bigNum(num2, s);        num3 = div_bigNum(num1, num2, num4);        println_bigNum(num3);    }    return 0;}21、背包问题的递归算法/*背包问题的递归算法 */#include//物品总种数不是常量，没法根据它来决定数组的长度，只有先定义个长度了#define N 100 int n ;//物品总种数double limitW ;//限制的总重量double totV ;//全部物品的总价值double maxv ;//解的总价值int option[N];//解的选择int cop[N];//当前解的选择struct {    //物品结构    double weight ;    double value ;}a[N];//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值void find(int i,double tw,double tv){    int k ;    //物品i包含在当前方案的可能性    if(tw+a[i].weight<=limitW)    {        cop[i]=1 ;        if(i

评论