前言

有几天没写博客了,其实我上一篇博客都还没有写完……。这几天忙着应付考试,抽空都补好。
今天,刷了一道蓝桥的题目,虽然现在都还没完成。算法提高里面的Glenbow Museum,花了半小时理解了题目。才知道这道题目是求排列组合的,数字大了之后又涉及到了 大数运算,然后就又去恶补了一顿大数运算。


大数加法

我说说,一开始的疑惑和感受:

  1. 刚开始不懂如何处理最高位,傻乎乎的在想,要不要把数组的所有元素都往后移动?就这样较劲脑汁想了半天,竟然忽略了这个是一个整型数组,可以存放大于9的数。
  2. 然后又觉得用了太多数组感觉好难受,又在考虑怎么能少点。(只要用的数组太多, 我就不想去用这种想法去写了,强迫症)
  3. (;′⌒`) 忧伤,发现整了半天,今天就写了个大数加法。(过两天就要开始寒假了,我要变强!!!)刷题 刷题 刷题 博客!
  4. 2018/1/23今天对这个程序进行了优化,今天在完成大数乘法时,发现了加法里的错误。(1234 123换成 123 1234时会输出不同的结果)。
  5. 2018/1/26今天在做大数减法时,有考虑到了正负号的问题,又对程序进行了优化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void  Num_add(int len_max, char max_num[], int len_min, char min_num[]);
int main(){
char strNum1[100], strNum2[100];
int len1, len2;

scanf("%s", strNum1);
scanf("%s", strNum2);
len1 = strlen(strNum1);
len2 = strlen(strNum2);

if(len1 > len2){
Num_add(len1, strNum1, len2, strNum2);
}else
Num_add(len2, strNum2, len1, strNum1);

return 0;
}
void Num_add(int len_max, char max_num[], int len_min, char min_num[]){
int i, j, num[200], jw = 0;

for(i = 0; i < len_max; i++){
num[i] = max_num[i] - '0';
}

for(i = len_max, j = len_min; j > 0; i--, j--){
num[i - 1] = num[i - 1] + min_num[j - 1] - '0' + jw; //两位相加,并加上要进的位
jw = num[i - 1] / 10;//获取下一位要进的位

if(i - 1 != 0)//因为第0位可能要存放比9大的数,所以通过这个方法筛选
num[i - 1] %= 10;
}

for(i = 0; i < len_max ;i++){
printf("%d ", num[i]);
}
}

2018/1/26
寒假开始了,开始刷题了,今天对大数的加法进行了改进。改进了正负数相加的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <stdio.h>
#include <string.h>

typedef struct{
char sign;
int num[1000]; //定义了一个数字的结构
int len; //将符号和数字分开存放
}Number;

void addition(int len_max, Number Num_max, int len_min, Number Num_min);
void subtraction(int len_max, Number Num_max, int len_min, Number Num_min);
int main(){
int i = 0, j, len1, len2;
char strNum1[1000], strNum2[1000];
Number Num1, Num2;
Num1.len= Num2.len= 0;

scanf("%s", strNum1);
scanf("%s", strNum2);
len1 = strlen(strNum1);
len2 = strlen(strNum2);

Num1.sign = strNum1[0] == '-' ? i++ , Num1.len= -1, '-' : '+';
for(j = 0; i < len1; i++, j++){
Num1.num[j] = strNum1[i] - '0';
}
Num1.len += len1;
i = 0;

Num2.sign = (strNum2[0] == '-' ?i++, Num2.len = -1, '-': '+');
for(j = 0; i < len2; i++, j++){
Num2.num[j] = strNum2[i] - '0';
}
Num2.len += len2; //上面的两块代码存在重复的问题,可以考虑写个函数。

if(Num1.sign == Num2.sign){ //感觉这个程序最精妙的地方就是在这个嵌套判断
if(Num1.len > Num2.len){ //同号时,进行相加运算;异号时,进行相减运算
addition(Num1.len, Num1, Num2.len, Num2);
}else
addition(Num2.len, Num2, Num1.len, Num1);
}else{
if(Num1.len > Num2.len){
subtraction(Num1.len, Num1, Num2.len, Num2);
}else
subtraction(Num2.len, Num2, Num1.len, Num1);
}

return 0;
}
void addition(int len_max, Number Num1, int len_min, Number Num2){
int i;

while(len_max-- && len_min--){
Num1.num[len_max] = Num1.num[len_max] + Num2.num[len_min];
if(Num1.num[len_max] > 9){
if(len_max != 0){
Num1.num[len_max - 1] += 1;
Num1.num[len_max] %= 10;
}
}
}

if(Num1.sign == '-')
printf("%c", Num1.sign);

for(i = 0; i < Num1.len; i++){
printf("%d", Num1.num[i]);
}

}
void subtraction(int len_max, Number Num1, int len_min, Number Num2){
int i = 0;

while(len_max-- && len_min--){
Num1.num[len_max] = Num1.num[len_max] - Num2.num[len_min];
if(Num1.num[len_max] < 0){
Num1.num[len_max - 1] -= 1;
Num1.num[len_max] += 10;
}
}

if(Num1.sign == '-')
printf("%c", Num1.sign);

while(Num1.num[i] == 0) i++;

while(i < Num1.len)
printf("%d", Num1.num[i++]);
}


大数乘法

今天看了半天的大数乘法,都没有头绪。最后在网上看到了这种思路。

  1. 模仿竖式解法,先求出未进位时各位的值,然后在统一对各位进位。
  2. 最后再进行逆序输出。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    int main(){
    char strNum1[100], strNum2[100];
    int Num[200] = {0}, len1, len2;
    int jw = 0, i, j, n;

    scanf("%s", strNum1);
    scanf("%s", strNum2);

    len1 = strlen(strNum1);
    len2 = strlen(strNum2);

    for(i = 0; i < len1; i++){
    strNum1[i] -= '0';//将字符串中的字符-‘0’,变成数字。(一开始看到这种写法的时候是很诧异的,不过挺好用。)
    }
    for(i = 0; i < len2; i++){
    strNum2[i] -= '0';
    }

    for(i = 0; i < len1; i++){
    for(j = 0; j < len2; j++){
    Num[i + j] +=strNum1[len1 - i - 1] * strNum2[len2 - j - 1];//模仿手写的形式,先保存未进位时,数字先不进位
    //这里的i+j想了半天~~~~(>_<)~~~~
    }
    }
    Num[i + j - 1] = -1;//这里设置一个结束标志,就可以解决100*1000这种问题
    i = 0;

    while(Num[i] != -1){
    Num[i] += jw;//将之前未进位的数字,进位!
    jw = Num[i] / 10;
    Num[i] %= 10;
    i++;
    }

    while(i--){
    printf("%d ", Num[i]);
    }

    return 0;
    }

大数阶乘

现在才做到,题目需要的算法,折腾了两个小时,终于搞出了点眉目来。

  1. 因为结果需要的位数过多,所以我把数组定义成了一个全局数组,当然也可以去定义一个局部的动态数组;
  2. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    int Num[10000000] = {1, -1};//把起始位设置为1,还有一个结束标志-1
    int main(){

    int n,jw = 0, i;

    scanf("%d", &n);
    while(n){

    for(i = 0; Num[i] != -1;i++){
    Num[i] *= n;
    Num[i] += jw;
    jw = Num[i] / 10;
    Num[i] %= 10; //获取下次要进的位,以及对当前位进行取余(保留这一位上的个位)

    if(Num[i + 1] == -1 && jw){ //当需要进位并且最后一位为结束标志时将,结束标志向后移动一位
    Num[i + 1] = 0;
    Num[i + 2] = -1;
    }
    }
    n--;
    }

    while(i--){
    printf("%d ", Num[i]);
    }

    return 0;
    }

大数减法

1.我在2018/1/26号修改的加法操作上进行了修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <stdio.h>
#include <string.h>

typedef struct{
char sign;
int num[1000];
int len;
}Number;

void addition(int len_max, Number Num_max, int len_min, Number Num_min);
void subtraction(int len_max, Number Num_max, int len_min, Number Num_min);
int main(){
int i = 0, j, len1, len2;
char strNum1[1000], strNum2[1000];
Number Num1, Num2;
Num1.len= Num2.len= 0;

scanf("%s", strNum1);
scanf("%s", strNum2);
len1 = strlen(strNum1);
len2 = strlen(strNum2);

Num1.sign = strNum1[0] == '-' ? i++ , Num1.len= -1, '-' : '+';
for(j = 0; i < len1; i++, j++){
Num1.num[j] = strNum1[i] - '0';
}
Num1.len += len1;
i = 0;

Num2.sign = (strNum2[0] == '-' ?i++, Num2.len = -1, '-': '+');
for(j = 0; i < len2; i++, j++){
Num2.num[j] = strNum2[i] - '0';
}
Num2.len += len2;

if(Num1.sign == Num2.sign){//主要是修改了这里的操作
if(Num1.len > Num2.len){//同号时进行相加操作,异号时进行相减操作。
subtraction(Num1.len, Num1, Num2.len, Num2);
}else
subtraction(Num2.len, Num2, Num1.len, Num1);
}else{
if(Num1.len > Num2.len){
addition(Num1.len, Num1, Num2.len, Num2);
}else
addition(Num2.len, Num2, Num1.len, Num1);
}

return 0;
}
void addition(int len_max, Number Num1, int len_min, Number Num2){
int i;

while(len_max-- && len_min--){
Num1.num[len_max] = Num1.num[len_max] + Num2.num[len_min];
if(Num1.num[len_max] > 9){
if(len_max != 0){
Num1.num[len_max - 1] += 1;
Num1.num[len_max] %= 10;
}
}
}

if(Num1.sign == '-')
printf("%c", Num1.sign);

for(i = 0; i < Num1.len; i++){
printf("%d", Num1.num[i]);
}

}
void subtraction(int len_max, Number Num1, int len_min, Number Num2){
int i = 0;

while(len_max-- && len_min--){
Num1.num[len_max] = Num1.num[len_max] - Num2.num[len_min];
if(Num1.num[len_max] < 0){
Num1.num[len_max - 1] -= 1;
Num1.num[len_max] += 10;
}
}

if(Num1.sign == '-')
printf("%c", Num1.sign);

while(Num1.num[i] == 0) i++;

while(i < Num1.len)
printf("%d", Num1.num[i++]);

}


大数除法

  1. 花了半个下午在调试这个除法,心里有点崩溃但终于调试出来了。
  2. 然后我就美滋滋的去看那道题目,我曹,发现用大数解还真是复杂,然后就去度娘了一波,发现根本不用大数。
  3. 今天过得还挺充实,解决了减法除法,还刷了七八道水题。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    #include <stdio.h>
    #include <string.h>
    typedef struct{
    int num[1000];
    int len;
    }Number;
    //这个除法只考虑全部是正数且不是小数的情况。
    //1.通过减法来运算,每次减去 被除数 * 10^n
    int devision(Number *Num1, Number Num2);
    void subtraction(Number *Num1, Number num2);
    int mypow(int ds, int zs);
    int main(){
    int i, result = 0, temp = 0;
    char str1[1000], str2[1000];
    Number Num1, Num2;

    scanf("%s %s", str1, str2);
    Num1.len = strlen(str1);
    Num2.len = strlen(str2);

    for(i = 0; i < Num1.len; i++){
    Num1.num[i] = str1[i] - '0';
    }
    Num1.num[i] = -1;
    for(i = 0; i < Num2.len; i++){
    Num2.num[i] = str2[i] - '0';
    }
    Num2.num[i] = -1;

    result = devision(&Num1, Num2);

    printf("%d", result);
    return 0;
    }
    int devision(Number *Num_max, Number Num_min){
    int dlen, i, result = 0, n = 0;
    Number temp;
    dlen = Num_max -> len - Num_min.len;
    result += mypow(10, dlen - 1);//当两数相差过大时,会导致变量溢出
    temp = Num_min;

    for(i = 0; i < dlen - 1; i++){
    Num_min.num[Num_min.len + i] = 0;//为被除数补零
    }
    Num_min.num[Num_min.len + i] = -1; //添加结束标志
    Num_min.len += i;

    while(Num_max -> len >= Num_min.len){
    if(Num_max -> num[0] < Num_min.num[0] && Num_max -> len == Num_min.len)
    break;//避免在长度相同,但是首位没有被除数大的情况

    subtraction(Num_max, Num_min);//减法函数

    n++;
    }
    result *= n;

    if(Num_max->len)
    return result + devision(Num_max, temp);//递归调用
    else
    return result;
    }
    void subtraction(Number *Num1, Number Num2){
    int len1, len2, i = 0, len = 0, wz;
    len1 = Num1 -> len;
    len2 = Num2.len;
    while(len1-- && len2--){
    Num1 -> num[len1] -= Num2.num[len2];
    if(Num1 -> num[len1] < 0){
    Num1 -> num[len1 - 1 ] -= 1; //进行了相减运算
    Num1 -> num[len1] += 10;
    }
    }
    while(Num1->num[i] == 0) i++; //得到的可能前几位为0,且都为数字不是字符
    wz = i;
    while(i < Num1 -> len){
    i++;
    len++;
    }
    //Num1.len = len; //是否要进行移位工作,并将数字变成字符
    if(i != len){
    i= 0;
    while(i < len){
    Num1 -> num[i] = Num1 -> num[wz + i];
    i++;
    }
    Num1 -> num[i] = -1;
    }

    Num1 -> len = len;
    }
    int mypow(int ds, int zs){
    int i, result = 1;
    for(i = 0; i < zs; i++) //math库中的pow函数参数是小数,存在一定的误差
    result *= ds;

    return result;
    }

留言

⬆︎TOP